数据结构 顺序表,链表源代码.docx

《数据结构 顺序表,链表源代码.docx》由会员分享，可在线阅读，更多相关《数据结构 顺序表,链表源代码.docx（22页珍藏版）》请在三一办公上搜索。

1、数据结构 顺序表,链表源代码淮海工学院计算机科学系 实验报告书 课程名： 数据结构 题 目： 线性表数据结构试验 班 级： 软件 081 学 号： 110831104 姓 名： 强余彬 评语： 成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 1 - 线性表实验报告要求 1目的与要求: 1）掌握线性表数据结构的基本概念和抽象数据类型描述； 2）熟练掌握线性表数据结构的顺序和链式存储存表示； 3）熟练掌握线性表顺序存储结构的基本操作算法实现； 4）熟练掌握线性表的链式存储结构的基本操作算法实现; 5）掌握线性表在实际问题中的应用和基本编程技巧; 6）按照实验题目要求独立正确地完

2、成实验内容； 7）认真书写实验报告,并在试验后的第三天提交电子和纸质。 2实验内容或题目 一、顺序表的基本操作实现实验 要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法： 1）创建任意整数线性表，长度限定在25之内； 2）打印/显示该线性表； 3）在线性表中查找第i个元素，并返回其值； 4）在线性表中第i个元素之前插入一已知元素； 5）在线性表中删除第i个元素； 6）求线性表中所有元素值之和； 二、链表基本操作实验 要求：数据元素类型ElemType取字符型char。按照动态单链表结构实现如下算法： 1）按照头插法创建一个带头结点的字符型单链表，长度限定在10之内；

3、 2）打印该链表； 数据结构 实验报告 - 2 - 3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE； 4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 5）在链表中按照有序方式插入一已知字符元素； 6）在线性表中删除第i个结点； 7）计算链表的长度。 3实验步骤与源程序 (1)顺序表 #include #include #include #define maxsize 25 int length; /表长 / 顺序表结构定义 struct seqlist int elemmaxsize; /线性表占用的数组空间 int last; /下

4、标，等于位序减1 seqList; / 遍历函数 void show (seqlist *p) int i=0; for(;ilast+1;i+) couti+1 elemiendl; ; / 插入函数 int insert(seqlist *p) / i位置 j插入的数 int i; int j; 数据结构 实验报告 - 3 - int flag=1; coutInput the position and the value: ij; if(ilength) coutThe wrong position! Input again: last; for(;pos=i;pos-) p-elemp

5、os+1=p-elempos; p-elemi-1=j; p-last+; return 0; ; / 查找函数 int find(seqlist *p) int i; int flag=1; coutInput the position you want to search: i; if(ilength) coutThe wrong position! Input again: endl; else flag=0; couti elemi-1endl; 数据结构 实验报告 - 4 - ; return 0; / 删除函数 int del(seqlist *p) int i; int flag

6、=1; coutInput the position you want to delete: i; if(ilength) coutThe wrong position! Input again: endl; else flag=0; for(;ielemi=p-elemi; p-last-; return 0; ; / 求和函数 int sum(seqlist *p) int i=0; int s=0; for(;ilast;i+) s+=p-elemi; coutsendl; return 0; 数据结构 实验报告 - 5 - ; / 主函数 void main seqlist *p; p

7、=(seqlist*)malloc(sizeof(seqlist); coutInput the length of the data: length; p-last=length-1; int i=0; for(;ip-elemi; int flag=1; int choose; while(flag) coutDisplay:1 ; coutInsert:2 ; coutSearch:3 ; coutDelete:4 ; coutSummary:5 ; coutClear screen:6 ; coutEXIT: 0choose; switch(choose) case 0:flag=0;

8、break; case 1:show (p);break; case 2:insert (p);break; case 3:find (p);break; 数据结构 实验报告 - 6 - case 4:del (p);break; case 5:sum (p);break; case 6:system(cls);break; (2)链表 #include #include #include #include #define TRUE 1 #define FALSE 0 int length=0; typedef struct node char data; struct node *next;

9、 nodetype,*Listlink; /进行头插法创建链表 void create(Listlink *head,int n) cout用头插法建立单链表,请输入链表数据,以$结束!n; int i; Listlink p; char c; cout(按照头插法插入)next=NULL; int flag=1; while(flag) /* flag初值为1，当输入$时，置flag为0，建表结束*/ 数据结构 实验报告 - 7 - ; cinc; if(c!=$) else i+; flag=0; p=(Listlink)malloc(sizeof(struct node);/*建立新结点

10、s*/ p-data=c; p-next=(*head)-next;/*将s结点插入表头*/ (*head)-next=p; /按位置查找 int Get1(nodetype *h,int i) int j; nodetype *p=h; j=0; while(p-next!=NULL)&(jnext; j+; if(i=j) ; /查找与已知字符e相同的结点 coutdata; else return FALSE; 数据结构 实验报告 - 8 - int Get2(nodetype *h,char e) nodetype *p=h; while(p-data!=e) ; /对各字符元素进行排

11、序 void paixu(nodetype *h) node *r,*q,*small; char temp; return TRUE; p=p-next-next; if(p-next=NULL) return FALSE; for(r=h-next;r-next!=NULL;r=r-next) small=r; for(q=r-next;q;q=q-next) /*找到链表中最小字符*/ if(q-datadata) small=q; if(small!=r) temp=r-data; r-data=small-data; /*把最小的数值换到P指针所指的位置数值上*/ 小字符位置*/ ;

12、 small-data=temp; /*把原先p指针所指位置的数值填入被置换出的最 数据结构 实验报告 - 9 - /对表进行插入操作 void show(nodetype *head) ; nodetype *search(nodetype *h,int i,int m) ; nodetype *cins(nodetype *h,int i,char x,int m) node *p; p=head-next; while(p!=NULL) coutendl; coutdatanext; nodetype *p=h; int j=1; if(im|i0) return NULL; else

13、while (p!=NULL&jnext; nodetype *p,*s; s=(nodetype *)malloc(sizeof(nodetype); s-data=x;s-next=NULL; 数据结构 实验报告 - 10 - ; if(i=0) else return h; p=search(h,i,m); if(p!=NULL) else cout输入的i值不正确next=p-next; p-next=s; s-next=h;h=s; /对链表进行删除操作 nodetype *del(nodetype *h,int i,int m) nodetype *p=h,*s; int j=1;

14、 if(i=1) else p=search(h,i,m); if(p!=NULL&p-next!=NULL) h=h-next;free(p); 数据结构 实验报告 - 11 - ; s=p-next;p-next=s-next;free(s); else cout输入的i值不正确endl; cout删除不成功!endl; return h; void main int i,flag=1; int select; Listlink a; length-; int f2=1; int f1=1; while(f2) coutnext; int n,y; char q,e; create(&a,

15、n); nodetype *b=a; while(b!=NULL) cout查找:2 ; 数据结构 实验报告 - 12 - cout插入字符:3 ; cout删除结点:4 ; cout链表长度:5 ; cout查找字符:6 ; cout清屏:7 ; coutEXIT:0n; coutselect; switch(select) case 2: while(f1) couti; if(!(i0&i=length) cout位置错误!endl; else f1=0; couti号位置值为: ; Get1(a,i); coutendl; f1=1; f2=0; break; case 3: cout

16、q; 数据结构 实验报告 - 13 - a=cins(a,1,q,n); paixu(a); cout插入成功,链表值为:endl; show(a); f2=0; break; case 4: cout请输入你要删除的结点:y; a=del(a,y,n); cout操作后链表值为: ; show(a); f2=0; break; case 5: cout该链表的长度为:length; coutendl; break; case 6: coute; coutGet2(a,e); coutendl; f2=0; break; case 7: system(cls); f2=1; flag=0; b

17、reak; case 0: 数据结构 实验报告 - 14 - flag=0; f2=0; break; 链表： #include #include #include #include #define TRUE 1 #define FALSE 0 int length=0; typedef struct node char data; struct node *next; case 1: show(a); f2=0; break; default : cout输入错误!endl; f2=0; break; nodetype,*Listlink; /进行头插法创建链表 void create(Li

18、stlink *head,int n) 数据结构 实验报告 - 15 - ; cout用头插法建立单链表,请输入链表数据,以$结束!; int i; Listlink p; char c; cout(按照头插法插入)next=NULL; int flag=1; cinc; if(c!=$) else i+; flag=0; p=(Listlink)malloc(sizeof(struct node);/*建立新结点s*/ p-data=c; p-next=(*head)-next;/*将s结点插入表头*/ (*head)-next=p; while(flag) /* flag初值为1，当输入$

19、时，置flag为0，建表结束*/ /按位置查找 int Get1(nodetype *h,int i) int j; nodetype *p=h; j=0; while(p-next!=NULL)&(jnext; j+; if(i=j) ; /查找与已知字符e相同的结点 int find(nodetype *h,char e) nodetype *p=h; coutdata; else return FALSE; while(p-data!=e) ; /对各字符元素进行排序 void paixu(nodetype *h) node *r,*q,*small; char temp; return

20、 TRUE; p=p-next; if(p-next=NULL) return FALSE; for(r=h-next;r-next!=NULL;r=r-next) small=r; for(q=r-next;q;q=q-next) /*找到链表中最小字符*/ if(q-datadata) 数据结构 实验报告 - 17 - small=q; if(small!=r) temp=r-data; r-data=small-data; /*把最小的数值换到P指针所指的位置数值上*/ 小字符位置*/ ; /对表进行插入操作 void show(nodetype *head) ; nodetype *s

21、earch(nodetype *h,int i,int m) small-data=temp; /*把原先p指针所指位置的数值填入被置换出的最node *p; p=head-next; while(p!=NULL) coutendl; coutdatanext; nodetype *p=h; int j=1; if(im|i0) return NULL; else while (p!=NULL&jnext; return p; ; nodetype *insert(nodetype *h,char q) nodetype *p=h,*s,*d=h; p=p-next ; s=(nodetype

22、 *)malloc(sizeof(nodetype); s-data=q; s-next =p; d-next=s; length+; return h; ; nodetype *input(nodetype *h,int i,char x,int m) nodetype *p,*s; s=(nodetype *)malloc(sizeof(nodetype); s-data=x;s-next=NULL; if(i=0) s-next=h;h=s; else p=search(h,i,m); if(p!=NULL) s-next=p-next; /x输入的字符 数据结构 实验报告 - 19 -

23、 ; p-next=s; else cout输入的i值不正确endl; return h; /对链表进行删除操作 nodetype *del(nodetype *h,int i) ; nodetype *p=h,*s; if(ilength) cout输入的i值不正确endl; else int j=1; while ( jnext; p-next=p-next-next; free(s); length-; return h; p=p-next ; j+; cout删除不成功!endl; 数据结构 实验报告 - 20 - void main int i,flag=1; int select;

24、 Listlink a; int n,y; char q,e; create(&a,n); nodetype *b=a; while( b!=NULL ) length-; int f2=1; int f1=1; while(f2) coutnext; cout查找:2 ; cout插入字符:3 ; cout删除结点:4 ; cout链表长度:5 ; cout查找字符:6 ; cout清屏:7 ; coutEXIT:0n; flag=1; while(flag) 数据结构 实验报告 - 21 - coutselect; switch(select) case 2: while(f1) cout

25、i; if(!(i0&i=length) cout位置错误!endl; else f1=0; couti号位置值为: ; Get1(a,i); coutendl; f1=1; f2=0; break; case 3: coutq; a=insert(a,q); paixu(a); cout插入成功,链表值为:endl; show(a); f2=0; break; case 4: cout请输入你要删除的结点:y; 数据结构 实验报告 - 22 - a=del(a,y); cout操作后链表值为: ; show(a); f2=0; break; case 5: cout该链表的长度为:lengt

26、h; coutendl; break; case 6: coute; if( find(a,e) ) cout1; else cout0; coutendl; f2=0; break; case 7: system(cls); f2=1; flag=0; break; case 0: flag=0; f2=0; break; case 1: show(a); f2=0; 数据结构 实验报告 - 23 - break; default : cout输入错误!endl; f2=0; break; 4测试数据与实验结果 线性表： 数据结构 实验报告 - 24 - 链表： 数据结构 实验报告 - 25 - 5结果分析与实验体会 通过这次的数据结构学习，掌握线性表数据结构的基本概念和抽象数据类型的表示，线性表数据结构的顺序和链式存储存表示，以及链式存储结构喝基本算法。优势的确遇到了很大的问题，很想放弃，但是做什么事都是不容易的。这次我受益匪浅，我会继续努力学习数据结构的！ 数据结构 实验报告 - 26 -