数据结构上机实验报告

数据结构实验报告一顺序表要求：实现顺序表的初始化、在指定位置插入和删除元素。算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元 素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设 为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元 素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表, 而且删除点后面的元素要往前移动一个位。程序代码：#include #include #define MAXSIZE 50typedef char elemtype;typedef struct/类型定义 elemtype vMAXSIZE;int last;SeqList;SeqList *Init_SeqList()/初始化操作SeqList *L; L=(SeqList*)malloc(sizeof(SeqList);L-last=-1; return L;void Create(SeqList *L)/建立顺序表int i=0; elemtype ch;scanf(%c,&ch); while(ch!=n) L-vi+=ch;scanf(%c,&ch); L-last=i-1;void PrintL(SeqList *L)/输出顺序表int i;printf(” 此表为:n);for(i=0;ilast;i+)printf(%c,L-vi);printf(%cn,L-vi);/顺序表长度函数/插入函数void Length(SeqList *L)printf(此表长度:n%d,L-last+l); printf(n);void insert(SeqList *L,int i,elemtype x)int j;if(L-last=0)printf(Error!n);if(iL-last)printf(Error!);for(j=L-last;j=i-l;j-)L-vj+l=L-vj;L-vi-l=x;L-last+;PrintL(L);Length(L);void Delete(SeqList *L,int i)/删除函数int j;if(L-last=-l)printf(Error!);if(iL-last+l)printf(Error!);for(j=i;jlast;j+)L-vj-l=L-vj;L-last-;PrintL(L);Length(L);void main()/程序主函数int i,j,k; elemtype a,b;SeqList *L;L=Init_SeqList(); printf(”建立顺序表：n);Create(L);PrintL(L);Length(L);printf(n);printf(请输入你想插入的元素及其位置：n); scanf(%s %d,&b,&j);insert(L,j,b);printf(请输入你想删除的位置：n); scanf(%d,&k);Delete(L,k);程序运行： C:UsensE e I iDes kt p 隕亭表.王虚 ex e建立顺序表J 23455&此表为:123455&此表长度：7击输入你想插入的元素及其位置:7.234575&此表长度：8宇输入你想删除的位査：匕表为:234576严匕表长度：鲁按任意键继续-二单链表要求：实现单链表的初始化、在指定位置插入和删除元素。算法思路：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。 因此，为了表现每个元素与后继元素的逻辑关系需要用到指针。单链表的插入就是先生成一个数据域为插入元素的界点然后插入单链表中，并且修改前后节点的指针域，完成插入操作。反之删除链表元素时仅需修改前后两个元素的节点使之相连便可。程序代码：#define NULL 0#include stdlib.h#includestdio.htypedef struct LNodeint data;struct LNode *next; LNode, *LinkList;void CreateList_L( LinkList *L);void ShowList(LinkList *L);LNode *GetElem(LinkList head);void InsertList(LinkList *head);void DeleteList(LinkList head);void main() LNode *L;int j,loop=1;printf(n);while(loop)printf(l.建立单链表n); printf(2.在单链表插入元素n); printf(3删除单链表元素n); printf(请选择序号(1-3):);scanf(%d,&j);switch(j)case 1: CreateList_L(&L);break;case 2:InsertList(&L);break;case 3:DeleteList(L);break;printf(结束此程序吗？ (0结束1继续)：n); scanf(%d,&loop);printf(n);void CreateList_L( LinkList *L) LNode *p;int flag=1;(*L)=(LinkList)malloc(sizeof(LNode); (*L)-next=NULL;printf(”请输入链表元素(输0结束):n”);while(flag) p=(LinkList)malloc(sizeof(LNode); p-next=NULL;scanf(%d,&p-data);if (p-data=0)break;p-next=(*L)-next;(*L)-next=p;ShowList(L);void ShowList(LinkList *L)LinkList p;printf(头节点- );for(p=(*L)-next;p!=NULL;p=p-next)printf(%d - ,p-data);printf(NULL !n);void InsertList(LinkList *head)LNode *pre,*s;int i,j,x;printf(请输入插入位置:”)； scanf(%d,&i);printf(”请输入插入元素:)；scanf(%d,&x);pre=*head;j=0;while (pre!=NULL & jnext; j+;s=(LNode *)malloc(sizeof(LNode); s-data=x;s-next=pre-next;pre-next=s;ShowList(head);printf(n);void DeleteList(LinkList head)LNode *pre,*r;int i,j;pre=head;printf(请输入删除位置:”)；scanf(%d,&i);j=0;/*查找第i-1个结点*/while(pre-next!=NULL & jnext; j+; r=pre-next;pre-next=r-next ;free(r);ShowList(&head);程序运行：NULL ?1 继续）：|fl-青青土在单链表插入元素 刪歌单链表元素拖入樹入位置迈 捡入播A元素:昭T点-44 - 22II-建立卑链表,=在聲-链表:拯入兀素链表元素訝选毎汙号1 请输汎链羔元素输结束蛀3点一44 - 33 - 22 - 此程序吗？ 5结束结环此:呈J予出？ （3結更1继续）:|建立单犍表.链曩兀素 选径序号1-3鎂|认郦位*MULL i 継续）:亍点一44 - 33 - 22 - 此程序吗？（3结束三链表的合并要求：给定的2个有序线性链表的合并（合并到1个新的链表中以及合并到其中的1个链表 中两种方式）。算法思路：先创建两个有序线性链表a，b。然后将两个有序线性链表a，b合并到a或者h 中，得运用指针分别指向a，b当前待比较插入的节点，最后将两个链表的元素有序归并到 表a或者h中。程序代码：#includevstdlib.h#includevstdio.h#includevconio.h#includevmalloc.h#define L sizeof（struct Node）struct Nodelong int number;struct Node *next;struct Node *create(int a)int n;struct Node *p1, *p2, *head;head = NULL;n = 0;p2 = p1 = (struct Node *) malloc(L); scanf(%ld, &p1-number);while (a)n = n + 1;if (n = 1) head = p1;elsep2-next = p1;p2 = p1;p1 = (struct Node *) malloc(L);if (a != 1)scanf(%ld, &p1-number); a-;p2-next = NULL;return (head);void print(struct Node *head)struct Node *p;p = head;printf( ”数字:n);if (head != NULL)doprintf(%ld, p-number); printf( ); p = p-next; while (p != NULL);printf(n);struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) int temp;struct Node *head, *p1, *p2, *pos;if (a = b) head = p1 = chain1; p2 = chain2; else/*ba*/ head = p1 = chain2; p2 = chain1;temp = a, a = b, b = temp;pos = head;while (p2 != NULL) p1 = p1-next; pos-next = p2; pos = p2; p2 = p2-next; pos-next = p1; pos = p1;return head;void InsertSort(struct Node *p, int m)int i, j, t;struct Node *k;k = p;for (i = 0; i m - 1; i+) for (j = 0; j number (p-next)-number) t = p-number;p-number = (p-next)-number; (p-next)-number = t;p = p-next;p = k;int main()struct Node *p1, *p2;int a;int b;int h;printf(请输入第一个链表:n);printf(n 输入链表的长度 a:n);scanf(%d, &a);printf(请输入链表数据：”)；p1 = create(a);printf(n你刚才输入的第一个链表信息:n );print(p1)；printf(n请输入第二个链表:n);printf(n 输入链表的长度 b:n);scanf(%d, &b);printf(请输入链表数据：)；p2 = create(b);printf(n你刚才输入的第二个链表的信息:n);print(p2);p1 = inter_link(p1, a, p2, b);h = a + b;a = h;print(p1);InsertSort(p1, h);InsertSort(p1, a);printf(n 排序后的链表 a:n);print(p1);printf(n 排序后的链表 h:n);print(p1);return 0;程序运行：请输入第一个链急 卜入链表的长度牡 请输凡链表数据；123134145摯蓼输入的第一个链表信息：123134145请输入第二个链表：卜入链表的长度M请输入链表数据！ iii143245惨圈才愉入的第二个链表的信息:ill143数字：123ill245134143145245ill123134143145245鮭后的链表h：ill.123134143145245请?安任意键继续- 四双向链表要求：实现双向链表的初始化、在指定位置插入和删除元素。算法思路：因为单链表的节点中只有一个指示直接后继的指针域，因此只能从某节点出发顺 指针往后寻查其它节点，若需寻查节点的直接前趋，则需从表头指针出发。所以在双向链表 节点中有两个指针域，一个指向后继，一个指向前趋。程序代码：#includevstdio.h#includevmalloc.h#define ERROR 0#define OK 1typedef int Elemtype;typedef struct myNodeElemtype data;struct myNode *prior,*next;Node;Node * InitList()Node *H;H=(Node *)malloc(sizeof(Node);if(!H)return ERROR;H-next =H-prior=H;return H;int AddFromEnd(Node *L,Elemtype e)Node *s,*r;int flag=1;Elemtype data;r=L;while(flag)printf(请输入数据:”)；scanf(%d,&data);if(data=e)flag=0；elses=(Node *)malloc(sizeof(Node)；if(!s)return ERROR；s-data=data； s-next=r-next； s-next-prior=s； s-prior=r； r-next=s； r=s；return OK；int del(Node *L,int n,Elemtype *rec)Node *r;int c=0;if(n1)return ERROR;r=L;for(c=0;cnext != L;c+) r=r-next; if(r-next = L)return ERROR; r-next-prior=r-prior; r-prior-next=r-next; *rec=r-data; free(r); return OK;int insert(Node *L,int n,Elemtype num) Node *p,*s;int c;p=L-next; if(n1)return ERROR;for(c=1;cnext; if(p=L)return ERROR;s=(Node *)malloc(sizeof(Node); if(!s)return ERROR; s-data=num; p-prior-next=s; s-prior=p-prior; s-next=p; p-prior=s; return OK;int ListLength(Node *L)Node *p;int c=0;p=L-next;while(p!=L)c+;p=p-next;return c;void Show(Node *L)Node *p; for(p=L-next;p!=L;p=p-next) printf(%dn,p-data);int main()Node *La;Node *s;Elemtype rec;Elemtype num;Elemtype e=0;int n;La=InitList();printf(创建双向链表:n);AddFromEnd(La,e);Show(La);printf(长度=%dn,ListLength(La); scanf(%d,&n);printf(请输入插入元素序号及数值:n); scanf(%d%d,&n,&num); insert(La,n,num);Show(La);printf(长度=%dn,ListLength(La); printf(”删除什么元素?n); scanf(%d,&n);del(La,n,&rec);Show(La);printf(长度=%dn,ListLength(La); printf(”d 已删除！ n,rec);return 0;程序运行:五栈要求：实现顺序栈的初始化、PUSH、POP等操作。算法思路:栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据 元素，同时附设指针top指示栈顶元素在顺序栈中的位置。所以先为栈分配一个基本存储容 量，当栈空间不足时在扩大。栈的初始化操作是按设定的初始分配量进行第一次存储分配, base为栈顶指针始终指向栈底位置，若base为空表明栈结构不存在。Top为栈顶指针，每 次插入新的栈顶元素top增1,删除栈顶元素，top减1.因此非空栈中栈顶指针始终在栈顶 元素的下一位置上。程序代码:#includevstdio.h#include #include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0#define FALSE 0#define OVERFLOW 0#define TRUE 1typedef int Status;typedef int SElemType;typedef struct SElemType *base; SElemType *top;int stacksize; SqStack;Status InitStack(SqStack &S)S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base)exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE; return OK;Status Push(SqStack&S,SElemType e)、 if(S.top-S.base=S.stacksize)S.base = (SElemType *)realloc(S.base,(S.stacksize STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit (OVERFLOW);S.top =S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK;Status Pop(SqStack&S, SElemType&e)、 if(S.top=S.base)return ERROR; e = *-S.top;return OK;Status StackEmpty(SqStack&S) if(S.top=S.base)return TRUE;else return FALSE;main() SElemType e;SqStack S;printf(初始化栈 n);InitStack(S);printf(栈为 sn,(StackEmpty(S)?空:非空);printf(请输入栈元素 l,2,3,4,5n);Push(S,T);Push(S,2);Push(S,3);Push(S,4);Push(S,5);printf(栈为 sn,(StackEmpty(S)?空:非空);printf(出栈序列”)；while(!StackEmpty(S) Pop(S,e);printf(”c,e);printf(n);程序运行：C:User55 e liDes Icto p 栈.王1绽 t32继 一兀 復籐一 楞ra 化空入非序tf 转尊出请六队列要求：实现队列的插入和删除操作，以及循环队列的插入和删除操作。算法思路：队列是先进先出的线性表，只允许一端进行插入在另一端删除元素。所以链队列需 要2个分别指向队头和队尾的指针。而空链队列判决条件是头指针和尾指针均指向头结点。链 队列的插入和删除只需修改尾指针或者头指针就可以。程序代码：#includevstdio.h#include#define NULL 0 #define OK 1#define OVERFLOW 0#define ERROR 0typedef int Status; typedef int QElemType;typedef struct QNodeQElemType data; struct QNode *next; QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue&Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if(!Q.front)exit(OVERFLOW); Q.front-next=NULL;return OK;Status EnQueue(LinkQueue&Q,QElemType e) QNode*p;p = (QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW);p-data = e; p-next = NULL;Q.rear-next = p;Q.rear = p;return OK;、Status DeQueue(LinkQueue&Q,QElemType&e) QNode*p;if(Q.front=Q.rear) return ERROR; p = Q.front-next;e = p-data;Q.front-next = p-next; if(Q.rear=p) Q.rear = Q.front; free(p);return OK;、Status QueueEmpty(LinkQueue&Q) if(Q.rear=Q.front)return 1; else return 0;void main() LinkQueue Q;QElemType e; printf(初 _始_化_队_列 n); InitQueue(Q);printf(输_入_队_列_元素 l,3,5,7n”);EnQueue(Q, 1);EnQueue(Q, 3);EnQueue(Q, 5);EnQueue(Q, 7); if(DeQueue(Q,e)=O) printf(队空，不能出列5);elseprintf(出队一个元素 %dn,e); printf(出_队_列 _序_列 n); while(!QueueEmpty(Q) DeQueue(Q,e);printf(%d ,e); printf(n);程序运行：C;User55 e I kto L|a扶一始一化-臥列_队_列併一列七串要求：实现常规的串的匹配，求解next函数和nextval函数，然后实现KMP算法。算法思路：子串的定位操作通常称做串的模式匹配，采用定长顺序存储结构，可以写出不依 赖于其它串操作额匹配算法。KMP算法是在已知的next函数值的基础上执行的，我们可以 从分析其定义出发用递推的方法求得next函数值，求得next函数值后便可执行KMP算法。程序代码：#include#include #define maxsize 100 typedef struct char chmaxsize;int len; sqstring;void strassign(sqstring &str,char cstr) int i;for (i=0;cstri!=0;i+) str.chi=cstri;str.len=i;void dispstr(sqstring s) int i;if (s.len0) for (i=0;is.len;i+) printf (%c,s.chi); printf (n); int simple (sqstring s,sqstring t) int i=0,j=0,k;while (is.len&j=t.len) k=i-t.len; else k=-1; return k; void getnext(sqstring t,int next ) int j ,k;j=0;k=-1;next0=-1;while (jt.len-1) if (k=-1|t.chj=t.chk) j+;k+;nextj=k; else k=nextk;int kmpindex(sqstring s,sqstring t) int next maxsize,i=0,j=0,v; getnext(t,next);while (is.len&j=t.len) v=i-t.len;elsev=-1;return v;void getnextval(sqstring t,int nextval) int j=0,k=-1; nextval0=-1; while (jt.len) if (k=-1|t.chj=t.chk) j+;k+;if (t.chj!=t.chk) nextvalj=k;else nextvalj=nextvalk; else k=nextvalk;int main ()int i,j;int next maxsize,nextval maxsize; sqstring s,t;strassign (s,abcdeabcdefa);strassign (t,bcdef);printf (串 S:);dispstr(s);printf (串 t:);dispstr(t); getnext (t,next);getnextval(t,nextval);printf ( i );for (i=O;ivt.len;i+)printf (”4d,i);printf(n);printf(ti );for (i=O;ivt.len;i+)printf (”4c,t.chi);printf(n);printf(next );for (i=O;ivt.len;i+)printf (”4d,nexti);printf(n);printf(nextval);for (i=O;ivt.len;i+)printf (”4d,nextvali); printf(n);printf (kmp 算法：”)； j=kmpindex(s,t);if (j=-1) printf (串匹配失败5); else printf (t 在 s 中的位置dn,j); system(pause);f&0d0e0e程序运行：Ei extc30R中的位置右