实现两个链表的合并 数据结构课程设计

《实现两个链表的合并 数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、课程设计题目：实现两个链表的合并二、基本功能要求：1.建立两个链表A和B，链表元素个数分别为m和n个。2.假设元素分别为(x1,x2,…xm)，和(y1,y2,…yn)。把它们合并成一个线性表C，使得：当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn3.输出线性表C：用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。三、测试数据：1.A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）2.A表（30，41，15

2、，12，56，80，23，12，34）B表（23，56，78，23，12）四、理论分析结果：1.A表的数据元素个数m=6，B表的数据元素个数n=9，此时m

3、m>n分析合并结果：当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，8015五、设计步骤：5.1分析问题，给出数学模型，设计相应的数据结构：1)分析问题特点，用数学表达式或其它形式描述其数学模型。2)选择能够体现问题本身特点的一种或几种逻辑结构。3)依据逻辑结构和问题特点，设计并选择相应的存储

4、结构（顺序存储结构和链式存储结构对应的算法实现有区别）。5.2算法设计：1)确定所需模块：对于复杂的程序设计，要充分利用模块化程序设计方法和面向对象思想，自顶向下，逐步细化。2)各子模块功能描述：给出主要模块的算法描述，用流程图或伪代码表示。3)模块之间的调用关系：给出算法各模块之间的关系图示。5.3上机实现程序：为提高工作效率，充分利用上机调试时间，在上机之前应列出程序清单。5.4有代表性的各种测试数据去验证算法及程序的正确性：根据课程设计的要求对给定的数据进行测试，验证算法以及程序的正确性。5.5算法分析及优化：经过上机调试，源程序运行正确，并且

5、实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度，如有可能对程序进行优化改进。六、模块划分：1.单链表头文件：LinList.h主要包括单链表的存储结构、初始化、求数据元素个数、插入、删除数据元素、取数据元素、撤消单链表的函数。2.单链表操作头文件：MyList.h主要包括单链表测试、单链表合并、单链表合并排序函数。3.测试主函数文件：TestLinList.h主要包括文件包含、数据导入和操作模块程序。15七、算法设计：7.1带头结点的单链表存储结构typedefstructNode{DataTypedata;st

6、ructNode*next;}SLNode;7.2单链表的初始化voidListInitiate(SLNode**head){/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);(*head)->next=NULL;/*尾标记NULL*/}7.3求单链表中的数据元素个数intListLength(SLNode*head){SLNode*p=head;/*p指向头结点*/intsize=0;/*size初始为0*/while(

7、p->next!=NULL)/*循环计数*/{p=p->next;size++;}returnsize;}7.4向单链表中插入数据元素intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1;15while(p->next!=NULL&&jnext;j++;}if(j!=i-1){printf("Eorror:插入位置参数错!");return0;}if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)ex

8、it(1);q->data=x;q->next=p->next;p->next=q;return1;}//注