《NYIST_数据结构实验指导书.docx》由会员分享，可在线阅读，更多相关《NYIST_数据结构实验指导书.docx（24页珍藏版）》请在三一文库上搜索。
1、南阳理工学院数据结构上机实验指导书（2011 版）软件学院软件工程教研室2011.3.目录实验 1 线性表应用2实验 2 栈和队列的应用3实验 3 线性表应用6实验 4 图论及其应用17实验 5 查找19实验 6 排序22.实验 1 线性表应用一、实验目的1. 了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。2. 能够利用线性表结构对实际问题进行分析建模，利用计算机求解。3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。二、实验内容及步骤1. 利用程序设计语言分别实现顺序表和链表的抽象数据类型。2. 掌握程序分文件（头文件和实现文
2、件）书写的方式。3. 分别用顺序表和链表实现课本算法 2.2 ：合并两个非递减有序序列，并对其时间性能做出分析。 P21#includec1.htypedef int ElemType;#includec2-1.h#includebo2-1.c#includefunc2-3.c/*包括 equal() 、comp() 、print()、print2()和 print1()函数 */void MergeList(SqList La,SqList Lb,SqList *Lc) /*算法 2.2 */ /*已知线性表 La 和 Lb 中的数据元素按值非递减排列。*/*归并 La 和 Lb 得到新的线
3、性表Lc，Lc 的数据元素也按值非递减排列*/int i=1,j=1,k=0;int La_len,Lb_len;ElemType ai,bj;InitList(Lc); /*创建空表 Lc */La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len&j=Lb_len) /*表 La 和表 Lb 均非空 */GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else.ListInsert(Lc,+k,bj);+j; /*以下两个 while 循环
4、只会有一个被执行 */while(i=La_len) /*表 La 非空且表 Lb 空 */GetElem(La,i+,&ai);ListInsert(Lc,+k,ai);while(j=Lb_len) /*表 Lb 非空且表 La 空 */GetElem(Lb,j+,&bj);ListInsert(Lc,+k,bj);void main()SqList La,Lb,Lc;int j,a4=3,5,8,11,b7=2,6,8,9,11,15,20;InitList(&La); /*创建空表 La */for(j=1;j=4;j+) /*在表 La 中插入 4 个元素 */ListInsert(
5、&La,j,aj-1);printf(La= ); /*输出表 La 的内容 */ListTraverse(La,print1);InitList(&Lb); /*创建空表 Lb */for(j=1;j=7;j+) /*在表 Lb 中插入 7 个元素 */ListInsert(&Lb,j,bj-1);printf(Lb= ); /*输出表 Lb 的内容 */ListTraverse(Lb,print1);MergeList(La,Lb,&Lc);printf(Lc= ); /*输出表 Lc 的内容 */ListTraverse(Lc,print1);实验 2 栈和队列的应用一、实验目的1. 掌
6、握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。.2. 熟练掌握栈类型的两种实现方法。3. 熟练掌握循环队列和链队列的基本操作实现算法。二、实验内容及步骤1. 用程序设计语言实现栈和队列的抽象数据类型。2. 在第一题的基础上完成以下选择：选择一：1) 设计并实现括号匹配算法。2) 用队列实现在屏幕上打印杨辉三角。选择二：分别用栈和队列实现迷宫问题求解。选择三：分别用栈和队列实现一个列车调度系统。1.import java.util.Scanner;public class括号配对 public static void main(String args)int top=0
7、;/堆指针boolean end=true;/不匹配时只输出一次char stack=new char100;/存括号String s;System.out.println(请输入表达式： );Scanner scanner=new Scanner(System.in);s=scanner.next();/表达式char biao=s.toCharArray();/将字符串转化成字符数组System.out.println(表达式 :+s);for(inti=0;ibiao.length&end;i+)/遍历表达式中所有字符if(biaoi=()/如果是 ( 则入栈stacktop=(;top
8、+;else if(biaoi=)/如果是 ) 则出栈.if(!(top=0)top-;elseSystem.out.println(括号不匹配 );end=false;/除循环两种可能if(top=0&end)System.out.println(括号匹配 );/出循环 stack 空else if(top!=0&end)System.out.println(括号不匹配 );/出循环时 stack 不空2. #include #define N 11void main()int i,j,aNN;for(i=1;iN;i+)aii=1;ai1=1;for(i=3;iN;i+)for(j=2;j
9、i;j+)aij=ai-1j-1+ai-1j;for(i=1;iN;i+)for(j=1;j=i;j+)printf(%6d,aij);printf(n);.实验 3 线性表应用一、实验目的1. 领会并理解二叉树的类型定义。2. 熟练掌握二叉树的主要特性， 。3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4. 熟练掌握二叉树和树的各种存储结构及其建立的算法。二、实验内容及步骤1. 实现二叉树的抽象数据类型。2. 构造一棵二叉树并用递归实现其先序、中序、后序遍历算法并验证。3. 用非递归算法实现二叉树的中序遍历。一、二叉树的抽象数据类型：ADT BinaryTre
10、e/ 数据对象 D：D 是具有相同特性的数据元素的集合。/ 数据关系 R：/ 若 D=，则 R=，称 BinaryTree 为空二叉树；/ 若 D，则 R=H，H 是如下二元关系；/（1）在 D 中存在惟一的称为根的数据元素root ，它在关系 H下无前驱；/（2）若 D-root，则存在D-root=D1,Dr，且 D1Dr = ；/ （ 3）若 D1，则 D1中存在惟一的元素 x1， H，且存在 D1 上的关系 H1 ? H；若 Dr，则 Dr 中存在惟一的元素 xr ， H，且存在上的关系 Hr ? H；H=,H1,Hr；/ （4）(D1,H1) 是一棵符合本定义的二叉树，称为根的左子树
11、； (Dr,Hr) 是一棵符合本定义的二叉树，称为根的右子树。/ 基本操作：InitBiTree( &T )/操作结果：构造空二叉树T。.DestroyBiTree( &T )/ 初始条件：二叉树 T 已存在。/ 操作结果：销毁二叉树 T。CreateBiTree( &T, definition )/初始条件： definition给出二叉树T 的定义。/ 操作结果：按 definiton 构造二叉树 T。ClearBiTree( &T )/ 初始条件：二叉树 T 存在。/ 操作结果：将二叉树 T 清为空树。BiTreeEmpty( T )/ 初始条件：二叉树 T 存在。/ 操作结果：若 T
12、为空二叉树，则返回 TRUE，否则返回 FALSE。BiTreeDepth( T )/ 初始条件：二叉树 T 存在。/ 操作结果：返回 T 的深度。Root( T )/ 初始条件：二叉树 T 存在。/ 操作结果：返回 T 的根。Value( T, e )/ 初始条件：二叉树 T 存在， e 是 T 中某个结点。/ 操作结果：返回 e 的值。Assign( T, &e, value )/ 初始条件：二叉树 T 存在， e 是 T 中某个结点。/ 操作结果：结点 e 赋值为 value 。Parent( T, e )/ 初始条件：二叉树 T 存在， e 是 T 中某个结点。/ 操作结果：若 e 是
13、 T 的非根结点，则返回它的双亲，否则返回“空”。LeftChild( T, e )/ 初始条件：二叉树 T 存在， e 是 T 中某个结点。/ 操作结果：返回 e 的左孩子。若 e 无左孩子，则返回“空”。.RightChild( T, e )/ 初始条件：二叉树 T 存在， e 是 T 中某个结点。/ 操作结果：返回 e 的右孩子。若 e 无右孩子，则返回“空”。LeftSibling( T, e )/ 初始条件：二叉树 T 存在， e 是 T 中某个结点。/ 操作结果：返回 e 的左兄弟。若 e 是 T 的左孩子或无左兄弟，则返回“空”。RightSibling( T, e )/ 初始条
14、件：二叉树 T 存在， e 是 T 中某个结点。/ 操作结果：返回 e 的右兄弟。若 e 是 T 的右孩子或无右兄弟，则返回“空”。InsertChild( T, p, LR, c )/初始条件：二叉树T 存在， p 指向 T 中某个结点， LR为 0 或 1，非空二叉树c 与 T 不相交且右子树为空。/ 操作结果：根据 LR为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。 p 所指结点的原有左或右子树则成为 c 的右子树。DeleteChild( T, p, LR )/ 初始条件：二叉树 T 存在， p 指向/ 操作结果：根据 LR为 0 或 1，删除T 中某个结点， LR为
15、 0 或 1。T 中 p 所指结点的左或右子树。PreOrderTraverse( T, visit() )/初始条件：二叉树T 存在， Visit是对结点操作的应用函数。/ 操作结果：先序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。InOrderTraverse( T, visit() )/初始条件：二叉树T 存在， Visit是对结点操作的应用函数。/ 操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。PostOrderTraverse( T, visit() )/初始条件：二叉
16、树T 存在， Visit是对结点操作的应用函数。/ 操作结果：后序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。LevelOrderTraverse( T, visit() )/初始条件：二叉树T 存在， Visit是对结点操作的应用函数。/ 操作结果：层次遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。.ADT BinaryTree/ 二、基本操作的实现：/ 二叉树的结点结构体：typedef structTElemType data;struct BiTNode *lchild,*rchild
17、;BiTNode,*BiTree;/ 二叉树的创建：/*/*按照前序遍历建立二叉树*/*/Status CreateBiTree(BiTree &T)/ 按先序次序输入二叉树中结点的值（一个字符），/ 空格字符表示空树，构造二叉链表表示的二叉树T。char ch;ch = getchar();/scanf(%c,&ch);if(ch = )T = NULL;elseif(!(T = (BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data = ch;/生成根结点CreateBiTree(T-lchild);/ 构造左子树CreateBiTree
18、(T-rchild);/ 构造右子树return OK;/*/*按层次顺序建立一棵二叉树：队.列*/*/Status LevelCreateBiTree(BiTree &T)BiTree p,s;/p指向父亲结点， s 指向孩子结点Queue BiNodeQueue;char ch;ch=getchar();if(ch= )return NULL;T=(BiTNode*)malloc(sizeof(BiTNode); /生成根结点T-data=ch;EnQueue(BiNodeQueue,T); /用队列实现层次遍历while(!BiNodeQueue.Empty()DeQueue(BiNod
19、eQueue,p);ch=getchar(); /为了简化操作，分别对左右子结点进行赋值。if(ch!= )/子树不空则进队列进行扩充。下同s=(BiTNode*)malloc(sizeof(BiTNode);s-data=ch;p-lchild=s;EnQueue(BiNodeQueue,s);elsep-lchild=NULL;ch=getchar();if(ch!= )s=(BiTNode*)malloc(sizeof(BiTNode);s-data=ch;p-rchild=s;EnQueue(BiNodeQueue,s);else.p-rchild=NULL;return OK;/2.
20、 二叉树的前序遍历：/*/*按照前序递归遍历二叉树*/*/Status PreOrderTraverse(BiTree T)if(T)printf(%d,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);return OK;/*/*按照前序非递归遍历二叉树：栈*/*/Status PreOrderTraverse(BiTree T)stack S;InitStack(S);BiTree p=T;/p指向当前访问的结点while(p|!StackEmpty(S)if(p)printf(%c,p-data);Push(S,p
21、);p=p-lchild;.elsePop(S,p);p=p-rchild;return OK;/3. 二叉树的中序遍历：/*/*按照中序递归遍历二叉树*/*/Status InOrderTraverse(BiTree T)if(T)InOrderTraverse(T-lchild);printf(%d,T-data);InOrderTraverse(T-rchild);return OK;/*/*按照中序非递归遍历二叉树*/*/Status InOrderTraverse(BiTree T)stack S;BiTree p;InitStack(S);Push(S, T);while (!St
22、ackEmpty(S)while (GetTop(S, p) & p)Push(S, p-lchild);/向左走到尽头Pop(S, p);/空指针退栈 ( 叶子的左孩子 )if (!StackEmpty(S)/访问结点，向右一步.Pop(S, p);printf(%d,p-data);/当前根结点Push(S, p-rchild);return OK;/*/*按照中序非递归遍历二叉树*/*/Status InOrderTraverse(BiTree T)stack S;InitStack(S);BiTree p=T;while (p | !StackEmpty(S)if (p)Push(S,
23、 p);p = p-lchild;/ 非空指针进栈，继续左进else/ 上层指针退栈，访问其所指结点，再向右进Pop(S, p);printf(%d,p-data);p = p-rchild;return OK;/ 二叉树的后序遍历：/*/*按照后序递归遍历二叉树*/*/Status PostOrderTraverse(BiTree T).if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(%d,T-data);return OK;/*/* 按照后序非递归遍历二叉树 */ /*/Status PostOrder
24、Traverse(BiTree T)stack S;InitStack(S);BiTree p=T,pre=NULL;while ( p | !StackEmpty(S)if (p)Push(S,p);p = p-left;elsePop(S,p);if (p-right!=NULL & pre!=p-right) /pre指向上次访问的右结点，避免再次访问p=p-right;elseprintf(%d,p-data);pre=p;p=NULL;./*/* 按照后序非递归遍历二叉树 */ /*/Status PostOrderTraverse(BiTree T)BiTree p = T,las
25、t = NULL;stack S;InitStack(S);Push(S,p);while(!StackEmpty(S)Pop(S,p);if(last = p-left | last = p-right)/左右子树已经访问完了，该访问根节点了printf(%d,p-data);last = p;else if(p-left | p-right) /左右子树未访问，当前节点入栈，左右节点入栈Push(S,p);if(p-right)Push(S,p-right);if(p-left)Push(S,p-left);else /当前节点为叶节点，访问printf(%d,p-data);last =
26、 p;./ 二叉树的层次遍历：/*/* 按照层次遍历二叉树 */ /*/void LevelOrderTraverse(BiTree T)Queue BiNodeQueue;BiTree p=T;EnQueue(BiNodeQueue,p);while(!BiNodeQueue.Empty()DeQueue(BiNodeQueue,p);if(p)printf(%c,p-data);EnQueue(BiNodeQueue,p-lchild);EnQueue(BiNodeQueue,p-rchild);/ 交换左右子树：/*/* 递归法将二叉树的左右子树互换 */ /*/void Exchang
27、e(BiTree T)BiTree temp;if(T)Exchange1(T-lchild);Exchange1(T-rchild);temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;./*/*非递归法将二叉树的左右子树互换*/*/void Exchange(BiTree T)stack S;InitStack(S);BiTree p=T,temp;while(p|!StackEmpty(S)if(p)Push(S,p);temp=p-lchild;p-lchild=p-rchild;p-rchild=temp;p=p-lchild;elsePop(
28、S,p);p-rchild;4. 给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。实验 4 图论及其应用一、实验目的1. 了解图的基本概念及术语 , 并能够熟练掌握图的两种存储结构 ( 邻接矩阵和邻接表 ) 。2. 理解最小生成树的概念，能按 Prim 算法构造最小生成树。.3. 掌握图的两种遍历 ( 深度优先搜索遍历和广度优先搜索遍历 ) 、拓扑排序、关键路径、最短路径的算法思想。二、实验内容及步骤1. 实现网（有权图）的存储结构。2. 利用 prim 算法构造它的最小生成树。3. 选择一个源点，寻找从原点出发到达其它顶点的最短路径。.实验5查找一、实验目的1. 理解 查找表 的
29、结构特点以及各种表示方法的适用性。2. 熟练掌握顺序查找和折半查找，并对其性能做出分析。3. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。二、 实验内容及步骤1. 实现查找表的顺序查找和折半查找算法。#include #include #include const int ARRSIZE= 10015;/ 从小到大排序数组元素void asort(int *a, int s)int i, j, k, t;for (i = 0; i s-1; +i)k = i;for (j = i + 1; j aj)k = j;if (k != i)t = ai;ai = ak;ak
30、 = t;./ 顺序查找，找到返回该元素数组下标，否则返回 -1 int SeqSearch(int *a, int s, int k)int i;for (i = 0; i s; +i)if (k = ai)return i;return -1;/ 折半查找，找到返回该元素数组下标，否则返回 -1 int BinSearch(int *a, int s, int k)int low = 0;int high = s - 1;while (low = high)int mid = (low + high) / 2;if (k = amid)return mid;elseif (k amid)high = mid - 1;elselow = mid + 1;return -1;/分块查找，找到返回该元素数组下标，否则返回-1 ，bs