数据结构试验参考指导书.doc

目 录
试验一 线性表 1
试验二 数组基础操作 3
试验三 队列基础操作 5
试验四 栈基础操作 7
试验五 二叉树操作树 10
试验六 图基础操作 11

《数据结构试验指导书》
试验一 线性表
一、试验目标：
1、 掌握使用Turbo C2.0上机调试线性表基础方法；
2、 掌握线性表基础操作：插入、删除、查找和线性表合并等运算在次序存放结构和链接存放结构上。
二、试验环境：
PC机、Turbo C 或 Visual C++
三、试验描述：
一元多项式相加
四、试验要求：
（1）建立两个一元多项式A、B，按指数降序排列。
（2）实现A+B，输出其运算结果。
五、试验步骤：
（1） 用带头结点单链表存放多项式A、B，多项式类型定义以下：
typedef struct { //项表示，多项式项作为LinkList数据元素
float coef ；//系数
int expn； //指数
}term,ElemType;
typedef struct Lnode{
ElemType data;
Struct Lnode *next;
} *LinkList;
typedef LinkList polynomial ； //用带头结点有序（按指数递增）单链表表示多项式

（2） 基础操作：
int cmp(term a,term b)
//比较a于b指数，分别返回-1，0，1
void CreatPolyn(polynomial &p,int m)
//输入m项系数和指数，建立表示一元多项式有序单链表p
void PrintPolyn(polynomal p)
//输出多项式各项
void AddPolyn(polynomial &pa, polynomial &pb)
//多项式相加：pa=pa+pb，利用两个多项式结点组成“和多项式”
（3） 程序步骤
polynomal A,B; //定义多项式A，B
int m,n; //定义多项式A，B项数
CreatPolyn(A,m); //创建有m项多项式A，
PrintPolyn(A); //输出多项式A；
CreatPolyn(B,n); //创建有n项多项式B
PrintPolyn(B); //输出多项式B
AddPolyn(A,B); //两个多项式相加A=A+B
PrintPolyn(A); //输出相加结果A

(4) 测试数据：
1）（2x+5x8-3.1x11）+(7-5x8+11x9)=(7+2x+11x9-3.1x11)
2) (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)
3) (x+x3)+(-x-x3)=0
4) (x+x2+x3)+0=(x+x2+x3)

试验二 数组基础操作
一、试验目标：
掌握多种内部排序算法及多种内部排序效率。
二、试验环境：
PC机、Turbo C 或 Visual C++
三、试验描述：
经过随机数据比较多种内部排序算法。
四、试验要求：
（1）随机产生5组100个数据。
（2）对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序关键字比较和交换次数进行统计。
五、试验步骤：
（1） 用次序存放结构存放数据
（2） 产生100个随机数
（3） 用上述内部排序算法（算法见）对（2）随机数进行排序，并统计比较次数和交换次数。
参考算法：
#define M 5
#define N 4
#include "stdio.h"
main()
{ int i,j;
static float score[M+1][N+1]={{78,85,83,65}, {88,91,89,93}, {72,65,54,75},{86,88,75,60}, {69,60,50,72}};
for(i=0;i<M;i++)
{for(j=0;j<N;j++)
{ score[i][N] += score[i][j];
score[M][j] += score[i][j];
}
score[i][N] /= N;
}
for(j=0;j<N;j++)
score[M][j] /= M;
clrscr();
printf("学生编号 课程1 课程2 课程3 课程4 个人平均\n");
for(i=0;i<M;i++)
{ printf("学生%d\t",i+1);
for(j=0;j<N+1;j++)
printf("%6.1f\t",score[i][j]);
printf("\n");
}
for(j=0;j<8*(N+2);j++)
printf("-");
printf("\n课程平均");
for(j=0;j<N;j++)
printf("%6.1f\t",score[M][j]);
printf("\n");
getch();
}

（4） 反复（2）（3）共5次。
（5） 给出结论。

试验三 队列基础操作
一、试验目标：
掌握队列基础操作：初始化队列、判队列为空、出队列、入队列等运算。
二、试验环境：
PC机、Turbo C 或 Visual C++
三、试验描述：
经过队列操作掌握队列多种性质。
四、试验要求：
（1）随机产生5组100个数据，加入队列。
（2）初始化队列、判队列为空、出队列、入队列等运算
五、试验步骤：
（1）产生杨辉三角数据
（2）利用队列基础操作实现杨辉三角输出
算法以下：
void out_number(int n);
{
init_queue(Q);
printf(1);
en_queue(Q,s1+s2);
for(I=2;I<=n;I++)
{s1=0;for(j=1;j<=I-1;j++)
{s2=out_queue(Q);
printf(s2);
en_queue(q,s1+s2);
s1=s2;
}
printf(1);
en_queue(Q,1+s2);
}
参考程序以下
typedef struct
{ int *data;
int front;
int rear;
}
sqqueue;
main()
{
int i,j,m,s1=0,s2=1;
sqqueue q;
clrscr();
q.data=(int *)malloc(100*sizeof(int));
q.rear=q.front=0;
q.data[q.rear]=s2;
q.rear++;
printf("%40d",s2);
for(i=2;i<=8;i++)
{s1=0;
for(m=1;m<=40-i;m++)
printf("%c",' ');
for(j=1;j<=i-1;j++)
{s2=q.data[q.front];
q.front++;
printf("%d ",s2);
q.data[q.rear]=s1+s2;
q.rear++;
s1=s2;
}
printf("%d\n",1);
q.data[q.rear]=1+s2;
q.rear++;
}
}
（3）查看结果，得出结论。

试验四 栈基础操作
一、试验目标：
掌握栈基础操作：初始化栈、判栈为空、出栈、入栈等运算。
二、试验环境：
PC机、Turbo C 或 Visual C++
三、试验描述：
经过队列操作掌握栈多种性质。
四、试验要求：
1． 认真阅读和掌握本试验算法。
2． 上机将本算法实现。
3． 保留和打印出程序运行结果，并结合程序进行分析。
五、试验步骤：
1、定义栈次序存取结构
2、分别定义栈基础操作（初始化栈、判栈为空、出栈、入栈等）
3、定义一个函数用来实现上面问题：
1）十进制整数X和R作为形参
2）初始化栈
3）只要Ｘ不为０反复做下列动作
4）将Ｘ％Ｒ入栈
　　5）X=X/R
6）只要栈不为空反复做下列动作
　　7）栈顶出栈
　　8）输出栈顶元素

　 参考程序：
#define MAXSIZE 100
#include<stdlib.h>
struct stack{
int data[MAXSIZE];
int top;
};

void init(struct stack *s){
s->top=-1;
}

int empty(struct stack *s){
if(s->top==-1)
return 1;
else
return 0;
}

void push(struct stack *s,int i){
if(s->top==MAXSIZE-1){
printf("Stack is full\n");
return;
}
s->top++;
s->data[s->top]=i;
}

int pop(struct stack *s){
if(empty(s)){
printf("stack is empty");
return -1;
}
return(s->data[s->top--]);
}

void trans(int num){
struct stack s;
int k;
init(&s);
while(num){
k=num%16;
push(&s,k);
num=num/16;
}
while(!empty(&s)){
k=pop(&s);
if(k<10)
printf("%d",k);
else
printf("%c",k+55);
}
printf("\n");
}

main(){
int num;
clrscr();
printf("Input a num,-1 to quit:\n");
scanf("%d",&num);
while(num!=-1){
trans(num);
scanf("%d",&num);
}
}

试验五 二叉树操作树
一、试验目标：
掌握二叉树存放结构及先序、中序和后序三种基础遍历、层次遍历操作。
二、试验环境：
PC机、Turbo C 或 Visual C++
三、试验描述：
二叉树建立和遍历
四、试验要求：
1. 采取递归方法建立二叉树
2. 采取非递归方法建立二叉树
3. 采取先序、中序和后序三种方法遍历该二叉树
4. 按层次遍历该二叉树
五、试验步骤：
1. 定义二叉树结点类型及二叉树类型
2. 递归方法建立二叉树（算法参见书本）
3. 三种方法遍历二叉树（算法参见书本）
4. 层次遍历该二叉树
5. 非递归方法（按层次）建立二叉树
提醒：
1. 以三元组（F，C，L/R）形式表示输入一棵二叉树诸边（F：表示双亲结点标识，C表示孩子结点标识，L/R表示作为F左右孩子标识）。
2. 创建一个队列BQ，用于将输入二叉树每个结点起始地址及结点值保留起来
3. 按层次输入二叉树每一个结点（以三元组形式），创建每一个新结点P，同时把该结点起始地址及值入队BQ
4. 每输入一个三元组，查找BQ中和F相同值（查找父结点起始地址），依据L/R信息，将该结点作为F左或右孩子（F->Lchild=P或F->Rchild=P）

试验六 图基础操作
一、试验目标：
掌握图存放结构及深度优先遍历和广度优先遍历操作。
二、试验环境：
PC机、Turbo C 或 Visual C++
三、试验描述：
在连通无向图上访问全部结点
四、试验要求：
（1）以邻接表为存放结构，建立一个无向图
（2）以用户指定顶点为起点，实现图深度和广度优先遍历，分别输出结点访问序列
五、试验步骤：
（1） 定义邻接表存放类型
（2） 基础操作
Status CreateGraph(ALGraph &G)
//采取邻接表表示法，结构无向图G
void DFSTraverse(ALGraph G, Status (*Visit)(int v))
//对图G作深度优先遍历
void BFSTraverse(ALGraph G, Status (*Visit)(int v))
//对图G作广度优先遍历
void Visit(int v)
// 访问顶点v
（3） 程序步骤
CreateGraph(ALGraph &G)
DFSTraverse(ALGraph G, Status (*Visit)(int v))
BFSTraverse(ALGraph G, Status (*Visit)(int v))