NYIST_数据结构实验指导书

1、南阳理工学院数据结构上机实验指导书（2011 版）软件学院软件工程教研室2011.3实验1线性表应用2实验2栈和队列的应用 3实验3线性表应用 6实验4图论及其应用 17实验5查找19实验6排序22实验1线性表应用、实验目的1. 了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在 计算机中的实现。2. 能够利用线性表结构对实际问题进行分析建模，利用计算机求解。3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特 点及其适用场合。、实验内容及步骤1. 利用程序设计语言分别实现顺序表和链表的抽象数据类型。2. 掌握程序分文件(头文件和实现文件)书写的方式。3. 分别用顺

2、序表和链表实现课本算法2.2 :合并两个非递减有序序列，并对其时间性能做出分析。P21#i nclude"c1.h"typedef int ElemType;#i nclude"c2-1.h"#in clude"bo2-1.c"#include"func2-3.c"/* 包括 equal()、comp()、print() 、print2() 和 print1()函数*/void MergeList(SqList La,SqList Lb,SqList *Lc) /*算法 2.2 */ /* 已知线性表La和Lb中的

3、数据元素按值非递减排列。*/* 归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列*/ int i=1,j=1,k=O;int La_le n,Lb_le n;ElemType ai,bj;InitList(Lc); /*创建空表 Lc */La_le n=ListLe ngth(La);Lb_le n=ListLe ngth(Lb);while(i<=La_len&&j<=Lb_len) /*表 La 和表 Lb 均非空 */GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai<=bj)List I

4、n sert(Lc,+k,ai);+i;elseListl nsert(Lc,+k,bj);+j； /* 以下两个while循环只会有一个被执行*/while(i<=La_len) /* 表 La 非空且表 Lb 空 */GetElem(La,i+,&ai);List In sert(Lc,+k,ai);while(j<=Lb_len) /* 表 Lb 非空且表 La 空 */GetElem(Lb,j+,&bj);List In sert(Lc,+k,bj);void main()SqList La,Lb,Lc;int j,a4=3,5,8,11,b7=2,6,8,

5、9,11,15,20;InitList(&La); /*创建空表 La */for(j=1;j<=4;j+) /*在表La中插入4个元素*/ListI nsert(& La,j,aj-1);printf("La= "); /*输出表 La 的内容 */ListTraverse(La,pri nt1);InitList(&Lb); /*创建空表 Lb */for(j=1;j<=7;j+) /*在表Lb中插入7个元素*/ListI nsert(& Lb,j,bj-1);printf("Lb= "); /*输出表 L

6、b 的内容 */ListTraverse(Lb,pri nt1);MergeList(La,Lb,&Lc);printf("Lc= "); /*输出表 Lc 的内容 */ListTraverse(Lc,pri nt1);实验2栈和队列的应用、实验目的1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正 确选用它们。2. 熟练掌握栈类型的两种实现方法。3. 熟练掌握循环队列和链队列的基本操作实现算法。、实验内容及步骤1. 用程序设计语言实现栈和队列的抽象数据类型。2. 在第一题的基础上完成以下选择：选择一：1）设计并实现括号匹配算法。2）用队列实现在屏

7、幕上打印杨辉三角。选择二：分别用栈和队列实现迷宫问题求解。选择三：分别用栈和队列实现一个列车调度系统。l.import iava.util.Scanner;public class 括号配对public static void mai n( Stri ng args)int top-0;II堆指针不匹配时只输出一次boolea n en d-true;IIchar stack-new char100;II存括号Stri ng s;System.out.pri ntl n(”请输入表达式："）;Scanner sca nner-newScann er(System.i n);s=sca

8、 nner.n ext();II 表达式char biao=s.toCharArray();将字符串转化成字符数组(”表达式："+s);for(i nti=0;i<bia o.len gth&&en d;i+)/I遍历表达式中所有字符if(biaoi='(')/I如果是(则入栈stacktop='('top+;丄else if(biaoi=')')/I如果是)则出栈丄if(!(top=0)top-;else(”括号不匹配”);en d=false;" 除循环两种可能if(top=0&&en

9、d)System.out.println("括号匹配 ”);/出循环 stack 空else if(top!=0&&end)System.out.println("括号不匹配");/ 出循环时stack不空丄2. #i nclude <stdio.h>#defi ne N 11void mai n()int i,j,aNN;for(i=1;i<N;i+)aii=1;ai1=1;for(i=3;i<N;i+)for(j=2;j<i;j+) aij=ai-1j-1+ai-1j;for(i=1;i<N;i+)for(j

10、=1;j<=i;j+)prin tf("%6d",aij);prin tf("n");实验3线性表应用、实验目的1. 领会并理解二叉树的类型定义。2. 熟练掌握二叉树的主要特性，。3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的 其它操作。4. 熟练掌握二叉树和树的各种存储结构及其建立的算法。二、实验内容及步骤1. 实现二叉树的抽象数据类型。2. 构造一棵二叉树并用递归实现其先序、中序、后序遍历算法并验证。3. 用非递归算法实现二叉树的中序遍历。、二叉树的抽象数据类型：ADT Bi naryTree/数据对象D: D是具有相同特

11、性的数据元素的集合。/数据关系R/若 D=,贝U R=,称 BinaryTree 为空二叉树；/ 若 X，则R=H, H是如下二元关系；/(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；/(2)若 D-root工，则存在 D-root=D1,Dr，且 D1A Dr =；/(3)若D1工，贝U D1中存在惟一的元素x1，<root,x1> H,且存在D1上的关系H1 ?H；若Dr工，贝U Dr中存在惟一的元素xr， <root,xr> H,且存在上的关系 Hr ? H；H=<root,x1>,<root,xr>,H1,Hr ；/

12、(4) (D1,H1)是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。/基本操作：In itBiTree( &T)/操作结果：构造空二叉树 ToDestroyBiTree( &T)/初始条件：二叉树 T已存在。/操作结果：销毁二叉树ToCreateBiTree( &T, definition )/初始条件：definition 给岀二叉树T的定义。/ 操作结果：按definiton 构造二叉树T。ClearBiTree( &T)/初始条件：二叉树 T存在。/操作结果：将二叉树T清为空树。BiTreeEmpty(

13、T )/初始条件：二叉树 T存在。/ 操作结果：若T为空二叉树，则返回 TRUE否则返回FALSEBiTreeDepth( T )/初始条件：二叉树T存在。/操作结果：返回T的深度。Root( T )/初始条件：二叉树T存在。/操作结果：返回T的根。Value( T, e )/初始条件：二叉树T存在，e是T中某个结点。/操作结果：返回e的值。Assig n( T, &e, value )/初始条件：二叉树T存在，e是T中某个结点。/操作结果：结点e赋值为value。Pare nt( T, e )/初始条件：二叉树T存在，e是T中某个结点。/ 操作结果：若e是T的非根结点，则返回它的双亲

14、，否则返回“空”LeftChild( T, e )/初始条件：二叉树T存在，e是T中某个结点。/ 操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild( T, e )/ 初始条件：二叉树T存在，e是T中某个结点。/操作结果：返回e的右孩子。若e无右孩子，则返回“空”。LeftSibli ng( T, e )/ 初始条件：二叉树T存在，e是T中某个结点。/操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。RightSibli ng( T, e )/ 初始条件：二叉树T存在，e是T中某个结点。/操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空

15、”。In sertChild( 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指向T中某个结点，LR为0或1。/操作结果：根据LR为0或1删除T中p所指结点的左或右子树。PreOrderTraverse( T, visit()/ 初始条件：二叉树T存在，Visit是对结点操作的应用函数。/操作结果：先序遍历T，对每个结点调用函数Visi

16、t 次且仅一次。一旦visit() 失败，则操作失败。InO rderTraverse( T, visit()/ 初始条件：二叉树T存在，Visit是对结点操作的应用函数。/ 操作结果：中序遍历T，对每个结点调用函数Visit 次且仅一次。一旦visit() 失败， 则操作失败。PostOrderTraverse( T, visit()/ 初始条件：二叉树T存在，Visit是对结点操作的应用函数。/操作结果：后序遍历T，对每个结点调用函数Visit 次且仅一次。一旦visit() 失败，则操作失败。LevelOrderTraverse( T, visit()/ 初始条件：二叉树T存在，Visi

17、t是对结点操作的应用函数。/操作结果：层次遍历 T,对每个结点调用函数 Visit 次且仅一次。一旦 visit() 失败， 则操作失败。ADT Bin aryTree/二、基本操作的实现:/二叉树的结点结构体:typedef structTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/二叉树的创建:/*/*按照前序遍历建立二叉树*/*/Status CreateBiTree(BiTree &T)/按先序次序输入二叉树中结点的值（一个字符）， /空格字符表示空树，构造二叉链表表示的二叉树 char ch;ch

18、 = getchar();/sca nf("%c", &ch);if(ch ='')T = NULL;elseif(!(T = (BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T->data = ch;/生成根结点CreateBiTree (T->lchild);CreateBiTree (T->rchild);return OK;/*/*/构造左子树/构造右子树按层次顺序建立一棵二叉树：队列*/*/Status LevelCreateBiTree(BiTree &T)BiTre

19、e p,s;/p指向父亲结点，s指向孩子结点Queue BiNodeQueue;char ch;ch=getchar();if(ch='')return NULL;T=(BiTNode*)malloc(sizeof(BiTNode); /生成根结点T->data=ch;En Queue(BiNodeQueue,T); /用队列实现层次遍历 while(!BiNodeQueue.Empty()DeQueue(BiNodeQueue,p);ch=getchar(); /为了简化操作，分别对左右子结点进行赋值if(ch!=' ')/子树不空则进队列进行扩充。下同

20、s=(BiTNode*)malloc(sizeof(BiTNode);s->data=ch;p->lchild=s;En Queue(BiNodeQueue,s);elsep->lchild=NULL;ch=getchar();if(ch!='')s=(BiTNode*)malloc(sizeof(BiTNode);s->data=ch;p->rchild=s;En Queue(BiNodeQueue,s);elsep->rchild=NULL;return OK;2.二叉树的前序遍历:/*按照前序递归遍历二叉树*/*/*/Status Pr

21、eOrderTraverse(BiTree T)if(T)pri ntf("%d",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);return OK;/*/*按照前序非递归遍历二叉树：栈*/*/Status PreOrderTraverse(BiTree T)stack S;In itStack(S);BiTree p=T; /p指向当前访问的结点while(p|!StackEmpty(S)if(p)pri ntf("%c",p->data);Pu

22、sh(S,p);p=p->lchild;elsePop(S,p); p=p->rchild; return OK;3.二叉树的中序遍历：/*/按照中序递归遍历二叉树*/*/Status InO rderTraverse(BiTree T)if(T)In OrderTraverse (T->lchild); pri ntf("%d",T->data);In OrderTraverse(T->rchild);return OK;/*/按照中序非递归遍历二叉树*/*/Status InO rderTraverse(BiTree T)stack S;B

23、iTree p;In itStack(S);Push(S, T);while (!StackEmpty(S)while (GetTop(S, p) && p)Push(S, p->lchild);Pop(S, p);if (!StackEmpty(S)/ 访问结点，向右一步/向左走到尽头/空指针退栈（叶子的左孩子）Pop(S, p)；/当前根结点prin tf("%d",p->data);Push(S, p->rchild);return OK;/*/*按照中序非递归遍历二叉树*/*/Status InO rderTraverse(BiTr

24、ee T)stack S;In itStack(S);BiTree p=T;while (p | !StackEmpty(S)if (p)Push(S, p);p = p->lchild;/非空指针进栈，继续左进else/上层指针退栈，访问其所指结点，再向右进Pop(S, p);pri ntf("%d",p->data);p = p->rchild;return OK;/二叉树的后序遍历：/*/*按照后序递归遍历二叉树*/*/Status PostOrderTraverse(BiTree T)if(T)PostOrderTraverse (T->lc

25、hild);PostOrderTraverse(T->rchild); pri ntf("%d",T->data);return OK;/*/*按照后序非递归遍历二叉树*/*/Status PostOrderTraverse(BiTree T)stack S;In itStack(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)

26、 /pre指向上次访问的右结点，避免再次访问p=p->right;elsepri ntf("%d",p->data);pre=p;p=NULL;/*/*按照后序非递归遍历二叉树*/*/Status PostOrderTraverse(BiTree T)BiTree p = T,last = NULL;stack S;In itStack(S);Push(S,p);while(!StackEmpty(S)Pop(S,p);if(last = p->left | last = p->right)左右子树已经访问完了，该访问根节点了pri ntf(&quo

27、t;%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 /当前节点为叶节点，访问pri ntf("%d",p->data);last = p;/二叉树的层次遍历:/*/按照层次遍历二叉树*/*/void LevelOrderTraverse(BiTree T)Queue BiNodeQu

28、eue;BiTree p=T;En Queue(BiNodeQueue,p);while(!BiNodeQueue.Empty()DeQueue(BiNodeQueue,p);if(p)pri ntf("%c",p->data);En Queue(BiNodeQueue,p->lchild);En Queue(BiNodeQueue,p->rchild);/交换左右子树:*/递归法将二叉树的左右子树互换*/*/void Excha nge(BiTree T)BiTree temp;if(T)Excha nge1(T->lchild);Excha ng

29、e1(T->rchild); temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;吠*/非递归法将二叉树的左右子树互换/*/void Excha nge(BiTree T)stack S;In itStack(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(S,p);p->r

30、child;4. 给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。实验4图论及其应用、实验目的1. 了解图的基本概念及术语，并能够熟练掌握图的两种存储结构（邻接矩阵 和邻接表）。2. 理解最小生成树的概念，能按Prim算法构造最小生成树。3. 掌握图的两种遍历（深度优先搜索遍历和广度优先搜索遍历）、拓扑排序、 关键路径、最短路径的算法思想。、实验内容及步骤1. 实现网（有权图）的存储结构。2. 利用prim算法构造它的最小生成树。3. 选择一个源点，寻找从原点出发到达其它顶点的最短路径。实验5查找、实验目的1. 理解"查找表"的结构特点以及各种表示方法的适用性。

31、2. 熟练掌握顺序查找和折半查找，并对其性能做出分析。3. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性 的差别。实验内容及步骤1. 实现查找表的顺序查找和折半查找算法。#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <time.h>const int ARRSIZE= 10015;/从小到大排序数组元素 void asort(i nt *a, int s) int i, j, k, t;for (i = 0; i < s-1; +i) k = i;for (j = i + 1; j

32、< s; +j) if (ak > aj)k = j;if (k != i)t = ai; ai = ak; ak = t;/顺序查找，找到返回该元素数组下标，否则返回int SeqSearch(i nt *a, int s, int k)int i;for (i = 0; i < s; +i)if (k = ai)return i;return -1;/折半查找，找到返回该元素数组下标，否则返回int Bin Search(i nt *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表示数列分成的块数/分块查找，找到返回该元素数组下标，否则返回- int BlkSearch(i nt *a, i nt s, i nt