NYIST数据结构实验指导书样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。

南阳理工学院

数据结构上机实验指导书
( )

软件学院·软件工程教研室

.3

目 录
实验1 线性表应用 2
实验2 栈和队列的应用 2
实验3 线性表应用 3
实验4 图论及其应用 3
实验5 查找 4
实验6 排序 4

实验1 线性表应用
一、 实验目的
1. 了解和掌握线性表顺序存储和链式存储在计算机中的表示, 基本操做在计算机中的实现。
2. 能够利用线性表结构对实际问题进行分析建模, 利用计算机求解。
3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
二、 实验内容及步骤
1. 利用程序设计语言分别实现顺序表和链表的抽象数据类型。
2. 掌握程序分文件( 头文件和实现文件) 书写的方式。
3. 分别用顺序表和链表实现课本算法2.2: 合并两个非递减有序序列, 并对其时间性能做出分析。P21
#include"c1.h"
typedef int ElemType;
#include"c2-1.h"
#include"bo2-1.c"
#include"func2-3.c" /* 包括equal()、 comp()、 print()、 print2()和print1()函数 */
void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法2.2 */
{ /* 已知线性表La和Lb中的数据元素按值非递减排列。 */
/* 归并La和Lb得到新的线性表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循环只会有一个被执行 */
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,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
InitList(&La); /* 创立空表La */
for(j=1;j<=4;j++) /* 在表La中插入4个元素 */
ListInsert(&La,j,a[j-1]);
printf("La= "); /* 输出表La的内容 */
ListTraverse(La,print1);
InitList(&Lb); /* 创立空表Lb */
for(j=1;j<=7;j++) /* 在表Lb中插入7个元素 */
ListInsert(&Lb,j,b[j-1]);
printf("Lb= "); /* 输出表Lb的内容 */
ListTraverse(Lb,print1);
MergeList(La,Lb,&Lc);
printf("Lc= "); /* 输出表Lc的内容 */
ListTraverse(Lc,print1);
}
实验2 栈和队列的应用
一、 实验目的
1. 掌握栈和队列这两种抽象数据类型的特点, 并能在相应的应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法。
3. 熟练掌握循环队列和链队列的基本操作实现算法。
二、 实验内容及步骤
1. 用程序设计语言实现栈和队列的抽象数据类型。
2. 在第一题的基础上完成以下选择:
选择一:
1) 设计并实现括号匹配算法。
2) 用队列实现在屏幕上打印杨辉三角。
选择二:
分别用栈和队列实现迷宫问题求解。
选择三:
分别用栈和队列实现一个列车调度系统。
1.import java.util.Scanner;

public class 括号配对 {

public static void main(String args[])
{
int top=0;//堆指针
boolean end=true;//不匹配时只输出一次

char stack[]=new char[100];//存括号
String s;
System.out.println("请输入表示式: ");
Scanner scanner=new Scanner(System.in);

s=scanner.next();

//表示式
char biao[]=s.toCharArray();//将字符串转化成字符数组
System.out.println("表示式: "+s);

for(int i=0;i<biao.length&&end;i++)//遍历表示式中所有字符
{
if(biao[i]=='(')//如果是(则入栈
{
stack[top]='(';
top++;
}
else if(biao[i]==')')//如果是)则出栈
{
if(!(top==0))
top--;
else
{
System.out.println("括号不匹配");
end=false;
}

}

}//除循环两种可能

if(top==0&&end)
System.out.println("括号匹配");//出循环stack空
else if(top!=0&&end)
System.out.println("括号不匹配");//出循环时stack不空

}

}
2. #include <stdio.h>
#define N 11
void main()
{
int i,j,a[N][N];
for(i=1;i<N;i++)
{a[i][i]=1;
a[i][1]=1;
}
for(i=3;i<N;i++)
for(j=2;j<i;j++)
a[i][j]=a[i-1][j-1]+a[i-1][j];
for(i=1;i<N;i++)
{for(j=1;j<=i;j++)
printf("%6d",a[i][j]);
printf("\n");
}
}

实验3 线性表应用
一、 实验目的
1. 领会并理解二叉树的类型定义。
2. 熟练掌握二叉树的主要特性, 。
3. 熟练掌握二叉树的各种遍历算法, 并能灵活运用遍历算法实现二叉树的其它操作。
4. 熟练掌握二叉树和树的各种存储结构及其建立的算法。
二、 实验内容及步骤
1. 实现二叉树的抽象数据类型。
2. 构造一棵二叉树并用递归实现其先序、 中序、 后序遍历算法并验证。
3. 用非递归算法实现二叉树的中序遍历。

一、 二叉树的抽象数据类型:

ADT BinaryTree{ 
 //数据对象D: D是具有相同特性的数据元素的集合。 
 //数据关系R:  
 //  若D=Φ, 则R=Φ, 称BinaryTree为空二叉树;  
 //  若D≠Φ, 则R={H}, H是如下二元关系;  
 //    ( 1) 在D中存在惟一的称为根的数据元素root, 它在关系H下无前驱;  
 //    ( 2) 若D-{root}≠Φ, 则存在D-{root}={D1,Dr}, 且D1∩Dr =Φ;  
 //    ( 3) 若D1≠Φ, 则D1中存在惟一的元素x1, <root,x1>∈H, 且存在D1上的关系H1 ⊆H; 若Dr≠Φ, 则Dr中存在惟一的元素xr, <root,xr>∈H, 且存在上的关系Hr ⊆H; H={<root,x1>,<root,xr>,H1,Hr};  
 //    ( 4) (D1,{H1})是一棵符合本定义的二叉树, 称为根的左子树; (Dr,{Hr})是一棵符合本定义的二叉树, 称为根的右子树。 

 //基本操作:  
   InitBiTree( &T ) 
     //操作结果: 构造空二叉树T。
   DestroyBiTree( &T ) 
   //  初始条件: 二叉树T已存在。 
   //  操作结果: 销毁二叉树T。 
   CreateBiTree( &T, definition ) 
   //  初始条件: definition给出二叉树T的定义。 
   //  操作结果: 按definiton构造二叉树T。 
   ClearBiTree( &T ) 
   //  初始条件: 二叉树T存在。 
   //  操作结果: 将二叉树T清为空树。 
   BiTreeEmpty( T ) 
   //  初始条件: 二叉树T存在。 
   //  操作结果: 若T为空二叉树, 则返回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是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 ) 
   //  初始条件: 二叉树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指向T中某个结点, LR为0或1。 
   //  操作结果: 根据LR为0或1, 删除T中p所指结点的左或右子树。 
   PreOrderTraverse( T, visit() ) 
   //  初始条件: 二叉树T存在, Visit是对结点操作的应用函数。 
   //  操作结果: 先序遍历T, 对每个结点调用函数Visit一次且仅一次。一旦visit()失败, 则操作失败。 
   InOrderTraverse( T, visit() ) 
   //  初始条件: 二叉树T存在, Visit是对结点操作的应用函数。 
   //  操作结果: 中序遍历T, 对每个结点调用函数Visit一次且仅一次。一旦visit()失败, 则操作失败。 
   PostOrderTraverse( T, visit() ) 
   //  初始条件: 二叉树T存在, Visit是对结点操作的应用函数。 
   //  操作结果: 后序遍历T, 对每个结点调用函数Visit一次且仅一次。一旦visit()失败, 则操作失败。 
   LevelOrderTraverse( T, visit() ) 
   //  初始条件: 二叉树T存在, Visit是对结点操作的应用函数。 
   //  操作结果: 层次遍历T, 对每个结点调用函数Visit一次且仅一次。一旦visit()失败, 则操作失败。 
}ADT BinaryTree

//
//二、 基本操作的实现:
//二叉树的结点结构体:
typedef struct{ 
    TElemType data; 
    struct BiTNode *lchild,*rchild; 
}BiTNode,*BiTree;
//二叉树的创立:
 /*******************************************/
 /*          按照前序遍历建立二叉树         */
 /*******************************************/
 Status CreateBiTree(BiTree &T) 
 { 
     //按先序次序输入二叉树中结点的值( 一个字符) ,  
     //空格字符表示空树, 构造二叉链表表示的二叉树T。 
     char ch; 
     ch = getchar();//scanf("%c",&ch); 
     if(ch == ' ') 
         T = NULL; 
     else
     { 
         if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) 
             exit(OVERFLOW); 
         T->data = ch;                //生成根结点 
         CreateBiTree(T->lchild);     //构造左子树 
         CreateBiTree(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(BiNodeQueue,p); 
         ch=getchar(); //为了简化操作, 分别对左右子结点进行赋值。 
         if(ch!=' ')//子树不空则进队列进行扩充。下同 
         { 
             s=(BiTNode*)malloc(sizeof(BiTNode)); 
             s->data=ch; 
             p->lchild=s; 
             EnQueue(BiNodeQueue,s); 
         } 
         else
         { 
             p->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.二叉树的前序遍历:
 /*******************************************/
 /*          按照前序递归遍历二叉树         */
 /*******************************************/
 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); 
             p=p->lchild; 
         } 
         else
         { 
             Pop(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 (!StackEmpty(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, 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 PostOrderTraverse(BiTree T)  
 {  
     stack S; 
     InitStack(S); 
     BiTree p=T,pre=NULL; 
     while ( p || !StackEmpty(S))  
     {  
         if (p)  
         {  
             Push(S,p);  
             p = p->left;  
         }  
         else 
         {  
             Pop(S,p);  
             if (p->right!=NULL && pre!=p->right) 
             { //pre指向上次访问的右结点, 避免再次访问 
                 p=p->right;  
             }  
             else
             {  
                 printf("%d",p->data); 
                 pre=p; 
                 p=NULL;  
             }  
         }  
     }  
}
 /*******************************************/
 /*        按照后序非递归遍历二叉树         */
 /*******************************************/
 Status PostOrderTraverse(BiTree T)  
 { 
     BiTree p = T,last = 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 = 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 Exchange(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; 
         } 
         else
         { 
             Pop(S,p); 
             p->rchild; 
         } 
     } 
 }

4. 给出一段报文和每个字符出现的概率, 对其进行哈夫曼编码和解码。

实验4 图论及其应用
一、 实验目的
1. 了解图的基本概念及术语,并能够熟练掌握图的两种存储结构(邻接矩阵和邻接表)。
2. 理解最小生成树的概念, 能按Prim算法构造最小生成树。
3. 掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)、 拓扑排序、 关键路径、 最短路径的算法思想。
二、 实验内容及步骤
1. 实现网( 有权图) 的存储结构。
2. 利用prim算法构造它的最小生成树。
3. 选择一个源点, 寻找从原点出发到达其它顶点的最短路径。
实验5 查找
一、 实验目的
1. 理解"查找表"的结构特点以及各种表示方法的适用性。
2. 熟练掌握顺序查找和折半查找, 并对其性能做出分析。
3. 熟练掌握哈希表的构造方法, 深刻理解哈希表与其它结构的表的实质性的差别。
二、 实验内容及步骤
1. 实现查找表的顺序查找和折半查找算法。

#include <stdio.h>
#include <stdlib.h>
#include