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

数据结构实验课程设计题目：实验一线性表的抽象数据类型的实现姓名：杨静学号：2011114105班级：2班（44号）组长：指导老师：解德祥计算机与信息学院实验一线性表的抽象数据类型的实现实验目的1.掌握线性表的顺序存储结构和链式存储结构；2.熟练掌握顺序表和链表基本算法的实现；3.掌握利用线性表数据结构解决实际问题的方法和基本技巧；4.按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5.按时提交实验报告。实验环境:计算机、C语言程序设计环境实验学时:2学时，选做实验。实验内容一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：①创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在20之内；②打印（遍历）该线性表（依次打印出表中元素值）；③在线性表中查找第i个元素，并返回其值；④在线性表中第i个元素之前插入一已知元素；⑤在线性表中删除第i个元素；⑥求线性表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：①创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；②打印（遍历）该链表（依次打印出表中元素值）；③在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；④在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；⑤在链表中按照有序方式插入一已知字符元素；⑥在线性表中删除第i个结点；⑦计算链表的长度。实验步骤：C源程序代码如下：#includestdio.h#defineOK1#defineERROR0#defineMAXSIZE20typedefintElemType;typedefstruct{ElemTypeelem[MAXSIZE];intlast;}SeqList;voidCreateSeqList(SeqList*L){intx,i=0;printf(请输入正整数，不超过20个:\n);scanf(%d,&x);while(iMAXSIZE){L-elem[i]=x;scanf(%d,&x);i++;}L-last=i;}voidPrintList(SeqList*L){inti;printf(数据元素为:\n);for(i=0;iL-last;i++)printf(%d\n,L-elem[i]);}intLocate(SeqList*L,inti){if(i=1&&i=L-last)returnL-elem[i-1];elsereturn0;}intInsList(SeqList*L,inti,ElemTypee){intk;if((i1)||(iL-last+2)){printf(插入i位置值不合法);return(ERROR);}if(L-last=MAXSIZE-1){printf(表已满，无法插入);return(ERROR);}for(k=L-last;k=i-1;k++)L-elem[k+1]=L-elem[k];L-elem[i-1]=e;L-last++;return(OK);}intDelList(SeqList*L,inti,ElemType*e){intk;if((i1)||(iL-last+1)){printf(删除位置不合法);return(ERROR);}*e=L-elem[i-1];for(k=i;i=L-last;k++)L-elem[k-1]=L-elem[k];L-last--;return(OK);}intSumList(SeqList*L){inti,sum=0;for(i=0;i=L-last;i++)sum=sum+L-elem[i];return(sum);}voidjiemian(){SeqListL;intj,i,a;printf(创建新链表请按1\n打印链表请按2\n按序号查找元素请按3\n在链表中查找与一已知字符相同的第一个结点请按4\n在链表中按照有序方式插入一已知字符元素请按5\n在线性表中删除第i个结点请按6\n计算链表的长度请按7\n操作结束请按0\n);scanf(%d,&j);while(j){switch(j){case1:CreateSeqList(&L);break;case2:printf(打印顺序表如下:\n);PrintList(&L);break;case3:printf(请问你要查找第几个元素:\n);scanf(%d,&i);if(Locate(&L,i))printf(您要找的元素为%d\n,Locate(&L,i));elseprintf(i值不合法!);break;case4:printf(请您输入选择插入位置以及输入插入元素:\n);scanf(%d%d,&i,&a);if(InsList(&L,i,a))PrintList(&L);elseprintf(i值不合法!\n);break;case5:printf(请您输入要删除元素的位置:\n);scanf(%d,&i);if(DelList(&L,i,&a))PrintList(&L);elseprintf(i值不合法!\n);break;case6:printf(所有元素之和为:%d\n,SumList(&L));break;case7:break;default:printf(数据输入错误，请重新输入!);}printf(操作结束请按7;继续操作请按1-6,请输入您的选择:\n);scanf(%d,&j);}}voidmain(){jiemian();}链表（带头结点）基本操作实验：#includestdlib.h#includestdio.hstructLNode{charelem;structLNode*next;}*l,*p,*q;voidOrder(structLNode*l,intn){inti;charswap,*e,*f;for(i=1;i=n-1;i++){p=l-next;while(p-next!=l){if(p-elemp-next-elem){e=&p-elem;f=&p-next-elem;swap=*e;*e=*f;*f=swap;}p=p-next;}}return;}voidPrint(structLNode*l,intn){inti;p=l-next;for(i=1;i=n;i++){printf(%c\n,p-elem);p=p-next;}printf(\n);return;}voidLocate(structLNode*l,intn,intm){inti;if(mn){printf(FALSE!\t);return;}else{p=l;for(i=1;i=m;i++){p=p-next;}printf(Theelemis:%c\n,p-elem);}return;}voidInsertelem(structLNode*l,intn,charm){q=(structLNode*)malloc(sizeof(structLNode));q-next=l-next;l-next=q;q-elem=m;n=n+1;Order(l,n);Print(l,n);return;}voidDelete(structLNode*l,intn,intm){inti;p=l;for(i=1;im;i++){p=p-next;}p-next=p-next-next;n=n-1;printf(删除后的链表为:\n);Print(l,n);return;}voidLength(intn){inti;intlength=0;for(i=1;i=n+1;i++){length=length+sizeof(structLNode);}printf(--------------------------------------------------------------\n);printf(Thelengthofthelistis:%d\n,length);return;}main(){printf(--------------欢迎进入数据结构实验设计--------------\n);inti,a,k,n;charc,s;l=(structLNode*)malloc(sizeof(structLNode));l-next=NULL;printf(请输入链表的元素数:);scanf(%d,&n);getchar();if(n=15){for(i=n;i0;i--){q=(structLNode*)malloc(sizeof(structLNode));q-next=l-next;l-next=q;}p=l;while(p-next!=NULL)p=p-next;p-next=l;printf(输入元素:);p=l-next;for(i=1;i=n;i++){scanf(%c,&p-elem);getchar();p=p-next;}Order(l,n);printf(--------------------------------------------------------------\n);printf(您输入的元素为:\n);Print(l,n);printf(--------------------------------------------------------------\n);printf(输入您想查找的元素序号:);scanf(%d,&a);getchar();Locate(l,n,a);printf(--------------------------------------------------------------\n);printf(输入您想插入的元素:);scanf(%c,&s);getchar();Insertelem(l,n,s);n=n+1;printf(--------------------------------------------------------------\n);printf(输入您要删除的元素序号:);scanf(%d,&k);if(k1||kn)printf(ERROR!);else{Delete(l,n,k);}n=n-1;Length(n);}elseprintf(ERROR!);}