桂电数据结构实验指导书.doc

《桂电数据结构实验指导书.doc》由会员分享，可在线阅读，更多相关《桂电数据结构实验指导书.doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、给大家的实验文档中分为一下几部分1.实验准备：请好好复习C语言，有时间也复习一下C+。2.c语言实验教案中是一些c语言的基础知识，包括VC环境的使用和程序的调试，希望对c语言已经忘记的同学好好看看复习一下。（程序的编写调试是长年累月的过程，需要不断的积累，写得多了，程序调试的多了，自然就熟练了）3.文件夹中还有一个名为“CodeBlocks使用简略教程.pdf”的文件，虽然大家对VC6比较熟悉，但是VC6毕竟比较老了，比起别的编译环境没有那么好用了，所以，还请大家学习一下CodeBlocks的使用。当然，实验时候的编译环境由大家自由选择，不强迫大家使用某种编译环境，只是希望大家能学习使用Cod

2、eBlocks而已，哈。4.对应的flash课件：其中是一些实验的flash课件演示，给大家做一下参考5.实验指导书和实验教案大家在做每个实验前都需要看看。阅读的时候，老版本word可以使用【视图】|【文档结构图】，可以比较自由跳到相应位置。如果是新点的word，通过“视图”选项卡，然后勾选“导航窗格”就可以了。6. 总体实验难度比较大，时间紧，单靠实验课上的几个学时，作为初学者是无法完成的，需要大家在课前课后尽自己最大的努力。7.每个实验的代码编写可以用c也可以用c+8. 文件夹中还有“数据结构实验报告模板v1.0”的文档，实验前做好预习，需要填写好该文档的部分内容，如果有代码，也请贴在其上

3、。实验结束后需要将该文档中的内容补充完整，并打印，于下次实验前交给班长，班长按照学号排好顺序后，下次实验交给实验老师。实验安排1、多项式加减法，2学时2、栈和队列的应用，2学时3、迷宫，4学时4、二叉树的建立和遍历，4学时5、排序，2学时6、图，2学时实验一 多项式加减法一、实验目的通过实现多项式的加减法，对链表有更深入的了解二、实验内容问题描述：设计一个一元稀疏多项式简单的加减法计算器实现要求：一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式：；（2）输出多项式（3）多项式A和B相加，建立多项式CAB，并输出相加的结果多项式C（4）选作：多项式A和B相减，建立多项式CAB，并输出

4、相加的结果多项式D方法说明：（1）多项式的输入与存储用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数），可对应建立链表的一个结点。每个节点的结构为：Coef exp next建立两个链表，其中pa和pb分别为它们的头指针：9 8 3 17 0 4 -1Pa-9 2 8 13 -1pb结果链表Pa(或者是Pc)9 8 -9 211 17 0 7 -1Pc（2）多项式数据类型的定义struct tagNodefloat coef;int exp;struct tagNode *next;typedef struct tagNo

5、de Node;typedef struct tagNode* pNode;（3）主要算法创建两个链表，分别存放多项式1和多项式2，这两个链表中的节点是按指数降序或者升序排列的多项式相加或相减，下面给出多项式相加的部分实现/*下面的函数实现两个多项式的相加，要相加的链表分别由pa和pb指向（其中，pa，pb都是分配了空间的头结点）。相加的结果直接由pa指向的链表保存，即是在pa链表中添加或删除（当系数因为相加为0的情况下）一些结点，构成结果。这里要相加的链表中指数都是按从小到大的顺序排列好了的，是升序链表。*/void add_poly(Node *pa,Node *pb)Node *p=pa

6、-pNext;/链表1，将来的结果也放在此Node *q=pb-pNext;/链表2Node *pre=pa;Node *u;/临时用float x;while (p!=NULL & q!=NULL)/当两个链表都不为空if (p-expexp)/比较链表1跟链表2当前节点的指数大小，链表1也是存放结果的地方pre=p;p=p-pNext;/p指向要比较的下一个结点。pre指向的是结果链表的最后一个结点。else if (p-exp=q-exp)/假如链表1和链表2的指数相等，就要系数相加x=p-coef+q-coef;if (x!=0)/相加后的系数不为0，有必要保留一个结点就可以了p-co

7、ef=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

8、=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中的栈进行序列的反转，编译运行#include int main( )/* Pre: The user supplies an integer n and n de

9、cimal numbers.Post: The numbers are printed in reverse order.Uses: The STL class stack and its methods */int n;double item;stack numbers; / declares and initializes a stack of numberscout Type in an integer n followed by n decimal numbers. endl The numbers will be printed in reverse order. n;for (in

10、t i = 0; i item;numbers.push(item);cout endl endl;while (!numbers.empty( ) cout numbers.top( ) ;numbers.pop( );cout endl;提示：（1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stack numbers;中就是声明了一个栈，这个栈中存放的数据类型为double。（2）要使

11、用c+的输入输出需要加上几行语句如下，因为cout和cin是在命名空间std中的：#include using namespace std;（2）自己编写程序实现栈该栈可以用链表实现，也可以用数组实现。C语言或者c+描述都可以。该实现的栈要求至少具有（1）压栈（2）出栈（3）判断栈是否空（4）取栈顶元素值等功能。如果用数组实现该栈，则该栈还需要具有下面函数（5）判断栈是否满（3）使用自己编写的栈，进行序列的反转2、自己编写程序，实现队列，并自己编写主程序测试该队列（选作）该队列可以使用链表实现，也可以使用数组实现，C语言或者c+描述都可以。实现队列后，再编写一个简单的主函数，测试自己编写的队列

12、的各个功能。要求：自己实现的队列至少需要有如下功能：（1）进队（2）出队（3）取队首元素（4）判断队列是否为空。如果是用数组实现的队列，至少还需要具有下面的函数（5）判断队列是否满附录：STL中栈的使用#pragma warning(disable:4786)#include #include using namespace std ;typedef stack STACK_INT;int main() STACK_INT stack1; cout stack1.empty() returned (stack1.empty()? true: false) endl; / Function 3

13、cout stack1.push(2) endl; stack1.push(2); if (!stack1.empty() / Function 3 cout stack1.top() returned stack1.top() endl; / Function 1 cout stack1.push(5) endl; stack1.push(5); if (!stack1.empty() / Function 3 cout stack1.top() returned stack1.top() endl; / Function 1 cout stack1.push(11) endl; stack

14、1.push(11); if (!stack1.empty() / Function 3 cout stack1.top() returned stack1.top() endl; / Function 1 / Modify the top item. Set it to 6. if (!stack1.empty() / Function 3 cout stack1.top()=6; endl; stack1.top()=6; / Function 1 / Repeat until stack is empty while (!stack1.empty() / Function 3 const

15、 int& t=stack1.top(); / Function 2 cout stack1.top() returned t endl; cout stack1.pop() 0 1 1 1 0 0 0 0 0 00 0 0 1 0 0 0 1 0 00 1 0 1 1 0 0 1 0 00 1 0 0 1 0 1 1 0 00 1 0 0 1 0 1 1 0 01 1 1 0 1 0 1 0 0 00 0 1 0 0 0 1 0 1 10 0 1 0 0 0 1 0 1 10 1 1 0 1 0 1 0 0 00 0 0 0 1 0 1 1 0 0 - EXIT下面是可能的路径（注意：从入口

16、到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！） Path: ( maze00, maze10, maze11, maze12, maze22, maze32, maze33, maze43, maze53, maze63, maze64, maze65, maze55, maze45, maze35, maze25, maze26, maze16, maze06, maze07, maze08, maze18, maze28, maze38, maze48, maze58, maze57, maze67, maze77, maze87, maze88, maze89, maze

17、99)Enter- X 1 1 1 0 0 X-X-X 0X-X-X 1 0 0 X 1 X 00 1 X 1 1 X-X 1 X 00 1 X-X 1 X 1 1 X 00 1 0 X 1 X 1 1 X 01 1 1 X 1 X 1 X-X 00 0 1 X-X-X 1 X 1 10 0 1 0 0 0 1 X 1 10 1 1 0 1 0 1 X- X- X0 0 0 0 1 0 1 1 0 X - EXIT1、提示：（1）数据结构： 用二维数组MAZEm+2n+2表示迷宫的结构，数组中的值为1表示是墙，为0表示可以走通。（用MAZEm+2n+2而不用MAZEmn的原因在于想表示和编写代

18、码的时候简单些，而且让迷宫周围都是墙，防止错误的走出去） 用二维数组MARKm+2n+2表示迷宫是否被走过，主要是为了回溯时已经证明走不通的路线就不要再去走了。（用MARKm+2n+2而不用MARKmn的原因在于想表示和编写代码的时候简单些） 二维数据MOVE82是为了更方便的移动到下一步，改变坐标。这个二维数组是为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路 用栈保存走过的路径（2）输出： 迷宫布局，用0表示可以走通的地方，用1表示墙 如果能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通 带有路径的迷宫布局2、伪代码注意：下面的仅仅是伪代码！不能直接做代码使用的

19、，揭示的仅仅是算法本身Path(MAZE, MARK, m, n, MOVE, STACK)/A binary matrix MAZE(0:m+1,0:n+1) holds the maze./STACK(mn,2) records the pathMARK(1,1)=1;STACK.push(1,1,1);While not STACK.empty()(i,j,mov) = STACK.top();STACK.pop();While mov!=8 g=i+MOVE(mov,1);h=j+MOVE(mov,2);if g=m and h=nreverseprint STACK;print i,

20、j;print m,n;return;if MAZE(g,h)=0 and MARK(g,h)=0MARK(g,h)=1;STACK.push(i,j,mov);i=g;j=h;mov=0;else mov=mov+1;print “No path has been found”实验四 二叉树的建立和遍历一、实验目的1、设计数据结构和算法，实现按层次构造二叉树的算法2、掌握树的前根序、中根序和后根序遍历算法二、实验内容1、实验题目按层次（从上到下，从左到右的顺序）输入树的结点，如果该结点为空，则用一个特定的值替代（比如0或者.）。例如下面的图中，输入为e b f a d . g . . c（当

21、然为了方便输入，也可以用结束字符串的输入）要求构造一棵如下的二叉树，当二叉树构造成功后，需要对其进行先序遍历，后序遍历，中序遍历。2、按层次构造树的两种方法对于如下的一棵树输入：为了构造上图所示的这样一棵二叉树，键盘上输入的顺序如下：ebfad.g.c#其中可以看到这是根据层次的一种输入，先输入第一层的结点，然后是第二层的结点，第三层.直到把所有的带信息的结点输入完。也可以看到，在输入的序列中，有.号，这是代表结点为空。注意在输入的时候，为空的结点也要这样输入进去。构造二叉树：方法一：用队列queue A;queue B;假如我们把读入的数据放到一个队列中A，用于方便我们的后续处理，那么，在读

22、入后，这个队列中的数据为ebfad.g.c，其中e为队列头存放的元素值（即该指针所指向的节点空间数据域中的值为e），而点代表空指针NULL把数据读入队列A中的方法如下：Binary_node* tempNode=new Binary_node();cintempNode-data;tempNode-left=NULL;tempNode-right=NULL;A.push(tempNode);为了按层次的构造二叉树，我们还要使用一个队列B，这个队列中保存的是指向要有儿子结点的父亲结点的指针。下面是这两个队列的变化和树的构造变化情况：（1）第一步很特殊，首先是树根Binary_node* pNod

23、e=A.front();A.pop();B.push(pNode);A：bfad.g.cB：e树：（2）后面的每一步都是从A中取出两个队首，放入B队列尾部（如果为NULL则不放）。从B中取出队首，队列A中取出的元素正好是B中取出元素的小孩子Binary_node* pfather= B.front();B.pop();Binary_node* pLchild= A.front();/先出来的是左孩子A.pop();Binary_node* pRchild= A.front();A.pop();pfather-left=pLchild;pfather-right=pRchild;/先放入左孩子i

24、f(pLchild!=NULL)B.push(pLchild);if(pRchild!=NULL)B.push(pRchild);A：ad.g.cB：bf树：（3）A：.g.cB：fad树：（4）A：.cB：adg树：（5）A：cB：dg树：（6）A：空（当队列A为空的时候整个算法结束，树构造成功）B：g树：第二种方法：给树的结点按层次从上到下，从左到右编号（编号从1开始，空节点也要编号），利用父亲跟小孩的编号的关系来编写代码。即节点的编号除以2，得到的商代表这该节点父亲节点的编号，得到的余数为0，则表示该节点为父亲的左孩子，若得到的余数为1，则表示该节点为父亲的右孩子。实现方法可以为，（1）

25、为每个节点分配空间；（2）定义一个一维数组，该数组中存放的元素为指向节点的指针，将每个分配好空间的节点的指针放入该一维数组中（3）逐一访问节点，确定节点的父子关系。当除了根节点外，每个节点的父亲都确定后，这颗二叉树就构造好了。两种方法分析：用队列的方法，实现有点难度，但是灵活。数组的方法，实现比较简单，但是有局限性。3、程序简单模板#include using namespace std;struct Binary_nodechar data; /data membersBinary_node *left;Binary_node *right;class Binary_treepublic:B

26、inary_tree();/构造函数，里面将root=NULL;/通过队列中保存的数据，构造树void buildTree(void);/遍历二叉树void preorder(void);void inorder(void);void postorder(void);private:/遍历树的辅助函数void recursive_inorder(Binary_node* root);void recursive_preorder(Binary_node* root);void recursive_postorder(Binary_node* root);Binary_node *root;/树

27、根;这里给出一个C+的类，仅供参考，自己写代码的时候并不要求一定如此。附录：STL中队列的使用注：队列，这里也不要求大家再去自己实现一个有关队列的类，直接用标准模板库（STL）中的队列就可以了。需要#include STL中的queue，里面的一些成员函数如下（这里仅仅描述也许会用到的几个，具体不明白可以查找msdn，搜索queue class）：front：Returns a reference to the first element at the front of the queue.pop：Removes an element from the front of the queuepu

28、sh：Adds an element to the back of the queueempty：Tests if the queue is empty程序示例：/ queue:push(), queue:pop(), queue:empty(), queue:back(),/ queue:front(),queue:size()#include #include using namespace std ;typedef queue INTQUEUE;typedef queue CHARQUEUE;int main(void) int size_q; INTQUEUE q; CHARQUEUE

29、 p; / Insert items in the queue q.push(42); q.push(100); q.push(49); q.push(201); / Output the size of queue size_q = q.size(); cout size of q is: size_q endl; / Output items in queue using front() / and use pop() to get to next item until / queue is empty while (!q.empty() cout q.front() endl; q.po

30、p(); / Insert items in the queue p.push(cat); p.push(ape); p.push(dog); p.push(mouse); p.push(horse); / Output the item inserted last using back() cout p.back() endl; / Output the size of queue size_q = p.size(); cout size of p is: size_q endl; / Output items in queue using front() / and use pop() t

31、o get to next item until / queue is empty while (!p.empty() cout p.front() endl; p.pop(); 输出结果：size of q is:44210049201horsesize of p is:5catapedogmousehorse实验五 排序一、实验目的至少掌握一种排序算法二、实验内容随机生成10个从1100之间的随机数，编程实现至少一种排序算法，对该数据进行排序。要求1、要排序的数据随机生成2、先升序排序一次，再用同样的算法降序排序一次附录（帮助文档中的随机数生成）：/ crt_rand.c/ This pr

32、ogram seeds the random-number generator/ with the time, then exercises the rand function./#include #include #include void SimpleRandDemo( int n ) / Print n random numbers. int i; for( i = 0; i n; i+ ) printf( %6dn, rand() );void RangedRandDemo( int range_min, int range_max, int n ) / Generate random

33、 numbers in the half-closed interval / range_min, range_max). In other words, / range_min = random number range_max int i; for ( i = 0; i n; i+ ) int u = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min; printf( %6dn, u); int main( void ) / Seed the random-number generator with

34、the current time so that / the numbers will be different every time we run. srand( (unsigned)time( NULL ) ); SimpleRandDemo( 10 ); printf(n); RangedRandDemo( -100, 100, 10 ); 结果： 22036 18330 11651 27464 18093 3284 11785 14686 11447 11285 74 48 27 65 96 64 -5 -42 -55 66实验六 图一、实验目的掌握求最小生成树的Prim算法掌握求最短

35、路径的Dijkstra算法二、实验内容1、编写程序，用Prim算法求图的最小生成树2、编写程序，用Dijkstra算法求图的最短路径上面两个题目选择一个来实现就可以。提示：程序简单模板（只是参考，不需要照着这个来写，下面的模板用到了C的一些语法知识，如果对面向对象的一些知识有所遗忘，可以用C编写代码）/最小生成树#ifndef MYGRAPH_H_#define MYGRAPH_H_class MyGraphpublic:void readUndirectedGraph();MyGraph(int size);/构造函数中设置图的大小，分配空间void writeGraph();void fi

36、ndMinimalSpanningTree(int source);void writeTree(void);protected:private:int *m_graph;/用二维数组保存图int m_size;/图的大小/这是为了求无向图的最小生成树而用的辅助结构int *tree_component; /指向数组的指针，数组元素记录点是属于旧图还是新图，0表示旧，1表示新int *tree_distance; / 到新图最短的距离，指向数组的指针int *tree_neighbor; /到新图最短距离的点，指向数组的指针int *m_tree;/*树，这里是一个二维数组来存放最后生成的最小

37、生成树，跟图的数据结构一样。注意：此处如果不会如何分配空间的话，直接定义一个名字叫做m_tree的二维数组也可以，自己写！*/;#endif/构造函数中设置图的大小，分配空间MyGraph:MyGraph(int size)int i,j;m_size=size;/给图分配空间m_graph=new int* m_size;for (i=0;im_size;i+)m_graphi=new intm_size;for (i=0;im_size;i+)for(j=0;jm_size;j+)m_graphij=INT_MAX;/ /最短路径#ifndef MYGRAPH_H_#define MYGRAPH_H_class MyGraphpublic:voi