实验二线性链表的建立与应用

辽宁石油化工大学计算机与通信工程学院实验报告 实验二 线性链表的建立与应用 第 1 页 实验二 线性链表的建立与应用 一 实验目的： 了解并掌握线性表在采取链式存储时的逻辑关系与物理存储关系的特点和计算特性，掌握线性链表的各种运算方法。 二 实验内容： 实现单向链表的初始化、查找、删除、添加、排序、查找、合并、逆转、复制等操作。要求程序能够循环执行 三 实验原理： 关于单链表 链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”，存放数据元素信息的称为数据域，存放其后继地址的称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。 单链表上基本运算的实现 线性链表的创建：创建过程实际上是链表结点的申请和连接的过程。向系统申请内存单元，输入用户数据，将结点加入到链表中，连接前后件，明确关系后添加下一个结点。 线性链表的删除：选定要删除的结点，将该结点前件的指针域数据修改为后件的物理地址值，释放该节点占用的内存空间。 线性链表的查找：给定查找条件，从链表头开始，顺延向后查找，当找到符合条件的结点时，返回该结点的地址值。 线性链表的编辑：给定查找条件，查找到符合条件的结点后，修改相应的用户数据，但不能改变该结点的指针值。 线性链表的排序：按照指定的用户数据用指定的的排序要求（升序或降序）对链表的逻辑结构进行重组，重组的过程中，只改变逻辑结构，而不是物理结构， 单链表结点结构 data nex t a1 an ∧ H … a2 链表示意图 辽宁石油化工大学计算机与通信工程学院实验报告 实验二 线性链表的建立与应用 第2 页 也不改变结点的数据。 线性链表的合并：将一个链表的头结点连接到另一个链表的为结点后作为其后件。 线性链表的逆转：将链表按照顺序反转，即尾结点变为头结点，头结点变为尾结点。 四 实验步骤 1 进入Turbo C2.0，新建一个文件。 2 输入程序，程序要求使用子函数进行组织。 3 将源程序保存到指定文件夹“D:\学生姓名”。 4 按F9调试，纠正语法错误。 5按Ctrl＋F9运行，调试逻辑错误。 6 按Alt＋F5查看结果。 五、实验中应注意的问...