随笔分类 - 数据结构与算法
摘要: 前面介绍了基本的排序算法，排序通常是查找的前奏操作。这篇介绍基本的查找算法。 1、符号表 符号表（Symbol Table）是一种存储键值对的数据结构，它可以将键和值关联起来。支持两种操作：插入，将一组新的键值对插入到表中；查找，根据给定的键得到响应的值。 符号表，有时又称索引，是为了加快查找速度而
Alent 阅读(350) |
摘要: 转载请注明出处：/wangyingli/p/5994256.html 这节总结一下常见的排序算法。 说明： 由于对对象元素进行排序需要实现Comparable接口，这里为了实现简单，方便测试，仅对整数进行排序（即排序的对象为整型数组）。 1、插入排序 排序
Alent 阅读(303) |
摘要: 图是一种比线性表和树更复杂的数据结构，在图中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。图是一种多对多的数据结构。 1、基本概念 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 注意
Alent 阅读(687) |
摘要: 这节总结一下优先队列的常用实现方法。 1、基本概念 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （largest in，first out）的行为特征。(百度百科) 抽象数据
Alent 阅读(493) |
摘要: 转载请注明出处：/wangyingli/p/5933257.html 前面讲到的顺序表、栈和队列都是一对一的线性结构，这节讲一对多的线性结构——树。「一对多」就是指一个元素只能有一个前驱，但可以有多个后继。 一、基本概念 树（tree）是n（n =0）个结
Alent 阅读(599) |
摘要: 转载请注明出处：/wangyingli/p/5931782.html 上一篇《 "数据结构与算法（二），线性表" 》中介绍了数据结构中线性表的两种不同实现——顺序表与链表。这一篇主要介绍线性表中比较特殊的两种数据结构——栈与队列。首先必须明确一点，栈和队列
Alent 阅读(586) |
摘要: 转载请注明出处：/wangyingli/p/5928308.html 在上一篇博客《 "数据结构与算法（二），线性表" 》中介绍了线性表的创建、插入、删除等基本操作，这一篇将总结一下链表中最常考的面试题。 目录： 1、从尾到头打印单链表 2、在O(1)时间
Alent 阅读(195) |
摘要: 转载请注明出处：/wangyingli/p/5928258.html 上一篇《 "数据结构与算法（一），概述" 》中介绍了数据结构的一些基本概念，并分别举例说明了算法的时间复杂度和空间复杂度的求解方法。这一篇主要介绍线性表。 本节内容： 一、基本概念 二、
Alent 阅读(447) |
摘要: 转载请注明出处：/wangyingli/p/5919297.html 数据结构学了有一年的时间了，但是一直没有好好的总结一下，现在回想起来，感觉好像都不怎么记得了。所以接下来一段时间我将重新学习一下，算是温故而知新了。本着「分享是一种美德」的精神，我将把我
Alent 阅读(754) |数据结构实例分析-海文库
全站搜索：
您现在的位置：&>&&>&计算机软件及应用
数据结构实例分析
数据结构实践教程1前言数据结构是计算机专业的必修。主干课程之一，它旨在使读者学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算（操作），把现实世界中的问题转化为计算机内部的表示和处理，这是一个良好的程序设计技能训练的过程。在整个教学或学习过程中，解题能力和技巧的训练是一个重要的环节。为了帮助教师讲授“数据结构”，满足指导和评价“课程设计”的需要，为了帮助和指导读者更好地学习数据结构这门课程，我们特编写了这本《数据结构实践教程》辅助教材，旨在弥补课堂教学和实验中的不足，帮助学生充分理解和巩固所学的基本概念、原理和方法，达到融会贯通、举一反三的目的。实践证明，理解课程内容与较好地解决实际问题之间存在着明显差距，而算法设计完成的质量与基本的程序设计素质的培养是密切相关的。要想理解和巩固所学的基本概念。原理和方法，牢固地掌握所学的基本知识。基本技能，达到融会贯通。举一反三的目的，就必须多做。多练。多见（见多识广）。正是为了达到上述目的，书中用一些实际的应用，对一些重要的数据结构和算法进行解读。经过循序渐进地训练，就可以使读者掌握更多的程序设计技巧和方法，提高分析。解决问题的能力。本书根据学生的基础知识和兴趣爱好将内容分为基础篇和提高篇两个部分。第一部分基础篇精选出适当的、与实际生活结合密切的课程设计实例加以分析实现。第二部分提高篇旨在使读者通过运用数据结构知识及复杂算法去解决现实世界中的一些实际问题。本书依据数据结构课程教学大纲要求，同时又独立于具体的教科书，既重视实践应用，又重视理论分析，本书的主要特点有：●本书精选出来的实例项目经典、实用、具有一定的趣味性，其内容丰富、涉及面广、难易适当，能给读者以启发，达到让读者掌握相关知识和开阔视野的目的●为了提高学生分析问题、解决问题的能力，本书对实例项目进行分析，其设计思路清晰流畅，值得参考。●本书不仅仅是对照数据结构课程教学大纲举些例子说明数据结构能解决什么问题，而是通过分析具体的实例项目，得到对数据组织关系的需求，从而选择某个数据结构适应一些特定的问题和算法，并说明使用这种数据结构的优缺点。●所有实例项目都给出了参考算法和源程序代码并在TurboC和VisualC++6.0环境下运行通过。由于作者水平有限、时间仓促，本书难免存在一些缺点和错误，恳请广大读者及同行们批评指正。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程序清单32.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项目简介24.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运行结果3第六章查找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知识要点47.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航空客运定票系统58.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运行测试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];}ElemT//学号//姓名//成绩1.1.4程序清单#include&iostream.h&#include&iomanip.h&#include&malloc.h&#include&string.h&#defineMaxListSize20#defineEQUAL1typedefstructSTU{charstuno[10];charname[10];}ElemT4classList{private://线性表的数组表示ElemTypeelem[MaxListSize];intMaxSpublic://输入学生数据voidinit(List**L,intms);//删除所有学生数据voidDestroyList(List&L){free(&L);}//将顺序表置为空表voidClearList(){length=0;}//判断顺序表是否为空表boolListEmpty(){returnlength==0;}//判断顺序表是否为满boolListFull(){returnlength==MaxS}//删除某个学生数据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=}intList::ListLength(){}boolList::ListDelete(intmark,ElemType&e){inti,j;if(ListEmpty())if(mark&0){//删除表头元素e=elem[0];for(i=1;i&i++)elem[i-1]=elem[i];}else//删除表尾元素if(mark&0)e=elem[length-1];else{//删除值为e的元素for(i=0;i&i++)if(strcmp(elem[i].name,e.name)==0)if(i&=length)elsee=elem[i];for(j=i+1;j&j++)elem[j-1]=elem[j];}length--;}voidList::ListTraverse(){for(inti=0;i&i++){cout&&setw(8)&&elem[i].cout&&setw(10)&&elem[i].cout&&setw(9)&&elem[i].cout&&setw(8)&&elem[i].score&&}}voidList::GetElem(inti,ElemType*e)6{*e=elem[i];}boolList::EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1-&name,e2-&name))if(strcmp(e1-&stuno,e2-&stuno))if(e1-&age!=e2-&age)if(e1-&score!=e2-&score)}boolList::Less_EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1-&name,e2-&name)&=0)}boolList::LocateElem(ElemTypee,inttype){switch(type){caseEQUAL:for(i=0;i&i++)if(EqualList(&elem[i],&e))default:}}//修改学生数据boolList::UpdateList(ElemType&e,ElemTypee1){for(inti=0;i&i++)if(strcmp(elem[i].name,e.name)==0){elem[i]=e1;}}7boolList::ListInsert(inti,ElemType&e){ElemType*p,*q;if(i&1||i&length+1)q=&elem[i-1];for(p=&elem[length-1];p&=q;--p)*(p+1)=*p;*q=e;++}//对学生成绩按升序或降序输出voidList::printlist(intmark){int*b=newint[length];inti,k;cout&&&if(mark!=0){for(i=0;i&i++)b[i]=i;for(i=0;i&i++){k=i;for(intj=i+1;j&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&i++){cout&&setw(8)&&elem[b[i]].cout&&setw(10)&&elem[b[i]].cout&&setw(9)&&elem[b[i]].cout&&setw(8)&&elem[b[i]].score&&}}else{for(i=0;i&i++){cout&&setw(8)&&elem[i].cout&&setw(10)&&elem[i].cout&&setw(9)&&elem[i].cout&&setw(8)&&elem[i].score&&}}}姓名学号成绩\n&;8voidmain(){cout&&&linelist1m.cpp运行结果:\n&;ElemTypee,e1,e2,e3,e4,e5,e6;List*La,*Lb,*Lc;cout&&&首先调用插入函数.\n&;La-&init(&La,4);strcpy(e1.name,&stu1&);strcpy(e1.stuno,&100001&);e1.age=22;e1.score=88;La-&ListInsert(1,e1);strcpy(e2.name,&stu2&);strcpy(e2.stuno,&100002&);e2.age=21;e2.score=79;La-&ListInsert(2,e2);strcpy(e3.name,&stu3&);strcpy(e3.stuno,&100003&);e3.age=19;e3.score=87;La-&ListInsert(3,e3);La-&printlist(0);cout&&&表La长:&&&La-&ListLength()&&cin.get();Lb-&init(&Lb,4);strcpy(e4.name,&zmofun&);strcpy(e4.stuno,&100001&);e4.age=20;e4.score=94;Lb-&ListInsert(1,e4);strcpy(e5.name,&bobjin&);strcpy(e5.stuno,&100002&);e5.age=23;9e5.score=69;Lb-&ListInsert(2,e5);strcpy(e6.name,&stu1&);strcpy(e6.stuno,&100001&);e6.age=22;e6.score=88;Lb-&ListInsert(3,e6);Lb-&printlist(0);cout&&&表Lb长:&&&Lb-&ListLength()&&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运行结果首先建立学生信息管理，输出结果为：姓名Stu1Stu2Stu3学号成绩其次查询学号为100002的学生的成绩，输出结果为：91再次调用插入函数，插入Stu4成功！输入结果为：姓名Stu1学号10成绩Stu2Stu3Stu5最后删除Stu2成果！输出结果为：姓名Stu1Stu3Stu4学号成绩查询不及格的学生，输出结果为：Stu1.2考试报名管理1.2.1项目简介考试报名工作给各高校报名工作带来了新的挑战，给教务管理部门增加了很大的工作量，报名数据手工录入既费时又会不可避免地出现错误，同时也给不少学生以可乘之机。本项目是对考试报名管理的简单模拟，用菜单选择方式完成下列功能：输入考生信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生信息。1.2.2设计思路本项目的实质是完成对考生信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。1.2.3数据结构本项目的数据是一组考生信息，每条考生信息由准考证号、姓名、性别、年龄、报考类别等信息组成，这组考生信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据也具有线性表中数据元素的性质，所以该系统的数据可以采用线性表来存储。从上一节的例子中可见，线性表的顺序存储结构的特点是逻辑关系相邻的两个元素在物理位置上也相邻，因此可以随机存储表中任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，从另一个方面来看，这个特点也铸成了这种存储结构的弱点：在做插入或11删除操作时，需要移动大量元素。为克服这一缺点，我们引入另一种存储形式DD链式存储。链式存储是线性表的另一种表示方法，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构的弱点，但同时也失去了顺序表可随机存取的特点。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。事实上，链表插入、删除运算的快捷是以空间代价来换取时间。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。本项目对考生数据主要进行插入、删除、修改等操作，所以采用链式存储结构比较适合。用结构体类型定义每个考生信息，故该单链表中的每个结点的结构可描述为：typedefstructexaminee{charexamno[10];charname[10];charexamtype[5];}ElemT//成绩//准考证号//姓名1.2.4程序清单//单链表的类定义linklist3.h#ifndeflinklist3H#definelinklist3H#defineLEN30//定义ElemType为inttypedefintElemT//单链表中结点的类型typedefstructLNode{ElemT//值域LNode*//指针域}LNclassLinkList{LNode*public://构造函数12LinkList();//析构函数~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=newLNhead-&next=NULL;}LinkList::~LinkList()//析构函数13{LNode*p=head-&next,*q;while(p){q=p-&free(p);p=q;}}voidLinkList::ClearList()//清空单链表{LNode*p=head-&next,*q;while(p){q=p-&free(p);p=q;}head-&next=NULL;}intLinkList::ListSize()//求单链表长度{LNode*p=head-&inti=0;while(p){i++;p=p-&}}boolLinkList::ListEmpty()//检查单链表是否为空{returnListSize()==0;}//返回单链表中指定序号的结点值ElemTypeLinkList::GetElem(intpos){LNode*p=head-&inti=1;while(p){if(i++==pos)returnp-&p=p-&}returnhead-&14}voidLinkList::TraverseList(voidf(ElemType&))//遍历单链表{LNode*p=head-&while(p){f(p-&data);p=p-&}}boolLinkList::FindList(ElemType&item)//从单链表中查找元素{LNode*p=head-&while(p){if(p-&data==item)return1;p=p-&}return0;}//更新单链表中的给定元素boolLinkList::UpdateList(constElemType&item,ElemTypee){LNode*p=head-&boolflag=0;while(p){if(p-&data==item){p-&data=e;flag=1;}p=p-&}}//向单链表插入元素voidLinkList::InsertList(ElemTypeitem,intmark){LNode*q=newLNq-&data=if(mark==0){q-&next=head-&head-&next=q;}LNode*p=while(p-&next)15{p=p-&}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-&item=p-&next-&q=p-&next-&free(p-&next);p-&next=q;return1;}//对单链表进行有序排列mark&0升序,否则降序voidLinkList::pailie(intmark){ElemTypea[LEN+1];LNode*p=head-&for(k=1;p!=NULL;k++,p=p-&next)a[k]=p-&k--;for(inti=1;i&k;i++)for(intj=1;j&=k-i;j++){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-&for(intj=1;j&=k;j++,p=p-&next)p-&data=a[j];}16//对单链表进行有序输出voidLinkList::OrderOutputList(intmark){ElemTypea[LEN+1];LNode*p=head-&for(k=1;p!=NULL;k++,p=p-&next)a[k]=p-&k--;for(inti=1;i&k;i++)for(intj=1;j&=k-i;j++){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,cout&&&首先请构造单链表list&;cout&&&\n初始化长度(1--30):&;cin&&init_seed=150;cout&&&是否排序:(=0不排序,=1升序,=-1降序):&;cin&&17cout&&&\n单链表list构造成功!&&&&\n它是:&;list.TraverseList(ff);cout&&&\n它为空吗?(1:是;0:不是):&&&list.ListEmpty();cout&&&\n长度为:&&&list.ListSize();cout&&&\n请输入你想得到第几个元素的值(1--&&&init_size&&&):&;cin&&i;cout&&&单链表list中第&&&i&&&的值是&&&list.GetElem(i);cout&&&\n请输入你想删除第几个元素的值(1--&&&init_size&&&):&;cin&&i;list.DeleteList(it,i);cout&&&\n单链表list删除第&&&i&&&个元素&&&&\'&&&it&&&\'&&&&后变为:&;list.TraverseList(ff);//对单链表list每个数进行遍历.intnews,cout&&&\n请输入要被修改的元素:&;cin&&cout&&&请输入修改后要变成的元素:&;cin&&list.UpdateList(olds,news);cout&&&\n修改后单链表list变为:&;list.TraverseList(ff);cout&&&\n下面请构造单链表list2&;cout&&&\n请输入单链表list2初始化长度(1--30):&;cin&&init_seed=120;cout&&&请选择是否排序:(=0不排序,=1升序,=-1降序):&;cin&&cout&&&\n按回车键结束...&;cin.get();cin.get();}1.2.5运行结果181.3约瑟夫生者死者游戏1.3.1项目简介约瑟夫生者死者游戏的大意是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。1.3.2设计思路本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。本游戏的要求用户输入的内容包括：1.旅客的个数，也就是n的值；2.离开旅客的间隔数，也就是m的值；3.所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1.离开旅客的序号；2.剩余旅客的序号；所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行算法实现。1.3.3数据结构为了解决这一问题，可以用长度为30的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每投入大海一个乘客，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较为复杂，而且效率低，还要移动大量的元素。用单循环链表解决这一问题，实现的方法相对要简单得多。首先要定义链表结点，单循环链表的结点结构与一般的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成具有30个结点的单循环链表。接下来从位置为1的结点开始数，数到第8个结点，就将下一个结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第8个结点，再将其下一个结点删去，如此进行下去，直到剩下15个结点为止。19为了不失一般性，将30改为一个任意输入的正整数n，而报数上限（原为9）也为一个任选的正整数k。这样该算法描述如下：(1)创建含有n个结点的单循环链表；(2)生着与死者的选择：p指向链表的第一个结点，初始i置为1；while(i&=n/2)//删除一半的结点｛从p指向的结点沿链前进k-1步；删除第k个结点（q所指向的结点）；p指向q的下一个结点；输出其位置q-&i自增1；｝(3)输出所有生者的位置。1.3.4程序清单LinkListInitRing(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;20//生者与死者的选择//尾插入法建立单循环链表函数ListNode*p,*q;p=R;for(i=1;i&n/2;i++){//删除一半结点for(j=1;j&k-1;j++)//沿链前进k-1步p=p-&q=p-&p-&next=q-&printf(“%4d”,q-&data);free(q);}R=p;returnR;}voidOutRing(intn,LinkListR){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{structnode*}ListNtypedefListNode*LinkLvoidmain(){LinkListR;intn,k;LinkListInitRing(intn,LinkListR);LinkListDeleteDeath(intn,intk,LinkListR);voidOutRing(intn,LinkListR);21//输出所有生者printf(“总人数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后并“回车”可得出如下结果：93012241.4约瑟夫双向生死游戏1.4.1项目简介约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上，正向计数后反向计数，然后再正向计数。具体描述如下：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，顺时针依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，逆时针数到第5人，将他投入大海，然后从他逆时针的下一个人数起，顺时针数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。1.4.2设计思路本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，数到第m个人就让其出列，然后从第m+1个人反向计数到m-k+1个人，让其出列，然后从m-k个人开始重新正向沿环计数，再数m个人后让其出列，然后再反向数k个人后让其出列。这个过程一直进行到剩下q个旅客为止。本游戏的要求用户输入的内容包括：1.旅客的个数，也就是n的值；2.正向离开旅客的间隔数，也就是m的值；223.反向离开旅客的间隔数，也就是k的值；4.所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1.离开旅客的序号；2.剩余旅客的序号；所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行算法实现。1.4.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-&i自增1；从p指向的结点沿链后退k-1步；删除第k个结点（q所指向的结点）；p指向q的上一个结点；输出其位置q-&i自增1；｝(3)输出所有生者的位置。231.4.4程序清单//双向循环链表的类定义dcirlinkl.htypedefintElemT//双向链表结点的类型定义typedefstructDuLNode{ElemTstructDuLNode*//左指针structDuLNode*//右指针}DuLN#defineLEN20classDuLinkList{private:DuLNode*//指向表头的指针DuLNode*//当前结点指针//双向循环链表的结点个数public://构造函数DuLinkList();//析构函数~DuLinkList(){}//创建有序或无序的带头结点的双向循环链表DuLNode*CreateCLinkL(int,int,intmark=0);//清空单循环链表voidClearCList();//求双向循环链表长度intCListSize();//检查双向循环链表是否为空boolCListEmpty();//返回指向第pos个结点的指针DuLNode*Index(intpos);//返回双向循环链表中指定序号的结点值ElemTypeGetElem(intpos);//遍历双向循环链表24voidTraverseCList();//当前指针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=newDuLNhead-&prior=25head-&next=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=newDuLNhead-&prior=NULL;head-&next=curr=p=newDuLNcurr-&prior=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=newDuLNcurr-&prior=p;p=}count++;}head-&prior=curr-&next=}//清空双向循环链表voidDuLinkList::ClearCList(){DuLNode*cp,*26cp=head-&while(cp!=head){np=cp-&cp=}head=NULL;}//求双向循环链表长度intDuLinkList::CListSize(){DuLNode*p=head-&inti=0;while(p!=head){i++;p=p-&}}//检查双向循环链表是否为空boolDuLinkList::CListEmpty(){returnhead-&next==}//返回指向第pos个结点的指针DuLNode*DuLinkList::Index(intpos){if(pos&1){cerr&&&posisoutrange!&&&exit(1);}DuLNode*p=head-&inti=0;while(p!=head){i++;if(i==pos)p=p-&}if(p!=head)else{cerr&&&posisoutrange!&&&returnNULL;}}//返回双向循环链表中指定序号的结点值ElemTypeDuLinkList::GetElem(intpos){if(pos&1){cerr&&&posisoutrange!&&&exit(1);}DuLNode*p=head-&27inti=0;while(p!=head){i++;if(i==pos)p=p-&}if(p!=head)returnp-&else{cerr&&&posisoutrange!&&&}}//遍历双向循环链表voidDuLinkList::TraverseCList(){DuLNode*p=head-&while(p!=head){cout&&setw(4)&&p-&p=p-&}cout&&}//当前指针curr指向pos结点并返回currDuLNode*DuLinkList::Reset(intpos){DuLNode*p=curr=head-&inti=-1;while(p!=head){i++;if(i==pos)p=p-&curr=curr-&}}//当前指针curr指向下一结点并返回DuLNode*DuLinkList::Next(){curr=curr-&}//当前指针curr指向上一结点并返回DuLNode*DuLinkList::Prior(){curr=curr-&28}//判双向循环链表当前指针curr==head否boolDuLinkList::EndOCList(){returncurr==}//判双向循环链表当前指针curr-&next是否到达表尾boolDuLinkList::EndCList(){returncurr-&next==}//判双向循环链表当前指针curr-&prior是否到达表尾boolDuLinkList::PEndCList(){returncurr-&prior==}//删除curr-&next所指结点,并返回所删结点的dataElemTypeDuLinkList::DeleteNt(){DuLNode*p=curr-&curr-&next=p-&curr-&next-&next-&prior=p-&ElemTypedata=p-&count--;}//从双向循环链表中查找元素boolDuLinkList::FindCList(ElemType&item){DuLNode*p=head-&while(p!=head)if(p-&data==item){item=p-&}elsep=p-&}//更新双向循环链表中的给定元素boolDuLinkList::UpdateCList(constElemType&item,ElemType&e){DuLNode*p=head-&while(p!=head)//查找元素if(p-&data==item)29elsep=p-&if(p==head)else{//更新元素p-&data=e;}}//向链表中第pos个结点前插入域值为item的新结点voidDuLinkList::InsertCLfront(constElemType&item,intpos){DuLNode*newP=newDuLNnewP-&data=DuLNode*p=head-&inti=0;while(p!=head){i++;if(i==pos)p=p-&}newP-&prior=p-&p-&prior-&next=newP;newP-&next=p;p-&prior=newP;count++;}//向链表中第pos个结点后插入域值为item的新结点voidDuLinkList::InsertCLafter(constElemType&item,intpos){DuLNode*newP=newDuLNnewP-&data=DuLNode*p=head-&inti=-1;while(p!=head){i++;if(i==pos)p=p-&}newP-&prior=p-&p-&prior-&next=newP;newP-&next=p;p-&prior=newP;30count++;}//从链表中删除第pos个结点并返回被删结点的dataElemTypeDuLinkList::DeleteCList(intpos){if(pos&1){cerr&&&posisoutrange!&&&exit(1);}DuLNode*p=head-&ElemTinti=0;while(p!=head){i++;if(i==pos)p=p-&}if(p!=head){data=p-&p-&prior-&next=p-&p-&next-&prior=p-&delete[]p;count--;}}//双向循环链表的测试与应用dcirlinklm.cpp#include&iomanip.h&#include&dcirlinkl.cpp&voidmain(){cout&&&dcirlinklm.cpp运行结果:\n&;intm=150,i,n=10,x,DuLinkListp,t,q,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&;31if(p.EndCList())cout&&&双向循环链表p满!\n&;elsecout&&&双向循环链表p非满!\n&;cout&&&双向循环链表t(无序):\n&;t.CreateCLinkL(n-2,m);t.TraverseCList();cout&&&双向循环链表t的长度:&&&t.CListSize()&&cout&&&双向循环链表q(降序):\n&;q.CreateCLinkL(n,m,-1);q.TraverseCList();cout&&&双向循环链表q的长度:&&&q.CListSize()&&cout&&&链表q的第1个元素:&&&q.GetElem(1)&&cout&&&链表q的第1个元素地址:&&&q.Index(1)&&cout&&&链表q的第5个元素:&&&q.GetElem(5)&&cout&&&链表q的第5个元素地址:&&&q.Index(5)&&cout&&&链表q的第10个元素:&&&q.GetElem(10)&&cout&&&链表q的第10个元素地址:&&&q.Index(10)&&cout&&&链表q的curr-&next所指元素地址:&&&q.Next()&&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()&&cout&&&第1个数:&&&q.DeleteCList(1)&&&删除成功!\n&;32cout&&&删除后q表长:&&&q.CListSize()&&q.TraverseCList();cout&&&第5个数:&&&q.DeleteCList(5)&&&删除成功!\n&;cout&&&删除后q表长:&&&q.CListSize()&&q.TraverseCList();cout&&&第11个数:&&&q.DeleteCList(11)&&&删除成功!\n&;cout&&&删除后q表长:&&&q.CListSize()&&q.TraverseCList();cout&&&删除的数为:&&&q.DeleteNt()&&cout&&&删除后q表长:&&&q.CListSize()&&q.TraverseCList();cin.get();cin.get();}1.4.5运行结果33第二章栈与队列栈和队列是两种重要的线性结构。从数据结构角度上看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛应用在各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。本章通过迷宫旅行游戏、八皇后问题和停车场管理三个项目来学习栈和队列的定义、表示方法和实现。2.1迷宫旅行游戏2.1.1项目简介迷宫只有两个门，一个门叫入口，另一个门叫出口。一个骑士骑马从入口走进迷宫，迷宫中设置很多墙壁，对前进方向形成了多处障碍。骑士需要在迷宫中寻找通路以到达出口。2.1.2设计思路迷宫问题的求解过程可以采用回溯法即在一定的约束条件下试探地搜索前进，若前进中受阻，则及时回头纠正错误另择通路继续搜索的方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要在试探过程中保存所能够到达的每一点的下标及从该点前进的方向，当找到出口时试探过程就结束了。为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。2.1.3数据结构迷宫问题是栈应用的一个典型例子。通过前面分析，我们知道在试探过程中为了能够沿着原路逆序回退，就需要一种数据结构来保存试探过程中曾走过的点的下标及从该点前进的方向，在不能继续走下去时就要退回前一点继续试探下一个方向，栈底元素是入口，栈顶元34素是回退的第一站，也即后走过的点先退回，先走过的点后退回，与栈的“后进选出，先进后出”特点一致，故在该问题求解的程序中可以采用栈这种数据结构。在迷宫有通路时，栈中保存的点逆序连起来就是一条迷宫的通路，否则栈中没有通路。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=xS//开始行y=yS//开始列35mazeTraversal(maze,xStart,yStart,x,y,RIGHT);printMaze(maze);cin.get();}voidmazeTraversal(charmaze[][COLS],constintxCoord,constintyCoord,introw,intcol,intdirection){staticboolflag=//开始位置标志变量maze[row][col]='x';//在当前位置插入xif(coordsAreEdge(row,col)&&row!=xCoord&&col!=yCoord){cout&&endl&&&成功走出迷宫!\n&;}elseif(row==xCoord&&col==yCoord&&flag){cout&&&\n返回迷宫开始位置.\n&;}else{flag=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);}caseRIGHT://向右移动if(validMove(maze,row,col+1)){mazeTraversal(maze,xCoord,yCoord,row,col+1,DOWN);}caseUP://向上移动if(validMove(maze,row-1,col)){mazeTraversal(maze,xCoord,yCoord,row-1,col,RIGHT);}caseLEFT://向左移动if(validMove(maze,row,col-1)){mazeTraversal(maze,xCoord,yCoord,row,col-1,UP);}}}}36//有效移动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))elseif((y==0||y==COLS-1)&&(x&=0&&x&=ROWS-1))}voidprintMaze(constcharmaze[][COLS]){for(intx=0;x&ROWS;++x){for(inty=0;y&COLS;++y)cout&&maze[x][y]&&'';cout&&'\n';}cout&&}voidmazeGenerator(charmaze[][COLS],int*xPtr,int*yPtr){inta,x,y,entry,do{entry=rand()%4;exit=rand()%4;}while(entry==exit);//确定入口位置if(entry==0){*xPtr=1+rand()%(ROWS-2);//避免死角*yPtr=0;maze[*xPtr][*yPtr]='0';}elseif(entry==1){*xPtr=0;*yPtr=1+rand()%(COLS-2);maze[*xPtr][*yPtr]='0';}elseif(entry==2){*xPtr=1+rand()%(ROWS-2);37*yPtr=COLS-1;maze[*xPtr][*yPtr]='0';}else{*xPtr=ROWS-1;*yPtr=1+rand()%(COLS-2);maze[*xPtr][*yPtr]='0';}//确定出口位置if(exit==0){a=1+rand()%(ROWS-2);maze[a][0]='0';}elseif(exit==1){a=1+rand()%(COLS-2);maze[0][a]='0';}elseif(exit==2){a=1+rand()%(ROWS-2);maze[a][COLS-1]='0';}else{a=1+rand()%(COLS-2);maze[ROWS-1][a]='0';}for(intloop=1;loop&(ROWS-2)*(COLS-2);++loop){x=1+rand()%(ROWS-2);//添加圆点到迷宫y=1+rand()%(COLS-2);maze[x][y]='0';}}2.1.5运行结果迷宫问题求解:返回迷宫开始位置.##0########0##000####000###xx##00###x#x####x#xx#xx38###xxxxxx####x#xxx############2.2八皇后问题2.2.1项目简介八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8′8格的国际象棋棋盘上，安放八个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即任意两个皇后都不能处于同一行、同一列或同一条对角线上，求解有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法得出结论，有92种摆法。2.2.2设计思路八皇后在棋盘上分布的各种可能的格局数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i-1个皇后处于不同列和不同对角线位置上即可。解决该问题采用回溯法。首先将第一个皇后放于第一行第一列，然后依次在下一行上放置下一个皇后，直到八个皇后全放置安全。在放置每一个皇后时，都依次对每一列进行检测，首先检测待第一列是否与已放置的皇后冲突，如不冲突，则将皇后放置在该列，否则，选择该行的下一列进行检没。如整行的八列都冲突，则回到上一行，重新选择位置，依次类推。2.2.3数据结构八皇后问题是栈应用的另一个典型例子。通过前面分析，我们知道在对八个皇后的位置进行试探的过程中，可能遇到在某一行上的所有位置都不安全的情况，这时就要退回到上一行，重新摆放在上一行放置的皇后。为了能够对上一行的皇后继续寻找下一个安全位置，就必须记得该皇后目前所在的位置，即需要一种数据结构来保存从第一行开始的每一行上的皇后所在的位置。在放置进行不下去时，已经放置的皇后中后放置的皇后位置先被纠正，先放置的皇后后被纠正，与栈的“后进选出，先进后出”特点一致，故在该问题求解的程序中可以采用栈这种数据结构。在八个皇后都放置安全时，栈中保存的数据就是八个皇后在八行上的列位置。392.2.4程序清单程序提示：用二维数组表示8′8格的国际象棋棋盘。栈用顺序结构实现。#include&iostream.h&#include&stdio.h&intline[8],answer=0;voidshow()//显示摆放的结果.{inti,j;for(i=0;i&8;i++){for(j=0;j&8;j++){if(line[i]==j)cout&&&Q&;elsecout&&&*&;}cout&&}answer++;cout&&cout&&answer&&getchar();}intJudge(intt)//判断摆放的位置是否正确,不正确返回1,正确返回0.{inti,n=0;for(i=0;i&t;i++){if(line[i]==line[t]){n=1;}if(line[i]+i==line[t]+t){n=1;}40if(line[i]-i==line[t]-t){n=1;}}}voidcontrol(intn)//主要控制函数.{intt=8;for(line[n]=0;line[n]&t;line[n]++){if(Judge(n))elseif(n!=7)control(n+1);elseshow();}}intmain()//主函数.{control(0);cout&&answer&&return0;}2.2.5运行结果Q***********Q**********Q*****Q****Q***********Q**Q******41***Q****12.3停车场管理2.3.1项目简介设停车场是一个可以停放n辆汽车的南北方向的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应缴纳的费用和它在停车场内停留的时间。2.3.2设计思路停车场的管理流程如下：①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进入停车场；如果停车场已满，则车辆进入便道等候。②当车辆要求出栈时，先让在它之后进入停车场的车辆退出停车场为它让路，再让该车退出停车场，让路的所有车辆再按其原来进入停车场的次序进入停车场。之后，再检查在便道上是否有车等候，有车则让最先等待的那辆车进入停车场。2.3.3数据结构由于停车场只有一个大门，当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，先进停车场的后退出，后进车场的先退出，符合栈的“后进先出，先进后出”的操作特点，因此，可以用一个栈来模拟停车场。而当停车场满后，继续来到的其它车辆只能停在便道上，根据便道停车的特点，先排队的车辆先离开便道进入停车场，符合队列的“先进先出，后进后出”的操作特点，因此，可以用一个队列来模拟便道。排在停车场中间的车辆可以提出离开停车场，并且停车场内在要离开的车辆之后到达的车辆都必须先离开停车场为它让路，然后这些车辆依原来到达停车场的次序进入停车场，因此在前面已设的一个栈和一个队列的基础上，还需要有一个地方保存为了让路离开停车场的车辆，由于先退出停车场的后进入停车场，所以很显然保存让路车辆的场地也应该用一个栈来模拟。因此，本题求解过程中需用到两个栈和一个队列。栈以顺序结构实现，队列以链表结构实现。422.3.4程序清单程序提示：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。#include&stdio.h&#include&stdlib.h&#include&iostream.h&#include&string.h&#include&math.h&#definesize1//停车场位置数//模拟停车场的堆栈的性质；typedefstructzanlind{//汽车车号intar_//汽车到达时间}zanItypedefstruct{zanInode*//停车场的堆栈底zanInode*//停车场的堆栈顶intstacksize_}//堆栈的基本操作；voidinitstack(stackhead&L)//构造一个空栈{L.base=(zanInode*)malloc(size*sizeof(zanlind));if(!L.base)exit(0);L.top=L.L.stacksize_curren=0;}voidpush(stackhead&L,zanInodee)//把元素e压入s栈{*L.top++=e;L.stacksize_curren++;43}voidpop(stackhead&L,zanInode&e)//把元素e弹出s栈{if(L.top==L.base){cout&&&停车场为空!!&;}e=*--L.L.stacksize_curren--;}//模拟便道的队列的性质；typedefstructduilie{intar_//汽车车号//汽车到达时间structduilie*}*typedefstruct{//便道的队列的对头//便道的队列的队尾}//队列的基本操作；voidinitqueue(linkqueue&q)//构造一个空队列{q.front=q.rear=(queueptr)malloc(sizeof(duilie));if(!q.front||!q.rear)exit(0);q.front-&next=NULL;q.length=0;}voidenqueue(linkqueue&q,intnumber,intar_time)//把元素的插入队列（属性为number，ar_time）{44p=(queueptr)malloc(sizeof(duilie));if(!p)exit(0);p-&number=p-&ar_time=ar_p-&next=NULL;q.rear-&next=p;q.rear=p;q.length++;}voidpopqueue(linkqueue&q,queueptr&w)//把元素的插入队列（属性为number，ar_time）{if(q.front==q.rear){cout&&&停车场的通道为空!!&&&}p=q.front-&w=p;q.front-&next=p-&q.length--;if(q.rear==p)q.front=q.}voidjinru(stackhead&st,linkqueue&q)//对进入停车场的汽车的处理；{intnumber,time_a;cout&&&车牌为：&;cin&&cout&&&进场的时刻:&;cin&&time_a;if(st.stacksize_curren&2){zanIe.number=45e.ar_time=time_a;push(st,e);cout&&&该车已进入停车场在:&&&st.stacksize_curren&&&号车道&&&endl&&}else{enqueue(q,number,time_a);cout&&&停车场已满，该车先停在便道的第&&&q.length&&&个位置上&&&}}voidlikai(stackhead&st,stackhead&sl,linkqueue&q)//对离开的汽车的处理；{//st堆栈为停车场，sl堆栈为倒车场intnumber,time_d,flag=1,money,cout&&&车牌为：&;cin&&cout&&&出场的时刻：&;cin&&time_d;zanInodee,q_to_s;while(flag)//找到要开出的车，并弹出停车场栈{pop(st,e);push(sl,e);if(e.number==number){flag=0;money=(time_d-e.ar_time)*2;arrivaltime=e.ar_}}pop(sl,e);//把临时堆栈的第一辆车（要离开的）去掉；while(sl.stacksize_curren)//把倒车场的车倒回停车场{46//q为便道队列pop(sl,e);push(st,e);}if(st.stacksize_curren&2&&q.length!=0)//停车场有空位，便道上的车开进入停车场{popqueue(q,w);q_to_s.ar_time=time_d;q_to_s.number=w-&push(st,q_to_s);cout&&&车牌为&&&q_to_s.number&&&的车已从通道进入停车场,所在的停车位为:&&&st.stacksize_curren&&endl&&}cout&&&\ncout&&&收据&&&======================车牌号:&&&number&&cout&&&===================================================&&&cout&&&|进车场时刻|出车场时刻|停留时间|应付（元）|&&&cout&&&====================================================&&&cout&&&|&&&arrivaltime&&&|oney&&&|&&&cout&&&-----------------------------------------------------&&&endl&&&&&time_d&&&|&&&time_d-arrivaltime&&&|&&&m}voidmain(){intm=100;//进入或离开的标识；stackheadsting,//停车场和临时倒车场堆栈的定义；initstack(sting);initstack(slinshi);initqueue(line);while(m){cout&&&\n**停车场管理程序**&&&47//队列的定义；//构造停车场堆栈sting//构造倒车场堆栈slinshi//构造便道队列linecout&&&===================================================&&&cout&&&****&&&cout&&&**A---汽车进车场D---汽车出车场**&&&cout&&&**cout&&&****&&&E---退出程序**&&&cout&&&===================================================&&&cout&&&请选择:(A,D,E):&;cin&&switch(flag){case'A':jinru(sting,line);//汽车进车场case'D':likai(sting,slinshi,line);//汽车出车场case'E':exit(0);}m--;}}2.3.5运行结果48第三章串、数组和广义表3.1单词检索统计程序3.1.1项目简介给定一个文3.1.2设计思路本项目的设计要求可以分为三个部分实现：其一，建立一个文1.建立文件的实现思路是：(1)定义一个串变量；(2)定义文(3)输入文件名，打开该文件；(4)循环读入文本行，写入文while(不是文件输入结束){读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；｝(5)关闭文件。2.给定单词计数的实现思路是：该功能需要用到模式匹配算法，逐行扫描文串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到越来越广泛的应用。在串的基本操作中，在主串中查找模式串的模式匹配算法是文本处理中最常用、最重要的操作之一，称为模式匹配或串匹配，就是求子串在主串中首次出现的位置。朴素模式匹配算法的基本思路是将给定字串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符位置开始比较，而且需要从主串的任一位置检索匹配字符串。其实现过程如下：49(1)输入要检索的文(2)输入要检索统计的单词；(3)循环读文串匹配函数进行计数。具体描述如下：while(不是文件结束){读入一行并到串中；求出串长度；模式匹配函数计数；｝(4)关闭文件，输出统计结果。3.检索单词出现在文这个设计要求同上一个设计类似，但是要相对复杂一些。其实现过程描述如下：(1)输入要检索的文(2)输入要检索统计的单词；(3)行计数器置初值0；(4)while(不是文件结束){读入一行到指定串中；求出串长度；行单词计数器0；调用模式匹配函数匹配单词定位、该行匹配单词计数；行号计数器加1；if(行单词计数器!=0)输出行号、该行有匹配单词的个数以及相应的位置；}4.主控菜单程序的结构该部分内容如下：(1)头文件包含；(2)菜单选项包括：1.建立文件2.单词计数3.单词定位4.退出程序(3)选择1-4执行相应的操作，其他字符为非法。503.1.3数据结构如果在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可.但在多数非数值处理的程序中，串也以变量的形式出现。串有三种机内表示方法：定长顺序存储表示、堆分配存储表示和串的块链存储表示。定长顺序存储表示类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照予定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组描述。――串的定长顺序存储表示――#defineMAXSTRLEN255//用户可在255以内定义最大串长typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串的长度串的实际长度可在这预定义长度的范围内随意，超过于定义长度的串值则被舍去，称之为&截断&。对串长有两种表示方法:一是如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，如PASCAL语言中的串类型采用这种表示方法;二是在串值后面加一个不计入串长的结束标记字符，如在有的C语言中以&\0&表示串值的终结。此时的串长为隐含值，显然不便于进行某些串操作。在这种存储结构表示时实现串求子串操作如下：求子串SubStrmg(&Sub,S,pos,len)过程即为复制字符序列的过程，将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中。显然，本操作不会有需截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回ERROR。其算法描述如算法4.3所示。StatusSubString(Sstring&Sub,SstringS,intpos,intlen){//用Sub返回串s第pos个字符起长度为len的子串。其中1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1.if(poss[0]||lenS[0]-pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=returnOK;}//EndofSubString由此可见，在顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度基于复制的字符序列的长度。本项目主要实现子串的检索和定位操作，所以用定长顺序存储表示比较简单易行。3.1.4程序清单//字符串的模式匹配Findstr.cpp#include&iostream.h&51#include&iomanip.h&#include&stdio.h&#include&stdlib.h&#include&string.h&#defineMAXSTRLEN64voidGetNext(charT[MAXSTRLEN],int(&next)[64]){inti,j;i=1;next[1]=j=0;while(i&(int)T[0])if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];for(j=1;j&(int)T[0];j++){printf(&next[%d]=%-3d&,j,next[j]);if((j)%5==0)printf(&\n&);}cout&&}voidGetNext(charT[MAXSTRLEN],int(&next)[64],intm){inti,j;i=0;next[0]=-1;for(j=1;j&m;j++){i=next[j-1];while(T[j]!=T[i+1]&&i&=0)i=next[i];if(T[j]==T[i+1])next[j]=i+1;elsenext[j]=-1;}for(j=0;j&=m;j++){printf(&next[%d]=%-3d&,j,next[j]);if((j+1)%5==0)printf(&\n&);}cout&&}voidGetNextVal(charT[MAXSTRLEN],int(&next)[64]){inti,j;i=1;next[1]=j=0;while(i&(int)T[0])if(j==0||T[i]==T[j]){++i;++j;if(T[i]!=T[j])next[i]=j;52elsenext[i]=next[j];}elsej=next[j];for(i=1;i&(int)T[0];i++){printf(&next[%d]=%-3d&,i,next[i]);if(i%5==0)cout&&}cout&&}intIndexKMP(charS[MAXSTRLEN],charT[MAXSTRLEN],int(&next)[64]){inti,j,n,m;i=j=1;n=(int)S[0];m=(int)T[0];while((i&n||j&m)&&T[j]!='\0'&&S[i]!='\0')if(j==0||S[i]==T[j]){++i;++j;}elsej=next[j];if(j&=m)returni+1-m;elsereturn0;}intIndexKMP(charS[MAXSTRLEN],charT[MAXSTRLEN],int(&next)[64],intpos){inti,j;i=j=1;while((i&(int)S[0]||j&(int)T[0])&&T[j]!='\0'&&S[i]!='\0')if(j==0||S[i]==T[j]){++i;++j;}elsej=next[j];if(j&=(int)T[0])returni+1-(int)T[0];elsereturn0;}intIndexKMP(charS[MAXSTRLEN],charT[MAXSTRLEN],int(&next)[64],intn,intm){inti,j;i=j=0;while(i&n&&j&m)if(S[i]==T[j]){++i;++j;}elseif(j==0)i++;elsej=next[j-1]+1;if(j&m)return-1;elsereturni-m+1;}intIndexBF(charS[MAXSTRLEN],charT[MAXSTRLEN],intpos){inti,j;i=j=1;53while(i&=S[0]&&j&=T[0])if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j&T[0])returni-T[0];elsereturn0;}voidmain(){printf(&Findstr.cpp运行结果:\n&);intIndex,N,M,next[64]={0};chars[MAXSTRLEN],t[MAXSTRLEN];printf(&GetNext-IndexKMP的结果:\n&);printf(&输入主串s:&);gets(s);printf(&输入模式串t:&);gets(t);N=strlen(s);M=strlen(t);printf(&主串s长=%d\n&,N);printf(&模式串t长=%d\n&,M);GetNext(t,next,M);Index=IndexKMP(s,t,next,N,M);if(Index!=-1)printf(&模式串在主串的位置从第%d个字符开始\n&,Index);elseprintf(&主串s中不含模式串t\n&);printf(&GetNext-IndexKMP的结果:\n&);s[0]=N;t[0]=M;GetNext(t,next);Index=IndexKMP(s,t,next,1);if(Index)printf(&模式串在主串的位置从第%d个字符开始\n&,Index);elseprintf(&主串s中不含模式串t\n&);printf(&GetNextVal-IndexKMP的结果:\n&);GetNextVal(t,next);Index=IndexKMP(s,t,next,1);if(Index)printf(&模式串在主串的位置从第%d个字符开始\n&,Index);54elseprintf(&主串s中不含模式串t\n&);printf(&GetNext-IndexKMP的结果:\n&);GetNext(t,next);Index=IndexKMP(s,t,next);if(Index)printf(&模式串t在主串s中的位置从第%d个字符开始\n&,Index);elseprintf(&主串s中不含模式串t\n&);printf(&IndexBF的结果:\n&);Index=IndexBF(s,t,1);if(Index)printf(&模式串t在主串s中的位置从第%d个字符开始\n&,Index);elseprintf(&主串s中不含模式串t\n&);cin.get();}3.1.5运行结果3.2Internet网络通路管理3.2.1项目简介本项目是对Interert网络通路管理的简单模拟，以完成建立Interert网络通路、修改Interert网络通路信息和删除Interert网络通路信息等功能。3.2.2设计思路本项目的实质是完成对Interert网络通路信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。3.2.3数据结构Interert网络通路中的主机之间关系可以是任意的，任意两个站点之间都可能相关。而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。所以55可以用图形结构来表示n个主机以及主机之间可能设置的Interert网络通路，其中网的顶点表示网络通路中的主机，边表示两个主机之间的网络通路，赋予边的权值表示相应的距离。可以用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的相邻关系。即用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。假设图中顶点数为n，网的邻接矩阵的定义为，当vi到vj有弧相邻接时，ai,j的值应为该弧上的权值，否则为∞。将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。图的数组(邻接矩阵)存储表示constINFINITY=INT_MAX;constMAX_VERTEX_NUM=20;//最大值∞//最大顶点个数typedefenum{DG,DN,AG,AN}GraphK//类型标志{有向图,有向网,无向图,无向网}typedefstructArcCell{VRT//弧的定义//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType*//该弧相关信息的指针}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点信息AdjMintvexnum,GraphK}MG//表示顶点之间关系的二维数组//图的当前顶点数和弧(边)数//图的种类标志3.2.4程序清单//图的相关数据类型的定义graph.h//最多顶点数constintMaxV=10;//最大权值constintMaxValue=99;//定义邻接表中的边结点类型structedgenode{//邻接点域//权值域56edgenode*//指向下一个边结点的链域};//定义邻接表类型typedefedgenode**//邻接矩阵类定义classAdjMatrix{private:charg[MaxV];//顶点信息数组//当前顶点数intGA[MaxV][MaxV];//定义邻接矩阵GAintnumE;//当前边数public://构造函数,初始化图的邻接矩阵AdjMatrix(intn,intk2);//判断图空否boolGraphEmpty(){returnsize==0;}//取当前顶点数intNumV(){}//取当前边数intNumEdges(){returnnumE;}//取顶点i的值charGetValue(constinti);//取弧&v1,v2&的权intGetWeight(constintv1,constintv2);//在位置pos处插入顶点VvoidInsertV(constchar&V,intpos);//插入弧&v1,v2&,权为weightvoidInsertEdge(constintv1,constintv2,intweight);//删除顶点i与顶点i相关的所有边charDeleteVE(constinti);//删除弧&v1,v2&voidDeleteEdge(constintv1,constintv2);//建立图的邻接矩阵voidCreateMatrix(intn,intk1,intk2);//k1为0则无向否则为有向,k2为0则无权否则为有权57//从初始点vi出发深度优先搜索由邻接矩阵表示的图voiddfsMatrix(bool*&visited,inti,intn,intk2);//从初始点vi出发广度优先搜索由邻接矩阵表示的图voidbfsMatrix(bool*&visited,inti,intn,intk2);//由图的邻接矩阵得到图的邻接表voidgraphChange(adjlist&GL,intn,intk2);//检查输入的边序号是否越界,若越界则重输voidCheck(intn,int&i,int&j);//由图的邻接矩阵建立图voidCreatgraph(intn,intk2);//对非连通图进行深度优先搜索voiddfsMatrix(intn,intk2);//对非连通图进行广度优先搜索voidbfsMatrix(intn,intk2);};//图的相关运算的实现graph.cpp#include&graph.h&//构造函数,初始化图的邻接矩阵AdjMatrix::AdjMatrix(intn,intk2){inti,j;if(k2==0){//初始化无(有)向无权图for(i=0;i&n;i++)for(j=0;j&n;j++)GA[i][j]=0;}else{//初始化无(有)向有权图for(i=0;i&n;i++)for(j=0;j&n;j++)if(i==j)GA[i][j]=0;elseGA[i][j]=MaxV}size=numE=0;}//建立图的邻接矩阵voidAdjMatrix::CreateMatrix(intn,intk1,intk2)//k1为0则无向否则为有向,k2为0则无权否则为有权58{inti,j,k,e,w;cout&&&输入图的总边数:&;cin&&e;if(k1==0&&k2==0){//建立无向无权图cout&&&输入&&&e&&&条无向无权边的起点和终点序号!&&&for(k=1;k&=e;k++){cin&&i&&j;Check(n,i,j);GA[i][j]=GA[j][i]=1;}}elseif(k1==0&&k2!=0){//建立无向有权图cout&&&输入&&&e&&&条无向带权边的起点和终点序号及权值!&&&for(k=1;k&=e;k++){cin&&i&&j&&w;Check(n,i,j);GA[i][j]=GA[j][i]=w;}}elseif(k1!=0&&k2==0){//建立有向无权图cout&&&输入&&&e&&&条有向无权边的起点和终点序号!&&&for(k=1;k&=e;k++){cin&&i&&j;Check(n,i,j);GA[i][j]=1;}}elseif(k1!=0&&k2!=0){//建立有向有权图cout&&&输入&&&e&&&条有向有权边的起点和终点序号及权值!&&&for(k=1;k&=e;k++){cin&&i&&j&&w;Check(n,i,j);GA[i][j]=w;}}numE=e;cout&&&创建后的邻接矩阵:\n&;for(i=0;i&n;i++){for(j=0;j&n;j++)cout&&setw(4)&&GA[i][j];59cout&&}}//从初始点vi出发深度优先搜索由邻接矩阵表示的图voidAdjMatrix::dfsMatrix(bool*&visited,inti,intn,intk2){cout&&g[i]&&':'&&i&&&visited[i]=&;//标记vi已被访问过for(intj=0;j&n;j++)//依次搜索vi的每个邻接点if(k2==0){if(i!=j&&GA[i][j]!=0&&!visited[j])dfsMatrix(visited,j,n,k2);}elseif(i!=j&&GA[i][j]!=MaxValue&&!visited[j])dfsMatrix(visited,j,n,k2);}//从初始点vi出发广度优先搜索由邻接矩阵表示的图voidAdjMatrix::bfsMatrix(bool*&visited,inti,intn,intk2){constintMaxLength=30;//定义一个队列q,其元素类型应为整型intq[MaxLength]={0};//定义队首和队尾指针intfront=0,rear=0;//访问初始点vicout&&g[i]&&':'&&i&&&&;//标记初始点vi已访问过visited[i]=//将已访问过的初始点序号i入队q[++rear]=i;//当队列非空时进行循环处理while(front!=rear){//删除队首元素,第一次执行时k的值为ifront=(front+1)%MaxLintk=q[front];//依次搜索vk的每一个可能的邻接点for(intj=0;j&n;j++)if(k2==0)60{if(k!=j&&GA[k][j]!=0&&!visited[j]){//访问一个未被访问过的邻接点vjcout&&g[j]&&':'&&j&&&visited[j]=&;//标记vj已访问过rear=(rear+1)%MaxL//顶点序号j入队q[rear]=j;}}elseif(k!=j&&GA[k][j]!=MaxValue&&!visited[j]){//访问一个未被访问过的邻接点vjcout&&g[j]&&':'&&j&&&visited[j]=&;//标记vj已访问过rear=(rear+1)%MaxL//顶点序号j入队q[rear]=j;}}}//检查输入的边序号是否越界,若越界则重输voidAdjMatrix::Check(intn,int&i,int&j){while(1){if(i&0||i&=n||j&0||j&=n)cout&&&输入有误,请重输!&;cin&&i&&j;}}//由图的邻接矩阵得到图的邻接表voidAdjMatrix::graphChange(adjlist&GL,intn,intk2){inti,j;if(k2==0){for(i=0;i&n;i++){for(j=0;j&n;j++)if(GA[i][j]!=0){edgenode*p=p-&adjvex=j;61p-&next=GL[i];GL[i]=p;cout&&'('&&i&&','&&p-&adjvex&&&)&;}cout&&}}else{for(i=0;i&n;i++){for(j=0;j&n;j++)if(GA[i][j]!=0&&GA[i][j]!=MaxValue){edgenode*p=p-&adjvex=j;p-&weight=GA[i][j];p-&next=GL[i];GL[i]=p;cout&&'('&&i&&','&&p-&adjvex&&','&&p-&weight&&&)&;}cout&&}}}//由图的邻接矩阵建立图voidAdjMatrix::Creatgraph(intn,intk2){inti,j,k,m=0;if(k2==0){for(i=0;i&n;i++){k=i;for(j=0;j&n;j++)if(GA[i][j]!=0)if(k==i&&m&n){g[m]='A'+m;size++;cout&&g[m]&&'('&&i&&','&&j&&&)&;m++;}}cout&&}else{for(i=0;i&n;i++){k=i;for(j=0;j&n;j++)if(GA[i][j]!=0&&GA[i][j]!=MaxValue)if(k==i&&m&n){g[m]='A'+m;size++;62cout&&g[m]&&'('&&i&&','&&j&&','&&GA[i][j]&&&)&;m++;}}cout&&}g[n]='\0';}//取顶点i的值charAdjMatrix::GetValue(constinti){if(i&0||i&size){cerr&&&参数i越界!\n&;exit(1);}returng[i];}//取弧&v1,v2&的权intAdjMatrix::GetWeight(constintv1,constintv2){if(v1&0||v1&size||v2&0||v2&size){cerr&&&参数v1或v2越界!\n&;exit(1);}returnGA[v1][v2];}//在位置pos处插入顶点VvoidAdjMatrix::InsertV(constchar&V,intpos){if(size==MaxV){cerr&&&表已满,无法插入!\n&;exit(1);}if(pos&0||pos&size){cerr&&&参数pos越界!\n&;exit(1);}for(i=i&i--)g[i]=g[i-1];g[pos]=V;size++;}//插入弧&v1,v2&,权为weightvoidAdjMatrix::InsertEdge(constintv1,constintv2,intweight){if(v1&0||v1&size||v2&0||v2&size){cerr&&&参数v1或v2越界!\n&;exit(1);}GA[v1][v2]=63numE++;}//删除顶点v与顶点v相关的所有边charAdjMatrix::DeleteVE(constintv){for(inti=0;i&i++)for(intj=0;j&j++)if((i==v||j==v)&&GA[i][j]&0&&GA[i][j]&MaxValue){GA[i][j]=MaxVnumE--;}if(size==0){cerr&&&表已空,无元素可删!\n&;exit(1);}if(v&0||v&size-1){cerr&&&参数v越界!\n&;exit(1);}chartemp=g[v];for(i=v;i&size-1;i++)g[i]=g[i+1];size--;g[size]='\0';}//删除弧&v1,v2&voidAdjMatrix::DeleteEdge(constintv1,constintv2){if(v1&0||v1&size||v2&0||v2&size||v1==v2){cerr&&&参数v1或v2出错!\n&;exit(1);}GA[v1][v2]=MaxVnumE--;}//对非连通图进行深度优先搜索voidAdjMatrix::dfsMatrix(intn,intk2){bool*vis=newbool[NumV()];for(inti=0;i&NumV();i++)vis[i]=for(i=0;i&NumV();i++)if(!vis[i])dfsMatrix(vis,i,n,k2);delete[]}//对非连通图进行广度优先搜索64voidAdjMatrix::bfsMatrix(intn,intk2){bool*vis=newbool[NumV()];for(inti=0;i&NumV();i++)vis[i]=for(i=0;i&NumV();i++)if(!vis[i])bfsMatrix(vis,i,n,k2);delete[]}//图的相关运算的测试graphM.cpp#include&iostream.h&#include&iomanip.h&#include&stdlib.h&#include&graph.cpp&voidmain(){cout&&&graphM.cpp运行结果:\n&;//定义图的点数及搜索起始点序号等intn,k,i;//k1为0则无向否则为有向,k2为0则无权否则为有权intk1,k2;//标记已访问过的点bool*//定义邻接表adjlistAL;cout&&&输入图的点数n=&;cin&&n;AL=newedgenode*[n];vis=newbool[n];if(!vis){cout&&&申请堆内存失败!\n&;exit(1);}for(i=0;i&n;i++)vis[i]=cout&&&输入选择无向(权)与有向(权)图的值k1,k2:&;cin&&k1&&k2;//定义邻接矩阵AdjMatrixA(n,k2);A.CreateMatrix(n,k1,k2);65cout&&&出发点Vk的序号=&;cin&&k;cout&&&\n输出邻接矩阵相应图的每个顶点:\n&;A.Creatgraph(n,k2);cout&&&当前的顶点数为:&&&A.NumV()&&cout&&&当前的边数为:&&&A.NumEdges()&&cout&&&图的深度优先搜索顺序:\n&;A.dfsMatrix(vis,k,n,k2);for(i=0;i&n;i++)vis[i]=cout&&&\n图的广度优先搜索顺序:\n&;A.bfsMatrix(vis,k,n,k2);cout&&&\n输出邻接表的每个邻接点:\n&;for(i=0;i&n;i++)vis[i]=A.graphChange(AL,n,k2);delete[]A.DeleteEdge(0,2);A.DeleteEdge(2,0);cout&&&当前的顶点数为:&&&A.NumV()&&cout&&&当前的边数为:&&&A.NumEdges()&&cout&&&图的深度优先搜索顺序:\n&;A.dfsMatrix(n,k2);cout&&&\n图的广度优先搜索顺序:\n&;A.bfsMatrix(n,k2);cin.get();cin.get();}3.2.5运行结果graphM.cpp运行结果:输入图的点数n=7输入选择无向(权)与有向(权)图的值k1,k2:01输入图的总边数:1266输入12条无向带权边的起点和终点序号及权值!251261521621创建后的邻接矩阵:
199999909999出发点Vk的序号=0输出邻接矩阵相应图的每个顶点:A(0,1,1)B(0,2,1)C(1,0,1)D(1,3,1)E(1,4,1)F(2,0,1)G(2,5,1)当前的顶点数为:7当前的边数为:12图的深度优先搜索顺序:A:0B:1D:3E:4C:2F:5G:6图的广度优先搜索顺序:A:0B:1C:2D:3E:4F:5G:6输出邻接表的每个邻接点:(0,1,1)(0,2,1)(1,0,1)(1,3,1)(1,4,1)(2,0,1)(2,5,1)(2,6,1)(3,1,1)(4,1,1)(5,2,1)(6,2,1)当前的顶点数为:7当前的边数为:10图的深度优先搜索顺序:A:0B:1D:3E:4C:2F:5G:6图的广度优先搜索顺序:A:0B:1D:3E:4C:2F:5G:667第四章树和二叉树树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。本章通过三个模拟项目来学习树及二叉树的存储结构及其各种操作，首先通过使用有关树的操作实现家谱管理，其次通过使用有关线索二叉树的操作实现图书目录分类管理，最后通过哈夫曼树的应用实现图像压缩编码优化。4.1家谱管理4.1.1项目简介家谱（或称族谱）是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史，地志，族谱）之一，属珍贵的人文资料，对于历史学、民俗学、人口学、社会学和经济学的深入研究，均有其不可替代的独特功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。4.1.2设计思路本项目的实质是完成对家谱成员信息的建立、查找、插入、修改、删除等功能，可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。4.1.3数据结构因为家族中的成员之间存在一个对多个的层次结构关系，所以不能用上面讲的线性表来表示。家谱从形状上看像一颗倒长的树，所以用树结构来表示家谱比较适合。树型结构是一类非常重要的非线性数据结构，直观看来，树是以分支关系定义的层次结构。可以二叉链表作为树的存储结构，链表中的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，固该表示法又称二叉树表示法，或孩子兄弟表示法。孩子兄弟表示法是一种链式存储结构，它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其具体的结点结构为：firstChilddata68nextSibling其中，firstchild为指向该结点第一个孩子的指针，nextsibling为指向该结点下一个兄弟，elem
是数据元素内容，举例如下：其存储形式定义如下：typedefstructCSLinklist{EstructCSLinklist*firstchild,*}CSLinklist,*CST4.1.4程序清单//树的孩子兄弟表示法为存储结构的结构体Tree.htemplate&classT&classTtemplate&classT&structTreeNode{friendclassTree&T&;//树类为友元private:TreeNode&T&*firstC//第一个孩子结点指针域TreeNode&T&*nextS//下一个兄弟结点指针域public:T//数据域//构造函数TreeNode(Tvalue,TreeNode&T&*fc=NULL,TreeNode&T&*ns=NULL):data(value),firstChild(fc),nextSibling(ns){}//访问指针域的成员函数TreeNode&T&*&FirstChild(){returnfirstC}TreeNode&T&*&NextSibling(){returnnextS}};//树类template&classT&classTree{private:TreeNode&T&*//根结点指针69TreeNode&T&*//当前结点指针//显示以t为先根结点的树的数据域voidPreOrderTree(TreeNode&T&*&t);//显示以t为后根结点的树的数据域voidPosOrderTree(TreeNode&T&*&t);//使当前结点为t所指结点intCurrent(TreeNode&T&*&t);//在树root中回溯查找结点s的双亲结点TreeNode&T&*SearchParent(TreeNode&T&*&root,TreeNode&T&*&s);public://构造函数与析构函数Tree(){root=curr=NULL;}~Tree(){DeleteSubTree(root);}//使根结点为当前结点intRoot();//使当前结点的双亲结点为当前结点intParent();//使当前结点的第一个孩子结点为当前结点intFirstChild();//使当前结点的兄弟结点为当前结点intNextSibling();//把valve插入到当前结点的最后一个结点voidInsertChild(Tvalue);//删除以t为根结点的子树voidDeleteSubTree(TreeNode&T&*&t);//删除当前结点的第i个孩子结点intDeleteChild(inti);//删除以root为根结点的子树的第i个孩子结点intDeleteChild1(inti);//按先根遍历次序显示树的数据域值voidDisplayTree();//按后根遍历次序显示树的数据域值voidDisplayTree1();};70//树类的实现Tree.cpptemplate&classT&voidTree&T&::DeleteSubTree(TreeNode&T&*&t){if(t==NULL)TreeNode&T&*q=t-&firstChild,*p;while(q!=NULL){p=q-&nextSDeleteSubTree(q);q=p;}printf(&释放:%2c&,t-&data);}template&classT&intTree&T&::Current(TreeNode&T&*&t){if(t==NULL)return0;curr=t;return1;}template&classT&intTree&T&::Root(){if(root==NULL){curr=NULL;return0;}returnCurrent(root);}template&classT&intTree&T&::FirstChild(){if(curr!=NULL&&curr-&firstChild!=NULL)returnCurrent(curr-&firstChild);elsereturn0;}template&classT&intTree&T&::NextSibling(){if(curr!=NULL&&curr-&nextSibling!=NULL)returnCurrent(curr-&nextSibling);71elsereturn0;}template&classT&intTree&T&::Parent(){if(curr==NULL){curr=return0;}TreeNode&T&*p=SearchParent(root,curr);if(p==NULL)return0;elsereturnCurrent(p);}template&classT&TreeNode&T&*Tree&T&::SearchParent(TreeNode&T&*&root,TreeNode&T&*&s){if(root==NULL)returnNULL;if(root-&FirstChild()==s||root-&NextSibling()==s)TreeNode&T&*p;if((p=SearchParent(root-&FirstChild(),s))!=NULL)if((p=SearchParent(root-&NextSibling(),s))!=NULL)returnNULL;}template&classT&voidTree&T&::InsertChild(Tvalue){TreeNode&T&*newNode=newTreeNode&T&(value);if(root==NULL)//当为空树时{root=curr=newN}if(curr-&firstChild==NULL)//当当前结点无孩子时curr-&firstChild=newNelse//当当前结点有孩子时{TreeNode&T&*p=curr-&firstCwhile(p-&nextSibling!=NULL)p=p-&nextSp-&nextSibling=newN}Current(newNode);//使新建立的结点成为当前结点72}template&classT&intTree&T&::DeleteChild(inti){TreeNode&T&*r=NULL;if(i==1)//当删除当前结点的第一棵子树时{r=curr-&firstCif(r==NULL)return0;//要删除子树为空时返回curr-&firstChild=r-&nextS//脱链要删除的子树}else{intk=1;TreeNode&T&*p=curr-&firstCwhile(p!=NULL&&k&=i-1)//寻找要删除子树的指针{p=p-&nextSk++;}if(p!=NULL)//寻找到要删除的子树的指针{r=p-&nextSif(r!=NULL)p-&nextSibling=r-&nextSelsereturn0;}elsereturn0;}DeleteSubTree(r);return1;}template&classT&intTree&T&::DeleteChild1(inti){if(root==NULL)return0;//当为空树时TreeNode&T&*r=NULL,*q=root-&firstCif(i==1&&q!=NULL)//当第一结点有孩子时{r=root-&firstCroot-&firstChild=r-&nextS//脱链要删除的子树}else//要删除第一结点外的其他子树时73//当删除当前结点的其他子树时{intk=1;TreeNode&T&*p=root-&firstCwhile(p!=NULL&&k&=i-1)//寻找要删除子树的指针{p=p-&nextSk++;}if(p!=NULL)//寻找到要删除的子树的指针{r=p-&nextSif(r!=NULL)p-&nextSibling=r-&nextS//脱链要删除的子树elsereturn0;}elsereturn0;}DeleteSubTree(r);//调用函数执行删除return1;}template&classT&voidTree&T&::PreOrderTree(TreeNode&T&*&t){if(t==NULL)cout&&setw(2)&&t-&//显示根结点数据if(t-&firstChild!=NULL)//先根遍历子树PreOrderTree(t-&firstChild);if(t-&nextSibling!=NULL)PreOrderTree(t-&nextSibling);}template&classT&voidTree&T&::DisplayTree(){PreOrderTree(root);}template&classT&voidTree&T&::DisplayTree1(){PosOrderTree(root);}template&classT&voidTree&T&::PosOrderTree(TreeNode&T&*&t)74{if(t==NULL)if(t-&firstChild!=NULL)//后根遍历子树PosOrderTree(t-&firstChild);printf(&%2c&,t-&data);//显示根结点数据if(t-&nextSibling!=NULL)PosOrderTree(t-&nextSibling);}//树类相关操作的测试TreeM.cpp#include&iostream.h&#include&iomanip.h&#include&stdlib.h&#include&conio.h&#include&stdio.h&#include&Tree.h&#include&Tree.cpp&voidmain(){printf(&TreeM.cpp运行结果:\n&);Tree&char&t;t.InsertChild('A');for(i=0;