〈数据结构〉上机实验指导

数据结构实验指导书陈宏明张亚红寇海洲编淮阴工学院计算机系二 OO 五年九月《数据结构》实验指导书 1 目录实验一线性表及其应用…………… ……………………2 实验二栈和队列及其应用…………………………………5 实验三二叉树及其应用……………………………………7 实验四图及其应用…………………………………………9 实验五查找……………… ………………………………11 实验六排序………………… ……………………………13 《数据结构》实验指导书 2 实验一线性表及其应用实验目的 1. 加深对线性表的结构特性的理解; 2. 熟练掌握线性表的链式存储结构的描述方法及基本操作; 3. 掌握线性表的链式存储结构的应用方法; 4.从时间和空间的角度对操作算法进行分析。 5.培养程序的设计能力和调试能力。实验学时：建议 2~4 学时实验内容内容 1：制作体育彩票（10 选 7）的选号器。【说明】 1）体育彩票（10 选 7）的 7 个号可以重复； 2）建议用首尾相连的链式结构，这样可以更逼真地模拟“摇奖”过程；而每个号的“摇动”次数可用随机数来确定。 3）怎样产生随机数？可以利用 C++语言中的种子函数 srand( )和伪随机函数 rand( )来实现。（includeSTDLIB.H） a) 首先，给 srand(m )提供一个“种子”m，它的取值范围是从 0～65535。 b) 然后，调用 rand( )，是伪随机数，它会根据提供给 srand( )的“种子” 值返回一个随机数（在 0～32767 之间）。 c) 根据需要多次调用 rand( )，从而不断地得到新的随机数。 d) 无论何时，你都可以给 srand( )提供一个新的“种子” ，从而进一步“随机化”rand( )的输出结果。《数据结构》实验指导书 3 例如，取 m=17，则执行了 srand(17)之后，再执行 rand( )函数，将得到输出值 94；第二次调用 rand( )，会得到 26,„„反复调用 rand( )就能产生一系列的随机数。注意：若 m 不变，则 rand( )的输出系列也不变，总是 94,26,602,„等等。所以，建议摇号的“种子”选当前日期或时间，以保证每天的摇号值都不相同。【选做内容】实现摇奖和对奖操作。内容 2：约瑟夫（Joseph）环问题【问题描述】约瑟夫问题的一种描述是：编号为 1 ，2 ，„，n 的 n 个人按顺时针方向围坐一圈, 从 1 起报到 k 则出圈，下一个人再从 1 报起，如此下去直到圈中只有一人为止。求最后剩下的人的编号。【说明】 1）建议用循环链表存储方式。 2 ）问题改进：在人数 n、k 及起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。若每人有一个密码 Ki（整数），留作其出圈后的报到 Ki 后出圈。密码 Ki 可用随机数产生。这样事前无法确定谁是最后一人【选做内容】约瑟夫问题的改进算法。【选做内容】内容 3：多项式的表示和相加【问题描述】建立多项式的链式存储表示，并设计算法实现多项式的相加。【要求】 1）多项式采用链式存储方式。 2）相加后可将原多项式销毁，也可以保留。《数据结构》实验指导书 4 【选做内容】多项式的减法、乘法及除法运算。【问题思考】建立的链表不带头结点与带头结点, 则在操作实现上有何差异? 《数据结构》实验指导书 5 实验二栈和队列及其应用实验目的 1. 加深理解栈和队列的特性； 2. 能根据实际问题的需要灵活运用栈和队列； 3. 了解递归算法的设计； 4. 掌握栈和队列的应用方法。实验学时：建议 2~4 学时实验内容内容 1：算术表达式求值【问题描述】表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法算术表达式求值的过程。【基本要求】以字符序列的形式输入语法正确且不含变量的整数表达式。利用教材中给出的算符优先关系表，实现对算术四则混合运算表达式的求值。【实现提示】（1）设置运算符栈和运算数栈算符优先辅助分析算符优先关系。（2）在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应的运算。参考算法如下： void del_blank(char *s);//删除串 s 中所有空格 int prior(char,char );//比较运算符的优先级 0—相等，1—大于，-1—小于 double value(char operate,double a,double b);//a 和 b 进行 operate 运算《数据结构》实验指导书 6 double calculate(char *s) //对表达式串 s 进行计算，并返回计算结果 { double opnd[100],a,b; // opnd 为运算数栈 char optr[100],operate; // optr 为运算符栈 int top1=0,top2=0;//分别为两栈的栈顶指针 optr[0]= # ; top2++; s[strlen(s)]= # ; //在表达式尾部加结束标志 while(*s!= # ||optr[top2-1]!= # ) //当前字符为 # 且栈顶也是 # ，则结束 { if(*s= 0 *s= 9 ) //当前字符为运算对象则入 opnd 栈 { opnd[top1++]=*s++- 0 ; continue; } while(prior(optr[top2-1],*s)==1) //栈顶运算符优先级高则计算 { operate=optr[top2---1]; b=opnd[top1---1]; a=opnd[top1---1]; opnd[top1++]=value(operate,a,b);//计算，结果入 opnd 栈 } if(*s== ) optr[top2-1]== ( ) //左右括号配对 { top2--; s++; continue; } if(prior(optr[top2-1],*s)==0)//当前运算符优先级高则入 optr 栈 optr[top2++]=*s++; } 《数据结构》实验指导书 7 return opnd[top1-1]; }// calculate int prior(char t,char c) { //计算 t 和 c 的优先级 switch(t) {case + : case - : if(c== + ||c== - ||c== ) ||c== # )return 1; //tc else return 0; //tc case * : case / : if(c== ( )return 0; //tc else return 1; //tc case ( : if(c== ) ) return -1;//相等 else return 0; case # : if(c== # ) return -1;//相等 else return 0; } return -2; //