搜索
给大家的实验文档中分为一下几部分1.实验准备：请好好复习C语言，有时间也复习一下C++。2.c语言实验教案中是一些c语言的基础知识，包括VC环境的使用和程序的调试，希望对c语言已经忘记的同学好好看看复习一下。（程序的编写调试是长年累月的过程，需要不断的积累，写得多了，程序调试的多了，自然就熟练了）3.文件夹中还有一个名为“CodeBlocks使用简略教程.pdf”的文件，虽然大家对VC6比较熟悉，但是VC6毕竟比较老了，比起别的编译环境没有那么好用了，所以，还请大家学习一下CodeBlocks的使用。当然，实验时候的编译环境由大家自由选择，不强迫大家使用某种编译环境，只是希望大家能学习使用CodeBlocks而已，哈。4.对应的flash课件：其中是一些实验的flash课件演示，给大家做一下参考5.实验指导书和实验教案大家在做每个实验前都需要看看。阅读的时候，老版本word可以使用【视图】|【文档结构图】，可以比较自由跳到相应位置。如果是新点的word，通过“视图”选项卡，然后勾选“导航窗格”就可以了。6.总体实验难度比较大，时间紧，单靠实验课上的几个学时，作为初学者是无法完成的，需要大家在课前课后尽自己最大的努力。7.每个实验的代码编写可以用c也可以用c++8.文件夹中还有“数据结构实验报告模板v1.0”的文档，实验前做好预习，需要填写好该文档的部分内容，如果有代码，也请贴在其上。实验结束后需要将该文档中的内容补充完整，并打印，于下次实验前交给班长，班长按照学号排好顺序后，下次实验交给实验老师。实验安排1、多项式加减法，2学时2、栈和队列的应用，2学时3、迷宫，4学时4、二叉树的建立和遍历，4学时5、排序，2学时6、图，2学时实验一多项式加减法一、实验目的通过实现多项式的加减法，对链表有更深入的了解二、实验内容问题描述：设计一个一元稀疏多项式简单的加减法计算器实现要求：一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式：1785937)(xxxxA；879228)(xxxxB（2）输出多项式（3）多项式A和B相加，建立多项式C＝A＋B，并输出相加的结果多项式C（4）选作：多项式A和B相减，建立多项式C＝A－B，并输出相加的结果多项式D方法说明：（1）多项式的输入与存储用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数），可对应建立链表的一个结点。每个节点的结构为：建立两个链表，其中pa和pb分别为它们的头指针：Papb结果链表Pa(或者是Pc)Pc（2）多项式数据类型的定义Coefexpnext4-1703198∧3-181-92∧7-170111-9298∧structtagNode{floatcoef;intexp;structtagNode*next;};typedefstructtagNodeNode;typedefstructtagNode*pNode;（3）主要算法①创建两个链表，分别存放多项式1和多项式2，这两个链表中的节点是按指数降序或者升序排列的②多项式相加或相减，下面给出多项式相加的部分实现/*下面的函数实现两个多项式的相加，要相加的链表分别由pa和pb指向（其中，pa，pb都是分配了空间的头结点）。相加的结果直接由pa指向的链表保存，即是在pa链表中添加或删除（当系数因为相加为0的情况下）一些结点，构成结果。这里要相加的链表中指数都是按从小到大的顺序排列好了的，是升序链表。*/voidadd_poly(Node*pa,Node*pb){Node*p=pa-pNext;//链表1，将来的结果也放在此Node*q=pb-pNext;//链表2Node*pre=pa;Node*u;//临时用floatx;while(p!=NULL&&q!=NULL)//当两个链表都不为空{if(p-expq-exp)//比较链表1跟链表2当前节点的指数大小，链表1也是存放结果的地方{pre=p;p=p-pNext;//p指向要比较的下一个结点。pre指向的是结果链表的最后一个结点。}elseif(p-exp==q-exp)//假如链表1和链表2的指数相等，就要系数相加{x=p-coef+q-coef;if(x!=0)//相加后的系数不为0，有必要保留一个结点就可以了{p-coef=x;pre=p;}else//如果相加后，系数不是0，不需要保留任何一个结点，在这里删除链表1的结点，下面删除链表2的结点{pre-pNext=p-pNext;//保持链表1的连续性free(p);}p=pre-pNext;//p指向要比较的下一个结点//下面的代码是进行链表2结点的删除工作，因为指数相等，仅仅需要保留一个结点就可以了//而结果直接保存在链表1中，所以，删除链表2的结点。u=q;q=q-pNext;free(u);}else//如果链表2的当前节点指数小，那么要把链表2的当前节点加入到结果链表中（即是链表1）{//相当于把结点插入到链表1中，用u作为临时变量，保存链表2的下一个当前节点的位置。u=q-pNext;q-pNext=p;pre-pNext=q;pre=q;q=u;}}if(q)//如果链表2比链表1长，那么需要把链表2多余的部分加入结果链表中。链表1比链表2长，则什么都不用做。{pre-pNext=q;}free(pb);}③输出结果多项式实验二栈和队列的应用一、实验目的1、掌握栈的编写和应用2、掌握队列的编写和应用二、实验内容1、分别使用STL中的栈和自己编写的栈类，实现序列的反转（1）简单修改下面代码，实现使用STL中的栈进行序列的反转，编译运行#includestackintmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.Uses:TheSTLclassstackanditsmethods*/{intn;doubleitem;stackdoublenumbers;//declaresandinitializesastackofnumberscoutTypeinanintegernfollowedbyndecimalnumbers.endlThenumberswillbeprintedinreverseorder.endl;cinn;for(inti=0;in;i++){cinitem;numbers.push(item);}coutendlendl;while(!numbers.empty()){coutnumbers.top();numbers.pop();}coutendl;}提示：（1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stackdoublenumbers;中就是声明了一个栈，这个栈中存放的数据类型为double。（2）要使用c++的输入输出需要加上几行语句如下，因为cout和cin是在命名空间std中的：#includeiostreamusingnamespacestd;（2）自己编写程序实现栈该栈可以用链表实现，也可以用数组实现。C语言或者c++描述都可以。该实现的栈要求至少具有（1）压栈（2）出栈（3）判断栈是否空（4）取栈顶元素值等功能。如果用数组实现该栈，则该栈还需要具有下面函数（5）判断栈是否满（3）使用自己编写的栈，进行序列的反转2、自己编写程序，实现队列，并自己编写主程序测试该队列（选作）该队列可以使用链表实现，也可以使用数组实现，C语言或者c++描述都可以。实现队列后，再编写一个简单的主函数，测试自己编写的队列的各个功能。要求：自己实现的队列至少需要有如下功能：（1）进队（2）出队（3）取队首元素（4）判断队列是否为空。如果是用数组实现的队列，至少还需要具有下面的函数（5）判断队列是否满附录：STL中栈的使用#pragmawarning(disable:4786)#includestack#includeiostreamusingnamespacestd;typedefstackintSTACK_INT;intmain(){STACK_INTstack1;coutstack1.empty()returned(stack1.empty()?true:false)endl;//Function3coutstack1.push(2)endl;stack1.push(2);if(!stack1.empty())//Function3coutstack1.top()returnedstack1.top()endl;//Function1coutstack1.push(5)endl;stack1.push(5);if(!stack1.empty())//Function3coutstack1.top()returnedstack1.top()endl;//Function1coutstack1.push(11)endl;stack1.push(11);if(!stack1.empty())//Function3coutstack1.top()returnedstack1.top()endl;//Function1//Modifythetopitem.Setitto6.if(!stack1.empty()){//Function3coutstack1.top()=6;endl;stack1.top()=6;//Function1}//Repeatuntilstackisemptywhile(!stack1.empty()){//Function3constint&t=stack1.top();//Function2coutstack1.top()returnedtendl;coutstack1.pop()endl;stack1.pop();}}运行结果：stack1.empty()returnedtruestack1.push(2)stack1.top()returned2stack1.push(5)stack1.top()returned5stack1.push(11)stack1.top()returned11stack1.top()=6;stack1.top()returned6stack1.pop()stack1.top()returned5stack1.pop()stack1.top()returned2stack1.pop()实验三迷宫一、实验目的1、了解回溯法在求解迷宫问题中的应用2、进一步掌握栈的使用二、实验内容用回溯法求解迷宫问题，可以用一个栈保存探索的序列。并且在该迷宫的行走中，站在一点可以有八个方向选择。比如如下的迷宫Enter-0111000000000100010001011001000100101100010010110011101010000010001011001000101101101010000000101100--EXIT下面是可能的路径（注意：从入口到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！）Path:(maze[0][0],maze[1][0],maze[1][1],maze[1][2],maze[2][2],maze[3][2],maze[3][3],maze[4][3],maze[5][3],maze[6][3],maze[6][4],maze[6][5],maze[