〈数据结构〉上机实验指导.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

11、 sum(bitree bt); /求二叉树中的结点个数算法可用递归或非递归实现。建立二叉树可用以下两种算法实现：方案1：btnode * createBT ( ) /前序建树 bitree T; char ch; cin ch ; if(ch=#) return NULL; /二叉树为空 T=new BinTNode; /申请根结点 T-data=ch; T-lchild=createBTpre(); /创建根的左子树 T-rchild=createBTpre(); /创建根的右子树 return T;方案2：btnode* createBT ( char *preorder,char *m

12、idorder) /由前序preorder和中序midorder建树，返回根指针 if(strlen (preorder) =0) return NULL; /空二叉树 T= new Node; /建立根结点 T-data=*preorder; k=locate(midorder， *preorder); /找根在中序中的位置 lmidorder=fetch(midorder,0,k); /左子树的中序 lpreorder =fetch(preorder,1,k); /左子树的前序 rmidorder=fetch(midorder,k+1); /右子树的中序 rpreorder =fetch(

13、preorder, k+1); /右子树的前序 T-lchild=createBT (lmidorder , lpreorder);/建根的左子树 T-rchild=createBT(rmidorder , rpreorder); /建根的右子树 return T;int sum(bitree bt) /求二叉树中的结点个数 if(!bt) return 0; /二叉树为空return sum(bt-lchild) + sum(bt-rchild) +1;【选做内容】（1） 对二叉树进行层次遍历算法。（2） 求二叉树的深度、宽度等操作。（3） 复制二叉树，交换二叉树中左右子树的问题怎么实现?内

14、容2：哈夫曼编码/译码器【问题描述】51481156357203251频度zyxwvut字符11611882380频度p21fq15gr47hsonmlkj字符5710332221364186频度iedcba空格字符设字符集为26个英文字母，其出现频度如下表所示。先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。【基本要求】算法具有以下功能：（1）CreateHuffmanTree：根据给定字符的出现频数，建立其哈夫曼树。（2）Encoding：对给定的原字符串进行编码。（4） Decoding：对给定的编码串进行译码（或解码）。（5） S

15、howHuffmanTree：显示哈夫曼树【实现提示】（1） 用户界面可设计成模拟菜单方式。（2） 原字符串及编码串可从键盘输入。（3） 生成Huffman树的步骤如下：由给定的 n 个权值w1, w2, , wn构成n棵二叉树的集合（即森林）F = T1, T2, , Tn ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。在F 中选取两棵根结点的权值最小的树 做为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F 中删去这两棵树，同时将新得到的二叉树加入 F中。重复 和, 直到 F 只含一棵树为止。这棵树便是赫夫曼树。【选做

16、内容】（1） 字符的出现频数能否从指定文件中统计而得？（2） 对指定的文件进行编码/解码。实验四 图及其应用实验目的1. 加深对图的结构的理解；2. 熟练掌握图的存储结构，特别是图的邻接表结构；3. 熟练掌握图的搜索算法原理及其实现；4. 掌握图的常用的应用方法。 实验学时：建议24学时实验内容内容1： 图的搜索问题【问题描述】设计一个程序，演示在连通的无向图上访问全部结点的操作。【基本要求】（1）以邻接表作为存储结构，并图进行深度优先和广度优先搜索。（2）以用户指定的结点为起点，分别输出每种搜索方式下的结点访问序列和相应生成树的边集。【实现提示】（1）图的每个结点用一个编号表示（如1n）。通

17、过输入图的全部边来输入一个图，每个边是一个数对。（2）数据结构描述见教材。（3）可设计以下三个函数过程：void createadjlist( &T)；/建立图的邻接表void desttraverse(T)；/图的深度优先搜索void besttraverse(T)；/图的广度优先搜索【选做内容】借助栈，用非递归算法实现深度优先搜索。内容2： 教学计划编制问题【问题描述】教学计划中各课程之间必须满足先修关系。每门课程的先修课程是确定的，可以有任意多门，也可以没有。试在这样的前提下设计一个教学计划编制的程序。【基本要求】（1）输入数据包括：学期总数、一学期的学分上限、课程号、课程学分和直接先修

18、课程的课程号。（2）编排策略：使每学期的总学分数尽量均匀。【实现提示】可设学期总数不超过12，课程总数不超过100。【选做内容】产生多种不同的方案，并使方案之间的差异尽可能大。实验五 查找实验目的1熟练掌握顺序表和有序表的查找方法及算法实现。2熟悉常用查找算法的编写。3理解静态查找和折半查找的关系。4熟练掌握二叉排序树的构造和查找方法。5通过上机操作,理解如何科学地组织信息存储,并选择高效的查找算法。实验学时：建议2学时实验内容内容1： 基本查找算法【问题描述】设计一个程序，演示折半查找和二叉排序树查找过程。【基本要求】（1）建立一棵二叉排序树，采用二叉链表存储结构，并进行查找。（2）给出一组

19、有序数，对其进行折半查找。【实现提示】（1）可设计以下三个功能函数：status insertbst(bitree &bt,elemtype e);/当二叉排序树中不存在关键字等于e.key的数据元素时,插入e 并返回truesearchebst(bitree bt,keytype key);/在根指针bt所指二叉树中递归地查找关键字等于key的数据元素,若查找成功,则返回指向该数据元素结点的指针,否则返回空指针。int Search_Bin(SSTable ST，keytype key)；/折半查找算法（2）可设计递归算法。【选做内容】设计非递归算法。内容2： 哈希表设计【问题描述】针对某集

20、体中的“人名”设计一个哈希表，完成相应的建表和查表程序。【基本要求】（1）人名用汉语拼音，待填入哈希表的人名共30个。（2）哈希函数用除留余数法构造，用线性探测再散列法处理冲突。【实现提示】（1） 数据结构设计人名用指向字符的指针表示，因而哈希表可设计成线性结构（即指针组）。（2） 设计以下的功能函数：status create_hash(H);/ 哈希表的建表操作int search_hash (H ,name);/ 哈希表的查表操作【选做内容】（1） 用链地址法处理冲突。（2） 通过分析给定人名的特点，设计出具有不（或较少）冲突的哈希函数。实验六 排序实验目的1深刻理解排序的定义和各种排序

21、方法的特点;2了解各种方法的排序过程及其依据的原则;3熟练掌握各种排序方法的时间复杂度的分析方法;4了解排序的过程及适用场合;5了解排序效果与采用算法的关系;6通过上机,加深对排序算法的理解.实验学时：建议2学时实验内容：内部排序算法比较【问题描述】设计一个程序，通过随机数据比较常用排序算法的关键字比较次数和关键字移动次数。【基本要求】（1）对以下排序算法进行比较：起泡排序、简单选择排序、直接插入排序、快速排序。（2）用随机数进行排序；至少用5组不同数据进行比较。（3）最后进行简单分析。【实现提示】在算法的适当位置插入对关键字比较次数和关键字移动次数的统计操作。【选做内容】对不同表长作试验，观察两指标的变化情况。