循环链表实验课程报告

《循环链表实验课程报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、个数据元素的存储序号（既存储结点的地址），即指向后件结点，称为指针域。线性链表中，用一个专门的指针指向线性链表中第一个数据元素的结点（即存放线性链表中第一个元素的存储结点的序号）。线性表中最后一个元素没有后件，最后一个结点的指针域为空，表示链表终止。循环链表是为克服线性链表的不足采用的另一种链接方式。循环链表增加了一个表头结点，其指针域指向第一个元素的结点，头指针指向表头结点，循环链表的最后一个结点的指针域不为空，而是指向头结点。四、需求说明1、功能分析(1)创建链表在内存中创建一个链式存储的循环线性

3、表。每当创建一个新的链表后，会提示用户是否输入新的元素，同时能够自动生成每一元素对应的序号以及整个链表的长度。(2)按序号查找链表中的某一元素链表中的元素按序号进行排列。当输入某一要查找的序号后，首先判断输入的序号是否在当前的链表中，如果不在，输出提示信息。如果在从链表的头依次查找直到找到此序号，输出此序号的元素所有的信息。(3)按内容查找链表中的某一元素输入元素的内容，从链表的头依次查找到尾，如果找到对应此内容的元素，则输出此元素对应的信息(序号、内容等)。如果没有找到此元素，则输出提示信息。(4)

4、插入元素此功能要求能在链表中任一元素之后插入新的元素。因此首先也要找到原链表中的某一元素，要求与(2)(3)相同。找到原链表中的元素后，输入新的元素内容，然后将此元素插入到原链表中。插入之后原链表中各元素的序号以及整个链表的长度能够随之自动更新。(5)删除元素与插入元素类似。首先能够找到原链表中要删除的元素，要求与(2)(3)同。找到原链表中的元素后，将此元素删除。删除之后，原链表中各元素的序号以及整个链表的长度能够随之自动更新。(1)输出链表能够将当前链表中所有元素的内容和序号按顺序输出。(2)逆置

5、链表能够将原链表中的各个元素逆置输出。2、其它分析(1)界面要美观友好，便于人机交互，通过用户的输入来执行相应的功能；(2)执行完某一特定功能后能返回主菜单，继续由用户选择相应的功能；(3)在主菜单内用户可以选择退出，其他情况下，程序都不会跑飞；(4)本程序需耍首先建立链表，在没有建立链表的情况下耍能给出提示信息。(5)软硬件环境：在WindowXP或者WindowsVista环境下，在安装MicrosoftVisualC++6.0的计算机上五、总体设计(1)数据结构设计建立一个单循环链表，采用结构体

6、的形式，每一个结构中包括三个部分：元素的内容，元素的序号、指向结构体中下一个元素的指针。①定义结构体类型：structbiaointx,y,num,xl,x2;struetbiao*next;};②创建结点与释放利用pl二(structbiao*)malloc(LEN)开辟空间利用free(pl)对结点空间进行释放③创建空循环链表先开辟一个节点pOpO->num=NULL,pO-〉next二pl;head二pO;⑵软件总体结构设计程序包括以下儿个函数：主函数、界而显示以及菜单选择函数、创建链表的函数、

7、查找某一元素的函数、按序号查找某一元素的函数、按内容查找某一元素的函数、插入某一元素的函数、删除某一元素的函数、正序输岀所有链表各元素的函数、逆置链表的函数。其中主函数调用界面显示以及菜单选择函数，根据用户的按键判断选择执行相应的功能，调用相应的功能函数。各个功能函数中，查找某一元素的函数调用两个函数，分别为按序号查找某一元素的函数和按内容查找某一元素的函数。而在插入某一元素的函数和删除某一元素的函数中也都需要调用查找某一元素的函数。⑶算法设计及效率分析本程序中的操作都是基于单项循环链表，主要算法设计

8、也是体现在对循环链表的操作中。链式结构的优点在于可以动态地分配空间,动态地增加或删减链表的长度，同时作为链表结构，每个节点都有数据域和指针域，指针域指向其后件结点，这两点为链表的操作提供了很大的方便。而作为循环链表，增加了表头结点，这又使得对空链表的操作对非空链表的操作保持了一致性，免除了对表头结点和表尾结点的特殊处理。⑷主程序流程设计⑸界面设计(屏幕截图)六、详细设计1、创建链表首先在内存中创建一个链式存储的循环线性表，建立存储空间。而后将输入的内容赋