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

淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 线性表数据结构试验 班 级： 软件 081 学 号： 110831104 姓 名： 强余彬 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 26 -线性表实验报告要求1目的与要求:1）掌握线性表数据结构的基本概念和抽象数据类型描述；2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现； 4）熟练掌握线性表的链式存储结构的基本操作算法实现;5）掌握线性表在实际问题中的应用和基本编程技巧;6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；7）认真书写实验报告,并在试验后的第三天提交电子（全部由学委打包提交）和纸质（每班每次5份，学委安排）。2实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印/显示（遍历）该线性表（依次打印/显示出表中元素值）；3）在线性表中查找第i个元素，并返回其值；4）在线性表中第i个元素之前插入一已知元素；5）在线性表中删除第i个元素；6）求线性表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。按照动态单链表结构实现如下算法（各算法边界条件适当给出）：1）按照头插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中按照有序方式插入一已知字符元素；6）在线性表中删除第i个结点；7）计算链表的长度。3实验步骤与源程序(1)顺序表#include#include#include #define maxsize 25int length; /表长/ 顺序表结构定义struct seqlistint elemmaxsize; /线性表占用的数组空间int last; /下标，等于位序减1seqList;/ 遍历函数void show (seqlist *p) int i=0; for(;ilast+1;i+) couti+1elemiendl;/ 插入函数int insert(seqlist *p) / i位置 j插入的数int i; int j;int flag=1;coutInput the position and the value: ij; if(ilength) coutThe wrong position! Input again: last; for(;pos=i;pos-) p-elempos+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; coutielemi-1endl;return 0;/ 删除函数int del(seqlist *p)int i; int flag=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;/ 主函数void main() seqlist *p; p=(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;break; case 1:show (p);break; case 2:insert (p);break; case 3:find (p);break; 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 0int length=0;typedef struct node char data;struct node *next;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，建表结束*/cinc; if(c!=$)p=(Listlink)malloc(sizeof(struct node);/*建立新结点s*/p-data=c;p-next=(*head)-next;/*将s结点插入表头*/(*head)-next=p;elseflag=0;i+;/按位置查找 int Get1(nodetype *h,int i)int j; nodetype *p=h;j=0;while(p-next!=NULL)&(jnext; j+; if(i=j)coutdata; elsereturn FALSE;/查找与已知字符e相同的结点int Get2(nodetype *h,char e)nodetype *p=h; while(p-data!=e) p=p-next-next; if(p-next=NULL) return FALSE;return TRUE;/对各字符元素进行排序void paixu(nodetype *h)node *r,*q,*small;char temp; 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指针所指的位置数值上（原P指针的next指向不变）*/small-data=temp; /*把原先p指针所指位置的数值填入被置换出的最小字符位置*/ ;/对表进行插入操作void show(nodetype *head)node *p;p=head-next;while(p!=NULL)coutdatanext;coutm|i0) return NULL;elsewhile (p!=NULL&jnext;return p;nodetype *cins(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;elsep=search(h,i,m);if(p!=NULL)s-next=p-next;p-next=s;else cout输入的i值不正确next;free(p); else p=search(h,i,m); if(p!=NULL&p-next!=NULL) s=p-next;p-next=s-next;free(s); else cout输入的i值不正确endl; cout删除不成功!next;length-;int f2=1;int f1=1;while(f2) cout遍历:1 ; cout查找:2 ; cout插入字符:3 ; cout删除结点:4 ; cout链表长度:5 ; cout查找字符:6 ; cout清屏:7 ; coutEXIT:0n;flag=1;while(flag)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: coutq; 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; break;case 0:flag=0;f2=0; break;case 1:show(a);f2=0;break;default :cout输入错误!endl;f2=0;break; 链表：#include #include#include#include#define TRUE 1#define FALSE 0int length=0;typedef struct node char data;struct node *next;nodetype,*Listlink;/进行头插法创建链表 void create(Listlink *head,int n) cout用头插法建立单链表,请输入链表数据,以$结束!; int i; Listlink p; char c; cout(按照头插法插入)next=NULL; int flag=1; while(flag) /* flag初值为1，当输入$时，置flag为0，建表结束*/cinc; if(c!=$)p=(Listlink)malloc(sizeof(struct node);/*建立新结点s*/p-data=c;p-next=(*head)-next;/*将s结点插入表头*/(*head)-next=p;elseflag=0;i+;/按位置查找 int Get1(nodetype *h,int i)int j; nodetype *p=h;j=0;while(p-next!=NULL)&(jnext; j+; if(i=j)coutdata; elsereturn FALSE;/查找与已知字符e相同的结点int find(nodetype *h,char e)nodetype *p=h; while(p-data!=e) p=p-next; if(p-next=NULL) return FALSE;return TRUE;/对各字符元素进行排序void paixu(nodetype *h)node *r,*q,*small;char temp; 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指针所指的位置数值上（原P指针的next指向不变）*/small-data=temp; /*把原先p指针所指位置的数值填入被置换出的最小字符位置*/ ;/对表进行插入操作void show(nodetype *head)node *p;p=head-next;while(p!=NULL)coutdatanext;coutm|i0) return NULL;elsewhile (p!=NULL&jnext;return p;nodetype *insert(nodetype *h,char q) nodetype *p=h,*s,*d=h; p=p-next ; s=(nodetype *)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) /x输入的字符 nodetype *p,*s;s=(nodetype *)malloc(sizeof(nodetype);s-data=x;s-next=NULL;if(i=0)s-next=h;h=s;elsep=search(h,i,m);if(p!=NULL)s-next=p-next;p-next=s; else cout输入的i值不正确endl;return h;/对链表进行删除操作nodetype *del(nodetype *h,int i)nodetype *p=h,*s;if(ilength) cout输入的i值不正确endl; cout删除不成功!endl;elseint j=1;while ( jnext ;j+;s=p-next;p-next=p-next-next;free(s);length-;return h;void main() int i,flag=1; int select; Listlink a; int n,y; char q,e; create(&a,n); nodetype *b=a; while( b!=NULL )length+;b=b-next;length-;int f2=1;int f1=1;while(f2) cout遍历:1 ; cout查找:2 ; cout插入字符:3 ; cout删除结点:4 ; cout链表长度:5 ; cout查找字符:6 ; cout清屏:7 ; coutEX