数据结构课程设计全集样本

数据构造实践教程前言数据构造是计算机专业必修。

主干课程之一，

它旨在使读者学会分析研究数据对象特性，

学会数据组织办法，

以便选取适当数据逻辑构造和存储构造，

以及相应运算（操作），

把现实世界中问题转化为计算机内部表达和解决，

这是一种良好程序设计技能训练过程。

在整个教学或学习过程中，

解题能力和技巧训练是一种重要环节。

为了协助教师讲授“数据构造”，

满足指引和评价“课程设计”需要，

为了协助和指引读者更好地学习数据构造这门课程，

咱们特编写了这本《数据构造实践教程》辅助教材，旨在弥补课堂教学和实验中局限性，协助学生充分理解和巩固所学基本概念、原理和办法，达到融会贯通、举一反三目。

实践证明，

理解课程内容与较好地解决实际问题之间存在着明显差距，

而算法设计完毕质量与基本程序设计素质培养是密切有关。

要想理解和巩固所学基本概念。

原理和办法，

牢固地掌握所学基本知识。

基本技能，

达到融会贯通。

举一反三目，

就必要多做。

多练。

多见（见多识广）。

正是为了达到上述目，

书中用某些实际应用，

对某些重要数据构造和算法进行解读。

通过循序渐进地训练，

就可以使读者掌握更多程序设计技巧和办法，提高分析。

解决问题能力。本书依照学生基本知识和兴趣兴趣将内容分为基本篇和提高篇两个某些。第一某些基本篇精选出恰当、与实际生活结合密切课程设计实例加以分析实现。第二某些提高篇旨在使读者通过运用数据构造知识及复杂算法去解决现实世界中某些实际问题。本书根据数据构造课程教学大纲规定，同步又独立于详细教科书，既注重实践应用，又注重理论分析，本书重要特点有：●本书精选出来实例项目典型、实用、具备一定趣味性，其内容丰富、涉及面广、难易恰当，能给读者以启发，达到让读者掌握有关知识和开阔视野目●为了提高学生分析问题、解决问题能力，本书对实例项目进行分析，其设计思路清晰流畅，值得参照。●本书不但仅是对照数据构造课程教学大纲举些例子阐明数据构造能解决什么问题，而是通过度析详细实例项目，得到对数据组织关系需求，从而选取某个数据构造适应某些特定问题和算法，并阐明使用这种数据构造优缺陷。●所有实例项目都给出了参照算法和源程序代码并在TurboC和VisualC++6.0环境下运营通过。由于作者水平有限、时间仓促，本书难免存在某些缺陷和错误，恳请广大读者及同行们批评指正。目录第一某些基本篇线性表学生成绩管理项目简介设计思路数据构造程序清单运营成果考试报名管理项目简介设计思路数据构造程序清单运营成果约瑟夫生者死者游戏项目简介设计思路数据构造程序清单运营成果约瑟夫双向生死游戏项目简介设计思路数据构造程序清单运营成果栈和队列2.1迷宫旅行游戏2.1.1项目简介2.1.2知识要点2.1.3设计思路2.1.4程序清单2.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项目简介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导航最短途径查询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运营成果查找6.1电话号码查询系统6.1.1项目简介6.1.2知识要点6.1.3设计思路6.1.4程序清单6.1.5运营成果6.2高校录取分数线查询系统6.2.1项目简介5.2.2知识要点6.2.3设计思路6.2.4程序清单6.2.5运营成果6.3储蓄账户查询系统6.3.1项目简介6.3.2知识要点6.3.3设计思路6.3.4程序清单6.3.5运营成果6.3期刊稿件查询系统6.3.1项目简介6.3.2知识要点6.3.3设计思路6.3.4程序清单6.3.5运营成果排序7.1设备清单排序7.1.1项目简介7.1.2知识要点7.1.3设计思路7.1.4程序清单7.1.5运营成果7.2地名排序7.2.1项目简介7.2.2知识要点7.2.3设计思路7.2.4程序清单7.2.5运营成果7.3工厂产量排序7.3.1项目简介7.3.2知识要点7.3.3设计思路7.3.4程序清单7.3.5运营成果7.4高校科研成果排序7.4.1项目简介7.4.2知识要点7.4.3设计思路7.4.4程序清单7.4.5运营成果7.5火车车次排序7.5.1项目简介7.5.2知识要点7.5.3设计思路7.5.4程序清单7.5.5运营成果7.6IP地址排序7.6.1项目简介7.6.2知识要点7.6.3设计思路7.6.4程序清单7.6.5运营成果第二某些综合篇8.1益智游戏之七巧板8.1.1项目需求8.1.2知识要点8.1.3设计流程8.1.4程序清单8.1.5运营测试8.2航空客运定票系统8.2.1项目需求8.2.2知识要点8.2.3设计流程8.2.4程序清单8.2.5运营测试8.4景区旅游信息管理系统8.4.1项目需求8.2.2知识要点8.4.2设计流程8.4.4程序清单8.4.5运营测试第一某些基本篇第一章线性表线性表是数据构造中最简朴、最惯用一种线性构造，也是学习数据构造所有内容基本，其掌握好坏直接影响着后继知识学习。本章通过四个模仿项目来学习线性表顺序和链式存储构造，一方面通过使用关于数组操作实现学生成绩管理，另一方面通过使用关于线性链表操作实现考试报名管理，然后通过使用循环链表操作实现约瑟夫生者死者游戏。1.1学生成绩管理1.1.1项目简介学生成绩管理是学校教务部门寻常工作重要构成某些，其解决信息量很大。本项目是对学生成绩管理简朴模仿，用菜单选取方式完毕下列功能：输入学生数据；输出学生数据；学生数据查询；添加学生数据；修改学生数据；删除学生数据。1.1.2设计思路本项目实质是完毕对学生成绩信息建立、查找、插入、修改、删除等功能，可以一方面定义项目数据构造，然后将每个功能写成一种函数来完毕对数据操作，最后完毕主函数以验证各个函数功能并得出运营成果。1.1.3数据构造本项目数据是一组学生成绩信息，每条学生成绩信息由学号、姓名和成绩构成，这组学生成绩信息具备相似特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据具备线性表中数据元素性质，因此该系统数据采用线性表来存储。顺序表是线性表顺序存储构造，是指用一组持续内存单元依次存储线性表数据元素。在顺序存储构造下，逻辑关系相邻两个元素在物理位置上也相邻，这是顺序表特点。本项目可以采用顺序表线性表顺序存储构造。若一种数据元素仅占一种存储单元，则其存储方式参见图1-1。从图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程序清单#include<iostream.h>#include<iomanip.h>#include<malloc.h>#include<string.h>#defineMaxListSize20#defineEQUAL1typedefstructSTU{charstuno[10];charname[10];floatscore;}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);};voidList::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(mark>0){//删除表头元素e=elem[0];for(i=1；i<length；i++)elem[i-1]=elem[i];}else//删除表尾元素if(mark<0)e=elem[length-1];else{//删除值为e元素for(i=0;i<length;i++)if(strcmp(elem[i].name,)==0)break;if(i>=length)returnfalse;elsee=elem[i];for(j=i+1;j<length;j++)elem[j-1]=elem[j];}length--;returntrue;}voidList::ListTraverse(){for(inti=0;i<length;i++){cout<<setw(8)<<elem[i].name;cout<<setw(10)<<elem[i].stuno;cout<<setw(9)<<elem[i].age;cout<<setw(8)<<elem[i].score<<endl;}}voidList::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;i<length;i++) if(EqualList(&elem[i],&e)) returntrue; break;default:break;}returnfalse;}//修改学生数据boolList::UpdateList(ElemType&e,ElemTypee1){for(inti=0;i<length;i++)if(strcmp(elem[i].name,)==0){elem[i]=e1;returntrue;}returnfalse;}boolList::ListInsert(inti,ElemType&e){ElemType*p,*q;if(i<1||i>length+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；i<length;i++)b[i]=i;for(i=0；i<length;i++){k=i;for(intj=i+1;j<length;j++){if(mark==1&&elem[b[j]].score<elem[b[k]].score)k=j;if(mark==-1&&elem[b[k]].score<elem[b[j]].score)k=j;}if(k!=i){intx=b[i];b[i]=b[k];b[k]=x;}}for(inti=0;i<length;i++){cout<<setw(8)<<elem[b[i]].name;cout<<setw(10)<<elem[b[i]].stuno;cout<<setw(9)<<elem[b[i]].age;cout<<setw(8)<<elem[b[i]].score<<endl;}}else{for(i=0;i<length;i++){cout<<setw(8)<<elem[i].name;cout<<setw(10)<<elem[i].stuno;cout<<setw(9)<<elem[i].age;cout<<setw(8)<<elem[i].score<<endl;}}}voidmain(){cout<<"linelist1m.cpp运营成果:\n";ElemTypee,e1,e2,e3,e4,e5,e6;List*La,*Lb,*Lc;intk;cout<<"一方面调用插入函数.\n";La->init(&La,4);strcpy(,"stu1");strcpy(e1.stuno,"100001");e1.age=22;e1.score=88;La->ListInsert(1,e1);strcpy(,"stu2");strcpy(e2.stuno,"100002");e2.age=21;e2.score=79;La->ListInsert(2,e2);strcpy(,"stu3");strcpy(e3.stuno,"100003");e3.age=19;e3.score=87;La->ListInsert(3,e3);La->printlist(0);cout<<"表La长:"<<La->ListLength()<<endl;cin.get();Lb->init(&Lb,4);strcpy(,"zmofun");strcpy(e4.stuno,"100001");e4.age=20;e4.score=94;Lb->ListInsert(1,e4);strcpy(,"bobjin");strcpy(e5.stuno,"100002");e5.age=23;e5.score=69;Lb->ListInsert(2,e5);strcpy(,"stu1");strcpy(e6.stuno,"100001");e6.age=22;e6.score=88;Lb->ListInsert(3,e6);Lb->printlist(0);cout<<"表Lb长:"<<Lb->ListLength()<<endl;cin.get();k=Lc->ListDelete(-1,e6);if(k==0)cout<<"删除失败!\n";elsecout<<"删除成功!\n";cout<<"输出表Lc:\n";Lc->printlist(0);cin.get();cout<<"按成绩升序输出表Lc\n";Lc->printlist(1);cin.get();cout<<"按成绩降序输出表Lc\n";Lc->printlist(-1);cin.get();}1.1.5运营成果一方面建立学生信息管理，输出成果为：姓名 学号 成绩Stu1 100001 80 Stu2 100002 91 Stu3 100003 56另一方面查询学号为100002学生成绩，输出成果为：91再次调用插入函数，插入Stu4成功！输入成果为：姓名 学号 成绩 Stu1 100001 80 Stu2 100002 91 Stu3 100003 56 Stu4 100004 75 最后删除Stu2成果！输出成果为：姓名 学号 成绩 Stu1 100001 80 Stu3 100003 56 Stu4 100004 75 查询不及格学生，输出成果为：Stu3 100003 56 1.2考试报名管理1.2.1项目简介考试报名工作给各高校报名工作带来了新挑战，给教务管理部门增长了很大工作量，报名数据手工录入既费时又会不可避免地浮现错误，同步也给不少学生以可乘之机。本项目是对考试报名管理简朴模仿，用菜单选取方式完毕下列功能：输入考生信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生信息。1.2.2设计思路本项目实质是完毕对考生信息建立、查找、插入、修改、删除等功能，可以一方面定义项目数据构造，然后将每个功能写成一种函数来完毕对数据操作，最后完毕主函数以验证各个函数功能并得出运营成果。1.2.3数据构造本项目数据是一组考生信息，每条考生信息由准考证号、姓名、性别、年龄、报考类别等信息构成，这组考生信息具备相似特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据也具备线性表中数据元素性质，因此该系统数据可以采用线性表来存储。从上一节例子中可见，线性表顺序存储构造特点是逻辑关系相邻两个元素在物理位置上也相邻，因而可以随机存储表中任一元素，它存储位置可用一种简朴、直观公式来表达。然而，从另一种方面来看，这个特点也铸成了这种存储构造弱点：在做插入或删除操作时，需要移动大量元素。为克服这一缺陷，咱们引入另一种存储形式――链式存储。链式存储是线性表另一种表达办法，由于它不规定逻辑上相邻元素在物理位置上也相邻，因而它没有顺序存储构造弱点，但同步也失去了顺序表可随机存取特点。链式存储长处是插入或删除元素时很以便，使用灵活。缺陷是存储密度小，存储空间运用率低。事实上，链表插入、删除运算快捷是以空间代价来换取时间。顺序表适当于做查找这样静态操作；链表宜于做插入、删除这样动态操作。若线性表长度变化不大，且其重要操作是查找，则采用顺序表；若线性表长度变化较大，且其重要操作是插入、删除操作，则采用链表。本项目对考生数据重要进行插入、删除、修改等操作，因此采用链式存储构造比较适合。用构造体类型定义每个考生信息，故该单链表中每个结点构造可描述为：typedefstructexaminee{ charexamno[10]; //准考证号 charname[10]； //姓名 charsex; floatage;charexamtype[5]; //成绩}ElemType;1.2.4程序清单//单链表类定义linklist3.h#ifndeflinklist3H#definelinklist3H#defineLEN30//定义ElemType为inttypedefintElemType;//单链表中结点类型typedefstructLNode{ElemTypedata;//值域LNode*next；//指针域}LNode;classLinkList{LNode*head;public://构造函数LinkList();//析构函数~LinkList();//清空单链表voidClearList();//求单链表长度intListSize();//检查单链表与否为空boolListEmpty();//返回单链表中指定序号结点值ElemTypeGetElem(intpos);//遍历单链表voidTraverseList(voidf(ElemType&));//从单链表中查找元素boolFindList(ElemType&item);//更新单链表中给定元素boolUpdateList(constElemType&item,ElemTypee);//向单链表插入元素,mark=0插在表首,否则插在表尾voidInsertList(ElemTypeitem,intmark);//从单链表中删除元素，mark为要删除第几种元素boolDeleteList(ElemType&item,intmark);//对单链表进行有序排列mark>0升序,否则降序voidpailie(intmark=1);//对单链表进行有序输出,mark=0不排序,mark>0升序,mark<0降序voidOrderOutputList(intmark=0);};#endif//linklist3.cpp#include"linklist3.h"LinkList::LinkList()//构造函数{head=newLNode;head->next=NULL;}LinkList::~LinkList()//析构函数{LNode*p=head->next,*q;while(p){q=p->next;free(p);p=q;}}voidLinkList::ClearList()//清空单链表{LNode*p=head->next,*q;while(p){q=p->next;free(p);p=q;}head->next=NULL;}intLinkList::ListSize()//求单链表长度{LNode*p=head->next;inti=0;while(p){i++;p=p->next;}returni;}boolLinkList::ListEmpty()//检查单链表与否为空{returnListSize()==0;}//返回单链表中指定序号结点值ElemTypeLinkList::GetElem(intpos){LNode*p=head->next;inti=1;while(p){if(i++==pos)returnp->data;p=p->next;}returnhead->data;}voidLinkList::TraverseList(voidf(ElemType&))//遍历单链表{LNode*p=head->next;while(p){f(p->data);p=p->next;}}boolLinkList::FindList(ElemType&item)//从单链表中查找元素{LNode*p=head->next;while(p){if(p->data==item)return1;p=p->next;}return0;}//更新单链表中给定元素boolLinkList::UpdateList(constElemType&item,ElemTypee){LNode*p=head->next;boolflag=0;while(p){if(p->data==item){p->data=e;flag=1;}p=p->next;}returnflag;}//向单链表插入元素voidLinkList::InsertList(ElemTypeitem,intmark){LNode*q=newLNode;q->data=item;if(mark==0){q->next=head->next;head->next=q;return;}LNode*p=head;while(p->next){p=p->next;}q->next=NULL;p->next=q;}//从单链表中删除元素boolLinkList::DeleteList(ElemType&item,intmark){if(ListEmpty()||mark<1||mark>ListSize())return0;LNode*p=head,*q;for(inti=0;i<mark-1;i++)p=p->next;item=p->next->data;q=p->next->next;free(p->next);p->next=q;return1;}//对单链表进行有序排列mark>0升序,否则降序voidLinkList::pailie(intmark){ElemTypea[LEN+1];LNode*p=head->next;intk;for(k=1;p!=NULL;k++,p=p->next)a[k]=p->data;k--;for(inti=1;i<k;i++)for(intj=1;j<=k-i;j++){intt;if(mark>0&&a[j]>a[j+1]||mark<0&&a[j]<a[j+1]){t=a[j+1];a[j+1]=a[j];a[j]=t;}}p=head->next;for(intj=1;j<=k;j++,p=p->next)p->data=a[j];}//对单链表进行有序输出voidLinkList::OrderOutputList(intmark){ElemTypea[LEN+1];LNode*p=head->next;intk;for(k=1;p!=NULL;k++,p=p->next)a[k]=p->data;k--;for(inti=1;i<k;i++)for(intj=1;j<=k-i;j++){intt;if(mark>0&&a[j]>a[j+1]||mark<0&&a[j]<a[j+1]){t=a[j+1];a[j+1]=a[j];a[j]=t;}}for(intj=1;j<=k;j++)cout<<a[j]<<"";}#include<iostream.h>#include<iomanip.h>#include<stdlib.h>//#include<stdio.h>#include"linklist3.cpp"voidff(int&a)//用于遍历函数{cout<<a<<"";}voidmain(){cout<<"\nlinklist3m.cpp运营成果:\n";intinit_size,seed,xu;cout<<"一方面请构造单链表list";cout<<"\n初始化长度(1--30):";cin>>init_size;seed=150;cout<<"与否排序:(=0不排序,=1升序,=-1降序):";cin>>xu;cout<<"\n单链表list构导致功!"<<"\n它是:";list.TraverseList(ff);cout<<"\n它为空吗?(1:是;0:不是):"<<list.ListEmpty();cout<<"\n长度为:"<<list.ListSize();inti;cout<<"\n请输入你想得到第几种元素值(1--"<<init_size<<"):";cin>>i;cout<<"单链表list中第"<<i<<"值是"<<list.GetElem(i);intit;cout<<"\n请输入你想删除第几种元素值(1--"<<init_size<<"):";cin>>i;list.DeleteList(it,i);cout<<"\n单链表list删除第"<<i<<"个元素"<<"\'"<<it<<"\'"<<"后变为:";list.TraverseList(ff);//对单链表list每个数进行遍历.intnews,olds;cout<<"\n请输入要被修改元素:"；cin>>olds;cout<<"请输入修改后要变成元素:";cin>>news;list.UpdateList(olds,news);cout<<"\n修改后单链表list变为:";list.TraverseList(ff);cout<<"\n下面请构造单链表list2";cout<<"\n请输入单链表list2初始化长度(1--30):";cin>>init_size;seed=120;cout<<"请选取与否排序:(=0不排序,=1升序,=-1降序):";cin>>xu;cout<<"\n按回车键结束...";cin.get();cin.get();}1.2.5运营成果1.3约瑟夫生者死者游戏1.3约瑟夫生者死者游戏大意是：30个旅客同乘一条船，由于严重超载，加上风高浪大，危险万分；因而船长告诉乘客，只有将全船一半旅客投入海中，别的人才干幸免遇难。无奈，人们只得批准这种办法，并议定30个人围成一圈，由第一种人开始，依次报数，数到第9人，便把她投入大海中，然后从她下一种人数起，数到第9人，再将她投入大海，如此循环，直到剩余15个乘客为止。问哪些位置是将被扔下大海位置。1.3本游戏数学建模如下：假设n个旅客排成一种环形，依次顺序编号1，2，…，n。从某个指定第1号开始，沿环计数，每数到第m个人就让其出列，且从下一种人开始重新计数，继续进行下去。这个过程始终进行到剩余k个旅客为止。本游戏规定顾客输入内容涉及：1.旅客个数，也就是n值；2.离开旅客间隔数，也就是m值；3.所有旅客序号作为一组数据规定存储在某种数据构造中。本游戏规定输出内容是涉及1.离开旅客序号；2.剩余旅客序号；因此，依照上面模型分析及输入输出参数分析，可以定义一种数据构造后进行算法实现。1.3为理解决这一问题，可以用长度为30数组作为线性存储构造，并把该数组当作是一种首尾相接环形构造，那么每投入大海一种乘客，就要在该数组相应位置做一种删除标记，该单元后来就不再作为计数单元。这样做不但算法较为复杂，并且效率低，还要移动大量元素。用单循环链表解决这一问题，实现办法相对要简朴得多。一方面要定义链表结点，单循环链表结点构造与普通结点构造完全相似，只是数据域用一种整数来表达位置；然后将它们构成具备30个结点单循环链表。接下来从位置为1结点开始数，数到第8个结点，就将下一种结点从循环链表中删去，然后再从删去结点下一种结点开始数起，数到第8个结点，再将其下一种结点删去，如此进行下去，直到剩余15个结点为止。为了不失普通性，将30改为一种任意输入正整数n，而报数上限（原为9）也为一种任选正整数k。这样该算法描述如下：(1)创立具有n个结点单循环链表；(2)生着与死者选取：p指向链表第一种结点，初始i置为1；while(i<=n/2)//删除一半结点｛从p指向结点沿链迈进k-1步； 删除第k个结点（q所指向结点）； p指向q下一种结点； 输出其位置q->data; i自增1；｝(3)输出所有生者位置。1.3LinkListInitRing(intn，LinkListR)//尾插入法建立单循环链表函数{ ListNode*p，*q; intI; R=q=(LinkNode*)malloc(sizeof(LinkNode)); for(i=1;i<n;i++){ p=(LinkNode*)malloc(sizeof(LinkNode)); q->data=i; q->next=p; q=p; } p->data=n; p->next=R; R=p; returnR;}LinkListDeleteDeath(intn，intk，LinkListR)//生者与死者选取{ inti，j; ListNode*p，*q; p=R; for(i=1；i<n/2；i++){ //删除一半结点 for(j=1；j<k-1；j++) //沿链迈进k-1步 p=p->next; q=p->next; p->next=q->next; printf(“%4d”，q->data); free(q);}R=p；returnR; } voidOutRing(intn，LinkListR){//输出所有生者 inti; LinkNode*p; p=R; for(i=1;i<=n/2；i++，p=p->next){ printf(“%4d”，p->data) } }有了上述算法分析和设计之后，实现就比较简朴了。一方面要定义一种链表构造类型，然后编写一种主函数调用上面已定义好函数即可。主函数源程序如下：#include<stdio.h>#include<stdlib.h>typedefstructnode{ intdata; structnode*next;}ListNode;typedefListNode*LinkList;voidmain(){ LinkListR; intn,k; LinkListInitRing(intn，LinkListR); LinkListDeleteDeath(intn，intk，LinkListR); voidOutRing(intn，LinkListR); printf(“总人数n.报数上限k=”); scanf(“%d%d”,&n，&k); R=InitRing(n，R); R=DeleteDeath(n，k，R); OutRing(n，R);}1.3编译运营上述程序，提示：总人数n.报数上限k=输入30和9后并“回车”可得出如下成果：9182761626719301224822523212528291234101113141517201.4约瑟夫双向生死游戏1.4约瑟夫双向生死游戏是在约瑟夫生者死者游戏基本上，正向计数后反向计数，然后再正向计数。详细描述如下：30个旅客同乘一条船，由于严重超载，加上风高浪大，危险万分；因而船长告诉乘客，只有将全船一半旅客投入海中，别的人才干幸免遇难。无奈，人们只得批准这种办法，并议定30个人围成一圈，由第一种人开始，顺时针依次报数，数到第9人，便把她投入大海中，然后从她下一种人数起，逆时针数到第5人，将她投入大海，然后从她逆时针下一种人数起，顺时针数到第9人，再将她投入大海，如此循环，直到剩余15个乘客为止。问哪些位置是将被扔下大海位置。1.4本游戏数学建模如下：假设n个旅客排成一种环形，依次顺序编号1，2，…，n。从某个指定第1号开始，沿环计数，数到第m个人就让其出列，然后从第m+1个人反向计数到m-k+1个人，让其出列，然后从m-k个人开始重新正向沿环计数，再数m个人后让其出列，然后再反向数k个人后让其出列。这个过程始终进行到剩余q个旅客为止。本游戏规定顾客输入内容涉及：1.旅客个数，也就是n值；2.正向离开旅客间隔数，也就是m值；3.反向离开旅客间隔数，也就是k值；4.所有旅客序号作为一组数据规定存储在某种数据构造中。本游戏规定输出内容是涉及1.离开旅客序号；2.剩余旅客序号；因此，依照上面模型分析及输入输出参数分析，可以定义一种数据构造后进行算法实现。1.4约瑟夫双向生死游戏如果用单循环链表作为线性存储构造，就只能正向计数结点，反向计数比较困难，算法较为复杂，并且效率低。用双向循环链表解决这一问题，实现办法相对要简朴得多。为了不失普通性，将30改为一种任意输入正整数n，而正向报数上限（原为9）也为一种任选正整数m，正向报数上限（原为5）也为一种任选正整数k，。这样该算法描述如下：(1)创立具有n个结点双向循环链表；(2)生着与死者选取：p指向链表第一种结点，初始i置为1；while(i<=n/2)//删除一半结点｛从p指向结点沿链迈进m-1步； 删除第m个结点（q所指向结点）； p指向q下一种结点； 输出其位置q->data; i自增1； 从p指向结点沿链后退k-1步； 删除第k个结点（q所指向结点）； p指向q上一种结点； 输出其位置q->data; i自增1；｝(3)输出所有生者位置。1.4//双向循环链表类定义dcirlinkl.htypedefintElemType;//双向链表结点类型定义typedefstructDuLNode{ElemTypedata;structDuLNode*prior;//左指针structDuLNode*next;//右指针}DuLNode;#defineLEN20classDuLinkList{private:DuLNode*head;//指向表头指针DuLNode*curr;//当前结点指针intcount;//双向循环链表结点个数public://构造函数DuLinkList();//析构函数~DuLinkList(){deletehead;}//创立有序或无序带头结点双向循环链表DuLNode*CreateCLinkL(int,int,intmark=0);//清空单循环链表voidClearCList();//求双向循环链表长度intCListSize();//检查双向循环链表与否为空boolCListEmpty();//返回指向第pos个结点指针DuLNode*Index(intpos);//返回双向循环链表中指定序号结点值ElemTypeGetElem(intpos);//遍历双向循环链表voidTraverseCList();//当前指针curr指向pos结点并返回currDuLNode*Reset(intpos=0);//当前指针curr指向下一结点并返回DuLNode*Next();//当前指针curr指向上一结点并返回DuLNode*Prior();//判双向循环链表当前指针curr==head否boolEndOCList();//判双向循环链表当前指针curr->next与否到达表尾boolEndCList();//判双向循环链表当前指针curr->prior与否到达表尾boolPEndCList();//删除curr->next所指结点,并返回所删结点dataElemTypeDeleteNt();//从双向循环链表中查找元素boolFindCList(ElemType&item);//更新双向循环链表中给定元素boolUpdateCList(constElemType&item,ElemType&e);//向链表中第pos个结点前插入域值为item新结点voidInsertCLfront(constElemType&item,intpos);//向链表中第pos个结点后插入域值为item新结点voidInsertCLafter(constElemType&item,intpos);//从链表中删除第pos个结点并返回被删结点dataElemTypeDeleteCList(intpos);};//双向循环链表实现dcirlinkl.cpp#include<iostream.h>#include<stdlib.h>#include"dcirlinkl.h"//构造函数DuLinkList::DuLinkList(){head=newDuLNode;head->prior=head;head->next=head;curr=NULL;count=0;}//创立有序或无序带头结点双向循环链表DuLNode*DuLinkList::CreateCLinkL(intn,intm,intmark){ElemTypex,a[LEN];srand(m);for(inti=0;i<n;i++)a[i]=rand()%100;for(i=0;i<n-1;i++){intk=i;for(intj=i+1;j<n;j++)if(a[k]>a[j])k=j;if(k!=i){x=a[k];a[k]=a[i];a[i]=x;}}DuLNode*p;head=newDuLNode;head->prior=NULL;head->next=curr=p=newDuLNode;curr->prior=head;for(i=0;i<n;i++){if(mark==1)p->data=a[i];//升序elseif(mark==-1)p->data=a[n-1-i];//降序elsep->data=rand()%100;//无序if(i<n-1){curr=curr->next=newDuLNode;curr->prior=p;p=curr;}count++;}head->prior=curr;curr->next=head;returnhead;}//清空双向循环链表voidDuLinkList::ClearCList(){DuLNode*cp,*np;cp=head->next;while(cp!=head){np=cp->next;deletecp;cp=np;}head=NULL;}//求双向循环链表长度intDuLinkList::CListSize(){DuLNode*p=head->next;inti=0;while(p!=head){i++;p=p->next;}returni;}//检查双向循环链表与否为空boolDuLinkList::CListEmpty(){returnhead->next==head;}//返回指向第pos个结点指针DuLNode*DuLinkList::Index(intpos){if(pos<1){cerr<<"posisoutrange!"<<endl;exit(1);}DuLNode*p=head->next;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}if(p!=head)returnp;else{cerr<<"posisoutrange!"<<endl;returnNULL;}}//返回双向循环链表中指定序号结点值ElemTypeDuLinkList::GetElem(intpos){if(pos<1){cerr<<"posisoutrange!"<<endl;exit(1);}DuLNode*p=head->next;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}if(p!=head)returnp->data;else{cerr<<"posisoutrange!"<<endl;returnpos;}}//遍历双向循环链表voidDuLinkList::TraverseCList(){DuLNode*p=head->next;while(p!=head){cout<<setw(4)<<p->data;p=p->next;}cout<<endl;}//当前指针curr指向pos结点并返回currDuLNode*DuLinkList::Reset(intpos){DuLNode*p=curr=head->next;inti=-1;while(p!=head){i++;if(i==pos)break;p=p->next;curr=curr->next;}returncurr;}//当前指针curr指向下一结点并返回DuLNode*DuLinkList::Next(){curr=curr->next;returncurr；}//当前指针curr指向上一结点并返回DuLNode*DuLinkList::Prior(){curr=curr->prior;returncurr;}//判双向循环链表当前指针curr==head否boolDuLinkList::EndOCList(){returncurr==head;}//判双向循环链表当前指针curr->next与否到达表尾boolDuLinkList::EndCList(){returncurr->next==head;}//判双向循环链表当前指针curr->prior与否到达表尾boolDuLinkList::PEndCList(){returncurr->prior==head;}//删除curr->next所指结点,并返回所删结点dataElemTypeDuLinkList::DeleteNt(){DuLNode*p=curr->next;curr->next=p->next;curr->next->next->prior=p->prior;ElemTypedata=p->data;deletep;count--;returndata;}//从双向循环链表中查找元素boolDuLinkList::FindCList(ElemType&item){DuLNode*p=head->next;while(p!=head)if(p->data==item){item=p->data;returntrue;}elsep=p->next;returnfalse;}//更新双向循环链表中给定元素boolDuLinkList::UpdateCList(constElemType&item,ElemType&e){DuLNode*p=head->next;while(p!=head)//查找元素if(p->data==item)break;elsep=p->next;if(p==head)returnfalse;else{//更新元素p->data=e;returntrue;}}//向链表中第pos个结点前插入域值为item新结点voidDuLinkList::InsertCLfront(constElemType&item,intpos){DuLNode*newP=newDuLNode;newP->data=item;DuLNode*p=head->next;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}newP->prior=p->prior;p->prior->next=newP;newP->next=p;p->prior=newP;count++;}//向链表中第pos个结点后插入域值为item新结点voidDuLinkList::InsertCLafter(constElemType&item,intpos){DuLNode*newP=newDuLNode;newP->data=item;DuLNode*p=head->next;inti=-1;while(p!=head){i++;if(i==pos)break;p=p->next;}newP->prior=p->prior;p->prior->next=newP;newP->next=p;p->prior=newP;count++;}//从链表中删除第pos个结点并返回被删结点dataElemTypeDuLinkList::DeleteCList(intpos){if(pos<1){cerr<<"posisoutrange!"<<endl;exit(1);}DuLNode*p=head->next;ElemTypedata;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}if(p!=head){data=p->data;p->prior->next=p->next;p->next->prior=p->prior;delete[]p;count--;returndata;}elsereturnpos；}//双向循环链表测试与应用dcirlinklm.cpp#include<iomanip.h>#include"dcirlinkl.cpp"voidmain(){cout<<"dcirlinklm.cpp运营成果:\n";intm=150,i,n=10,x,it;DuLinkListp,t,q,mylink;p.CreateCLinkL(n,m,1);if(p.CListEmpty())cout<<"双向循环链表p空!\n";elsecout<<"双向循环链表p非空!\n";cout<<"双向循环链表p(升序):\n";p.TraverseCList();if(p.CListEmpty())cout<<"双向循环链表p空!\n";elsecout<<"双向循环链表p非空!\n";if(p.EndCList())cout<<"双向循环链表p满!\n";elsecout<<"双向循环链表p非满!\n";cout<<"双向循环链表t(无序):\n";t.CreateCLinkL(n-2,m);t.TraverseCList();cout<<"双向循环链表t长度:"<<t.CListSize()<<endl;cout<<"双向循环链表q(降序):\n";q.CreateCLinkL(n,m,-1);q.TraverseCList();cout<<"双向循环链表q长度:"<<q.CListSize()<<endl;cout<<"链表q第1个元素:"<<q.GetElem(1)<<endl;cout<<"链表q第1个元素地址:"<<q.Index(1)<<endl;cout<<"链表q第5个元素:"<<q.GetElem(5)<<endl;cout<<"链表q第5个元素地址:"<<q.Index(5)<<endl;cout<<"链表q第10个元素:"<<q.GetElem(10)<<endl;cout<<"链表q第10个元素地址:"<<q.Index(10)<<endl;cout<<"链表qcurr->next所指元素地址:"<<q.Next()<<endl;x=65;it=66;if(q.FindCList(x))cout<<x<<"查找成功!\n";elsecout<<x<<"查找不成功!\n";if(q.UpdateCList(x,it))cout<<x<<"更新成功!\n";elsecout<<x<<"更新不成功!\n";cout<<"更新后双向循环链表q:\n";q.TraverseCList();cout<<"插入后双向循环链表q:\n";it=100;q.InsertCLfront(it,1);q.TraverseCList();cout<<"插入后双向循环链表q:\n";it=101;q.InsertCLfront(it,5);q.TraverseCList();cout<<"插入后双向循环链表q:\n";it=102;q.InsertCLfront(it,13);q.TraverseCList();cout<<"插入后q表长:"<<q.CListSize()<<endl;cout<<"第1个数:"<<q.DeleteCList(1)<<"删除成功!\n";cout<<"删除后q表长:"<<q.CListSize()<<endl;q.TraverseCList();cout<<"第5个数:"<<q.DeleteCList(5)<<"删除成功!\n";cout<<"删除后q表长:"<<q.CListSize()<<endl;q.TraverseCList();cout<<"第11个数:"<<q.DeleteCList(11)<<"删除成功!\n";cout<<"删除后q表长:"<<q.CListSize()<<endl;q.TraverseCList();cout<<"删除数为:"<<q.DeleteNt()<<endl;cout<<"删除后q表长:"<<q.CListSize()<<endl;q.TraverseCList();cin.get();cin.get();}1.4第二章栈与队列栈和队列是两种重要线性构造。从数据构造角度上看，栈和队列也是线性表，其特殊性在于栈和队列基本操作是线性表操作子集，它们是受限线性表，因而，可称为限定性数据构造。但从数据类型角度看，它们是和线性表大不相似两类重要抽象数据类型。由于它们广泛应用在各种软件系统中，因而在面向对象程序设计中，它们是多型数据类型。本章通过迷宫旅行游戏、八皇后问题和停车场管理三个项目来学习栈和队列定义、表达办法和实现。2.1迷宫旅行游戏2.1.1项目简介迷宫只有两个门，一种门叫入口，另一种门叫出口。一种骑士骑马从入口走进迷宫，迷宫中设立诸多墙壁，对迈进方向形成了多处障碍。骑士需要在迷宫中寻找通路以到达出口。2.1.2设计思路迷宫问题求解过程可以采用回溯法即在一定约束条件下试探地搜索迈进，若迈进中受阻，则及时回头纠正错误另择通路继续搜索办法。从入口出发，按某一方向向前摸索，若能走通（未走过），即某处可达，则到达新点，否则试探下一方向；若所有方向均没有通路，则沿原路返回前一点，换下一种方向再继续试探，直到所有也许通路都摸索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能对的返回前一点以便继续从下一种方向向前试探，则需要在试探过程中保存所可以到达每一点下标及从该点迈进方向，当找到出口时试探过程就结束了。为了保证程序可以终结，调节时，必要保证曾被放弃过填数序列不被再次实验，即规定按某种有序模型生成填数序列。给解候选者设定一种被检查顺序，按这个顺序逐毕生成候选者并检查。2.1.3数据构造迷宫问题是栈应用一种典型例子。通过前面分析，咱们懂得在试探过程中为了可以沿着原路逆序回退，就需要一种数据构造来保存试探过程中曾走过点下标及从该点迈进方向，在不能继续走下去时就要退回前一点继续试探下一种方向，栈底元素是入口，栈顶元素是回退第一站，也即后走过点先退回，先走过点后退回，与栈“后进选出，先进后出”特点一致，故在该问题求解程序中可以采用栈这种数据构造。在迷宫有通路时，栈中保存点逆序连起来就是一条迷宫通路，否则栈中没有通路。2.1.4程序清单程序提示：用二维数组表达二维迷宫中各个点与否有通路，在二维迷宫里面，从出发点开始，每个点按四邻域计算，按照右、上、左、下顺序搜索一下落脚点，有路则走，无路即退回前点再从下一种方向搜索，即可构成一有序模型。栈用顺序构造实现。//求解迷宫问题maze.cpp#include<iostream.h>#include<stdlib.h>#include<time.h>enumDirection{DOWN,RIGHT,UP,LEFT};constintROWS=8,COLS=10;voidmazeTraversal(char[][COLS],constint,constint,int,int,int);voidmazeGenerator(char[][COLS],int*,int*);voidprintMaze(constchar[][COLS]);boolvalidMove(constchar[][COLS],int,int);boolcoordsAreEdge(int,int);voidmain(){cout<<"maze.cpp运营成果:\n";cout<<"迷宫问题求解:\n";charmaze[ROWS][COLS];intxStart,yStart,x,y;srand(time(0));for(intloop=0;loop<ROWS;++loop)for(intloop2=0;loop2<COLS;++loop2)maze[loop][loop2]='#';mazeGenerator(maze,&xStart,&yStart);x=xStart;//开始行y=yStart;//开始列mazeTraversal(maze,xStart,yStart,x,y,RIGHT);printMaze(maze);cin.get();}voidmazeTraversal(charmaze[][COLS],constintxCoord,constintyCoord,introw,intcol,intdirection){staticboolflag=false;//开始位置标志变量maze[row][col]='x'；//在当前位置插入xif(coordsAreEdge(row,col)&&row!=xCoord&&col!=yCoord){cout<<endl<<"成功走出迷宫!\n";return;}elseif(row==xCoord&&col==yCoord&&flag){cout<<"\n返回迷宫开始位置.\n";return;}else{flag=true;for(intmove=direction,count=0;count<4;++count,++move,move%=4)switch(move){caseDOWN://向下移动if(validMove(maze,row+1,col)){mazeTraversal(maze,xCoord,yCoord,row+1,col,LEFT);return;}break;caseRIGHT://向右移动if(validMove(maze,row,col+1)){mazeTraversal(maze,xCoord,yCoord,row,col+1,DOWN);return;}break;caseUP://向上移动if(validMove(maze,row-1,col)){mazeTraversal(maze,xCoord,yCoord,row-1,col,RIGHT);return;}break;caseLEFT://向左移动if(validMove(maze,row,col-1)){mazeTraversal(maze,xCoord,yCoord,row,col-1,UP);return;}break;}}}//有效移动boolvalidMove(constcharmaze[][COLS],intr,intc){return(r>=0&&r<=ROWS-1&&c>=0&&c<=COLS-1&&maze[r][c]!='#');}boolcoordsAreEdge(intx，inty){if((x==0||x==ROWS-1)&&(y>=0&&y<=COLS-1))returntrue;elseif((y==0||y==COLS-1)&&(x>=0&&x<=ROWS-1))returntrue;elsereturnfalse;}voidprintMaze(constcharmaze[][COLS]){for(intx=