数据结构实验指导书.doc

算法与数据结构 实实 验验 指指 导导 书书 徐州师范大学计算机科学与技术学院 2009 年 12 月 前 言 数据结构是计算机课程的一门重要的基础课，它的教学要求大致有三个重 要方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为 数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并 初步掌握算法的时间分析和空间分析；其三，学习和掌握较为复杂的程序设计 技巧。 基于以上的三点要求，在本实验指导书中贯穿这样的中心思想：让学生通 过数据结构的实验课，理论结合实践，达到上述三点要求。并要以这三点要求 为出发点，力求理解结构、掌握算法、读懂程序。 本指导书里每个实验都包括四个部分，分别是实验目的、实验要求、实验 内容和课后思考。实验内容部分分两部分，一是基本操作部分，另一是实例应 用部分。对于基本操作部分实验内容的源码可以从课堂和书本上得到，所以学 生应该详细的读懂书上的相关部分，然后依据本指导书认真做实验。实验主要 内容是实例应用部分上，即在基本操作的基础上综合应用之解决一些常见实际 问题。在实验过程中，应当注意避免输入书上或老师课堂上给的程序了事，应 当事先编写自己的程序，上机调试，参考程序只是用做参考。另外，有些参考 程序也不是最佳的，应对之进行改进处理。实验时，还应多多考虑怎样将每一 个实验应用到实际当中去，举一反三，可以不必拘泥于某一个实验，要前后贯 通，注意对基本的数据结构的理解和普遍的算法的研究。 依据学生对知识的掌握程度，在每个实验的最后都给出若干思考题，以拓 展学生的知识范围，也引导学生将所学知识得以更好的应用。 本指导书适合全日制计算机应用专业本科学生，作为数据结构课程学习的 实验课辅导资料。本指导书在编写过程中遵循由难到易，由浅入深的学习思路， 让学生在使用过程中，不会有无从下手的感觉。在编写过程中，得到赵向军院 长、张永常院长、郭小荟主任以及曾经上过数据结构课程老师的大力支持和帮 助，在此表示衷心感谢。 1 目目 录录 实验一实验一 线性表（线性表（2 课时）课时）2 一、实验目的2 二、实验要求2 三、实验内容2 四、课后思考11 实验二实验二 栈和队列（栈和队列（4 课时）课时）12 一、实验目的12 二、实验要求12 三、实验内容13 四、课后思考15 实验三实验三 串（串（2 课时）课时）17 一、实验目的17 二、实验要求17 三、实验内容17 四、课后思考21 实验四实验四 二叉树（二叉树（4 课时）课时）22 一、实验目的22 二、实验要求22 三、实验内容22 四、课后思考27 实验五实验五 图的应用（图的应用（4 课时）课时）28 一、实验目的28 二、实验要求28 三、实验内容28 四、课后思考33 实验六实验六 查找（查找（4 课时）课时）34 一、实验目的34 二、实验要求34 三、实验内容34 四、课后思考38 实验实验 排序（排序（4 课时）课时）40 一、实验目的40 二、实验要求40 三、实验内容40 四、课后思考43 参考文献参考文献.44 2 实验一实验一 线性表（线性表（2 课时）课时） 一、实验目的一、实验目的 1. 掌握线性表的顺序表示、链式表示以及基本操作。 2. 熟悉循环链表的结构特点及应用原理。 3. 理解双向链表和静态链表的存储方式及操作方法。 二、实验要求二、实验要求 1. 实验课前，要求学生对 C+语言知识做简单的复习，特别是对 C+语言中数组 的用法做进一步掌握。 2. 熟悉实验室计算机的环境，检查 VC 是否能够正常运行。方法是输入一简单小 程序，对其进行编译和执行，其过程是否正常。 3. 课前复习线性表的顺序存储结构的定义及 C+语言实现以及线性表的链式存储 结构单链表的定义及 C+语言实现。 4. 认真整理源程序及其注释，将实验过程中编写的源代码和运行结果以统一格式 保存发送给老师，打印出程序的运行结果，并结合程序进行分析，并写出实验总结。 5. 完成实验报告（包括源程序、实验结果、算法分析、心得体会等） 。 三、实验内容三、实验内容 1基本操作练习基本操作练习 （1-1） 求 A = A B （1-2） 合并 LA 和 LB 到 LC 中 （1-3） 合并两个单链表 （1-4） 合并两个循环链表 2.具体实例应用具体实例应用 （1）编写程序，实现单链表就地逆置。 四、课后思考四、课后思考 1. 设计一算法实现：某电信部门想开发一个查询知名电子企业服务电话号码的程 序。要求对于任意给出的一个企业名称，若该企业已注册其服务电话号码，则迅速找 到其电话号码；否则指出没有该企业的服务电话号码。 2. 约瑟夫环问题： 编号为 1，2，n 的 n 个人按照顺时针方向围坐一圈。从 第一个人开始顺时针方向自 1 开始报数，报到 m 时停止报数。报 m 的人出列，从他 在顺时针方向的下一个人开始重新报数，如此下去，直到所有人全部出列为止。设计 一个程序来求出出列顺序。其中 n,m 由键盘输入。 3 参考思路： 思路 1： 利用数组存放 n 个人，数组下标等于他的编号，然后模拟报数过程， 报到 m 时输出该位置的人编号，然后该位置的值清 0，继续报数并判断是否为 0，是 0 则跳过。直到 n 个人全部出列为止。 思路 2: 建立一个循环数组，数组元素的每一个值保存的是它的下一个元素的 编号，如果报到 m 后只要修改 m 前面的元素的编号为 m 后面的元素的编号，这样就 跳过了第 m 个元素，如此下去直到 n 个人全部出列。 4 实验二实验二 栈和队列（栈和队列（4 课时）课时） 一、实验目的一、实验目的 1. 熟悉掌握栈和队列的抽象数据类型。 2. 掌握实现栈和队列的各种操作的算法。 3. 理解栈与递归的关系。 二、实验要求二、实验要求 1. 实验课前复习栈的顺序存储结构 （1）类型定义： （2）栈的初始化操作 2. 复习栈的链式存储结构 3. 对于队列，思考队列链式存储结构与栈的链式存储结构不同之处，并付诸于上 机实现。 4. 在 VC 编程环境下，验证教材中给出的例题，在此基础上完成本实验内容所列 的实验任务。 5. 认真整理源程序及其注释，将实验过程中编写的源代码和运行结果以统一格式 保存发送给老师，打印出程序的运行结果，并结合程序进行分析，并写出实验总结， 完成实验报告。 三、实验内容三、实验内容 1. 基本操作练习基本操作练习 （1）取栈顶元素 （2）进栈操作 （3）出栈操作 （4）链栈的基本操作 （5）链队列的基本操作 2. 应用实例应用实例 （1）设计算法实现火车车厢重排问题 问题描述：一列货运列车共有 n 节车厢，每节车厢将停放在不同的车站。假定 n 个车站的编号分别为 1n, 即货运列车按照第 n 站至第 1 站的次序经过这些车站。为了 便于从列车上卸掉相应的车厢，车厢的编号应与目的地的编号相同，使各车厢从前至 后按编号 1 到 n 的次序排列，这样，在每个车站只需卸掉最后一节车厢即可。所以， 给定任意次序的车厢，必须重新排列它们。可能通过转轨站完成车厢的重排工作，在 转轨站中有一个入轨、一个出轨和 k 个缓冲轨，缓冲轨位于入轨和出轨之间。开始时， n 节车厢从入轨进入转轨站，转轨结束时各车厢按照编号 1 至 n 的次序离开转轨站进入 5 出轨。 基本要求：设计存储结构表示 n 个车厢、k 个缓冲轨以及入轨和出轨；设计并实 现车厢重排算法；分析算法的时间性能。 参考运行结果： 图 2-1 车厢重排结果图 （2）编写程序判断读入的字符系列是否为“回文”（正读和反读都相同的字符系列） 。 要求：同时用栈和队列，将输入的元素分别进栈和进队列，然后退栈和出队，若 两者出来的顺序相同则是“回文”。若是，则返回 1，否则返回 0. （3）设计算法实现银行排队问题 问题描述：设银行有 n 个服务窗口，每个窗口均可以办理存款、取款、挂失、还 贷业务，每种业务所需的服务时间不同，客户到达银行后，先到打号机上打号，号票 上包括到达时间、编号和需要办理的业务，然后在银行内等候。每个窗口办理完一个 客户的业务后，办理等候客户中排在最前面的客户的业务。 基本要求：设计算法实现： 编写银行排队叫号队列 编写银行服务窗口叫号操作。 参考运行结果： 6 图 2-2 银行排队结果图 （4）合并两个带头结点的有序循环链表合并为一个带头结点的有序循环链表 四、课后思考四、课后思考 1. 设计算法编程实现，利用循环队列生成杨辉三角形。 2. 编程实现中缀表达式转换为后缀表达式。 提示：要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式， 必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先 级高 的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，那么求值 顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序 （从右至左或从左至右） 。 转换过程包括用下面的算法读入中缀表达式的操作数、操 作符和括号： (1) 初始化一个空堆栈，将结果字符串变量置空。 (2) 从左到右读入中缀表达式，每次一个字符。 (3) 如果字符是操作数，将它添加到结果字符串。 (4) 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis） 、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入 （push）堆栈。 (5) 如果字符是个开括号，把它压入堆栈。 (6) 如果字符是个闭括号（closing parenthesis） ，在遇见开括号前，弹出所有操作 7 符，然后把它们添加到结果字符串。 (7) 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。 8 实验三实验三 串（串（2 课时）课时） 一、实验目的一、实验目的 1. 熟悉串的表示和实现。 2. 掌握串的模式匹配算法以及串的基本运算顺序结构上的实现。 3. 理解串在文本编辑操作中的应用。 二、实验要求二、实验要求 1. 本实验主要考查学生在处理非数值问题时对串的应用，在做本实验之前，先进 一步熟悉和掌握串的基本操作。 串插入 Status StrInsert(HString if (posS.length+1) return ERROR; if (T.length) if (!(S.ch=(char*) realloc(S.ch,(S.length+T.length)*sizeof(char) exit(OVERFLOW); 9 for (i=S.length-1;i=pos-1;-i) S.chi+T.length=S.chi; for (i=0; iS.length | lenS.length-pos+1) return ERROR; if (!len) Sub.ch=NULL; Sub.length=0; else Sub.ch=(char *)malloc(len*sizeof(char); for (int j=0;jT0) return i-T0; /匹配成功 else return 0; 2. 实例应用实例应用 （1）编写程序实现：求子串在主串中的位置，并置换子串：给定主串和子串，显 示出子串在主串中的第一个位置，基子串在主串中不存在，则返 0；若非零则用给定的 串替换子串。 参考运行结果： 图 3-1 串替换运行结果 （2）输入 3 个字符串 s，t，x, 在字符串 s 中查找字符串 t，并将字符串 s 中包含 的所有字符串 t 替换为 x。 参考运行结果： 图 3-2 串查找并替换运行结果 （3）综合利用串的基本操作设计一算法实现：将串 T 插入到串 S 的第 i 个位置上， 若 i 大于 S 的长度，则插入不执行。 12 四、课后思考四、课后思考 1. 用串解决“以一敌百”游戏的编程。 2. 编写算法实现：统计在一个输入字符串中各个不同字符出现的频度。用适当的 测试数据来验证这个算法。 13 实验四实验四 二叉树（二叉树（4 课时）课时） 一、实验目的一、实验目的 1. 熟悉树和二叉树的定义和基本术语。 2. 掌握二叉树的存储结构以及二叉树的基本操作。 3. 理解遍历二叉树和线索化二叉树算法思想。 二、实验要求二、实验要求 1. 实验课前进一步熟悉树和二叉树概念。 2. 完成利用 C+对二叉树的顺序存储和链式存储结构的实现。 3. 验证遍历二叉树、线索二叉树以及二叉树遍历应用算法。 4. 对实验内容里所列的实例进行算法设计、编写源代码、上机调试、显示调试结 果，写出实验总结。. 三、实验内容三、实验内容 1. 基本操作练习基本操作练习 （1）二叉链表定义）二叉链表定义 typedef struct BiTNode /二叉链表的定义 TElemType data; Struct BiTNode *lchild,*rchild; BiTNode, *BiTree; （2）先序遍历二叉树）先序遍历二叉树 void PreOrderTraverse(BiTree T) / 利用递归思想 if (T) printf(“%c“,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); void preorder(BiTree T) / 非递归思想 SqStack S; BiTree P=T; 14 InitStack(S); Push(S,NULL); while (P) printf(“%c“,P-data); if (P-rchild) Push(S,P-rchild); if (P-lchild) P=P-lchild; else Pop(S,P); （3）中序遍历二叉树）中序遍历二叉树 void InOrderTraverse(BiTree T) / 利用递归思想 if (T) InOrderTraverse(T-lchild); printf(“%c“,T-data); InOrderTraverse(T-rchild); void inorder(BiTree T) / 非递归 SqStack S; BiTree P=T; InitStack(S); do while(P)* (S.top) = P;S.top+;P=P-lchild; if (S.top) S.top-; P=*(S.top); printf(“%c“,P-data); P=P-rchild; while(S.top!=S.base) | P); 15 （4）后序遍历二叉树）后序遍历二叉树 void PostOrderTraverse(BiTree T) / 利用递归思想 if (T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(“%c“,T-data); void Postorder(BiTree T) / 非递归 BiTree p=T,q=NULL;/ q 指向最近一次访问过的结点 SqStack S;InitStack(S); Push(S,p); while (!StackEmpty(S) if (p p=p-lchild; else Pop(S,p); if (!StackEmpty(S) if (p-rchild p=p-rchild; else printf(“%c“,p-data); q=p; （5）二叉树显示）二叉树显示 void PrintBiTree(BiTree T,int n) int i; char ch= ; if (T) PrintBiTree(T-rchild,n+1); for (i=1;idata); PrintBiTree(T-lchild,n+1); （6）利用二叉树后序遍历计算二叉树的深度）利用二叉树后序遍历计算二叉树的深度 int Depth(BiTree T) int depl,depr; if (T) depl=Depth(T-lchild); depr=Depth(T-rchild); if (depl=depr) return (depl+1); else return (depr+1); return 0; （7）计算二叉树结点个数）计算二叉树结点个数 int Size(BiTree T) if (T=NULL) return 0; else return 1 + Size (T-lchild ) + Size ( T-rchild); （8）建立赫夫曼树及求赫夫曼编码）建立赫夫曼树及求赫夫曼编码 typedef struct unsigned int weight; /用来存放结点的权值 unsigned int parent,lchild,rchild; /孩子和双亲 HTNode, *HuffmanTree; /动态分配数组存储赫夫曼树 typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表 void HuffmanCoding(HuffmanTree char *cd; int i,s1,s2,start; unsigned int c,f; 17 if (nweight = *w; p-parent=0; p-lchild=0; p-rchild=0; /初始的 n 个结点 for (; iweight = 0; p-parent=0; p-lchild=0; p-rchild=0; /将要生成的 n-1 个结点 for (i=n+1; iadjvex=j; p-info = w; p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p; return; （3）深度优先遍历（）深度优先遍历（DFST） Boolean visitedMAX ； Status (*VisitFunc)(int v) ； void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历 VisitFunc = Visit; for (v=0; v=0 ; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / BFSTraverse （5）最小生成树构造）最小生成树构造PRIM 算法算法 void MiniSpantree_PRIM( mgraph G, VertexType u ) 辅助数组 closedge 的定义略 k=LocateVex(G,u); for (j=0; j #define MAX_SIZE 100 typedef struct int key; element; element sMAX_SIZE; int seqsearch(element s,int key,int num); int main() int i,num,key; printf(“how much number do you want to enter?“); scanf(“%d“, for(i=0;i #define MAX_SIZE 100 #define COMPARE(a,b) (a)(b)?1:(a)=(b)?0:-1 27 typedef struct int key; element; element listMAX_SIZE; int binsearch(element list,int key,int num); int main() int i,num,key; printf(“please enter numbers in increasing order.nhow many numbers do you want to enter?“); scanf(“%d“, for(i=0;idata.key) p=T;return TRUE; else if (LT(key,T-data.key) return SearchBST(T-lchild,key,T,p); else return SearchBST(T-rchild,key,T,p); （4）二叉排序树删除结点算法 int Delete(BiTree if (!p-rchild)/右子树空则只需重接它的左子树 q=p; p=p-lchild; free(q); else if (!p-lchild)/只需重连它的右子树 q=p; p=q-rchild; free(q); else/左右子树均不空 q=p; s=p-lchild; while (s-rchild) q=s; s=s-rchild;/转左,然后向右到尽头 p-data=s-data;/s 指向被删除接点的前驱 if (q!=p) q-rchild = s-lchild;/重接*q 的右子树 else q-lchild = s-lchild;/重接*q 的左子树 delete s; return TRUE; 2. 具体实例应用具体实例应用 （1）输 入 一 串 正 整 数 数 据， 最 后 以 1 作 为 结 束 的 标 志。 首 先， 请 建 立 一 棵 排 序 二 叉 树。 然 后， 再 输 入 每 个 结 点 的 权 值， 您 能 否 将 此 树 中 的 结 点 进 行 调 整， 使 得 对 二 叉 树 的 查 找 代 价 最 小， 即 建 立 一 棵 最 佳 查 找 树。 （2）作 为 输 入 给 定 的 是 已 分 类 的 数 列： a1,a2,a3, , an, 以 及 随后 的“ 问 题” 序 列： b1,b2,b3, , bn. 请 编 写 一 个 程 序， 首 先 顺 序存 储 数 列a1,a2,a3, , an, 然 后 用 折 半 查 找 法 对 每 个 问 题 bi 找 出使aj 等 于 bi 的 一 切 j , 当 没 有 这样 的j 及 有 多 个 这 样 的j 时， 程 序也 应 能 够 正 常 工 作。 四、课后思考四、课后思考 1. 设计算法实现：定义一个散列函数，例如 f(x)=(x mod 19)+19)mod 19，从键盘 输入一数列，依次插入到散列表中去，采用线性探测方法解决碰撞问题。 输入一个数 字，根据你所选择的散列函数进行相应的查找，输出查找结果。 2. 输 入 一 串 正 整 数 数 据， 最 后 以 1 作 为 结 束 的 标 志。 首 先， 请 建 立 一 棵 排 序 二 叉 树。 然 后， 再 输 入 每 个 结 点 的 权 值， 您 能 否 将 此 树 中 的 结 点 进 行 调 整， 使 得 对 二 叉 树 的 查 找 代 价 最 小， 即 建 立 一 棵 最 佳 查 找 树。 3. 如 果 在 二 叉 树 的 定 义 中 允 许 出 现 具 有 相 同 关 键 字 的 结 点。试 编 写 以 动 31 态 存 储 结 构 存 储 的 排 序 二 叉 树 的 插 入 及 删 除 程 序。 32 实验七实验七 排序（排序（4 课时）课时） 一、实验目的一、实验目的 1. 熟悉一些常用的简单排序方法。 2. 掌握各种常用排序方法的基本思想、排序过程、算法实现，能进行时间和空间 性能的分析，根据实际问题的特点和要求选择合适的排序方法。 3. 了解磁盘文件排序和磁带文件排序的算法思想。 二、实验要求二、实验要求 1. 认真阅读和掌握教材中给出的算法思想。 2. 上机实现各种内部排序算法。 3. 对实验内容里所列的实例进行算法设计、编写源代码、上机调试、显示调试结 果。4. 认真整理源程序及其注释，将实验过程中编写的源代码和运行结果以统一 格式保存发送给老师，打印出程序的运行结果，并结合程序进行分析，并写出实 验总结。 5. 完成实验报告（包括源程序、实验结果、算法分析、心得体会等） 。 三、实验内容三、实验内容 1. 基本操作练习基本操作练习 （1）直接插入排序算法直接插入排序算法 void InsertSort(SqList i L.rj+1.key ) L.r0 = L.rj; L.rj