数据结构实验1顺序表链表

1、浪海工曇浣针篇机科修系实验报告书课程名：数据结构线性表数据结构试验题目：班级：软件112学号：姓名：评语:成绩： 指导教师：批阅时间： 年 月线性表实验报告要求1目的与要求：1）掌握线性表数据结构的基本概念和抽彖数据类型描述；2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现；4）熟练掌握线性表的链式存储结构的基本操作算法实现；5）掌握线性表在实际问题中的应用和基本编程技巧；6）按照实验题冃要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结 果）；7）按照报告格式和内容要求，认真书写实验报告，并在试验后的第三天提交电子（全班同 学提交

2、到学委，再统一打包提交给老师）和纸质（每班每次5份，学委安排，保证每个同学至 少提交一次）；8）积极开展实验组组内交流和辅导，严禁复制和剽窃他人实验成果，一旦发现严肃处理;9）上实验课前，要求每个同学基本写好程序，并存储在自己的u盘上，用于实验课堂操 作时调试和运行。凡不做准备，没有提前编写程序者，拒绝上机试验。2实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型elemtype取整型ini。按照顺序存储结构实现如下算法：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表）,长度限定在25之内；2）打印/显示（遍历）该线性表（依次打印/显示出表中元素值

3、）；3）在顺序表中查找第i个元素，并返回其值；4）在顺序表第i个元素之前插入一已知元素；5）在顺序表中删除第i个元素；6）求顺序表屮所有元素值（整数）之和；二、链表带头结点基本操作实验要求：数据元素类型elemtype取字符型char。按照动态单链表结构实现如下算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回false；4）在链表屮查找与一已知字符相同的第一个结点，有则返回true,否则，返回fa

4、lse；5）在链表中第i个结点之前插入一个新结点；6）在线性表屮删除第i个结点；7）计算链表的长度。3实验步骤与源程序#inelude <iostream>#define ok 1#define error 0#define true 1#define false 0#define elemtype int#define maxstze 25 /*此处的宏定义常量表示线性表可能达到的最大长度*/using namespace std;typedef struct!elemtype elemmaxstze;/*线性表占用的数组空间*/intlast;/*记录线性表中最后一个元素在数组

5、elem中的位置(下标值)，空表置为t*/seqlist;void outputseqlist(seqlist *l)cout<<"顺序表如下："<endl;int i;for (i=0;i<=l->last;i+)cout<<l->elemi<<jn ;cout«e ndl;int getdate(seqlist *l)!int t;cout«zz请输入要查找的元素的序数："cndl;cin»t;if( t<0) | (t>l->last)cout

6、1;/，输入错误! ”;return(error);else return(l->elemtl);int inslist(seqlist *l)int i, e;cout«请输入要插入的元素插入位置及要插入的元素z/«endl;cin>>i>>e;int k;if(i<l) ii (i>l->last+2) /*首先判断插入位置是否合法*/!printf (，z插入位置i值不合法")；return(error);if(l->last>= maxsize-1)printf (z，表己满无法插入")

7、；return(error);for (k=l->last; k>=i-l; k-)/*为插入元素而移动位置*/l->elemk+l=l->elemk;l->elemi-l=e;/*在c语言数组中，第i个元素的下标为卜1*/l->last+;return(ok);int dellist(seqlist *l, elemtype *m)int w;cout«z/请输出要删除的元素位置：endl;cin>>w;int k;i f(w<1) |(w>l->last+l)icout«，z删除位置不合法!/z«

8、;endl;return(error);二l->elemw-l;/*将删除的元素存放到e所指向的变量屮*/for(k=w; k<=l->last; k+)l->elemk-l = i->elemk; /*将后面的元素依次前移*/l->last;return(ok);int sum(seqlist *l)int i, n=0;for(i=0;i<l->last+l;i+)n二n+l->elemi;return (n);void main()!int *q, n;seqlist *l;l=(seqli st*)malloc(sizeof(seq

9、li st);q = (int*)malloc(sizeof(int);cout«"请输入顺序表长度：；cin»n;l->last=n-l;cout«，z请输入顺序表：;for (i=0;i<n;i+)cin»l->elemi;char c=，y"whlie(c!=，n')cout«z，请选择你要进行的操作："endl;cout«，l.输出顺序表；/z«，n «，z2.查找元素；插入元素；n«4.删除元 素；"«'n

10、9;<<"5.求和"<<endl;int xuanze;cin>>xuanze;swi tch(xuan刁e)case 1:outputseqlist( l);break;case 2:cout«getdate( l)«cndl;break;case 3:inslist ( l);break;case 4:del li st(l, q);break;case 5:cout<<sum( l)<<endl;break;cout«，z是否要继续进行操作y/n：/z«endl;cin

11、>>c;#include<stdio.h>#include<malloc.h>#define max 15#define ture 1#define false 0typedef char elemtype;typedef struct nodechar date;struct node * next;node,*linklist;void initlist(linklist *l)* l=(linklist)mahoc(sizeof(char);(*l)->next=null;void printflink(linklist l)linklist p

12、;p=l->next;printf(n 链表为:”);while(p!二 null)printf("%c ",p->date);p=p->next;void create(linklist l)linklist s,r;char c;int flag= 1;int n;r=l;printf(”元素个数:”)； scanf(m%d'&n);if(n>max)printfc超出限定长度! ”);elseprint”输入字符(以#键结束 while(flag)scanf(” c",&c);if(c !=*#*) s=(no

13、de*)malloc(sizeof(char); s->date=c;r->next=s;r=s;elseflag=o;r->next =null;void order(linklist l)char c;node *r,*q,*p;for(r=l->next;r->next!=null;r=r->next) p=gfor(q=r->next;q;q=q->next) if(q->date)<(p->date)p二q；if(p!=r)c=r->date;r->date=p->date; p->date=c

14、;)printflink(l);void get(linklist l, int i, elemtype *e)int j; node *p;p=l；j=-l；while (p->next! =null)&&(j<i)p=p->next;j+；*e=p->date ;if(i=j)printf(um%d 个元素为:%c",i,*e); elseprintf(ufalseu);)void locate(linklist l, elemtype e)int i=l;linklist p;p=l->next;while(p&&p

15、->date !=e)i=i+;p=p->next;if(!p)printf(nfalsenh);elseprintf(htruenh);printf（h该元素在第d个位置!”卜1）;void in$list(linklist l,int i,elemtype e)node *p,*s;int k=0;p 二 l;while(p!=null&&k<i-l)p=p->next;k=k+；if(!p)printf(u插入位置不合理! ”)；s=(node*)malloc(sizeof(char);s->date=e;s->next=p >n

16、ext;p->next=s;order(l);void dellist(linklist l,inl i,elemtype *e)node *p,*r;intj;j 二 0;p=l;while(p->next! =null)&&(j<i-l)p=p->next;j+；iif(p->next!=null)p->next=p->next->next;r=p->next;*e=r->date;printfc删除第d 个元素:%cn”,i,*e);elseprintfc删除结点的位置i不合理!“)；void listlengt

17、h(linklist l)node *p;int j=0; p=l->next; while(p!=null)p=p->next; j+;printf（h单链表的长度:%dfj）;void menu()printf（nn1.创建任意字符型单循坏链表”）；printf（'rn2.打印（遍历）该链表”）；printf（hn3.查找第i个元素”）；printfc4查找与一已知字符相同的元素”）;printf（un5.插入元素”）；printf（hn6.删除第i个结点”）；printf（hn7.计算链表的长度”）；printf（"n&退出”）；void main(

18、)int i;int flag=0;elemtype e;linklist l;l=(linklist)malloc(sizeof(char);initlist(&l);menu();while(!flag)printfcnxn请输入你的选择(18):”); scanf(”d”,&i);switch(i)case 1:create(l);break;case 2:order(l);break;case 3:printfc*输入要查找的第i个元素:”）; scanf（”d”,&i）;get(ui,&e); break;case 4:printf("输入査找的元素:”); rewind(stdin);sca