数据结构课程设计题目02599.docx

《数据结构课程设计题目02599.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计题目02599.docx（163页珍藏版）》请在课桌文档上搜索。

1、数据结构实践教程目录第一部分基础篇第一章线性表1.1学生成绩管理1.1.1项目简介1.1.2设计思路1.1.3数据结构1.1.4程序清单1.1.5运行结果1.2考试报名管理1.2.1项目简介1.2.2设计思路1.2.3数据结构1.24程序清单1.2.5运行结果1.3约瑟夫生者死者游戏1.3.1项目简介1.3.2设计思路1.3.3数据结构1.3.4程序清单1.3.5运行结果1.4约瑟夫双向生死游戏1.4.1项目简介1.4.2设计思路143数据结构1.4.4程序清单1.4.5运行结果第二章栈和队列2.1迷宫旅行游戏2.1.1项目简介2.1.2知识要点2.1.3设计思路2.1.4程序清单2.1.5运

2、行结果2.2八皇后问题2.1.1项目简介2.1.2知识要点2.1.3设计思路2.1.4程序清单2.1.5运行结果2.3停车场的停车管理2.1.12.1.22.1.32.1.42.1.5第三章串、项目简介知识要点 设计思路程序清单 运行结果数组和广义表3.1.13.1.23.133.1.43.1.5单词检索统计程序项目简介设计思路数据结构程序清单运行结果3.2Internet网络通路管理3.2.1项目简介3.2.2设计思路3.2.3数据结构3.2.4程序清单3.2.5运行结果第四章树和二又树4.1家谱管理4.1.1项目简介4.1.2设计思路4.1.3数据结构4.1.4程序清单4.1.5运行结果4

3、.2表达式求值问题4.2.1项目简介4.2.2设计思路4.2.3数据结构4.2.4程序清单4.2.5运行结果4.4图像压缩编码优化4.4.1项目简介4.4.2设计思路4.4.3数据结构4.4.4程序清单4.4.5运行结果第五章图5.1公交路线管理5.1.1项目简介5.1.2设计思路5.1.3数据结构5.1.4程序清单5.1.5运行结果5.2导航最箱i路径查询5.2.1项目简介5.2.2设计思路5.2.3数据结构5.2.4程序清单5.2.5运行结果5.4电网建设造价计算5.4.1项目简介5.4.2设计思路5.4.3数据结构5.4.4程序清单5.4.5运行结果5.4软件工程进度规划5.4.1项目简

4、介5.4.2设计思路5.4.3数据结构544程序清单5.4.5运行结果第二部分综合篇1.1景区旅游信息管理系统1.1.1项目需求1.1.2知识要点1.1.3设计流程1.1.4程序清单1.1.5运行测试第一部分基础篇第一章线性表线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继知识的学习。本章通过四个模拟项目来学习线性表的顺序和链式存储结构，首先通过使用有关数组的操作实现学生成绩管理，其次通过使用有关线性链表的操作实现考试报名管理，然后通过使用循环链表的操作实现约瑟夫生者死者游戏。1.1学生成绩管理1.1.1项目简介学生成绩管理是学校教务部

5、门日常工作的重要组成部分，其处理信息量很大。本项目是对学生成绩管理的简单模拟，用菜单选择方式完成下列功能：输入学生数据；输出学生数据；学生数据查询；添加学生数据：修改学生数据；删除学生数据。1.1.2设计思路本项目的实质是完成对学生成绩信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。1.1.3数据结构本项日的数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名和成绩组成，这组学生的成绩信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据具有

6、线性表中数据元素的性质，所以该系统的数据采用线性表来存储。顺序表是线性表的顺序存储结构，是指用一组连续的内存单元依次存放线性表的数据元素。在顺序存储结构下，逻辑关系相邻的两个元素在物理位置上也相邻，这是顺序表的特点。本项目可以采用顺序表的线性表顺序存储结构。若一个数据元素仅占一个存储单元，则其存储方式参见图1-1。从图1-1中可见，第i个数据元素的地址为1.oc(ai)=loc(al)+(i-l)假设线性表中每个元素占用k个存储单元，那么在顺序表中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是1.oc(ai)=loc(a)+(i-l)*k这里LOC(ai)是第i个元素的存储位置，

7、loc(al)是第1个元素的存储位置，也称为线性表的基址。显然，顺序表便于进行随机访问，故线性表的顺序存储结构是一种随机存储结构。顺序表适宜于做查找这样的静态操作；顺序存储的优点是存储密度大，存储空间利用率高。缺点是插入或删除元素时不方便。由于C语言的数组类型也有随机存储的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。数组实现线性表的顺序存储的优点是可以随机存取表中任一元素0(1)，存储空间使用紧凑：缺点是在插入，删除某一元素时，需要移动大量元素O(n),预先分配空间需按最大空间分配，利用不充分，表容量难以扩充。用结构体类型定义每个学生数据，故该数组中的

8、每个数据的结构可描述为：typedefstructSTUcharstuno10;学号charname10;姓名oatscore;成绩ElemType:1.1.4程序清单#include#include#include#include#defineMaxListSize20#defineEQUAL1typedefstructSTUcharstuno10;charname10;floatscore;JElemType;classListprivate:/线性表的数组表示ElemTypeelemMaxListSize;intlength;intMaxSize;public:/输入学生数据voidin

9、it(List*L,intms);删除所有学生数据voidDestroyList(List&L)free(&L);)将顺序表置为空表voidCletrList()Iength=O;判断顺序表是否为空表boolListEmptyOreturnIength=O;判断顺序表是否为满boolListFullOreturnIength=MaxSize;删除某个学生数据boolListDeleteCinuEIemType&e);遍历顺序表voidListTraverseO;返回顺序表的长度intListLengthO;学生数据查询voidGetElem(intElemType*);/修改学生数据blUpd

10、atcList(ElcmType&e,ElcmType);添加学生数据boolListInserUinLElemType&);对学生数据按升序或降序输出voidprintlist(int);:voidList:init(List*LJntms)*L=(List*)malloc(sizeof(List);(*L)-length=0;(*L)-MaxSize=ms;intListzzListLengthOreturnlength;boolList:ListDelete(intmark,ElemType&e)intij;if(ListEmpty()returnfalse;if(mark0)删除表头元

11、素e=elem0;for(i=l;ilength;i+)elemi-l=elemijelse删除表尾元素if(mark0)e=elemlength-l;else删除值为e的元素for(i=O;i=length)returnfalse;elsee=elemi;for(j=i+lylengthy+)elemj-l=elcmj;length-;returntrue;IvoidList:ListTraverse()for(inti=O;ivlength;i+)coutsetw(8)elemi.name;coutsetw(IO)elemi.stuno;coutsetw(9)elemil.age;cout

12、setw(8)elemi.scorenamete2-namc)完整版学习资料分享-returnfalse;if(strcmp(e1-stuno,e2-stuno)returnfalse;if(el-age!=e2-age)returnfalse;if(el-score!=e2-score)returnfalse;returntrue;boolList:Less_EqualList(ElemType*el,ElemType*e2)if(strcmp(el-name,e2-name)=0)returntrue;elsereturnfalse;boolList:LocateE)em(ElemType

13、e,inttype)i11ti;switch(type)caseEQUAL:for(i=O;ilength;i+)if(EqualList(&elemi,&e)returntrue;break;defaulcbreak;returnfalse;I修改学生数据boolList:UpdateList(ElemTypeAe,ElemTypeel)for(inti=O;ilength;i+)if(strcmp(elemiJ.namete.name)=O)(elemil=eHrelurntrue;returnfalse;boolList:ListInsert(inti,ElemType&e)ElcmTy

14、pe*p,*q;if(ilength+l)returnfalse;q=&elemi-l;for(p=q;p)-完整版学习资料分享一*(pl)=*p;*q=e;+length;returntrue;对学生成绩按升序或降序输出voidList:printlist(intmark)int*b=newintlength;inti,k;cout,r姓名学号成绩、f;if(mark!=0)for(i=0;ilength;i+)bi=i;for(i=0;ilength;i+)k=i;fbr(intj=i+lylengthy+)if(mark=1&elembj.scoreelembk.score)k.;if(

15、mark=-l&elem|b|kl|.scoreelemb|j.score)k=j;if(k!=i)intx=bi;bi=bk;bk=x;)for(inti=O;ilength;i+)(coutsetw(8)elembij.name;coutsetw(10)elembi.stuno;coutsetw(9)elembi.age;coutsetw(8)elembli.scoreendl;)elsefor(i=O;ilength;i+)coutsetw(8)elemij.name;coutsetw(10)elemi.stuno;coutsetw(9)elemi.age;coutsetw(8)elem

16、i.scoreendl;)voidmain()cout*Lc;intk;COUtinit(La,4);StrCPy(eLnamcJstu);strcpy(e1.stunoj,1(X)OOl);el.age=22;el.score=88;1.a-ListInsert(1,e1);strcy(e2.nanestu2n);stcpy(e2.Stuno/1100002,);e2.age=21;e2.score=79;1.a-ListInsert(2,e2);strcpy(e3jaestu3);strcy(e3.Stuno/11(X1003,);e3.age=19;e3.score=87;1.a-Lis

17、tlnsert(3te3);1.a-Aprintlist(O);COUt表Lad,ListLength()init(ListInsert(1,e4);strcpy(e5.name,bobjin);strcy(e5.stuno11(XK)02,);e5.age=23;e5.score=69;1.b-Listlnsert(2+e5);strcpy(e6.name,stu,);strcpy(e6.Stuno,1100OO);eGage=22;e6.score=88;1.b-ListInsert(3,e6);Lb-printlist(O);CoUt表LbjzListLength()ListDelete

18、(-1,e6);if(k=O)cout”删除失败!n;elseCOUtVV”删除成功!n;COUtprintlist(O);cin.get();CoUtprintlist(1);cin.get();COUlVV按成绩降序输出表Lcnr,;1.c-printlist(-1);cin.get();1.1.5运行结果首先建立学生信息管理，输出结果为：姓名学号成绩Stul100OOl80Stu210000291Stu310000356其次查询学号为I(X)OO2的学生的成绩，输出结果为:91再次调用插入函数，插入Stu4成功！输入结果为：姓名学号成绩Stul10000180Stu210000291St

19、u310000356Stu410000475最后删除Stu2成果!输出结果为姓名学号成绩Stul10000180Stu310000356Stu410000475查询不及格的学生，输出结果为：Stu3100003561.2考试报名管理1.2,1项目简介考试报名工作给各高校报名工作带来了新的挑战，给教务管理部门增加了很大的工作量，报名数据手工录入既费时又会不可避免地出现错误，同时也给不少学生以可乘之机。本项目是对考试报名管理的简单模拟，用菜单选择方式完成下列功能：输入考生信息.：输出考生信息：查询考生信息：添加考生信息；修改考生信息；删除考生信息。1.2.2设计思路本项日的实质是完成对考生信息的建

20、立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。1.2.3数据结构本项目的数据是-组考生信息，每条考生信息由准考证号、姓名、性别、年龄、报考类别等信息组成，这组考生信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据也具有线性表中数据元素的性质，所以该系统的数据可以采用线性表来存储。从上一节的例子中可见，线性表的顺序存储结构的特点是逻辑关系相邻的两个元素在物理位置上也相邻，因此可以随机存储表中任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，

21、从另一个方面来看，这个特点也铸成了这种存储结构的弱点：在做插入或删除操作时，需要移动大量元素。为克服这一缺点，我们引入另一种存储形式一-链式存储。链式存储是线性表的另一种表示方法，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构的弱点，但同时也失去了顺序表可随机存取的特点。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。事实上，链表插入、删除运算的快捷是以空间代价来换取时间。顺序表适宜于做查找这样的静态操作；徒表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操

22、作是插入、删除操作，则采用链表。本项目对考生数据主要进行插入、删除、修改等操作，所以采用链式存储结构比较适合。用结构体类型定义每个考生信息，故该单链表中的每个结点的结构可描述为:Iypedefstructexamineecharexamno10;准考证号charname10;姓名charsex;floatage;charexamtype5;成绩ElemType;1.2.4程序清单单链表的类定义Iinklist3.h#ifndeflinklist3H#dcfinclinklist3H#defineLEN30定义ElemType为inttypcdcfintElcmTypc;单链表中结点的类型typ

23、edefstructLNodeElemTypedata;值域1.Node*next;指针域LNode;classLinkList1.Node*head;public:构造函数1.inkListO;析构函数LinkList();清空单链表voidClearListO;求单链表长度intListSizeO;检查单链表是否为空boolListEmptyO;返回单链表中指定序号的结点值ElemTypeGetElem(intos);遍历单链表voidTraverseList(voidf(ElemType&);从单链表中查找元素boolFindLiSt(ElemType&item);更新单链表中的给定元素

24、boolUpdateList(constElemType&item,ElemTypee);向单链表插入元素,mark=0插在表首,否则插在表尾voidInsertList(ElemTypeitemjntmark);从单链表中删除元素，mark为要删除的第几个元素boolDeleleList(ElemTypeAitemJntmark);对单链表进行有序排列mark*)升序,否则降序voidpailie(intmark=1);对单链表进行有序输出,mark=0不排序,markO升序,marknext=NULL;I1.inkList:LinkList()析构函数(LNcxJe*p=head-next

25、,*q;while(p)q=p-next;free(p);p=q；voidLinkList:ClCarLiSt()清空单链表LNode*p=head-next,*q;while(p)q=p-next;=X=WORD完整版.可编辑专业资料分享free(p);p=q;head-next=NULL;intLinkList:LiStSiZe()求单链表长度LNode*p=head-next;inti=0;while(p)i+;p=p-next;)returni;boolLinkLiSl:LiStEmPty()检查单链表是否为空returnListSizeO=O;)/返回单链表中指定序号的结点值Elem

26、TypeLinkLiSt:GetEIem(impos)LNode*p=head-next;inti=l;while(p)if(i+=pos)returnp-data;p=p-next;returnhead-data;voidLinkLiS1:TraVerSeLiSt(VOidf(ElemType&)遍历单链表ILNode*p=head-next;while(p)f(p-data);p=p-next;)boolLinkList:FindList(ElemType&item)/从单链表中杳找元素ILNode*p=head-next;while(p)if(p-data=item)return1;p=

27、p-next;)returnO;更新单链表中的给定元素boolLinkList:UpdateList(constEIemType&item,ElemTypee)LNode*p=head-next;boolflag=O;while(p)if(p-data=item)p-data=e;flag=l;)p=p-next;)returnflag;向单链表插入元素voidLinkList:InsertList(ElemTypeitem,intmark)LNode*q=newLNode;q-data=item;if(mark=O)q-next=head-next;head-next=q;return;1.

28、Node*p=head;while(p-nexl)p=p-next;q-next=NULL;p-next=q;从单链表中删除元素boolLinkList:DeleteList(ElemType&item,intmark)if(ListEmpty()markListSize()returnO;1.Node*p=head,*q;fbr(inti=O;inext;item=p-next-data;q=p-next-next;free(p-next);=X=WORD完整版.可编辑专业资料分享p-next=q;return1;对单链表进行有序排列mark0升序,否则降序voidLinkList:pail

29、ie(intmark)ElemTypea(LEN+l;1.Node*p=head-next;itk;for(k=l;p!=NULL;k+,p=p-next)ak=p-data;k-;fbr(inti=l;ik;i+)for(intj=I;jO&a|ja|j+l|markO&ajnext;fbr(intj=l;jnext)p-data=aj;对单链表进行有序输出voidLinkList:OrdcrOutputList(intmark)ElemTypeaLEN+l;1.Node*p=head-next;intk;fbr(k=l;p!=NULL;k+,p=p-next)ak=p-data;k-;fr

30、(imi=l；iO&ajaj+l|markO&ajaj+l)t=j+l;aj+l=aj;aj=t;Hfbr(itj=ly=ky+)coutaj,1;#include#include#include/#include#includeMIinklist3.cpp1voidff(int&a)用于遍历的函数couta;voidmain()(cout,nlinklist3m.cpp运行结果:n;intinit_size,Seed,xu;COUIVV首先请构造单链表list”；coutxu;coutn单链表list构造成功!n它是:;list.TraverseList(ff);coutwn它为空吗?(1:

31、是;0:不是):listListEmpty();cout*,n长度为:1ist.ListSize();inti;cout,n请输入你想得到第几个元素的值(linit_sizei;COUlv单链表list中第i的值是vlislGetElem(i);intit;cout,n请输入你想删除第几个元素的值(l-iIiJSiZei;IisLDeletcList(Itj);cout,n单链表IE删除第”i个元素”T”itT后变为:;IistTraverseLisKff);对单链表list每个数进行遍历.intnews,olds;coutolds;CoUtnews;list.UpdateList(olds,

32、news);cout,n修改后单链表list变为:；list.TraverseList(ff);coutn下面请构造单链表list2;coutxu;coutn按回车键结束；cin.get();cin.get();1.2.5运行结果1.3约瑟夫生者死者游戏1.3.1项目简介约瑟夫生者死者游戏的大意是：30个旅客同乘-条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难.无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，数到第9人，再将他投入大海，如此循环，直

33、到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。1.3.2设计思路本游戏的数学建模如下：假设n个旅客排成-个环形，依次顺序编号1,2n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。本游戏的要求用户输入的内容包括：1.旅客的个数，也就是n的值：2.离开旅客的间隔数，也就是m的值；3.所有旅客的序号作为一组数据要求存放在某种数据结构中._完整版学习资料分享一一本游戏要求输出的内容是包括1.离开旅客的序号：2.剩余旅客的序号；所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行算法实现

34、。1.3.3数据结构为了解决这一问题，可以用长度为30的数组作为线性存储结构，并把该数组看成是-个首尾相接的环形结构，那么每投入大海一个乘客，就要在该数组的相应位置做个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较为复杂，而且效率低，还要移动大量的元素。用单循环德表解决这一问题，实现的方法相对要简单得多。首先要定义链表结点，单循环链衣的结点结构与一般的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成具有30个结点的单循环链表。接下来从位置为1的结点开始数，数到第8个结点，就将下一个结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第8个结点，再将其下一个

35、结点删去，如此进行下去，直到剩下15个结点为止。为了不失一般性，将30改为一个任意输入的正整数n,而报数上限(原为9)也为一个任选的正整数匕这样该算法描述如下：(1)创建含有n个结点的单循环链表；(2)生着与死者的选择：P指向链表的第一个结点，初始i置为1;while(idata;i自增1:(3)输出所有生者的位置。1.3.4程序清单1.inkListInitRingfintn,LinkListR)尾插入法建立单循环链表函数1.istNode*p,*q;intI;R=q=(LinkNode*)malloc(sizeof(LinkNode);for(i=l;idata=i;q-next=p;qP

36、；p-data=n;p-next=R;R=P；returnR;1.inkListDeleteDeath(intn,intk,LinkListR)/生者与死者的选择i11ti,j；1.istNode*p,*q;p=R;for(i=hin2;i+)删除一半结点for(j=l;jnext;q=p-next;p-next=q-next;Printfr%4d,q-data);free(q);IR=p;returnR;voidOutRing(intn,LinkListR)输出所有生者inti;1.inkNode*p;p=R;fbr(i=l;inext)Printf(“4d,p-data)有了上述算法分析和

37、设计之后，实现就比较简单了。首先要定义一个链表结构类型，然后编写一个主函数调用上面已定义好的函数即可。主函数的源程序如下：一-完整版学习资料分享一一#include#includetypedefstructnodeintdata;structnode*next;ListNode;typedefListNode*LinkList;voidmain()1.inkListR;intn,k;1.inkListInitRing(intn.LinkListR);1.inkListDeleteDeath(intn,intk,LinkListR);voidOUtRingantn.LinkListR);Prim

38、f(“总人数n报数上限k=)；SCanf(“d%d”,&n,&k);R=InitRing(n,R);R=DeleteDeath(n,k,R);OutRing(n,R);)1.3.5运行结果编译运行上述程序，提示：总人数n.报数上限k=输入30和9后并回车可得出如下结果：9182761626719301224822523212528291234101113141517201.4约瑟夫双向生死游戏1.4.1项目简介约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上，正向计数后反向计数，然后再正向计数。具体描述如下：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分：因此船长告诉乘客，只有将全船-半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，顺时针依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，逆时针数到第5人，将他投入大海，然后从他逆时针的下一个人数起，顺时针数到第9人，再将他投入大海，如此循环，直到剩F15个乘客为止。问哪些位置是将被扔下大海的位置。1.4.2设计思路本游戏的数学建模如F：假设n个旅客排成一个环形，依次顺序编号1,2n。从某个指定的第