《数据结构》课程实验指导书

《数据构造》课程河南理工大学地理信息系统专业2023年九月前言GIS绍一些典型算法，以及算法的时间、空间效率分析。表示方法〔存储构造〕，以及相关根本操作的算法实现；把握典型算法的设计思GISGIS等后续课程和研制开发各种系统和应用软件打下扎实的理论与实践根底。实现要求，并对算法的实现进展提示，期望对同学们完成试验有所帮助。名目TOC\o“1-1“\h\z\u\l“_TOC_250005“试验一线性表的链表实现类的设计… 1\l“_TOC_250004“试验二挨次栈的自定义类设计… 2\l“_TOC_250003“试验三字符串的操作类设计… 3\l“_TOC_250002“试验四树和二叉树的自定义类的设计… 4\l“_TOC_250001“试验五图的最短路径算法设计… 5\l“_TOC_250000“试验六自定义类应用综合设计… 6试验一 线性表的链表实现类的设计试验类型：验证性 试验学时：2学时一、试验目的：1C++面对对象类的设计和用VC++上机调试线性表的根本方法；2、把握线性表的根本操作，如插入、删除、查找，以及线性表合并等运算在链式存储构造上的运算；并能够运用线性表根本操作解决问题，实现相应算法。二、试验要求：1C++完成类的设计及根本操作算法并上机调试通过。2三、试验内容:设计你的线性表的链式存储构造类，编程实现通过键盘输入数据建立链表、查找、插入结点、删除结点、显示链表以及两链表的合并运算等操作。测试数据例如：(1)L1={0,5,9,10,12,12,17,20,24}构造链表；1255；生成L2={33,45,50}的链表并将它与L1注:也可以完成课本其次章习题2.14〔P85〕的代码设计作为本次课堂试验内容。四、仪器设备:计算机、VC++编译环境五、试验方法：用C++语言设计类，并实现相关类的根本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、试验步骤：123七、试验结果处理：对程序调试中的问题要进展总结。八、试验留意事项：独立完成试验及试验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、试验报告要求：本门课程试验报告格式见附件1，鼓舞手写，可以打印。试验二 挨次栈的自定义类设计试验类型：验证性 试验学时：2学时一、试验目的：1、把握用VC++上机调试通过栈的挨次存储构造类的设计；2、把握挨次栈的根本操作，如进栈、出栈、推断栈空和栈满，取栈顶元素等运算在挨次存储构造上的运算；并能够运用栈的根本操作解决问题，实现相应算法。二、试验要求：1C++完成类的设计及根本操作算法并上机调试通过。2三、试验内容:设计你的栈的挨次存储构造类，编程实现栈的根本操作。栈中的数据元素类型最好为字符类型，便利今后对字符串的算法设计和应用。测试数据例如：以“ABCDEFG”的字符串挨次进栈；以适宜挨次出栈得到序列“CDBAGFE”；取栈顶元素得到‘F’；进栈直到栈满和出栈直到栈空，检验对这两种情形的正确推断和处理。注:也可以完成课本第三章习题3.13〔P132〕的代码设计作为本次课堂试验内容。四、仪器设备:计算机、VC++编译环境五、试验方法：用C++语言设计类，并实现相关类的根本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、试验步骤：123七、试验结果处理：对程序调试中的问题要进展总结。八、试验留意事项：独立完成试验及试验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、试验报告要求：本门课程试验报告格式见附件1，鼓舞手写，可以打印。试验三 字符串的操作类设计试验类型：验证性 试验学时：2学时一、试验目的：12、把握实现字符串的根本操作，如求串的长度、串的比较、复制、串的连接，取子串、子串匹配定位和串替换等运算。二、试验要求：1C++完成类的设计并上机调试通过。2三、试验内容:用堆安排存储表示串，实现串的比较、复制、串的连接，取子串、子串匹配定位和串替换等根本操作。测试数据例如：以“abcde”构造一个串s1，以“gabcdef”构造另一个串s2；比较s1和s2s2中定位s1复制s2s1注:也可以完成课本第四章习题4.17〔P185〕的代码设计作为本次课堂试验内容。四、仪器设备:计算机、VC++编译环境五、试验方法：用C++语言设计类，并实现相关类的根本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、试验步骤：123七、试验结果处理：对程序调试中的问题要进展总结。八、试验留意事项：独立完成试验及试验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、试验报告要求：本门课程试验报告格式见附件1，鼓舞手写，可以打印。试验四 树和二叉树的自定义类的设计试验类型：验证性 试验学时：2学时一、试验目的：1进一步把握树的构造及非线性特点，递归特点和动态性。2稳固对指针的使用和二叉树的三种遍历方法、建立方法及树的输入输出。二、试验要求：1C++完成类的设计并上机调试通过。2三、试验内容:中序遍历的非递归算法。测试数据例如：以abcdefghijklmn构造一棵二叉树；分别输出其先序、中序和后序遍历结果；注:也可以完成课本第五章习题5.37〔P250〕的代码设计作为本次课堂试验内容。四、仪器设备:计算机、VC++编译环境五、试验方法：用C++语言设计类，并实现相关类的根本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、试验步骤：123七、试验结果处理：对程序调试中的问题要进展总结。八、试验留意事项：独立完成试验及试验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、试验报告要求：本门课程试验报告格式见附件1，鼓舞手写，可以打印。试验五图的最短路径算法设计试验类型：验证性 试验学时：2学时一、试验目的：了解最短路径的概念，把握求最短路径的方法(Dijkstra算法或Floyd二、试验要求：1C++完成图的相关类及算法的设计并上机调试通过。2三、试验内容:6个结点的带权有向图，并求顶点V0到其它顶点的最短路径。测试数据由同学们自行选择。注:也可以完成课本第八章习题8.23〔P395〕的代码设计作为本次课堂试验内容。四、仪器设备:计算机、VC++编译环境五、试验方法：用C++语言设计类，并实现相关类的根本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、试验步骤：123七、试验结果处理：对程序调试中的问题要进展总结。八、试验留意事项：独立完成试验及试验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、试验报告要求：本门课程试验报告格式见附件1，鼓舞手写，可以打印。试验六自定义类应用综合设计试验类型：综合性 试验学时：2学时一、试验目的：12、通过具体的有实际应用意义的问题解决和对前面设计的类的使用进一步提高程序设计力气和算法设计、分析力气。3、考察学生的程序设计中的规律思维力气和觉察软件开发人才。二、试验要求：12三、试验内容:从下面给出的题目中选做其中的一题〔多做可加分〕：约瑟夫环问题1〕问题描述：有编号为1,2…n的n个人按顺时针方向围坐一圈，每人持有一个正整数密码。开头给定一个正整数m，从第一个人按顺时针方向自1开头报数，报到m列，不再参与报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开头重12〕试验要求:承受链式存储构造实现。3)实现提示：用链式存储解决此问题时可以承受循环链表。停车场治理问题问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场的早晚依次从停车场最里面对大门口处停放(最先到达的第一辆车放在停车场的最里面)。假设停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车走开，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必需先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应依据它在停车场内停留的时间长短交费。假设停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且照旧保持在便道上等待的车辆的次序。编写程序模拟该停车场的治理。试验要求:要求程序输出每辆车到达后的停车位置〔停车场或便道上〕，以及某辆车离开停车场时应缴纳的费用和他在停车场内停留的时间。3〕实现提示：以栈模拟停车场，以队列模拟便道，依据从终端读入的车辆“到达开”信息模拟停车场治理。实现一个哈夫曼编/译码系统1〕问题描述：利用哈夫曼编码进展信息通信可以大大提高信道利用率，缩短信息传输在接收端将传来的数据进展译码。对于双工信道，每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2〕试验要求：一个完整的系统应具有以下功能：I：初始化(Initializationnn个字符和n建立哈夫曼树，并将它存于文件hfmTreeE：编码(Encoding)。利用已建好的哈夫曼树对文件ToBeTran中的正文进展编码，然后将结果存入文件CodeFileD：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进展译码，结果存入文件TextFileP：打印代码文件(Print)。将文件CodeFile50代码。同时将此字符形式的编码文件写入文件CodePrinT：打印哈夫曼树(Treeprinting)。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint3)实现提示：文件CodeFile用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit户选择了“E”为止。在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不愿定执行I命令，由于文件hfmTree利用最小生成树算法解决通信网的总造价最低问题1〕nn-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。2〕试验要求：利用克鲁斯卡尔算法求网的最小生成树3)实现提示：通信线路一旦建立，必定是双向的。因此，构造最小生成树的网确定是无向网。为简洁起见，图的顶点数不超过10100。教学打算编制问题1〕问题描述：软件专业的学生要学习一系列课程，其中有些课程必需在其先修课完成后才能学习。2〕试验要求：假设每门课程的学习时间为一个学期，试为该专业的学生设计教学打算，使他们能在最短时间内修完专业要求的全部课程。3)实现提示：以顶点代表课程，弧代表课程的先后修关系，按课程先后关系建立有向无环图。利用拓扑排序实现。公交线路优化路径的查询【问题描述】对于某城市的公交线路，乘坐公交的顾客期望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为：12站坐标)；……；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。例如：63：A(32,45)；B(76,45)；C(76,90)；……；N(100,100)。15150/每分钟。假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。对这样的公交线路，需要在其上进展的优化路径查询包括：任何两个站点之间最廉价的路径；任何两个站点之间最省时间的路径。【设计要求】①依据上述公交线路的输入格式，定义并建立适宜的图模型。②针对上述公交线路，能查询获得任何两个站点之间最廉价的路径，即输入站名S，TS到Tx：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；…；换乘线路x：站名MK，…，站名T。共x③针对上述公交线路，能查询获得任何两个站点之间最省时间的路径〔不考虑在中间站等下一辆线路的等待时间〕，即输入站名S，TST中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，…，站名M1；换乘线路x：站名M1，…，站名M2；…；换乘线路x：站名MK，…，站名T。共花费x④针对上述公交线路，能查询获得任何两个站点之间最省时间的路径〔要考虑在中间站等下一辆线路的等待时间〕，S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径站名M1；换乘线路x：站名M1，…，站名M2；…；换乘线路x：站名MK，…，站名Tx时间。四、仪器设备:计算机、VC++编译环境五、试验方法：C++语言完成设计，程序在VC++环境下调试通过。并选择恰当的测试数据验证程序的正确性。六、试验步骤：123七、试验结果处理：对程序调试中的问题要进展总结。八、试验留意事项：独立完成试验及试验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、试验报告要求：本门课程试验报告格式见附件1，鼓舞手写，可以打印。1：测绘与国土信息工程学院《数据构造》课程试验报告姓 名：学 号：成 绩：日 期：试验一 线性表的链表实现类的设计一、需求分析所需求的各种功能。对线性表的操作有：输入形式为从键盘输入，用户依据界面的提示从键盘直接输入所对应〔例如字符串〕会产生不行推想的错误。输出的界面为DOS的输出结果显示到界面上。、删除、插入、构造、销毁和猎取链表长度的操作。1二个元素12并删除它；在第五个元素后插入55；生成L2

={33,45,50}的链L1

的链表合并。二、概要设计链表结点的数据构造：structLinkNode{ intdata;

据域LinkNode*link; /LinkNode(LinkNode*ptr=NULL)/初始化指针成员的构造函数{link=ptr;}//初始化数据和指针成员的构造函数LinkNode(constintx,LinkNode*ptrNULL){data=x;link=ptr;}};链表类：classList{ public:

头结点的单链表类的定义List{firstnewLinkNode;} 造函数List(constintx){first=newLinkNode(x);}造函数List(List&L); ~List{

制构造函数MakeEmpty; deletefirst;/}

链表为空表voidMakeEmpty;/intLengthconst;/

算链表长度LinkNode*Search(intx);/xLinkNode*Locate(inti);/iLinkNode*GetHeadconst{returnfirst;}取头结点地址intGetData(inti); /出第i个元素的值voidSetData(inti,intx);/x修改第i个元素的值boolInsert(inti,intx);//ixboolRemove(inti,int&x);除第i个元素，通过x返回其元素值voidAddTail(intx); /链表尾部添加元xvoidDeleteRepeatedElem;//voidMergeList(List&L);/链表L链接在当前链表尾部boolIsEmptyconst /断表空{returnfirst->link==NULL?true:false;}voidInput; /voidDisplay; /List&operator(List&L);/private:LinkNode*first;};三、具体设计List::List(List&L)//{

制构造函数intval;LinkNode*srcPtr=L.GetHead;//LinkNode*desPtrfirstnewLinkNode;//成头结点while(srcPtr->linkNULL){ /valsrcPtr->link->data;desPtr->linknewLinkNode(val);/辟结点内存，并为数据域赋值X}

desPtr=desPtr->link;srcPtr=srcPtr->link;desPtr->link=NULL;}voidList::MakeEmpty/{

链表置为空表，保存头结点LinkNode*p;{

链不为空时，删除链中全部结点p=first->link;first->link=p->link;/deletep; }}

除从链上摘下的结点intList::Lengthconst/{

算链表长度LinkNode*p=first->link;intlength=0;while(p!=NULL)/扫描直到链尾{p=p->link;length++;}returnlength;}LinkNode*List::Search(intx)/x{LinkNode*p=first->link;while(p!=NULL)/x的结点{if(p->data=x)break;elsep=p->link;}returnp;}LinkNode*List::Locate(inti)/i{if(i<0)returnNULL;//LinkNode*pfirst->link;intk=1;while(p!=NULL&&ki)//{

i个结点p=p->link;k++;}returnp;}intList::GetData(inti) /i{if(i0)return-1000000;//iLinkNode*pLocate(i);

合理，返回一个负值if(pNULL)return-1000000;//ielsereturnp->data;}

大，返回一个负值voidList::SetData(inti,intx)//{

x修改第iif(i0)return; LinkNode*p=Locate(i);if(pNULL)return;过大elsep->datax;}boolList::Insert(inti,intx)//ix{LinkNode*p=Locate(i);if(p==NULL)returnfalse;LinkNode*newNode=newLinkNode(x);if(newNode==NULL){exit(1);}newNode->link=p->link;p->link=newNode;returntrue;}boolList::Remove(inti,int&x)//ix{LinkNode*p=Locate(i-1);if(p==NULL||p->link==NULL)returnfalse;LinkNode*del=p->link;p->link=del->link;x=del->data;deletedel;returntrue;}voidList::AddTail(intx) /x{LinkNode*pfirst;指向头结点while(p->link!=NULL)/终让指针p{p=p->link;}//while//qLinkNode*newNode=newLinkNode(x);if(newNode==NULL){exit(1);}p->link=newNode; //给指针p->link重赋值newNode->link=NULL; //尾指针赋NULL}voidList::DeleteRepeatedElem//{inttemp1,temp2,i,j;intlength=Length;for(i=1;i<length;i++){temp1=GetData(i);for(j=i+1;j<=length;j++){temp2=GetData(j);if(temp1==temp2){Remove(j,temp1);/length--;}//if}//for(j=i+1;j<=length;j++)}//for(i=1;i<length;i++)}voidList::MergeList(List&L)/L{LinkNode*pfirst; //pLinkNode*q=L.GetHead;//q向Lif(q->linkNULL)//{

表Ldeleteq;//释放Lreturn;}while(p->linkNULL)/{

终让指针p指向链表尾结点p=p->link;}//whilewhile(q->linkNULL){ intvalq->link->data;

个结点复制p->link=newLinkNode(val);Xp=p->link;q=q->link;}

//辟结点内存，并为数据域赋值p->link=NULL;}voidList::Input /{intval=0;cout<<“请依次输入链表的数据元-1完毕):\n“;while(val!=-1){cin>>val;if(val!=-1)AddTail(val);elsebreak;}}voidList::Display//{

示表中元素if(IsEmpty){cout<<“Thelistisempty!\n“;return;}//ifcoutLinkNode*pfirst;while(p->link!=NULL){p=p->link;if(p->link!=NULL)cout<<p->data<<“,“;elsecout<<p->data<<“}\n“;}/