1、1 一、课程设计题目： 实现两个链表的合并 二、基本功能要求： 1. 建立两个链表 A 和 B，链表元素个数分别为 m 和 n 个。 2. 假设元素分别为(x1,x2,xm)，和(y1,y2, yn)。把它们合并成一个线性表 C，使 得： 当 m=n 时，C=x1,y1,x2,y2,xn,yn,xm 当 nm 时，C=y1,x1,y2,x2,ym,xm,yn 3. 输出线性表 C：用直接插入排序法对 C 进行升序排序，生成链表 D，并输出链表 D。 三、测试数据： 1. A 表（30，41，15，12，56，80） B 表（23，56，78，23，12，33，79，90，55） 2. A 表（
2、30，41，15，12，56，80，23，12，34） B 表（23，56，78，23，12） 四、理论分析结果： 1. A 表的数据元素个数 m=6，B 表的数据元素个数 n=9，此时 m=n 时，应该先插入 A 表中的数据元素，在偶数位插入 A 表中 的数据元素，在奇数位插入 B 表中的数据元素，最后插入 A 表中剩余的数据元素。 C=30，23，41，56，15，78，12，23，56，12，80，23，12， 34 排序结果： D=12，12，12，15，23，23，23，30，34，41，56，56，78，80 2 五、设计步骤： 5.1 分析问题，给出数学模型，设计相应的数据结构：
3、 1) 分析问题特点，用数学表达式或其它形式描述其数学模型。 2) 选择能够体现问题本身特点的一种或几种逻辑结构。 3) 依据逻辑结构和问题特点，设计并选择相应的存储结构（顺序存储结构和链式存储 结构对应的算法实现有区别） 。 5.2 算法设计 ： 1) 确定所需模块：对于复杂的程序设计，要充分利用模块化程序设计方法和面向对象 思想，自顶向下，逐步细化。 2) 各子模块功能描述：给出主要模块的算法描述，用流程图或伪代码表示。 3) 模块之间的调用关系：给出算法各模块之间的关系图示。 5.3 上机实现程序： 为提高工作效率，充分利用上机调试时间，在上机之前应列出程序清单。 5.4 有代表性的各种
4、测试数据去验证算法及程序的正确性： 根据课程设计的要求对给定的数据进行测试，验证算法以及程序的正确性。 5.5 算法分析及优化： 经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中 给出的问题后，分析算法的时间复杂度和空间复杂度，如有可能对程序进行优化改进。 六、模块划分： 1.单链表头文件：LinList.h 主要包括单链表的存储结构、初始化、求数据元素个数、插入、删除数据元素、 取数据元素、撤消单链表的函数。 2. 单链表操作头文件：MyList.h 主要包括单链表测试、单链表合并、单链表合并排序函数。 3.测试主函数文件：TestLinList.h 主要包括文件包含、数据导入和操作模块程序。 3 七、算法设计： 7.1 带头结点的单链表存储结构 typedef struct Node DataType data; struct Node *next; SLNode; 7.2 单链表的初始化 void ListInitiate(SLNode *head) /*如果有内存空间，申请头结点空间并使头指针 head
