1、 届课程设计 两个链表的交叉合并两个链表的交叉合并 课程设计论文课程设计论文 学生姓名 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机 指导教师 教师职称 讲师 第 1 页 共 16 页 目目 录录 前言前言 2 2 1.11.1 设计背景设计背景 2 2 1.1.11.1.1 数据结构简介数据结构简介 2 2 1.1.21.1.2 算法选择的原因算法选择的原因 2 2 1.21.2 设计的原理和内容设计的原理和内容 2 2 正文正文 2 2 2.12.1 课程设计目的课程设计目的 2 2 2.22.2 课程设计题目课程设计题目 3 3 2.2.12.2.1 问题定义
2、问题定义 3 3 2.2.22.2.2 需求分析需求分析 3 3 2.32.3 总体方案总体方案 3 3 2.42.4 运行环境运行环境 3 3 2.52.5 设计流程图设计流程图 4 4 2.62.6 设计思路设计思路 4 4 2 2.6.1.1.6.1.1 线性表的单链表结构线性表的单链表结构 4 4 2.6.1.22.6.1.2 实现两个链表的简单合并算法实现两个链表的简单合并算法 5 5 2.6.1.32.6.1.3 把元素插入到链表当中把元素插入到链表当中 5 5 2.6.1.42.6.1.4 将元素从链表中删除将元素从链表中删除 6 6 2.6.22.6.2 链表的合并链表的合并
3、6 6 2.6.32.6.3 链表的排序链表的排序 7 7 2.6.42.6.4 算法模块设计算法模块设计 8 8 2.72.7 程序运行分析程序运行分析 1111 参考文献参考文献 1212 附录附录 1313 第 2 页 共 16 页 前言前言 1.1 设计背景 1.1.1 数据结构简介 数据结构是计算机程序设计的重要理论设计基础， 它不仅是计算机学科的核心课 程， 而 且成为其他理工专业的热门选修课。 数据结构是计算机存储、 组织数据的方式。 通 常情况下， 精心选择的数据结构可以带来更高的运行或者存储效率的算法。 比如在计算机 中央处理器中，CPU 接到一个中断请求便会停下当前正在执行
4、的指令去 处理这个中断请求 完成中断操作， 首先要做的就是保护现场。 保护现场需要将下一条指令的 地址指针和当前 指令返回地址等重要的数据进行存储。 在众多的数据结构中， 这些重要的数 据被存储到栈 这个数据结构中。 1.1.2 算法选择的原因 在许多类型的程序的设计中， 数据结构的选择是一个基本的设计考虑因素。 许多大型 系 统的构造经验表明， 系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了 最优 的数据结构。 许多时候， 确定了数据结构后， 算法就容易得到了。 有些时候事情也 会反过来， 我们根据特定算法来选择数据结构与之适应。 不论哪种情况， 选择合适的数据 结构都是非常 重
5、要的。 1.2 设计的原理和内容 本次程序设计采用 C 语作为描述和实现算法的程序语言，主要的设计思路就是完成 对 链表的操作，如链表的插入、删除、取链表顶等等，这些操作都是通过 C 语言程序来实 现的。最 后的结果就是运行程序时能够完成对以上设计的操作。 正文正文 链表是一种物理存储单元上非连续、 非顺序的存储结构， 数据元素的逻辑顺序是通过链 表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点 可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是 存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。 2.
6、1 课程设计目的 课程设计为学生提供了一个既动手又动脑， 独立实践的机会将课本上的理论知识和实际 第 3 页 共 16 页 有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能 力。 2.2 课程设计题目 实现两个链表的交叉合并。 要求： （1）输入两个链表。 （2）输出两个链表合并后的链表。 2.2.1 问题定义 实现对两个的链表的交叉合并，输出线形表 C 用直接插入排序法对 C 进行升序排序， 生成链表 D，并输出链表 D。 2.2.2 需求分析 链表是线性表的链式表示， 由于它不要求逻辑上相邻的元素在物理上相邻， 所以它没有 不需要像顺序存储结构在插入，删除元素时移动大量的元素，只修改指针节点，并修改这些 节点的指针域，查找过程中需平均一定指针域为表长的一半，而采用顺序结构存储线性表， 插入和删除元素操作需要平均移动表彰的一半元素。 移动指针
