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

《线性表的抽象数据类型的实现.doc》由会员分享，可在线阅读，更多相关《线性表的抽象数据类型的实现.doc（10页珍藏版）》请在沃文网上搜索。

1、 数据结构实验报告 - 10 -1实验题目或内容实验题目：一、顺序表的基本操作实现实验二、链表（带头结点）基本操作实验实验内容：一、按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）： 1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内； 2）打印（遍历）该线性表（依次打印出表中元素值）； 3）在线性表中查找第i个元素，并返回其值； 4）在线性表中第i个元素之前插入一已知元素； 5）在线性表中删除第i个元素； 6）求线性表中所有元素值（整数）之和；二、按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）： 1）创建任意字符型有序（递增排序）单循

2、环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内； 2）打印（遍历）该链表（依次打印出表中元素值）； 3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE； 4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 5）在链表中按照有序方式插入一已知字符元素； 6）在线性表中删除第i个结点； 7）计算链表的长度。2目的与要求实验目的：1）掌握线性表的顺序存储结构和链式存储结构；2）熟练掌握顺序表和链表基本算法的实现；3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提

3、交程序清单及及相关实验数据与运行结果）；5）按时提交实验报告。 实验要求：一、要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）： 1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内； 2）打印（遍历）该线性表（依次打印出表中元素值）； 3）在线性表中查找第i个元素，并返回其值； 4）在线性表中第i个元素之前插入一已知元素； 5）在线性表中删除第i个元素； 6）求线性表中所有元素值（整数）之和；二、要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给

4、出）： 1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内； 2）打印（遍历）该链表（依次打印出表中元素值）； 3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE； 4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 5）在链表中按照有序方式插入一已知字符元素； 6）在线性表中删除第i个结点； 7）计算链表的长度。3实验步骤与源程序一、顺序表的源程序#include#include#includeint list25;int i,n,a,sum=0,k,l;int eleminsert;/*-

5、创建函数-*/void initlist()printf(Please input the total of the elems:);scanf(%d,&n);if(n25|n1) printf(ERROE!);return;printf(Please input the elems:.n);for(i=0;in;i+) scanf(%d,&listi); return;/*-打印函数-*/void Print(int list,int n)int j;for(j=0;jn;j+)printf(%dt,listj);printf(n);return;/*-查找函数-*/void Search(

6、int list,int n,int m)if(mn)printf(ERROR!n); return ;else printf(The elem is %d at %d placen,listm-1,m);return;/*-插入函数-*/void Insert(int list,int n,int m,int elem)int j;if(mn)printf(ERROR!n); return ;for(j=n-1;j=m-1;j-)listj+1=listj;listm-1=elem;n=n+1;printf(The new list are: );Print(list,n);return;/

7、*-删除函数-*/void Delete(int list,int n,int m)int q;if(mn) printf(ERROR!n); return ;for(q=m-1;q=n;q+)listq=listq+1;printf(The new list are:);Print(list,n-1);return;/*-求和函数-*/void Sum(int list,int n,int sum)int j;for(j=0;jn;j+)sum=sum+listj;printf(The sum is :%d,sum);return;void menu()int j;/*-菜单函数-*/men

8、ulab:printf(* MENU *nn);printf(Create a new int list :.press 1nn);printf(Print the whole list :.press 2nn);printf(Search by order :.press 3nn);printf(Insert the elem in the place i:.press 4nn);printf(Delete the elem by order :.press 5nn);printf(Sum all elem in the list :.press 6nn);printf(exit the p

9、rograme :.press 0nn);printf(* END *nn);printf(Please choose the number from (06).);checklabel: scanf(%1d,&j);getchar();if(j7) printf(Error! Please choose again.); goto checklabel; printf(ntYou choose the number %dn ,j);printf(ntPress any key to continue.);getchar();system(cls); /*clear screen*/switc

10、h(j) case 1:/*创建任意整数线性表*/initlist(); system(cls); /*clear screen*/goto menulab;case 2: /*打印（遍历）该线性表*/printf(The original list is:);Print(list,n);printf(Press any key to continue.);getchar();system(cls); /*clear screen*/goto menulab;case 3:/*在线性表中查找第i个元素，并返回其值*/printf(Input which LNode you want to Se

11、arch(Input number):);scanf(%d,&a);getchar();Search(list,n,a);printf(Press any key to continue.); getchar();system(cls); /*clear screen*/goto menulab;case 4:/*在线性表中第i个元素之前插入一已知元素*/printf(Please input the elems place where you want to insert);scanf(%d,&k);printf(Input the elem which you want to insert

12、:);scanf(%d,&eleminsert);Insert(list,n,k,eleminsert);printf(Press any key to continue.);getchar();system(cls); /*clear screen*/goto menulab;case 5:/*在线性表中删除第i个元素*/printf(Please input the elem you want to delete:);scanf(%d,&l);n=n+1;Delete(list,n,l);n=n-1;printf(Press any key to continue.);getchar();

13、system(cls); /*clear screen*/goto menulab;case 6:/*求线性表中所有元素值（整数）之和*/Sum(list,n,sum);printf(Press any key to continue.);getchar();system(cls); /*clear screen*/goto menulab;case 0:/*退出程序*/printf(Press any key to continue.);getchar();exit(0);void main() void menu(); menu();二、链表（带头结点）的源程序#include#inclu

14、destruct LNodechar elem;struct LNode* next;*l,*p,*new;int i,a,k,n;char c,s;/*-创建函数-*/void intilist(void) l=(struct LNode *)malloc(sizeof(struct LNode); l-next=NULL; system(cls); printf(Input the total of the elems:.); scanf(%d,&n); getchar(); if(n15) printf(Error!); for(i=n;i0;i-) new=(struct LNode

15、*)malloc(sizeof(struct LNode); new-next=l-next;l-next=new; p=l;while(p-next!=NULL) p=p-next;p-next=l;printf(Input elems:.n);p=l-next;for(i=1;ielem);getchar(); p=p-next; return;/*-排序函数-*/void Sequence(struct LNode * l, int n)int i;char swap,*e,*f;for(i=1;inext;while(p-next!=l)if(p-elemp-next-elem) e=

16、&p-elem;f=&p-next-elem;swap=*e;*e=*f;*f=swap;p=p-next;return;/*-打印函数-*/void Print(struct LNode * l, int n)int i;p=l-next;for(i=1;ielem);p=p-next;printf(n);return;/*-查找函数-*/void Locate(struct LNode * l, int n,int m)int i;if(mn) printf(FALSE!t);return; else p=l;for(i=1;inext;printf(The elem is:%cn,p-e

17、lem);return;/*-已知字母匹配首结点查找函数-*/void LocateLNode(struct LNode * l, int n,char m)int i;p=l;for(i=1;inext; if(p-elem=m) printf(TRUE!n);return;if(in) printf(FALSE!n);return;/*-插入函数-*/void Insert(struct LNode * l, int n,char m)new=(struct LNode *)malloc(sizeof(struct LNode);new-next=l-next;l-next=new;new

18、-elem=m;n=n+1;Sequence(l,n);Print(l,n);return;/*-删除函数-*/void Delete(struct LNode * l, int n,int m)int i;p=l;for(i=1;inext;p-next=p-next-next;n=n-1;printf(The new list is:);Print(l,n);return;/*-求表长函数-*/void Length(int n)int i;int length=0;for(i=1;i=n+1;i+)length=length+sizeof(struct LNode);printf(The

19、 length of the list is:%d,length);return;/*-菜单函数-*/ void menu()int j;menulab:printf(* MENU *nn);printf(Create the new list :.press 1nn);printf(Sequence the list :.press 2nn);printf(Search the Lnode by order :.press 3nn);printf(Search the Lnode by elem :.press 4nn);printf(Insert the elem :.press 5nn)

20、;printf(Delete the elem by order :.press 6nn);printf(Return the length of the list :.press 7nn);printf(exit the programe :.press 0nn);printf(* END *nn);printf(Please choose the number from (07).);checklabel: scanf(%1d,&j);getchar();if(j7) printf(Error! Please choose again.); goto checklabel; printf(

21、ntYou choose the number %dn ,j);printf(ntPress any key to continue.);getchar();system(cls); /*clear screen*/switch(j) case 1:/*创建链表并输入元素*/intilist(); system(cls); /*clear screen*/goto menulab;case 2: /*排序并打印链表*/Sequence(l,n); printf(The orignal list is:n);Print(l,n);printf(Press any key to continue.

22、);getchar(); system(cls); /*clear screen*/goto menulab;case 3:/*查找第i个元素*/printf(Input which LNode you want to locate(Input number):);scanf(%d,&a);getchar();Locate(l,n,a);printf(Press any key to continue.); getchar();system(cls); /*clear screen*/goto menulab;case 4:/*查找与已知字符相同的第一个结点*/printf(Input the

23、 elem you want to search );scanf(%c,&c);getchar();LocateLNode(l,n,c);printf(Press any key to continue.);getchar();system(cls); /*clear screen*/goto menulab;case 5:/*插入已知字符的结点*/printf(Input the elem you want to insert:);scanf(%c,&s);getchar();Insert(l,n,s);n=n+1;printf(Press any key to continue.);get

24、char();system(cls); /*clear screen*/goto menulab;case 6:/*删除第i个结点*/printf(Input which one you want to delete:);scanf(%d,&k);if(kn)printf(ERROR!);elseDelete(l,n,k);n=n-1;getchar();system(cls); /*clear screen*/goto menulab;case 7:/*计算链表长度*/Length(n);printf(Press any key to continue.);getchar();system(

25、cls); /*clear screen*/goto menulab;case 0:/*退出链表程序*/printf(Press any key to continue.);getchar();exit(0);/*-主函数-*/main() void menu(void); menu(); 4测试数据与实验结果一、 顺序表程序抓图及其简要说明菜单选项如下图所示：该菜单由八个函数组成，实现八项功能。关于顺序表的函数的具体执行情况请参照链表说明和抓图。两程序执行情况基本类似。一、 链表（带头结点）程序抓图及其简要说明菜单函数如下图所示：该菜单包含了程序的八项基本操作，实现了创建、排序、查找、以及删

26、除等功能。具体执行过程如下。选择菜单1，创建一个链表。如上图所示的操作，其余也是一样例如，当选择“2”时如下图：当执行1时如下图：创建链表完成，按任意键返回到菜单。当执行2时如下图：链表排序成功，将排好的链表打印出来，按任意键返回到菜单。当执行3时如下图：按排序位置查找节点，并打印出查得元素，按任意键返回到菜单。当执行4时如下图：按元素查找与之相同的节点，返回TURE或FALSE，按任意键返回到菜单。当执行5时如下图：插入元素，自动排序，打印出新链表元素，按任意键返回到菜单。当执行6时如下图：删除一元素，打印出要删除的元素，按任意键返回到菜单。当执行7时如下图：打印出链表长度，按任意键返回到菜

27、单。当执行0时：退出程序，按任意键返回到菜单。（图略）二、5结果分析与实验体会一、 顺序表的基本操作实现实验原程序代码中clrscr(); 都要改成system(cls); Search(l,n,a);都要改成Search(list,n,a);起初的时候执行到第四步老是直接跳到第一步，不懂为什么，就去问同学了，后来才知道原来要接着执行第二步，通过此次实验，我了解了线性表的顺序存储结构，掌握了顺序表的基本算法核心，利用线性表数据结构作出相关程序。有些程序看不懂，是但是看很多书，反复琢磨就能理解其实质，虽然中间出过错误，但是最后能调试出结果，作完题目。整体的技巧灵活性还需要加强，我会在以后的实验中，多多训练，提高灵活性二、 链表（带头结点）基本操作实验同样运行程序出错，需要改代码，把源程序中的“new”都要改成例如“newn”，clrscr(); 都要改成system(cls);然后根据要求一步步坐下来，刚开始先做的是链表带头节点基本实验操作，程序执行时不会参照它我才完成顺序表的基本操作实现实验，开始不懂里面的内涵，慢慢一步一步自己琢磨，发现其实操作不难，主要自己耐心看书学习，虚心求教，这就是我此次实验的的心得体会 .