〈数据结构〉上机实验指导.doc
《〈数据结构〉上机实验指导.doc》由会员分享,可在线阅读,更多相关《〈数据结构〉上机实验指导.doc(18页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构实验指导书周海岩编淮阴工学院计算机工程学院二O一五年九月目 录实验一 线性表及其应用 2实验二 栈和队列及其应用5实验三 二叉树及其应用7实验四 图及其应用9实验五 查找 11实验六 排序 13实验一 线性表及其应用实验目的1. 加深对线性表的结构特性的理解;2. 熟练掌握线性表的链式存储结构的描述方法及基本操作;3. 掌握线性表的链式存储结构的应用方法;4. 从时间和空间的角度对操作算法进行分析。5. 培养程序的设计能力和调试能力。实验学时:建议24学时实验内容内容1:制作体育彩票(10选7)的选号器。【说明】1) 体育彩票(10选7)的7个号可以重复;2) 建议用首尾相连的链式结构
2、,这样可以更逼真地模拟“摇奖”过程;而每个号的“摇动”次数可用随机数来确定。3) 怎样产生随机数?可以利用C+语言中的种子函数srand( )和伪随机函数rand( )来实现。(include)a) 首先,给srand(m )提供一个“种子”m,它的取值范围是从065535。b) 然后,调用rand( ),是伪随机数,它会根据提供给srand( )的“种子”值返回一个随机数(在032767之间)。c) 根据需要多次调用rand( ),从而不断地得到新的随机数。d) 无论何时,你都可以给srand( )提供一个新的“种子”,从而进一步“随机化”rand( )的输出结果。例如,取m=17,则执行了
3、srand(17)之后,再执行rand( )函数,将得到输出值94;第二次调用rand( ),会得到26,反复调用rand( )就能产生一系列的随机数。注意:若m不变,则rand( )的输出系列也不变,总是94,26,602,等等。所以,建议摇号的“种子”选当前日期或时间,以保证每天的摇号值都不相同。【选做内容】 实现摇奖和对奖操作。内容2:约瑟夫(Joseph)环问题【问题描述】约瑟夫问题的一种描述是:编号为1,2,n的n个人按顺时针方向围坐一圈,从1起报到k则出圈,下一个人再从1报起,如此下去直到圈中只有一人为止。求最后剩下的人的编号。【说明】 1) 建议用循环链表存储方式。2) 问题改进
4、:在人数n、k及起始报数人确定的情况下,最后剩下的人的编号事前是可以确定的。若每人有一个密码Ki(整数),留作其出圈后的报到Ki后出圈。密码Ki可用随机数产生。这样事前无法确定谁是最后一人【选做内容】约瑟夫问题的改进算法。【选做内容】内容3:多项式的表示和相加【问题描述】建立多项式的链式存储表示,并设计算法实现多项式的相加。【要求】 1)多项式采用链式存储方式。2)相加后可将原多项式销毁,也可以保留。【选做内容】多项式的减法、乘法及除法运算。【问题思考】建立的链表不带头结点与带头结点,则在操作实现上有何差异?实验二 栈和队列及其应用实验目的1. 加深理解栈和队列的特性;2. 能根据实际问题的需
5、要灵活运用栈和队列;3. 了解递归算法的设计;4. 掌握栈和队列的应用方法。实验学时:建议24学时实验内容内容1:算术表达式求值【问题描述】表达式计算是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。设计一个程序,演示用算符优先法算术表达式求值的过程。【基本要求】以字符序列的形式输入语法正确且不含变量的整数表达式。利用教材中给出的算符优先关系表,实现对算术四则混合运算表达式的求值。【实现提示】(1)设置运算符栈和运算数栈算符优先辅助分析算符优先关系。(2)在读入表达式的字符序列的同时,完成运算符和运算数的识别处理,以及相应的运算。参考算法如下:void del_blank(char
6、 *s);/删除串s中所有空格int prior(char,char );/比较运算符的优先级0相等,1大于,-1小于double value(char operate,double a,double b);/a和b进行operate运算double calculate(char *s) /对表达式串s进行计算,并返回计算结果double opnd100,a,b; / opnd为运算数栈char optr100,operate; / optr为运算符栈int top1=0,top2=0;/分别为两栈的栈顶指针optr0=#;top2+;sstrlen(s)=#; /在表达式尾部加结束标志whi
7、le(*s!=#|optrtop2-1!=#) /当前字符为#且栈顶也是#,则结束if(*s=0&*sc else return 0; /tc case *: case /:if(c=()return 0; /tc case (:if(c=) return -1;/相等else return 0; case #:if(c=#) return -1;/相等else return 0; return -2; /无此运算符/ prior(3)在识别出运算数的同时,实现将数字字符转换成整数形式。(4)在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。(5)算法的原理见教材。【选做内容】
8、(1) 扩充运算符集。如乘方、赋值等运算。(2) 运算分量可以是变量。(3) 运算分量可以是多位整数或实数类型。(4) 计算器的功能和仿真界面。内容2:航空客运订票系统【问题描述】航空客运订票的业务活动包括:查询航线、客票预订和办理退票等。试设计一个航空客运订票系统,完成上述功能。【基本要求】(1)每条航线信息:终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已定票的客户名单(包括姓名、定票量、舱位等级1,2或3)以及等候替补的客户名单。(2)作为模拟系统,全部数据可以只放在内存中。(3)系统功能:查询航线、客票预订和办理退票【实现提示】(1)已定票的客户名单可采用线性表及其链
9、表结构存储,等候替补的客户名单可采用队列。(2)系统每条航线信息可采用线性表及其顺序结构存储。(3)每条航线信息结构:包括以上8个成员信息,其中已定票的客户名单成员为已定票的客户名单链表的头指针,等候替补的客户名单成员为分别指向队头和队尾的指针。实验三 二叉树及其应用实验目的1. 加深对二叉树的结构特性的理解;2. 熟练掌握二叉树的存储结构,特别是二叉链表结构的特点;3. 熟练掌握二叉树的遍历算法原理及实现;4. 学会编写实现二叉树的各种算法; 5. 掌握二叉树的应用方法;实验学时:建议24学时实验内容内容1: 二叉树及其操作【问题描述】建立一棵以二叉链表结构存储的二叉树,并对其进行遍历。求该
10、二叉树中的结点个数等操作。【基本要求】(1)建立二叉树的方法可以用教材中的先序方式建立,也可以根据二叉树的先序序列和中序序列来建立。(2)对二叉树的遍历可采用递归或非递归的算法。【实现提示】(1) 二叉链表的结点结构描述typedef struct btnode / 定义结点类型ElemType data; /数据域 struct btnode * lchild,* rchild; /左、右指针域/ *bitree; / btnode(2) 可设计以下功能函数:bitree createbitree(); /建立二叉链表void preorder(bitree bt); /先序遍历二叉树int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 上机 实验 指导
限制150内