数据结构上机实验报告

《数据结构上机实验报告》由会员分享，可在线阅读，更多相关《数据结构上机实验报告（22页珍藏版）》请在装配图网上搜索。

1、数据结构实验报告 一．顺序表 要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元 素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设 为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元 素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表, 而且删除点后面的元素要往前移动一个位。 程序代码： #include #include #define MAXSIZE

2、 50 typedef char elemtype; typedef struct //类型定义 { elemtype v[MAXSIZE]; 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'

3、) { L->v[i++]=ch; scanf("%c",&ch); L->last=i-1; } } void PrintL(SeqList *L) //输出顺序表 { int i; printf(” 此表为:\n"); for(i=0;ilast;i++) { printf("%c",L->v[i]); } printf("%c\n",L->v[i]); //顺序表长度函数 //插入函数 } void Length(SeqList *L) { printf("此表长度:\n%d",L->last+l); printf("\n"); } vo

4、id 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->v[j+l]=L->v[j]; L->v[i-l]=x; L->last++; PrintL(L); Length(L); } void Delete(SeqList *L,int i) //删除函数 { int j; if(L->last==-l) printf(

5、"Error!"); if(iL->last+l) printf("Error!"); for(j=i;j<=L->last;j++) L->v[j-l]=L->v[j]; 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("请输

6、入你想插入的元素及其位置：\n"); scanf("%s %d",&b,&j); insert(L,j,b); printf("请输入你想删除的位置：\n"); scanf("%d",&k); Delete(L,k); } 程序运行： ' C:\Usens\E e I i\Des kt □ p\ 隕亭表.王虚 ex e 建立顺序表 J 23455& 此表为: 123455& 此表长度： 7 击输入你想插入的元素及其位置: 7 ^..234575& 此表长度： 8 宇输入你想■删除的位査： ［匕表为: ^234576 严匕表长度： 鲁按任意键继续---

7、 二•单链表 要求：实现单链表的初始化、在指定位置插入和删除元素。 算法思路：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。 因此，为了表现每个元素与后继元素的逻辑关系需要用到指针。单链表的插入就是先生成一 个数据域为插入元素的界点然后插入单链表中，并且修改前后节点的指针域，完成插入操作。 反之删除链表元素时仅需修改前后两个元素的节点使之相连便可。 程序代码： #define NULL 0 #include "stdlib.h" #include"stdio.h" typedef struct LNode { int data; struct

8、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.

9、在单链表插入元素\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)

10、 { 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(LinkL

11、ist *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 (pr

12、e!=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!

13、=NULL && jnext; j++; } r=pre->next; pre->next=r->next ; free(r); ShowList(&head); } 程序运行： NULL ? 1 ——继续）： || fl -青青土 在单链表插入元素 刪歌单链表元素 拖入樹入位置迈 捡入播A■元素:昭 T点-》44 -> 22 II -建立卑链表 ,=在「聲-链表:拯入兀素 ■ 链表元素 訝选毎汙号1 请输汎链羔元素〔输结束蛀 3 点一》44 -> 33 -> 22 -> 此程序吗？ 5——结束 结环［此:

14、］■■呈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> #includ

15、evstdio.h> #includevconio.h> #includevmalloc.h> #define L sizeof（struct Node） struct Node { long 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); whil

16、e (a) { n = n + 1; if (n == 1) head = p1; else p2->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) do

17、 { printf("%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/*b>a*/ { head =

18、 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;

19、 i++) { for (j = 0; j < m - i - 1; j++) { if (p->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");

20、 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

21、 = h; print(p1); InsertSort(p1, h); InsertSort(p1, a); printf("\n 排序后的链表 a:\n"); print(p1); printf("\n 排序后的链表 h:\n"); print(p1); return 0; } 程序运行： 请输入第一个链急 卜入链表的长度牡 请输凡链表数据；123 134 145 摯蓼输入的第一个链表信息： 123 134 145 请输入第二个链表： 卜入链表的长度M 请输入链表数据！ iii 143 245 惨圈才愉入的第二个链表的信息: ill 143 数字

22、： 123 ill 245 134 143 145 245 ill 123 134 143 145 245 鮭后的链表h： ill . 123 134 143 145 245 请? 安任意键继续- ■ ■ 四•双向链表 要求：实现双向链表的初始化、在指定位置插入和删除元素。 算法思路：因为单链表的节点中只有一个指示直接后继的指针域，因此只能从某节点出发顺 指针往后寻查其它节点，若需寻查节点的直接前趋，则需从表头指针出发。所以在双向链表 节点中有两个指针域，一个指向后继，一个指向前趋。 程序代码

23、： #includevstdio.h> #includevmalloc.h> #define ERROR 0 #define OK 1 typedef int Elemtype; typedef struct myNode { Elemtype 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; } i

24、nt 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； } else { s=(Node *)malloc(sizeof(Node))； if(!s) return ERROR； s->data=data； s->next=r->next； s->next->prior=s； s->prior=r； r->ne

25、xt=s； r=s； } } return OK； int del(Node *L,int n,Elemtype *rec) { Node *r; int c=0; if(n<1) 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

26、(Node *L,int n,Elemtype num) { Node *p,*s; int c; p=L->next; if(n<1) 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; } in

27、t 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("%d\n",p->data); } } int main() { Node *La; Node *s; Elemtype rec; Elemtype num; Elemtype e=0; int n; La=Ini

28、tList(); printf("创建双向链表:\n"); AddFromEnd(La,e); Show(La); printf("长度=%d\n",ListLength(La)); scanf("%d",&n); printf("请输入插入元素序号及数值:\n"); scanf("%d%d",&n,&num); insert(La,n,num); Show(La); printf("长度=%d\n",ListLength(La)); printf(”删除什么元素?\n"); scanf("%d",&n); del(La,n,&rec); Show(La); printf(

29、"长度=%d\n",ListLength(La)); printf(”％d 已删除！ \n",rec); return 0; } 程序运行: 五•栈 要求：实现顺序栈的初始化、PUSH、POP等操作。 算法思路:栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据 元素，同时附设指针top指示栈顶元素在顺序栈中的位置。所以先为栈分配一个基本存储容 量，当栈空间不足时在扩大。栈的初始化操作是按设定的初始分配量进行第一次存储分配, base为栈顶指针始终指向栈底位置，若base为空表明栈结构不存在。Top为栈顶指针，每 次插入新的栈顶元素top增1,删除栈顶元

30、素，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 1 typedef int Status; typedef int SElemType; typedef struc

31、t { 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.t

32、op-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) re

33、turn 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("栈为 ％s\n",(StackEmpty(S)?"空":"非空")); printf("请输入栈元素 l,2,3,4,5\n"); Push(S,T); Push(S,2);

34、 Push(S,'3'); Push(S,'4'); Push(S,'5'); printf("栈为 ％s\n",(StackEmpty(S)?"空":"非空")); printf("出栈序列”)； while(!StackEmpty(S)) { Pop(S,e); printf(”％c",e); } printf("\n"); } 程序运行： "C:\User5\5 e li\Des Icto p\ 栈.王 」1绽 t32继 一兀 復籐一 楞ra 化空入非序tf 转尊出请 六•队列 要求：实现队列的插入和删除操作，以及循环队列的插入和删除操作。 算法思路：

35、队列是先进先出的线性表，只允许一端进行插入在另一端删除元素。所以链队列需 要2个分别指向队头和队尾的指针。而空链队列判决条件是头指针和尾指针均指向头结点。链 队列的插入和删除只需修改尾指针或者头指针就可以。 程序代码： #includevstdio.h> #include #define NULL 0 #define OK 1 #define OVERFLOW 0 #define ERROR 0 typedef int Status; typedef int QElemType; typedef struct QNode{ QElemType data;

36、struct QNode *next; } QNode, *QueuePtr; typedef struct{ QueuePtr 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*

37、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)

38、 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,7\n”); EnQueue(Q, 1); EnQueue(Q, 3); EnQueue(Q, 5); EnQueue

39、(Q, 7); if(DeQueue(Q,e)==O) printf("队空，不能出列5"); else printf("出队一个元素 %d\n",e); printf("出_队_列 _序_列 \n"); while(!QueueEmpty(Q)) { DeQueue(Q,e); printf("%d ",e); } printf("\n"); } 程序运行： C;\User5\5 e I kto L|a± 扶一始一化--臥 列 _队_列併一列 七•串 要求：实现常规的串的匹配，求解next函数和nextval函数，然后实现KMP算法。 算法思路：子串的定位操作通常称

40、做串的模式匹配，采用定长顺序存储结构，可以写出不依 赖于其它串操作额匹配算法。KMP算法是在已知的next函数值的基础上执行的，我们可以 从分析其定义出发用递推的方法求得next函数值，求得next函数值后便可执行KMP算法。 程序代码： #include #include #define maxsize 100 typedef struct { char ch[maxsize]; int len; } sqstring; void strassign(sqstring &str,char cstr[]) { int i; for (i=0

41、;cstr[i]!='\0';i++) str.ch[i]=cstr[i]; str.len=i; } void dispstr(sqstring s) { int i;if (s.len>0) { for (i=0;i

42、; j=0; } } if (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;next[0]=-1; while (j

43、v; getnext(t,next); while (i=t.len) v=i-t.len; else v=-1; return v; } void getnextval(sqstring t,int nextval[]) { int j=0,k=-1; nextval[0]=-1; while (j

44、f (t.ch[j]!=t.ch[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[k]; } } 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)

45、; getnextval(t,nextval); printf (" i "); for (i=O;ivt.len;i++) printf (”％4d",i); printf("\n"); printf("t[i] "); for (i=O;ivt.len;i++) printf (”％4c",t.ch[i]); printf("\n"); printf("next "); for (i=O;ivt.len;i++) printf (”％4d",next[i]); printf("\n"); printf("nextval"); for (i=O;ivt.len;i++) printf (”％4d",nextval[i]); printf("\n"); printf ("kmp 算法：”)； j=kmpindex(s,t); if (j==-1) printf ("串匹配失败5"); else printf ("t 在 s 中的位置％d\n",j); system("pause"); } f & 0 d 0 e 0 e 程序运行： Ei] ext c 3 0 R中的位置右