数据结构课程设计-单链表.doc

《数据结构课程设计-单链表.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录1选题背景22方案与论证32.1链表的概念和作用32.3算法的设计思想42.4相关图例52.4.1单链表的结点结构52.4.2算法流程图53实验结果63.1链表的建立63.2单链表的插入63.3单链表的输出73.4查找元素73.5单链表的删除83.6显示链表中的元素个数（计数）94结果分析104.1单链表的结构104.2单链表的操作特点104.2.1顺链操作技术104.2.2指针保留技术104.3链表处理中的相关技术105设计体会及今后的改进意见11参考文献12附录代码：131选题背景陈火旺院士把计算机60多年的发展成

2、就概括为五个“一”：开辟一个新时代----信息时代，形成一个新产业----信息产业，产生一个新科学----计算机科学与技术，开创一种新的科研方法----计算方法，开辟一种新文化----计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究

3、的基础。2方案与论证2.1链表的概念和作用链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象)+ 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表）单链表是链式存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。因此，查找第i个数据元素的基本操作为：移动指针，比较j和i单链表1、链接存储方法链接方式存储的线性表简称为链表（Link

4、edList）。链表的具体存储表示为：①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2、链表的结点结构┌───┬───┐│data│next│└───┴───┘data域--存放结点值的数据域nex

5、t域--存放结点的直接后继的地址（位置）的指针域（链域）注意：①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。②每个结点只有一个链域的链表称为单链表（SingleLinkedList）。3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。注意：链表由头指针唯一确定，单链表可以用头指针的名字来命名。终端结点无后继，故终端结点的指针域为空，即NULL。2.2实验的基本要求（软硬件）用VC++6.0软件平台，操作

6、系统：WindowsXP硬件：内存要求：内存大小在256MB，其他配置一般就行。2.3算法的设计思想（a）定义一个创建链表的函数，通过该头插法创建一个带头结点的链表，在接下来的链表操作中使用。（b）定义输出链表的算法，遍历结点的指针域判断是否为空，如果不为空则输出其数据域，直到指针域为空为止。（c）定义一个遍历查找的算法，通过遍历的数据域，分别与要查询的元素进行比较，如果查找到则返回并输出，如入查找失败则返回错误提示信息。（d）定义插入结点的算法，首先查找指针域为空的结点，并申请空间插入在结点的后边，并且将其指针域置空。（

7、e）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作，其关键在于前驱结点的保留，查找到需删除的结点，将其删除，并将其后继结点连到其前驱结点。2.4相关图例2.4.1单链表的结点结构如图2-1所示,为单链表的结点结构示意图：Data域Next域图2-1单链表的结点结构2.4.2算法流程图如图2-2所示，为此算法流程图：开始定义结构体Node构建各种对链表操作的函数（插入、删除、查找、输出），并写出相应的算法及实现过程创建一个单链表，用于之前所定义的函数对其进行操作按要求输出结果结束图2-2算法流程图3实验结果3

8、.1链表的建立图3-1链表的建立3.2单链表的插入图3-2单链表的插入3.3单链表的输出图3-3输出单链表元素3.4查找元素图3-4查找成功图3-5查找失败3.5单链表的删除图3-6删除成功图3-6删除失败3.6显示链表中的元素个数（计数）图3-7输出长度4结果分析4.1单链表的结构一般情况下，使用链表