循环链表实验课程报告.docx

《循环链表实验课程报告.docx》由会员分享，可在线阅读，更多相关《循环链表实验课程报告.docx（19页珍藏版）》请在三一办公上搜索。

1、循环链表实验课程报告计算机软件技术基础实验报告 实验名称：循环链表操作姓名：专业：学号：时间： 一、实验目的 通过实验，深刻理解单项循环链表的逻辑结构，熟练掌握链式存储的表示及其所执行的运算，实现循环链表的基本操作。 二、实验内容 创建，插入，删除，计数，逆置以及按关键字和按序号查找。 三、实验原理 线性表的链式存储结构称为线性链表。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号，即指向后件结点，称为指针域。 线性链表

2、中，用一个专门的指针指向线性链表中第一个数据元素的结点。线性表中最后一个元素没有后件，最后一个结点的指针域为空，表示链表终止。循环链表是为克服线性链表的不足采用的另一种链接方式。循环链表增加了一个表头结点，其指针域指向第一个元素的结点，头指针指向表头结点，循环链表的最后一个结点的指针域不为空，而是指向头结点。 四、需求说明 1、功能分析 创建链表 在内存中创建一个链式存储的循环线性表。每当创建一个新的链表后，会提示用户是否输入新的元素，同时能够自动生成每一元素对应的序号以及整个链表的长度。 按序号查找链表中的某一元素 链表中的元素按序号进行排列。当输入某一要查找的序号后，首先判断输入的序号是否

3、在当前的链表中，如果不在，输出提示信息。如果在从链表的头依次查找直到找到此序号，输出此序号的元素所有的信息。 按内容查找链表中的某一元素 输入元素的内容，从链表的头依次查找到尾，如果找到对应此内容的元素，则输出此元素对应的信息。如果没有找到此元素，则输出提示信息。 插入元素 此功能要求能在链表中任一元素之后插入新的元素。因此首先也要找到原链表中的某一元素，要求与相同。找到原链表中的元素后，输入新的元素内容，然后将此元素插入到原链表中。插入之后原链表中各元素的序号以及整个链表的长度能够随之自动更新。 删除元素 与插入元素类似。首先能够找到原链表中要删除的元素，要求与同。找到原链表中的元素后，将此

4、元素删除。删除之后，原链表中各元素的序号以及整个链表的长度能够随之自动更新。 输出链表 能够将当前链表中所有元素的内容和序号按顺序输出。 逆置链表 能够将原链表中的各个元素逆置输出。 2、其它分析 界面要美观友好，便于人机交互，通过用户的输入来执行相应的功能； 执行完某一特定功能后能返回主菜单，继续由用户选择相应的功能； 在主菜单内用户可以选择退出，其他情况下，程序都不会跑飞； 本程序需要首先建立链表，在没有建立链表的情况下要能给出提示信息。 软硬件环境： 在WindowXP或者WindowsVista环境下，在安装Microsoft Visual C+6.0的计算机上 五、总体设计 数据结构

5、设计 建立一个单循环链表，采用结构体的形式，每一个结构中包括三个部分：元素的内容，元素的序号、指向结构体中下一个元素的指针。 定义结构体类型：struct biao int x,y,num,x1,x2; struct biao *next; ; 创建结点与释放 利用p1=(struct biao*)malloc(LEN)开辟空间 利用free对结点空间进行释放 创建空循环链表 先开辟一个节点p0 p0-num=NULL,p0-next=p1 ;head=p0; 软件总体结构设计 程序包括以下几个函数： 主函数、界面显示以及菜单选择函数、创建链表的函数、查找某一元素的函数、按序号查找某一元素的函

6、数、按内容查找某一元素的函数、插入某一元素的函数、删除某一元素的函数、正序输出所有链表各元素的函数、逆置链表的函数。 其中主函数调用界面显示以及菜单选择函数，根据用户的按键判断选择执行相应的功能，调用相应的功能函数。各个功能函数中，查找某一元素的函数调用两个函数，分别为按序号查找某一元素的函数和按内容查找某一元素的函数。而在插入某一元素的函数和删除某一元素的函数中也都需要调用查找某一元素的函数。 算法设计及效率分析 本程序中的操作都是基于单项循环链表，主要算法设计也是体现在对循环链表的操作中。链式结构的优点在于可以动态地分配空间，动态地增加或删减链表的长度，同时作为链表结构，每个节点都有数据域

7、和指针域，指针域指向其后件结点，这两点为链表的操作提供了很大的方便。而作为循环链表，增加了表头结点，这又使得对空链表的操作对非空链表的操作保持了一致性，免除了对表头结点和表尾结点的特殊处理。 主程序流程设计 建立循环链表 显示所有元素 插入元素 功能选择 开始 删除元素 统计元素个数 逆转链表 查询 退出 返回菜单 界面设计 六、详细设计 1、创建链表 首先在内存中创建一个链式存储的循环线性表，建立存储空间。而后将输入的内容赋给结构体中的元素内容，并使插入的尾结点的*next指向链表中头结点，而原来链表中尾结点的*next指向当前结构。输入所要存储的数据，每当插入一个元素，都要根据其所在位置，

8、自动生成每一元素对应的序号以及整个链表的长度。序号从1依次递加，并以输入数据“0”结束。当程序运行完毕后，利用free对结点空间进行释放。 2、显示当前元素 显示元素的功能使当前存储的数据进行输出，对当前运行程序的结果实现检验。从头到尾按顺序将每个元素对应的序号和内容依次输出。本程序设计的思想为定义了一个结构体指针：*p始终指向结点的下一个结点，它的作用是使链表不会丢失。并将此结点所存储的数据进行输出，直至链表首地址为止。 3、插入元素 插入元素的功能分为：“按位置插入”和“插入某元素后”两项。程序实现的方法为：首先调用查找元素找到原链表中的所要插入的位置，而后动态申请一个新的存储空间，建立一

9、个新的结构体。对于单循环链表来说，只需要将此元素的*next指向原链表中找到元素的后一个元素，再将原链表中找到元素的*next指向此指针即可。 4、删除元素 删除元素的功能分为：“按位置删除”和“按内容删除”两项。此功能实现的方法为：首先调用查找元素找到原链表中的所要删除的元素。对于单循环链表而言，只需要将此元素前一个元素的*next指向此元素后一个元素。而后将所存储的元素顺序输出即可。与此同时进行元素序号更改以及存储空间释放等操作。 5、统计元素个数 对单循环链表而言，统计元素功能的实现，是使指针依循环链表依次移动，直至返回链表表头为止，记下指针移动的次数并以此进行输出。 6、逆转链表 逆转

10、链表功能的实现，先前为定义了三个结构体指针：*p0,*p1,*p2。*p1始终指向头结点的下一个结点，它的作用是使链表不会丢失。*p0首先指向尾结点，*p2指向倒数第二个结点。由于*p1的存在，可以将头结点的*next指向尾结点而不会使整个链表丢失。而尾结点的*next指向倒数第二个结点。然后*p1,*p2前移，再重复使*p1指向的结点的*next指向*p2指向的结点。注意，*p1前移很容易，只需指向*p1指向的结点即可，而* p2则需要从*p0开始依次后移了。最后要将*p1的*next指向头结点。 7、查询 查询功能分为：“按序号查询”和“按内容查询”两项。在单循环链表中，实现此功能的方法为

11、：用指针在链表中依次移动，直至所需查找的内容与所存储内容相同时为止。随后将此结构体中所存储的数据进行输出。 七、编码实现 1、创建链表 struct biao *p0,*p1,*p2; struct biao *head; printf(请输入你要存储的元素，按0结束!n); p0=p2=(struct biao*)malloc(LEN); p0-num=NULL,p0-next=p1 ; head=p0; p1=(struct biao*)malloc(LEN); scanf(%d,&p1-num); while(p1-num!=00) p2-next=p1; p2=p1; p1=(stru

12、ct biao*)malloc(LEN); scanf(%d,&p1-num); p2-next=p0; free(p1); return(head); 2、显示当前元素 struct biao *p; printf(n目前线性链表为:); p=head-next; if(p=head) printf( 空n); else do printf( %d,p-num); p=p-next; while(p!=head); printf(nnnn); 3、插入元素 struct biao *p0,*p1; int x,y,i,b; printf(n1：按位置插入 2：插入某元素的后面n); scan

13、f(%d,&b); if(b=1) printf(n请输入要插入的元素和位置); scanf(%d %d,&x,&y); p0=(struct biao*)malloc(LEN); p0-num=x; p1=head; for (i=0;inext=head) printf(输入的序号超过链表最大值，系统将自动在尾部插入); break; p1=p1-next; p0-next=p1-next; p1-next=p0; printf(插入已成功n); else if(b=2) printf(n请输入要插入的元素和被插元素); scanf(%d %d,&x,&y); p0=(struct bia

14、o*)malloc(LEN); p0-num=x; p1=head; while(p1-numnext; p0-next=p1-next; p1-next=p0; printf(插入已成功n); 4、删除元素 struct biao *p1,*p2; int i=0,x1,x8,x9; printf(n1：按位置删除 2：按内容删除); scanf(%d,&x8); if(x8=1) printf(n请输入要删除的位置); scanf(%d,&x1); p1=head; while(inext; i+; p2-next=p1-next; printf(已完成删除操作n); else if(x8

15、=2) printf(n请输入要删除的内容); scanf(%d,&x9); p1=head; while(p1-num!=x9) p2=p1; p1=p1-next; p2-next=p1-next; printf(已完成删除操作n); 5、统计元素个数 struct biao *p0,*p1,*p2; int i=0; p1=p0=head-next; while(p1-next!=p0) p2=p1; p1=p1-next; i+; printf(当前链表一共有%d个元素n,i); 6、逆转链表 struct biao *p0,*p1,*p2; int i=1; p1=head-next

16、; p0=head; while(p1!=head) p2=p1-next; p1-next=p0; p0=p1; p1=p2; p1-next=p0; printf(逆置操作已经完成n); 7、查询 struct biao *p1; int i=0,x2,x4,x5; printf(n1：按序号查询 2：按内容查询n); scanf(%d,&x2); if(x2=1) printf(n输入你要查询的序号n); scanf(%d,&x4); p1=head-next; for(i=1;inext; if(p1=head) printf(你所查询的序号超出了链表的范围n); break; pri

17、ntf(n%dn,p1-num); else if(x2=2) printf(n输入你要查询的内容n); scanf(%d,&x5); p1=head-next; i=0; while(p1-num!=x5) p1=p1-next; i+; ; printf(n你所查询的数在第%d个n,i+1); printf(nn); 8、主函数 void main struct biao *head,p0,p1,p2; int a,b; b=1; while(b) printf( 1:建立循环链表n); printf( 2:显示所有元素n); printf( 3:插入元素n); printf( 4:删除元

18、素n); printf( 5:统计元素个数n); printf( 6:逆转链表n); printf( 7:查询n); printf( 8:其余键退出n); printf(*注意*n); printf(*当程序发生错误时，键入ctrl+c退出*n); printf(请按键选择n); scanf(%d,&a); if (a=1) head=creat; else if(a=2) print(head); else if(a=3) insert(head); else if(a=4) del(head); else if(a=5) count(head); else if(a=6) revesal(

19、head); else if(a=7) inquire(head); else if(a=8) b=0; else printf(The number is illegal , please input again!n); 八、测试及分析 1、测试用例列表 在主界面下： 输入 12 预期输出 输出原界面，提示“请选择1-8” 实际输出 The number is illegal , please input again! Ctrl+C 程序发生错误时，退出界面 1 将建立新的链表，该链表将覆盖已经存在的链表 请输入元素 程序发生错误时，退出界面 将建立新的链表，该链表将覆盖已经存在的链表 请输

20、入元素 开始进入建立链表并插入元素的过程： 输入 预期输出 实际输出 2；3；4 输入过程结束 2；3；4 2；3；4 0 输入过程结束 下面执行插入元素的操作 输入 3 预期输出 实际输出 您将在链表的某一个位置插入新元素。您将在链表的某一个位置插入新元您将以何种方式找到原链表中的元素：素。您将以何种方式找到原链表中的1. 按位置插入 2. 插入某元素的后面 元素：1. 按位置插入2. 插入某元素的后面 y 输出“The number is illegal , please 输出“The number is illegal , input again!” 1 60；3 请输入要插入的元素和位

21、置： 输出“插入已成功” please input again!” 请输入要插入的元素和位置： 输出“插入已成功” 或进行： 2 3；60 请输入要插入的元素和被插元素： 输出“插入已成功” 请输入要插入的元素和被插元素： 输出“插入已成功” 为了了解是否正确插入元素，可以输出当前列表 输入 2 预期输出 输出：目前线性链表为“第一个元素是实际输出 输出：目前线性链表为“第一个元素2；第二个元素是3；第三个元素是60；是2；第二个元素是3；第三个元素是第四个元素是4” 60；第四个元素是4” 下面执行删除元素的操作 输入 4 预期输出 您将删除链表中的某一个元素您将以何种方式找到原链表中的元素

22、：1. 按位置删除2. 按内容删除 1 3 请输入要删除的位置： 已完成删除操作 实际输出 您将删除链表中的某一个元素您将以何种方式找到原链表中的元素：1. 按位置删除2. 按内容删除 请输入要删除的位置： 已完成删除操作 或进行： 2 60 请输入要删除的内容： 已完成删除操作 请输入要删除的内容： 已完成删除操作 为了了解是否正确删除元素，可以输出当前列表 输入 2 预期输出 输出：目前线性链表为“第一个元素是实际输出 输出：目前线性链表为“第一个元素2；第二个元素是3；第三个元素是4” 是2；第二个元素是3；第三个元素是4” 统计元素个数 输入 5 预期输出 输出：当前链表一共有3个元素

23、 实际输出 输出：当前链表一共有3个元素 逆转链表 下面执行逆转链表的操作 输入 6 预期输出 逆置操作已完成 实际输出 逆置操作已完成 为了了解是否正确删除元素，可以输出当前列表 输入 2 预期输出 输出：目前线性链表为“第一个元素是实际输出 输出：目前线性链表为“第一个元素4；第二个元素是3；第三个元素是2” 是4；第二个元素是3；第三个元素是2” 查询 输入 3 预期输出 您将查找链表中的某一个元素。您将以何种方式找到原链表中的元素：1. 按序号查找2. 按内容查找 y 实际输出 您将查找链表中的某一个元素。您将以何种方式找到原链表中的元素：1. 按序号查找2. 按内容查找 输出“The

24、 number is illegal , please 输出“The number is illegal , input again!” please input again!” 重新选择7执行到此过程： 输入 1 5 预期输出 请输入要查找元素的序号： 你所查询的序号超出了链表的范围 实际输出 请输入要查找元素的序号： 你所查询的序号超出了链表的范围 回到此过程的上一步： 输入 1 2 预期输出 请输入要查找元素的序号： 3 实际输出 请输入要查找元素的序号： 3 重新选择7执行此过程： 输入 2 9 预期输出 请输入要查找元素的内容： 实际输出 请输入要查找元素的内容： 输出“The nu

25、mber is illegal , please 输出“The number is illegal , input again!” please input again!” 回到此过程的上一步， 输入 2 3 预期输出 请输入要查找元素的内容： 你说查询的数在第2个 实际输出 请输入要查找元素的内容： 你说查询的数在第2个 最后输入0，正确退出了程序。 2、出现的错误，解决方法与回归测试 由于程序主函数声明的变量为int型，所以当输入字符变量时，程序会出现错误，出现跑飞的现象。这是由于考虑问题不全面的结果。解决的办法是提前声明输入char型字符变量时，所进行的算法。 语法错误。有的通过程序的编

26、译可以直接帮助检查出来，比如有时少定义了一个变量，少写了一个分号。但有的错误，主要原因如漏了大括号，这主要是通过好的编程风格使用缩进来帮助检查避免，还有的则需要自己逐行看，如大括号打成了中括号。 还有一些错误是因为自己对于算法考虑的不够周全。例如如何计数整个链表的长度。一开始定义在个别函数中，参数传递较为复杂，且出现错误。后来定义了一个全局变量，问题迎刃而解。 程序的健状性不够。当错误输入之后，会出现程序跑飞等情况。也是通过反复检测，并用软件设计的思想指导自己，把总体设计和具体的模块设计做到位。 九、实验总结 通过此次实验，我进一步熟悉了循环链表操作的有关知识，对书本上的知识又有了更进一步的认

27、识。另一方面，通过编写程序也让我对C语言课程中学习到的有关知识进行了一次复习。由于在大一时对C语言的学习并不太好，尤其对结构体指针的理解并深，所以在编写程序的初期遇到了一些困难。为了解决问题，我又对C语言的相关章节进行了复习，在复习的过程中加深了对结构体、指针、字符数组、字符串函数、for循环、while循环、函数的理解。并以此作为指导程序编写的知识储备。 通过回忆老师上课所教授的知识，尤其是对于软件工程部分的讲授，更使我对此次实验程序的编写有了整体构架上的认识。对老师上课讲的需求分析、总体设计的重要性也有了更深的理解。通过实验我意识到：原来编写程序时刚开始思路总是很混乱，说到底，就是因为这些方面做得不够。在这次实验中，我推迟了编码实现的过程，但事实证明，这样反而会为编码节省大量时间。先理清思路，再进行程序的编写反而使编程的效率大大提高。在进行有关于的测试时，我按老师所讲，进行了较为全面的覆盖。同时，为了避免遗漏，我还请同学帮助我进行测试，果然发现了很多我之前未发现的问题。从而使编写的程序更为完善。 通过实验，我发现自己对知识的理解还存在许多遗漏，思维的严谨性和完善性仍旧有待提高。在下一阶段的学习中，我一定会针对自身存在的缺点与不足进行查缺补漏，以便能够更好地学好这门课。