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

《数据结构课程设计-链表操作》由会员分享，可在线阅读，更多相关《数据结构课程设计-链表操作（16页珍藏版）》请在毕设资料网上搜索。

1、 目录 1 选题背景 1 2 方案与论证 1 2.1 链表的概念和作用 1 2.2 实验的基本要求（软硬件） 1 2.3 算法的设计思想 . 1 2.4 相关图例 2 2.4.1 单链表的结点结构. 2 2.4.2 算法流程图. 2 3 过程论述 3 3.1 链表的建立 3 3.2 取出链表中的元素 4 3.3 插入元素 4 3.4 删除元素 5 3.5 查找元素 6 4 结果分析 6 4.1 单链表的结构 6 4.2 单链表 6 4.2.1 顺链操作技术. 6 4.2.2 指针保留技术. 7 5 结论与总结 7 参考文献 8 附录代码： 9 数据结构课程设计 1 1 选题背景 陈火旺院士把计

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

3、念和作用 链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用 的动态存储方法。为了克服顺序表的缺陷，可以采用链式方式存储线性表。通常 将采用链式存储结构的线性表称为线性链表。单链表的结构包括数据域和指针 域，这两部分总称为结点（Node） 。单链表中每个结点的存储地址放在其前驱结 点的指针域中，由于线性表中的第一个结点无前驱，所以应设一个头指针 H 指向 第一个结点。由于线性表的最后一个节点没有直接后继，则制定单链表的最后一 个结点的指针域为空（NULL） 。它可以和随意的在其任意一个位置进行插入和删 除操作，这对于动态的数据处理十分的有利。利用头插建立一个带头结点的单链 表，

4、并用算法实现该单链表的插入、删除查找、输出、求前驱和后继、再把此单 链表逆置，然后在屏幕上显示每次操作的结果当所有操作完成后能撤销该单链 表。 2.2 实验的基本要求（软硬件） 用 VC+6.0 软件平台，操作系统：Windows XP 硬件：内存要求：内存大小 在 256MB，其他配置一般就行。 2.3 算法的设计思想 （1）定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函 数应用做好准备。 （2）定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用， 在这一步通过调用输出链表的函数算法来实现对链表的输出操作。 链表操作 2 （3）定义一个遍历查找的算法，通过此算法

5、可以查找到链表中的每一个节点是 否存在。 （4）定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实 现对链表的前驱和后继的查找工作。 （5）定义插入节点的算法，通过定义这个算法，并结合这查找前驱和后继的算 法便可以在连链表的任意位置进行插入一个新节点。 （6）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作。 2.4 相关图例 2.4.1 单链表的结点结构 如图 2-1 所示,为单链表的结点结构示意图： 图 2-1 单链表的结点结构 2.4.2 算法流程图 如图 2-2 所示，为此算法流程图： 图 2-2 算法流程图 Data 域 Next 域 定义结构体 node

6、 构建各种对联表操作的函数 （插入、 删除、 查找、输出） ，并写出相应的算法及实现 过程 创建一个单链表，用于之前所定义的函数 对其进行操作 按要求输出结果 结束 数据结构课程设计 3 3 过程论述 3.1 链表的建立 图 3-1 链表的建立 图 3-2 建立链表并打印链表中的元素 链表操作 4 3.2 取出链表中的元素 图 3-3 取出链表中的元素 3.3 插入元素 图 3-4 插入元素 数据结构课程设计 5 3.4 删除元素 图 3-5 删除元素 图 3-6 删除元素后打印链表 链表操作 6 3.5 查找元素 图 3-7 查找位置为 6 的元素 4 结果分析 4.1 单链表的结构 一般情况下，使用链表，只关心链表中结点间的逻辑顺序，并不关心每个结 点的实际存储位置，因此通常情况下用箭头来表示链域中的指针，于是链表就可 以更直观的画成用箭头链接起来的结点序列，如下图所示： H 图 4-1 单链表的示例图 4.2 单链表 4.2.1 顺链操作技术 从“头”开始，访问单链表 L 中的结点 i（p 指向该节点）时，由于第 i 个 结点的地址在第