已阅读5页,还剩10页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
一、课程设计题目:实现两个链表的合并二、基本功能要求: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,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,80,23,12,34) B表(23,56,78,23,12) 四、理论分析结果:1. A表的数据元素个数m=6,B表的数据元素个数 n=9,此时mn 分析合并结果:当mn分析合并结果:当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五、设计步骤:5.1 分析问题,给出数学模型,设计相应的数据结构:1) 分析问题特点,用数学表达式或其它形式描述其数学模型。 2) 选择能够体现问题本身特点的一种或几种逻辑结构。 3) 依据逻辑结构和问题特点,设计并选择相应的存储结构(顺序存储结构和链式存储结构对应的算法实现有区别)。 5.2 算法设计 :1) 确定所需模块:对于复杂的程序设计,要充分利用模块化程序设计方法和面向对象思想,自顶向下,逐步细化。 2) 各子模块功能描述:给出主要模块的算法描述,用流程图或伪代码表示。3) 模块之间的调用关系:给出算法各模块之间的关系图示。 5.3 上机实现程序:为提高工作效率,充分利用上机调试时间,在上机之前应列出程序清单。5.4 有代表性的各种测试数据去验证算法及程序的正确性: 根据课程设计的要求对给定的数据进行测试,验证算法以及程序的正确性。5.5 算法分析及优化:经过上机调试,源程序运行正确,并且实现算法要求的功能,解决课程设计题目中给出的问题后,分析算法的时间复杂度和空间复杂度,如有可能对程序进行优化改进。六、模块划分:1. 单链表头文件:LinList.h主要包括单链表的存储结构、初始化、求数据元素个数、插入、删除数据元素、取数据元素、撤消单链表的函数。2. 单链表操作头文件:MyList.h主要包括单链表测试、单链表合并、单链表合并排序函数。3.测试主函数文件:TestLinList.h主要包括文件包含、数据导入和操作模块程序。七、算法设计:7.1 带头结点的单链表存储结构typedef struct Node DataType data;struct Node *next;SLNode;7.2 单链表的初始化void ListInitiate(SLNode *head)/*如果有内存空间,申请头结点空间并使头指针head指向头结点*/if(*head = (SLNode *)malloc(sizeof(SLNode)=NULL) exit(1);(*head)-next = NULL;/*尾标记NULL */7.3 求单链表中的数据元素个数int ListLength(SLNode *head)SLNode *p = head; /*p指向头结点*/int size = 0; /*size初始为0*/while(p-next != NULL) /*循环计数*/p = p-next;size +;return size;7.4 向单链表中插入数据元素int ListInsert(SLNode *head,int i,DataType x)SLNode *p, *q; int j; p = head;j = -1;while(p-next!=NULL & jnext; j+;if(j != i - 1)printf(Eorror: 插入位置参数错!n);return 0; if(q = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);q-data = x;q-next = p-next;p-next = q;return 1; /注:此单链表是带头结点的7.5 从单链表中删除数据元素int ListDelete(SLNode *head,int i,DataType *x)SLNode *p, *s;int j;p=head;j = -1;while(p-next != NULL & p-next-next!=NULL & jnext;j+;if(j!=i-1)printf(Eorror: 删除位置参数错!n);return 0;s = p-next; *x=s-data; p-next = p-next-next;free(s); return 1;7.6 从单链表中取数据元素ListGet(SLNode *head,int i,DataType *x)SLNode *p;int j;p=head;j=-1;while(p-next!=NULL & jnext;j+;if(j!=i)printf(Eorror: 取数据元素位置参数出错!n);return 0;*x=p-data;return 1;7.7 撤消单链表void Destroy(SLNode *head)SLNode *p,*p1;p=*head;while(p!=NULL)p1=p;p=p-next;free(p1);*head=NULL;7.8 单链表测试函数void SingleList(int a,int al)int i,x;SLNode *head;ListInitiate(&head);/向单链表插入数据元素for(i=0;ial;i+)if(ListInsert(head,i,ai) = 0) printf(Error:插入数据元素错误! n);return; /从单链表取数据元素printf(结果:);for(i=0; iListLength(head); i+)if(ListGet(head,i,&x) = 0) printf(Error:取数据元素错误! n);return; else printf(%d , x);printf(n);Destroy(&head);/撤消单链表printf(n);7.9 单链表合并函数void CombineList(int a,int b,int al,int bl)int i,j=0,x;int *list;SLNode *head;list=(int *)malloc(al+bl)*sizeof(int);if(albl)/a数组的数据元素个数 b数组的数据元素个数/较长数组的数据元素赋给动态数组的偶数位for(i=0;i2*al;i+=2)if(i%2=0)listi=bj;j+;j=0;/恢复公共下标初始值/较短数组的数据元素赋给动态数组的奇数位for(i=0;i2*al;i+)if(i%2=1)listi=aj;j+;/较长数组剩余数据元素赋值for(i=2*al;i= b数组的数据元素个数/较长数组b的数据元素赋给动态数组的偶数位for(i=0;i2*bl;i+=2)if(i%2=0)listi=aj;j+;j=0;/恢复公共下标初始值/较短数组a的数据元素赋给动态数组的奇数位for(i=0;i2*bl;i+)if(i%2=1)listi=bj;j+;/较长数组a剩余数据元素赋值for(i=2*bl;ial+bl;i+)listi=aj;j+;ListInitiate(&head);/向单链表插入数据元素for(i=0;ial+bl;i+)if(ListInsert(head,i,listi) = 0) printf(Error:插入A的数据元素错误! n);free(list);/从单链表取数据元素for(i=0;iListLength(head);i+)if(ListGet(head,i,&x) = 0) printf(Error:取数据元素错误! n);return; else printf(%d , x);printf(n);Destroy(&head);/撤消单链表7.10 直接插入法排序for(i=0;i-1 & templistj)listj+1=listj;j-;listj+1=temp;/直接插入法对数组list排序7.11 操作模块设计printf(*数据结构单链表合并测试实验*n);printf(* 1. 测试单链表A *n);printf(* 2. 测试单链表B *n);printf(* 3. 合并单链表A、B得到单链表C *n);printf(* 4. 对单链表C升序排序得到单链表D *n);printf(* 0. 退出合并单链表的测试程序 *n);printf(*数据结构单链表合并测试实验*n); while(flag=1)printf(输入功能号码:);scanf(%d,&flag);switch(flag)case 1:printf(测试单链表An);SingleList(&a,al);flag=1;/功能循环标志break;case 2:printf(测试单链表Bn);SingleList(&b,bl);flag=1;/功能循环标志break;case 3:printf(测试单链表A、B的合并n);CombineList(&a,&b,al,bl);flag=1;/功能循环标志break;case 4:printf(测试单链表C的排序n);SortList(&a,&b,al,bl);flag=1;/功能循环标志break;case 0:printf(Message:欢迎下次再次测试单链表合并程序!n);break;/flag!=0退出程序标志default:printf(Error:功能号码选择错误,请重新选择!n);flag=1;/功能循环标志break;八、测试程序运行结果:8.1 测试第1组数据(1)单链表测试:测试目的:测试单链表是否能够进行插入、读取等操作。测试结果:单链表A=30,41,15,12,56,80单链表B=23,56,78,23,12,33,79,90,55(2)单链表合并测试:测试目的:测试两个单链表是否能够按照要求进行合并测试结果:单链表C=23,30,56,41,78,15,23,12,12,56,33,80,79,90,55(3)单链表合并后排序测试:测试目的:测试两个合并后的单链表是否能够升序排序后输出测试结果:单链表D=12,12,15,23,23,30,33,41,55,56,56,78,79,80,908.2 测试第2组数据(1)单链表测试:测试目的:测试单链表是否能够进行插入、读取等操作。测试结果:单链表A= 30,41,15,12,56,80,23,12,34单链表B= 23,56,78,23,12(2)单链表合并测试:测试目的:测试两个单链表是否能够按照要求进行合并测试结果:单链表C= 30,23,41,56,15,78,12,23,56,12,80,23,12, 34(3)单链表合并后排序测试:测试目的:测试两个合并后的单链表是否能够升序排序后输出测试结果:单链表D= 12,12,12,15,23,23,23,30,34,41,56,56,78,808.3 测试说明:(1) 经过反复的程序调试和修改,最终实现了本次课程设计的任务。限于篇幅,程序运行结果只有调试修改正确以后的的运行结果。(2) 为了方便测试,在测试过程中,把要测试的数据直接通过添加数据程序代码导入到程序中。把程序运行结果和理论分析结果进行对比,验证程序的正确性。8.4 测试结论:(1) 在程序完成编写之后,程序的连接、编译、运行开始不能够正常通过,经过调试、修改之后,最终都能够正常通过,修改过后的程序中没有语法错误。(2) 把测试结构和理论的分析结构进行对比,通过程序运行结果的观察得知程序运行结果和理论分析结果基本吻合。(3) 通过单链表的操作可以完成两个单链表的合并,除此之外,还能够对单链表合并后的数据元素进行排序。九、 课程设计总结:9.1 课程设计题目的选择在本次的数据结构课程设计中,我选择的题目是“实现两个单链表的合并”,从所学习过的知识入手进行课程的设计。程序设计语言选择C语言,由于学习的时间较早,经过一段时间的编程积累用的相对比较熟练。9.2 对题目的认识单链表是数据结构里面典型的线性表,适用范围比较广泛,使用方法也相对灵活,在课堂上我们学习了单链表的基本数据结构和单链表的基本操作,但是并没有运用到实际的程序中,这次课程设计把我们的理论知识和程序实践联系起来了。9.3 编程心得通过本次的课程设计,使我学会了如何去组织代码量较大大程序。与此同时,也使我学会了一些对代码量较大的的程序进行编写、连接、编译运行、以及调试和修改的技巧。9.4 课程设计感想这次的课程设计涉及到编程语言和数据结构的知识,要求和平时的实验相比相对较高。从本次的课程设计可以检验我们对C语言和数据结构的掌握情况,同时也检验了
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年秋九年级历史上册 第21课 马克思主义的诞生和国际工人运动的兴起教案 新人教版
- 2023一年级语文上册 第五单元 6 画说课稿 新人教版
- 辽宁省抚顺市八年级地理上册 2.1 地形教案 (新版)新人教版
- 2024-2025学年高中生物 专题1 传统发酵技术的应用 课题3 制作泡菜并检测亚硝酸盐含量教案2 新人教版选修1
- 2023九年级道德与法治下册 第一单元 我们共同的世界 第一课 同住地球村第1课时 开放互动的世界说课稿 新人教版
- 开水间管理规范
- 资产处理合同(2篇)
- 2023年国家公务员考试《申论》真题(行政执法卷)及答案解析
- 丰子恺杨柳课件
- 孟子成语 课件
- Unit 14 I remember meeting all of you in Grade 7 第1课时公开课教学设计【人教版九年级英语】
- 工程地质剖面图的绘制(正式)
- JJG 707-2014扭矩扳子行业标准
- 2024医保练兵理论知识考试题库(浓缩500题)
- 三重一大培训课件
- 【增加多场景】员工使用公司车辆协议
- 单孔腹腔镜手术
- 2024年度2024行政复议法培训
- 车辆托运合同
- 2023土的分散性判别试验规程
- (高清版)TDT 1048-2016 耕作层土壤剥离利用技术规范
评论
0/150
提交评论