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

上传人：jian****018

文档编号：9148441

上传时间：2020-04-03

格式：DOC

页数：27

大小：242KB

《题目1线性表的链式表示和实现1报告.doc》由会员分享，可在线阅读，更多相关《题目1线性表的链式表示和实现1报告.doc（27页珍藏版）》请在装配图网上搜索。

理学院课程设计说明书课程名称: 数据结构与算法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. 冯博琴等编著，《软件技术基础》（修改版），西安交通大学出版社，1997 2. 严蔚敏等著，《数据结构》，清华大学出版社，2003 3. 李芸芳等著，《软件技术基础》（第二版），清华大学出版社，2000 4. 徐孝凯等著，《数据结构（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所示：图5 4 结论单链表作为一种十分重要的线性表，在日常生活中有着十分重要的作用，在数据结构这门课程中，占着很重的地位，这就要求我们认真学习体会它的精髓，熟练掌握它的表示与应用。在日常生活中要注意锻炼自己的逻辑思维和动手动脑的实践能力，才能在日后的计算机学习中取得长足的进步。这次课程设计，体现出自己单独设计程序的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情。从中发现自己平时学习的不足和薄弱环节，从而加以弥补。通过这次课程设计，我对这种写程序的方法有了一定的了解，自己有一个很明确的思路去写程序，提高了效率。老师严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；而您开朗的个性和宽容的态度，帮助我能够很顺利的完成了这次课程设计。同时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊。由于自己的设计能力有限，在设计过程中难免出现错误，恳请老师多多指教。参考资料： 5. 冯博琴等编著，《软件技术基础》（修改版），西安交通大学出版社，1997 6. 严蔚敏等著，《数据结构》，清华大学出版社，2003 7. 李芸芳等著，《软件技术基础》（第二版），清华大学出版社，2000 8. 徐孝凯等著，《数据结构（C语言描述）》，清华大学出版社，2004 附录：源代码 // 线性表的链式表示和实现1.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include #include #include #include using namespace std; typedef struct LNode { int data; struct LNode *next; }LNode, LinkList ; typedef struct Array { int data; int num; }Array; LNode *CreateList(LNode *Head) { LNode *p,*q,*s,*t; cout<<"开始创建链表，当输出值为0或者负数时则停止："<>p->data; if(p->data<=0) { delete p; break; } if(Head==NULL) { Head=p; p->next=NULL; q=p; } else { if(p->data<=Head->data) { 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<<"链表为空！按任意键返回！"<data<<" "; pt=pt->next; } cout<>ch; 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; cout<<"数值："; cin>>pnew->data; if(pnew->data<=0) { delete pnew; break; } if(pnew->data<=Head->data) { pnew->next=Head; Head=pnew; } else if(pnew->data>=pend->data) { pend->next=pnew; pend=pnew; } else { ps=Head; pe=ps->next; while(pe->datadata) { ps=ps->next; pe=pe->next; } pnew->next=pe; ps->next=pnew; } } 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;} cout<>t; while(p) { if(t==p->data) { flag=1; cout<data <<"在第"<next; j++; } if (flag==0) cout<<"线性表中无此数据"; } void *LengthList(LNode *Head) { LNode *p; p=Head; int j=0; while(p) { p=p->next; j++; } 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)//若为相同值排序时将<改为<=并注释掉下面的else if 语句即可。 { c->data = a->data; a = a->next; } else if (a->data==b->data) { c->data = a->data; a = a->next; b = b->next; } else { c->data = b->data; b = b->next; } if (head3==NULL) { head3 = c; c->next = NULL; p = c; } else { p->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<<"请输入第一个链表"<data == p2->data) { if (head3 == NULL) { head3 = p1; p3 = head3; } else { p3->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<<"请输入第一个链表"<>myA[i].data; myA[i].num = i + 1; i++; } //myA[i - 1].num = NULL; } void PrintArray(Array myA[]) //打印数组链表 { int i = 0; while (myA[i].num != NULL) { i = myA[i].num; cout<< myA[i].data<<" "; } } void DeleteArray(Array *mA, int n) //删除数组链表第n个结点 { Array *myA; myA = mA; int i = 0, m = 0; for (i; i>n; Array *myA; myA = (Array*)calloc(n + 1, sizeof(Array)); if (myA == NULL) { printf_s("没有分配内存\n"); exit(1); } myA[0].data = 0; myA[0].num = 1; CreateArray(myA, n); PrintArray(myA); cout<

下载提示(请认真阅读)

1.请仔细阅读文档，确保文档完整性，对于不预览、不比对内容而直接下载带来的问题本站不予受理。
2.下载的文档，不会出现我们的网址水印。
3、该文档所得收入（下载+内容+预览）归上传者、原创作者；如果您是本文档原作者，请点此认领！既往收益都归您。

同意并开始全文预览

文档包含非法信息？点此举报后获取现金奖励！

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

9.9 积分

版权申诉 word格式文档无特别注明外均可编辑修改；预览文档经过压缩，下载后原文更清晰！ 立即下载

配套讲稿：: 如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
特殊限制：: 部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
关键词：: 题目线性链式表示实现报告

温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

装配图网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。

关于本文

本文标题：题目1线性表的链式表示和实现1报告.doc
链接地址：https://www.zhuangpeitu.com/p-9148441.html

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

最新文档