题目1线性表的链式表示和实现1报告.doc

理学院课程设计说明书课 程 名 称: 数据结构与算法A设计实践课 程 代 码: 6015059 题 目 一: 线性表的链式表示和实现1 年级/专业/班: 2013/信息与计算科学/2 学 生 姓 名: 刘凯 学 号: 3120130902212 开 始 时 间: 2015 年 12 月 28 日完 成 时 间: 2016 年 1 月 10 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日 数据结构与算法A设计实践任务书学院名称： 理学院 课程代码：_ 6015059_专 业： 信科 年 级： 2013 一、设计题目 线性表的链式表示和实现1（限最多1人完成）二、主要内容实现一些线性表的基本操作。三、具体要求及提交的材料（1）动态地建立单链表,实现插入元素、删除元素、查询、求表长度；（2）建两个有序的单链表LA和LB，实现合并成LC，要求分LC中有和无重复值两种情况的实现；（3）求两链LA和LB两链元素的交集LD。（4）静态链表的实现：使用数组实现单向链表的建立、插入元素、删除元素。测试数据及测试结果请在上交的资料中写明；必须上机调试通过l按数据结构课程设计大纲中的要求完成课程设计报告格式。设计结束后，每个学生必须上交的材料有：1 课程设计报告打印稿一份 2课程设计的源代码电子文档一份四、主要技术路线提示合并采用教材相关的现成算法。注意各种算法的性能比较。五、进度安排共计两周时间，建议进度安排如下：1. 选题，应该在上机实验之前完成2. 需求分析、概要设计可分配4学时完成3. 详细设计可分配4学时4. 调试和分析可分配10学时5. 学时的机动，可提前安排部分提前结束任务的学生答辩六、 推荐参考资料1. 冯博琴 等编著，软件技术基础（修改版），西安交通大学出版社，19972. 严蔚敏 等著，数据结构，清华大学出版社，20033. 李芸芳 等著，软件技术基础（第二版），清华大学出版社，20004. 徐孝凯 等著，数据结构（C语言描述），清华大学出版社，2004指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日目录摘要- 3 -1 引言- 4 -1.1问题的提出- 4 -1.2 C/C+语言- 4 -1.3 C/C+语言发展过程- 5 -1.4任务与分析- 5 -2 设计方案- 6 -2.1 步骤- 6 -2.2 设计流程图- 6 -3 程序演示- 7 -3.1 编译- 7 -3.2 运行结果- 7 -4 结论- 12 -参考资料：- 13 -附录：源代码- 14 -摘要线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，他的存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也铸成了这种存储结构的弱点：在作插入或删除操作时，需要移动大量的元素。线性表的链式存储结构，不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点。关键词：链式存储，插入，删除1 引言 1.1问题的提出线性表的链式存储结构，不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但是怎么表示和实现一些线性表的基本操作呢？1.2 C/C+语言C语言是在70年代初问世的。一九七八年由美国电话电报公司(AT&T)贝尔实验室正式发表了C语言。同时由B.W.Kernighan和D.M.Ritchit合著了著名的“THE C PROGRAMMING LANGUAGE”一书。通常简称为K&R，也有人称之为K&R标准。但是，在K&R中并没有定义一个完整的标准C语言，后来由美国国家标准学会在此基础上制定了一个C 语言标准，于一九八三年发表。通常称之为ANSI C。C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。C语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址，进行位(bit)一级的操作。由于C语言实现了对硬件的编程操作，因此C语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发，也适合于应用软件的开发。此外，C语言还具有效率高，可移植性强等特点。因此广泛地移植到了各类各型计算机上，从而形成了多种版本的C语言。C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。目前主要的C语言版本有：Microsoft Visual C+；Borland Turbo C+1；AT&T C。这些C语言版本不仅实现了ANSI C标准，而且在此基础上各自作了一些扩充，使之更加方便、完美。在C的基础上，一九八三年又由贝尔实验室的Bjarne Strou-strup推出了C+。 C+进一步扩充和完善了C语言，成为一种面向 对象的程序设计语言。C+目前流行的集成开发环境最新版本是Borland C+4.5,Symantec C+6.1,和Microsoft VisualC+ 2012。C+提出了一些更为深入的概念，它所支持的这些面向对象的概念容易将问题空间直接地映射到程序空间，为程序员提供了一种与传统结构程序设计不同的思维方式和编程方法。因而也增加了整个语言的复杂性，掌握起来有一定难度。但是，C是C+的基础，C+语言和C语言在很多方面是兼容的。因此，掌握了C语言，再进一步学习C+就能以一种熟悉的语法来学习面向对象的语言，从而达到事半功倍的目的。1.3 C/C+语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本可移植的C语言编译程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。早期的C语言主要是用于UNIX系统。由于C语言的强大功能和各方面的优点逐渐为人们认识，到了八十年代，C开始进入其它操作系统，并很快在各类大、中、小和微型计算机上得到了广泛的使用。成为当代最优秀的程序设计语言之一。C语言是当今最流行的程序设计语言之一，它的功能丰富、表达力强、使用灵活方便、应用面广、目标程序高、可植入性好，既有高级语言的特点，又有低级语言的许多特点，适合作为系统描述语言，既可以用来编写系统软件，也可以用来编写应用软件。C语言诞生后，许多原来用汇编语言编写的软件，现在都可以用C语言编写了（如UNIX操作系统），而学习和适用C语言要比学习和适用汇编语言容易得多。1.4任务与分析（1）动态地建立单链表,实现插入元素、删除元素、查询、求表长度；（2）建两个有序的单链表LA和LB，实现合并成LC，要求分LC中有和无重复值两种情况的实现；（3）求两链LA和LB两链元素的交集LD。（4）静态链表的实现：使用数组实现单向链表的建立、插入元素、删除元素。2 设计方案2.1 步骤（1）编写主函数，调用初始化，建立线性链表的算法以及插入和删除算法。（2）调试。（3）运行输入数据得出结果并进行分析。2.2 设计流程图3 程序演示3.1 编译编译之后发现错误，error C2144: syntax error : missing ; before type int。缺少分号。如下图：修改之后，在编译一次。没有错误。如下图：连接没有问题。如下图：3.2 运行结果菜单如图1：图1动态地建立单链表,实现插入元素、删除元素、查询、求表长度如图2所示：图2建两个有序的单链表LA和LB，实现合并成LC，要求分LC中有和无重复值两种情况的实现如图3所示：图3求两链LA和LB两链元素的交集LD如图4所示：图4静态链表的实现：使用数组实现单向链表的建立、插入元素、删除元素如图5所示：图54 结论单链表作为一种十分重要的线性表，在日常生活中有着十分重要的作用，在数据结构这门课程中，占着很重的地位，这就要求我们认真学习体会它的精髓，熟练掌握它的表示与应用。在日常生活中要注意锻炼自己的逻辑思维和动手动脑的实践能力，才能在日后的计算机学习中取得长足的进步。这次课程设计，体现出自己单独设计程序的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情。从中发现自己平时学习的不足和薄弱环节，从而加以弥补。通过这次课程设计，我对这种写程序的方法有了一定的了解，自己有一个很明确的思路去写程序，提高了效率。老师严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；而您开朗的个性和宽容的态度，帮助我能够很顺利的完成了这次课程设计。同时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊。由于自己的设计能力有限，在设计过程中难免出现错误，恳请老师多多指教。参考资料：5. 冯博琴 等编著，软件技术基础（修改版），西安交通大学出版社，19976. 严蔚敏 等著，数据结构，清华大学出版社，20037. 李芸芳 等著，软件技术基础（第二版），清华大学出版社，20008. 徐孝凯 等著，数据结构（C语言描述），清华大学出版社，2004附录：源代码/ 线性表的链式表示和实现1.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#include#include#includeusing namespace std;typedef struct LNode int data; struct LNode *next; LNode, LinkList ;typedef struct Arrayint data;int num;Array; LNode *CreateList(LNode *Head) LNode *p,*q,*s,*t; cout开始创建链表，当输出值为0或者负数时则停止：endl;for(;)p=new LNode;coutp-data;if(p-datanext=NULL; q=p;elseif(p-datadata)p-next=Head;Head=p;else if (p-data=q-data)q-next=p;p-next=NULL;q=p;else s=Head; t=s-next; while(p-data=t-data) s=s-next; t=t-next; s-next=p; p-next=q; return Head; void PrintList (LNode *Head) LNode *pt=Head;if(pt=NULL)cout链表为空！按任意键返回！endl;system(pause);return;cout线性表为：endl;while (pt)coutdatanext;coutendl;void *InsertList(LNode *Head) if(Head=NULL) coutch; if(ch!=Y&ch!=y)return Head; else Head=CreateList(Head);return Head; LNode *pnew,*pend=Head,*ps,*pe;while(pend-next)pend=pend-next;cout请输入数值，当数值data=0则退出：next=NULL;coutpnew-data;if(pnew-datadatadata)pnew-next=Head;Head=pnew;else if(pnew-data=pend-data)pend-next=pnew;pend=pnew;elseps=Head;pe=ps-next;while(pe-datadata)ps=ps-next;pe=pe-next;pnew-next=pe;ps-next=pnew;coutendl; cout添加成功，当前线性表为：endl;PrintList(Head) ; coutendl;return Head; void * DeleteList(LNode *Head) cout请输入你要删除的数据：t; while(temp-data!=t & temp-next!=NULL) p=temp;temp=temp-next; if(temp-data=t) if(temp=Head) Head=Head-next;delete temp; else if(temp-next=NULL) p-next=NULL;delete temp;else p-next=temp-next;delete temp; coutendl; cout删除成功，当前线性表更新为：endl; else cout线性表中无此数据endl; PrintList(Head) ; coutendl; return Head; void SearchList(LNode * Head)LNode *p=Head;cout请输入你要查找的数据：t;while(p) if(t=p-data) flag=1;coutdata 在第j个位置next; j+;if (flag=0)coutnext; j+; cout线性表的长度为jendl; return Head; void Work(LNode *Head)label:cout您可以选择以下数据进行相应操作：endl;coutt 1-查找数据 endl;coutt 2-添加数据 endl;coutt 3-删除数据 endl;coutt 4-线性表长度 endl;coutt 5-退出 endl;cout请输入您的选择:work;switch(work)case 1: SearchList(Head);goto label;case 2: InsertList(Head); goto label;case 3: DeleteList(Head); goto label; case 4: LengthList(Head); goto label;case 5: break;default:cout操作错误！datadata)/若为相同值排序时 将改为data = a-data;a = a-next;else if (a-data=b-data)c-data = a-data;a = a-next;b = b-next;elsec-data = b-data;b = b-next;if (head3=NULL)head3 = c;c-next = NULL;p = c;elsep-next = c;p = p-next;p-next = NULL;if(a!= NULL)p-next=a;if(b!=NULL)p-next=b;return(head3);void second () LNode *Head1=NULL;LNode *Head2=NULL; cout请输入第一个链表endl; Head1=CreateList(Head1); PrintList(Head1); coutendl; cout请输入第二个链表endl; Head2=CreateList(Head2); PrintList(Head2);LNode *head3= MergeList(Head1 ,Head2);coutendl;coutdata = p2-data)if (head3 = NULL)head3 = p1;p3 = head3;elsep3-next = p1;p3 = p3-next;break;p2 = p2-next;p1 = p1-next;p2 = head2;p3-next = NULL;return head3;void third() LNode *Head1=NULL;LNode *Head2=NULL; cout请输入第一个链表endl; Head1=CreateList(Head1); PrintList(Head1); coutendl; cout请输入第二个链表endl; Head2=CreateList(Head2); PrintList(Head2);LNode *head3= SameList(Head1 ,Head2);coutendl;cout两链表的交集为;PrintList(head3);system(pause);/第三问结束void CreateArray(Array *myA, int n)/建立数组链表int i = 0;cout输入节点数：;while (imyAi.data;myAi.num = i + 1;i+;/myAi - 1.num = NULL;void PrintArray(Array myA)/打印数组链表int i = 0;while (myAi.num != NULL)i = myAi.num;cout myAi.data ;void DeleteArray(Array *mA, int n)/删除数组链表第n个结点Array *myA;myA = mA;int i = 0, m = 0;for (i; in - 1; i+)m = myAm.num;myAm + 1.data = 0;myAm.num = myAmyAm.num.num;myAm + 1.num = NULL;i = 0;while (myAi.num)i = myAi.num;myAi.num = m + 1;void AddArray(Array *myA, int n, int k)/向数组链表第n个结点添加结点kint i1 = 0, i11 = 0, i2 = 0, m = 0;while (myAi1.num != NULL)/寻找数组空缺位置存放ki11 = i1;i1 = myAi1.num;if (myAi1.data = 0)/myAi1空缺break;myAi1.data = k;/赋值if (myAi1.num = NULL)myAi11.num = NULL;for (i2; i2 n;Array *myA;myA = (Array*)calloc(n + 1, sizeof(Array);if (myA = NULL)printf_s(没有分配内存n);exit(1);myA0.data = 0;myA0.num = 1;CreateArray(myA, n);PrintArray(myA);coutendl;DeleteArray(myA, 4);PrintArray(myA);coutendl;AddArray(myA, 2, 9);PrintArray(myA);coutendl;void menu()label:cout*endl;cout1：动态地建立单链表,实现插入元素、删除元素、查询、求表长度endl;cout2：建两个有序的单链表LA和LB，实现合并成LC，要求分LC中有和无重复值两种情况的实现endl;cout3：求两链LA和LB两链元素的交集LD endl;cout4：静态链表的实现：使用数组实现单向链表的建立、插入元素、删除元素endl;cout0：退出endl;cout*endl;int _tmain(int argc, _TCHAR* argv)menu();while (12)int k;printf_s(请输入你选择的项);scanf_s(%d, &k);switch (k)case 1:first();break;case 2:second();break;case 3:third();break;case 4:fouth();break;case 0:exit(1);default:printf_s(重新输入);