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