线性表的抽象数据类型的实现

淮海工学院计算机工程学院实验报告书课程名：数据结构题目：线性表的抽象数据类型的实现班级：D软件101学号：511021112姓名：丁冬梅评语：成绩：指导教师：批阅时间：2011年月日《数据结构》实验报告-1-1实验题目或内容实验题目：一、顺序表的基本操作实现实验二、链表（带头结点）基本操作实验实验内容：一、按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3）在线性表中查找第i个元素，并返回其值；4）在线性表中第i个元素之前插入一已知元素；5）在线性表中删除第i个元素；6）求线性表中所有元素值（整数）之和；二、按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；2）打印（遍历）该链表（依次打印出表中元素值）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中按照有序方式插入一已知字符元素；6）在线性表中删除第i个结点；7）计算链表的长度。2目的与要求实验目的：1）掌握线性表的顺序存储结构和链式存储结构；2）熟练掌握顺序表和链表基本算法的实现；3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5）按时提交实验报告。实验要求：一、要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3）在线性表中查找第i个元素，并返回其值；4）在线性表中第i个元素之前插入一已知元素；5）在线性表中删除第i个元素；6）求线性表中所有元素值（整数）之和；二、要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；《数据结构》实验报告-2-2）打印（遍历）该链表（依次打印出表中元素值）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中按照有序方式插入一已知字符元素；6）在线性表中删除第i个结点；7）计算链表的长度。3实验步骤与源程序一、顺序表的源程序#includestdlib.h#includestdio.h#includemalloc.hintlist[25];inti,n,a,sum=0,k,l;inteleminsert;/*------------------创建函数--------------*/voidinitlist(){printf(Pleaseinputthetotaloftheelems:);scanf(%d,&n);if(n25||n1){printf(ERROE!);return;}printf(Pleaseinputtheelems:...\n);for(i=0;in;i++){scanf(%d,&list[i]);}return;}/*------------------打印函数--------------*/voidPrint(intlist[],intn){intj;for(j=0;jn;j++)printf(%d\t,list[j]);printf(\n);return;}/*------------------查找函数------------*/voidSearch(intlist[],intn,intm){if(m1||mn){printf(ERROR!\n);return;}elseprintf(Theelemis%dat%dplace\n,list[m-1],m);return;}/*----------------插入函数------------*/voidInsert(intlist[],intn,intm,intelem){intj;if(m1||mn){printf(ERROR!\n);return;}for(j=n-1;j=m-1;j--){list[j+1]=list[j];}list[m-1]=elem;n=n+1;printf(Thenewlistare:);Print(list,n);return;}/*---------------删除函数-----------*/voidDelete(intlist[],intn,intm){《数据结构》实验报告-3-intq;if(m1||mn){printf(ERROR!\n);return;}for(q=m-1;q=n;q++){list[q]=list[q+1];}printf(Thenewlistare:);Print(list,n-1);return;}/*-------------求和函数------------*/voidSum(intlist[],intn,intsum){intj;for(j=0;jn;j++){sum=sum+list[j];}printf(Thesumis:%d,sum);return;}voidmenu(){intj;/*------------菜单函数------------*/menulab:printf(**********************MENU******************\n\n);printf(Createanewintlist:...................press1\n\n);printf(Printthewholelist:....................press2\n\n);printf(Searchbyorder:........................press3\n\n);printf(Inserttheelemintheplacei:...........press4\n\n);printf(Deletetheelembyorder:................press5\n\n);printf(Sumalleleminthelist:................press6\n\n);printf(exittheprograme:.......................press0\n\n);printf(**********************END*******************\n\n);printf(Pleasechoosethenumberfrom(0~6).....);checklabel:scanf(%1d,&j);getchar();if(j0||j7){printf(Error!Pleasechooseagain......);gotochecklabel;}printf(\n\tYouchoosethenumber%d\n,j);printf(\n\tPressanykeytocontinue.....);getchar();system(cls);/*clearscreen*/switch(j){case1:/*创建任意整数线性表*/initlist();system(cls);/*clearscreen*/gotomenulab;case2:/*打印（遍历）该线性表*/printf(Theoriginallistis:);Print(list,n);printf(Pressanykeytocontinue.....);getchar();system(cls);/*clearscreen*/gotomenulab;case3:/*在线性表中查找第i个元素，并返回其值*/printf(InputwhichLNodeyouwanttoSearch(Inputnumber):);《数据结构》实验报告-4-scanf(%d,&a);getchar();Search(list,n,a);printf(Pressanykeytocontinue.....);getchar();system(cls);/*clearscreen*/gotomenulab;case4:/*在线性表中第i个元素之前插入一已知元素*/printf(Pleaseinputtheelem'splacewhereyouwanttoinsert);scanf(%d,&k);printf(Inputtheelemwhichyouwanttoinsert:);scanf(%d,&eleminsert);Insert(list,n,k,eleminsert);printf(Pressanykeytocontinue.....);getchar();system(cls);/*clearscreen*/gotomenulab;case5:/*在线性表中删除第i个元素*/printf(Pleaseinputtheelemyouwanttodelete:);scanf(%d,&l);n=n+1;Delete(list,n,l);n=n-1;printf(Pressanykeytocontinue.....);getchar();system(cls);/*clearscreen*/gotomenulab;case6:/*求线性表中所有元素值（整数）之和*/Sum(list,n,sum);printf(Pressanykeytocontinue.....);getchar();system(cls);/*clearscreen*/gotomenulab;case0:/*退出程序*/printf(Pressanykeytocontinue.....);getchar();exit(0);}}voidmain(){voidmenu();menu();}二、链表（带头结点）的源程序#includestdlib.h#includestdio.hstructLNode{charelem;structLNode*next;}*l,*p,*new;inti,a,k,n;charc,s;/*----------------创建函数-------------*/voidintilist(void){《数据结构》实验报告-5-l=(structLNode*)malloc(sizeof(structLNode));l-next=NULL;system(cls);printf(Inputthetotaloftheelems:.....);scanf(%d,&n);getchar();if(n15)printf(Error!);for(i=n;i0;i--){new=(structLNode*)malloc(sizeof(structLNode));new-next=l-next;l-next=new;}p=l;while(p-next!=NULL)p=p-next;p-next=l;printf(Inputelems:.......\n);p=l-next;for(i=1;i=n;i++){scanf(%c,&p-elem);getchar();p=p-next;}return;}/*----------------排序函数-------------*/voidSequence(structLNode*l,intn){inti;charswap