数据结构课程设计-链表操作

《数据结构课程设计-链表操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录1选题背景12方案与论证12.1链表的概念和作用12.2实验的基本要求（软硬件）12.3算法的设计思想12.4相关图例22.4.1单链表的结点结构22.4.2算法流程图23过程论述33.1链表的建立33.2取出链表中的元素43.3插入元素43.4删除元素53.5查找元素64结果分析64.1单链表的结构64.2单链表64.2.1顺链操作技术64.2.2指针保留技术75结论与总结7参考文献8附录代码：9数据结构课程设计1选题背景陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代----信息时代，形成一个新产业----信息产业，产生一个新科学----计算机科学与技术，开

2、创一种新的科研方法----计算方法，开辟一种新文化----计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。2方案与论证2.1链表的概念和作用链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。为了克服顺序表的缺陷，可以采用链式方式存储线性表。通常将采用链式存

3、储结构的线性表称为线性链表。单链表的结构包括数据域和指针域，这两部分总称为结点（Node）。单链表中每个结点的存储地址放在其前驱结点的指针域中，由于线性表中的第一个结点无前驱，所以应设一个头指针H指向第一个结点。由于线性表的最后一个节点没有直接后继，则制定单链表的最后一个结点的指针域为空（NULL）。它可以和随意的在其任意一个位置进行插入和删除操作，这对于动态的数据处理十分的有利。利用头插建立一个带头结点的单链表，并用算法实现该单链表的插入、删除查找、输出、求前驱和后继、再把此单链表逆置，然后在屏幕上显示每次操作的结果当所有操作完成后能撤销该单链表。2.2实验的基本要求（软硬件）用VC

4、++6.0软件平台，操作系统：WindowsXP硬件：内存要求：内存大小在256MB，其他配置一般就行。2.3算法的设计思想（1）定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备。（2）定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步通过调用输出链表的函数算法来实现对链表的输出操作。（3）13数据结构课程设计定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个节点是否存在。（4）定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实现对链表的前驱和后继的查找工作。（5）定义插入节点的算法，通过定义这个算法，并结合这查

5、找前驱和后继的算法便可以在连链表的任意位置进行插入一个新节点。（6）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作。2.4相关图例2.4.1单链表的结点结构如图2-1所示,为单链表的结点结构示意图：Data域Next域图2-1单链表的结点结构2.4.2算法流程图如图2-2所示，为此算法流程图：定义结构体node构建各种对联表操作的函数（插入、删除、查找、输出），并写出相应的算法及实现过程创建一个单链表，用于之前所定义的函数对其进行操作按要求输出结果结束图2-2算法流程图13数据结构课程设计3过程论述3.1链表的建立图3-1链表的建立图3-2建立链表并打印链表中的元素13

6、数据结构课程设计3.2取出链表中的元素图3-3取出链表中的元素3.3插入元素图3-4插入元素13数据结构课程设计3.4删除元素图3-5删除元素图3-6删除元素后打印链表13数据结构课程设计3.5查找元素图3-7查找位置为6的元素4结果分析4.1单链表的结构一般情况下，使用链表，只关心链表中结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此通常情况下用箭头来表示链域中的指针，于是链表就可以更直观的画成用箭头链接起来的结点序列，如下图所示：ABCDE^H图4-1单链表的示例图4.2单链表4.2.1顺链操作技术从“头”开始，访问单链表L中的结点i（p指向该节点）时，由于第i个结点的地址在

7、第i-1个结点（pre指向该结点，为p的前驱）的指针域中存放，查找必须从单链表的“首结点”开始（p=L）；通过p=p->next并辅助计数器来实现。13数据结构课程设计4.2.2指针保留技术通过对第i个结点进行插入、删除等操作时，需要对第i-1个结点的指针域进行链址操作（pre->next），因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系，将这种技术称为“指针保留技术”。5结论与总结通过这十几天的时间，最后终于完成了这次数据结构