数据结构课程设计题目

1数据结构实践教程2目录第一部分基础篇第一章线性表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.2.4程序清单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设计思路1.4.3数据结构1.4.4程序清单1.4.5运行结果第二章栈和队列2.1迷宫旅行游戏2.1.1项目简介2.1.2知识要点2.1.3设计思路2.1.4程序清单22.1.5运行结果2.2八皇后问题2.1.1项目简介2.1.2知识要点2.1.3设计思路2.1.4程序清单2.1.5运行结果2.3停车场的停车管理2.1.1项目简介2.1.2知识要点2.1.3设计思路2.1.4程序清单2.1.5运行结果第三章串、数组和广义表3.1单词检索统计程序3.1.1项目简介3.1.2设计思路3.1.3数据结构3.1.4程序清单3.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.2表达式求值问题4.2.1项目简介34.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导航最短路径查询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项目简介5.4.2设计思路5.4.3数据结构5.4.4程序清单5.4.5运行结果4第二部分综合篇1.1景区旅游信息管理系统1.1.1项目需求1.1.2知识要点1.1.3设计流程1.1.4程序清单1.1.5运行测试2第一部分基础篇第一章线性表线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继知识的学习。本章通过四个模拟项目来学习线性表的顺序和链式存储结构，首先通过使用有关数组的操作实现学生成绩管理，其次通过使用有关线性链表的操作实现考试报名管理，然后通过使用循环链表的操作实现约瑟夫生者死者游戏。1.1学生成绩管理1.1.1项目简介学生成绩管理是学校教务部门日常工作的重要组成部分，其处理信息量很大。本项目是对学生成绩管理的简单模拟，用菜单选择方式完成下列功能：输入学生数据；输出学生数据；学生数据查询；添加学生数据；修改学生数据；删除学生数据。1.1.2设计思路本项目的实质是完成对学生成绩信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。1.1.3数据结构本项目的数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名和成绩组成，这组学生的成绩信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据具有线性表中数据元素的性质，所以该系统的数据采用线性表来存储。顺序表是线性表的顺序存储结构，是指用一组连续的内存单元依次存放线性表的数据元素。在顺序存储结构下，逻辑关系相邻的两个元素在物理位置上也相邻，这是顺序表的特点。本项目可以采用顺序表的线性表顺序存储结构。若一个数据元素仅占一个存储单元，则其存储方式参见图1-1。3从图1-1中可见，第i个数据元素的地址为Loc(ai)=loc(a1)+(i-1)假设线性表中每个元素占用k个存储单元，那么在顺序表中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是Loc(ai)=loc(a1)+(i-1)*k这里Loc(ai)是第i个元素的存储位置，loc(a1)是第1个元素的存储位置，也称为线性表的基址。显然，顺序表便于进行随机访问，故线性表的顺序存储结构是一种随机存储结构。顺序表适宜于做查找这样的静态操作；顺序存储的优点是存储密度大，存储空间利用率高。缺点是插入或删除元素时不方便。由于C语言的数组类型也有随机存储的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。数组实现线性表的顺序存储的优点是可以随机存取表中任一元素O(1)，存储空间使用紧凑；缺点是在插入，删除某一元素时，需要移动大量元素O(n)，预先分配空间需按最大空间分配，利用不充分，表容量难以扩充。用结构体类型定义每个学生数据，故该数组中的每个数据的结构可描述为：typedefstructSTU{charstuno[10];//学号charname[10];//姓名floatscore;//成绩}ElemType;1.1.4程序清单#includeiostream.h#includeiomanip.h#includemalloc.h#includestring.h#defineMaxListSize20#defineEQUAL1typedefstructSTU{charstuno[10];charname[10];floatscore;4}ElemType;classList{private://线性表的数组表示ElemTypeelem[MaxListSize];intlength;intMaxSize;public://输入学生数据voidinit(List**L,intms);//删除所有学生数据voidDestroyList(List&L){free(&L);}//将顺序表置为空表voidClearList(){length=0;}//判断顺序表是否为空表boolListEmpty(){returnlength==0;}//判断顺序表是否为满boolListFull(){returnlength==MaxSize;}//删除某个学生数据boolListDelete(int,ElemType&e);//遍历顺序表voidListTraverse();//返回顺序表的长度intListLength();//学生数据查询voidGetElem(int,ElemType*);//修改学生数据boolUpdateList(ElemType&e,ElemType);//添加学生数据boolListInsert(int,ElemType&);//对学生数据按升序或降序输出voidprintlist(int);};5voidList::init(List**L,intms){*L=(List*)malloc(sizeof(List));(*L)-length=0;(*L)-MaxSize=ms;}intList::ListLength(){returnlength;}boolList::ListDelete(intmark,ElemType&e){inti,j;if(ListEmpty())returnfalse;if(mark0){//删除表头元素e=elem[0];for(i=1;ilength;i++)elem[i-1]=elem[i];}else//删除表尾元素if(mark0)e=elem[length-1];else{//删除值为e的元素for(i=0;ilength;i++)if(strcmp(elem[i].name,e.name)==0)break;if(i=length)returnfalse;elsee=elem[i];for(j=i+1;jlength;j++)elem[j-1]=elem[j];}length--;returntrue;}voidList::ListTraverse(){for(inti=0;ilength;i++){coutsetw(8)elem[i].name;coutsetw(10)elem[i].stuno;coutsetw(9)elem[i].age;coutsetw(8)elem[i].scoreendl;}}6voidList::GetElem(inti,ElemType*e){*e=elem[i];}boolList::EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1-name,e2-name))returnfalse;if(strcmp(e1-stuno,e2-stuno))returnfalse;if(e1-age!=e2-age)returnfalse;if(e1-score!=e2-score)returnfalse;returntrue;}boolList::Less_EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1-name,e2-name)=0)returntrue;elsereturnfalse;}boolList::LocateElem(ElemTypee,inttype){inti;switch(type){caseEQUAL:for(i=0;ilength;i++)if(EqualList(&elem[i],&e))returntrue;break;default:break;}returnfalse;}//修改学生数据boolList::UpdateList(ElemType&e,ElemTypee1){for(inti=0;ilength;i++)if(strcmp(elem[i].name,e.name)==0){elem[i]=e1;returntrue;}returnfalse;7}boolList::ListInsert(inti,ElemType&e){ElemType*p,*q;if(i1||ilength+1)returnfalse;q=&elem[i-1];for(p=&elem[length-1];p=q;--p)*(p+1)=*p;*q=e;++length;returntrue;}//对学生成绩按升序或降序输出voidList::printlist(intmark){int*b=newint[length];inti,k;cout姓名学号成绩\n;if(mark!=0){for(i=0;ilength;i++)b[i]=i;for(i=0;ilength;i++){k=i;for(intj=i+1;jlength;j++){if(mark==1&&elem[b[j]].scoreelem[b[k]].score)k=j;if(mark==-1&&elem[b[k]].scoreelem[b[j]].score)k=j;}if(k!=i){intx=b[i];b[i]=b[k];b[k]=x;}}for(inti=0;ilength;i++){coutsetw(8)elem[b[i]].name;coutsetw(10)elem[b[i]].stuno;coutsetw(9)elem[b[i]].age;coutsetw(8)elem[b[i]].scoreendl;}}else{for(i=0;ilength;i++){coutsetw(8)elem[i].name;coutsetw(10)elem[i].stuno;coutsetw(9)e