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

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

ID:26166621

大小:215.50 KB

页数:15页

时间:2018-11-25

实现两个链表的合并 数据结构课程设计_第1页
实现两个链表的合并 数据结构课程设计_第2页
实现两个链表的合并 数据结构课程设计_第3页
实现两个链表的合并 数据结构课程设计_第4页
实现两个链表的合并 数据结构课程设计_第5页
资源描述:

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

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,12,56

2、,80,23,12,34)B表(23,56,78,23,12)四、理论分析结果:1.A表的数据元素个数m=6,B表的数据元素个数n=9,此时mn分析合并结果:当m

3、>=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;structNode*next;}SLNode;7.2单链表的初

6、始化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(p->next!=NULL)/*循环计数*/{p=p->next;siz

7、e++;}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)exit(1);q->data=x;q->next=p->next;p->next=q;

8、return1;}//注

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。