《数据结构与算法实验》实验指导.doc

《数据结构与算法实验》上机实验指导书暨实验报告

湖北汽车工业学院实验报告
班 号 序 号 姓 名
课程名称 数据结构与算法实验 第 1 号实验 完成日期 年 月 日 午
实验一 线性表操作
一、 实验目的
1．掌握用 C语言调试程序的基本方法。
2. 掌握结构体类型的基本用法。
3．掌握线性表的基本运算，包括顺序表和链表的基本操作，如插入、删除等。

二、 实验内容
1．利用顺序表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。
2．建立一个单链表，同时对该链表实现指定位置的插入、删除操作。

三、 实验操作（在空白处填上合适的代码）
（一）利用顺序表完成一个班级学生课程成绩的简单管理
1、预定义以及顺序表结构类型的定义
　(1)#define ListSize //根据需要自己设定一个班级能够容纳的最大学生数
(2)typedef struct Stu
{
int num; //学生的学号
char name[10]; //学生的姓名
float wuli; //物理成绩
float shuxue; //数学成绩
float yingyu; //英语成绩
}STUDENT; //存放单个学生信息的结构体类型

typedef struct List
{
stu[ListSize]; //存放学生的数组定义，静态分配空间
int length; //记录班级实际学生个数
}LIST; //存放班级学生信息的顺序表类型

2、建立班级的学生信息
void listcreate(LIST *Li,int m) //m为该班级的实际人数
{
int i;

Li->length=0;
for(i=0;i<m;i++) //输入m个学生的所有信息
{
printf("please input the %dth student's information:\n",i+1);
printf("num=");
scanf("%d", ); //输入第i个学生的学号
printf("name=");
scanf("%s", ); //输入第i个学生的姓名
printf("wuli=");
scanf("%f", ); //输入第i个学生的物理成绩
printf("shuxue=");
scanf("%f", ); //输入第i个学生的数学成绩
printf("yingyu=");
scanf("%f", ); //输入第i个学生的英语成绩

Li->length++; //学生人数加1
}
}

3、插入一个学生信息
int listinsert(LIST *Li,int i) //将学生插入到班级Li的第i个位置。
{
int j;
STUDENT e;

if( ) //测试存储空间是否被占满
{
printf("无更多的存储空间!\n");
return 0;
}

if ( ) //插入位置检验，如果错误就返回0退出程序。
return 0;
else
{

printf("请输入插入的学生信息:");
printf("num=");scanf("%d",&e.num);
printf("name=");scanf("%s",e.name);
printf("wuli=");scanf("%f",&e.wuli);
printf("shuxue=");scanf("%f",&e.shuxue);
printf("yingyu=");scanf("%f",&e.yingyu);

for(j= ;j>= ;j--) //从i位置到最后的元素依次往后移动
Li->stu[j+1]=Li->stu[j];

=e; //学生e放入到i位置
Li->length++; //学生实际人数加1
return 1;
}
}

4、删除一个学生信息
int listdel(LIST *Li,int i) //删除第i个学生的信息
{
int j;

if ( ) //删除位置检验，如果错误就返回0退出程序。
return 0;
else
{
for(j= ;j< ;j++) //从删除位置后一个到最后的元素依次往前移动
Li->stu[j-1]=Li->stu[j];

Li->length--;
return 1;
}
}

5、显示所有学生信息
void listdisplay(LIST L)
{
int i;

printf("班级学生信息如下:\n");
for(i=0;i< ;i++)
printf("%10d[学号]%10s[姓名]%10.2f[物理成绩]%10.2f[数学成绩]%10.2f[英语成绩]\n",L.stu[i].num,L.stu[i].name,L.stu[i].wuli,L.stu[i].shuxue,L.stu[i].yingyu);
}

6、编写主函数main，要求测试以上所编写的listcreat、listinsert、listdel和listdisplay
void main() //自己设计主函数完成
{

}
（二）利用单链表完成一个班级学生课程成绩的简单管理
1、单链表结构体类型的定义
typedef struct Stu
{
int num; //学生的学号
char name[10]; //学生的姓名
float wuli; //物理成绩
float shuxue; //数学成绩
float yingyu; //英语成绩
}STUDENT; //存放单个学生信息的结构体类型

typedef struct Snode
{
STUDENT data; //结点的值
struct Snode *link; //指向下一个结点的地址
}SNODE;

2、建立班级学生信息
SNODE *listcreate(int n) //n为该班级的实际人数
{
int i;
SNODE *head,*p,*q;

if(n==0)
return NULL; //如果要创建的是空表，返回NULL

head=p=(SNODE *)malloc(sizeof(SNODE)); //动态建立第一个结点，head指针指向
printf("please input the 1th student's information:\n");
printf("num="); scanf("%d",&p->data.num); //输入第1个学生的学号
printf("name=");scanf("%s",p->data.name); //输入第1个学生的姓名
printf("wuli=");scanf("%f",&p->data.wuli); //输入第1个学生的物理成绩
printf("shuxue=");scanf("%f",&p->data.shuxue); //输入第1个学生的数学成绩
printf("yingyu=");scanf("%f",&p->data.yingyu); //输入第1个学生的英语成绩

for(i=1;i<n;i++) //插入剩下的n-1个学生
{
printf("\nThe %dth element's data:\n",i+1);
q=(SNODE *)malloc(sizeof(SNODE));
printf("num="); scanf("%d",&q->data.num);
printf("name=");scanf("%s",q->data.name);
printf("wuli=");scanf("%f",&q->data.wuli);
printf("shuxue=");scanf("%f",&q->data.shuxue);
printf("yingyu=");scanf("%f",&q->data.yingyu);
q->link=NULL;

}

}

3、插入一个学生信息
int listinsert(SNODE **Li_head,int i) //将学生插入到班级Li_head的第i个位置。
{

SNODE * p,* q,*newsnode;
int m=0; //用来统计学生位置
if(i<1)
return 0; //插入位置检验，如果错误就返回0退出程序

newsnode=(SNODE *)malloc(sizeof(SNODE)); //产生新结点
printf("please input the new student's information:\n");
printf("num="); scanf("%d",&newsnode->data.num);
printf("name=");scanf("%s",newsnode->data.name);
printf("wuli=");scanf("%f",&newsnode->data.wuli);
printf("shuxue=");scanf("%f",&newsnode->data.shuxue);
printf("yingyu=");scanf("%f",&newsnode->data.yingyu);

p=*Li_head,q=NULL; //查找第i个结点，使p指向，q指向第i-1个结点
while(p!=NULL)
{
m++;
if( )
break;
else
{

}
}

if( ) //插入在表头
{
newsnode->link=p;
*Li_head=newsnode;
}
else //插入在q和p之间
{

}
return 1;
}

4、删除一个学生信息
int listdel(SNODE **Li_head,int i) //删除链表Li_head中第一个元素值为b的结点
{
int m=0;
SNODE *p,*q;
p=*Li_head;q=NULL;

if(i<1 || *Li_head==NULL) //单链表为空及插入位置校验，如果错误就退出程序
return 0;

while(p!=NULL)
{
m++;
if(i==m)
break;
else
{
q=p;p=p->link;
}
}

if(p==NULL) //i位置结点没有(超过最后一个结点)
return 0;

if(p==*Li_head) //删除表头结点

else //删除非表头结点

//释放该结点所占的空间

return 1;
}

5、显示所有学生信息
void listdisplay(SNODE *Li_head)
{
printf("班级学生信息如下:\n");
while( )
{
printf("%10d[学号]%10s[姓名]%10.2f[物理成绩]%10.2f[数学成绩]%10.2f[英语成绩]\n",Li_head->data.num,Li_head->data.name,Li_head->data.wuli,Li_head->data.shuxue,Li_head->data.yingyu);
Li_head=Li_head->link;
}
}

6、编写主函数main，要求测试以上所编写的listcreat、listinsert、listdel和listdisplay
void main() //自己设计主函数完成
{

}

四、实验小结(自己总结本次实验的重难点及心得、体会、收获)

得 分_____________

评阅日期_____________

教师签名__ __________
湖北汽车工业学院实验报告
班 号 序 号 姓 名
课程名称 数据结构与算法实验 第 2 号实验 完成日期 年 月 日 午
实验二 栈和队列的操作与应用
一、 实验目的
1．掌握栈和队列的基本操作，并能对其进行简单应用。

二、 实验内容
1．利用栈将一个十进制的正整数转换成n进制数据，并将其转换结果输出。
2．用顺序栈实现算术表达式求值。
3. 编程用一维数组模拟一个队列（顺序队列），实现入队列和出队列操作。

三、 实验操作（在空白处填上合适的代码）
（一）利用顺序栈实现十进制整数转换转换成n进制
1、算法思想
将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下：
N N / 8 （整除） N % 8（求余）
3467 433 3 低
433 54 1
54 6 6
6 0 6 高
所以：（3456）10 =（6563）8
我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。
算法思想如下：当N>0时重复1，2
1． 若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束。
2． 用N / r 代替 N

2、转换子程序
#define L_size //根据需要自己定义L_size为顺序栈的最大存储容量
void conversion(int N，int r) //将十进制数N转换为r进制的数
{
int s[L_size],top; //定义一个顺序栈，top为栈顶指针，注意此处没有使用结构体类型
int x;
//初始化栈
while ( ) //此循环为入栈操作
{
//余数入栈
N=N / r ; //商作为被除数继续
}

while ( ) //此循环为出栈操作
{

printf(“%d”,x);
}
}

3、编写主函数验证上述转换子函数是否正确。
void main() //自己设计主函数完成
{

｝

（二）用顺序栈实现算术后缀表达式求值
1、算法思想
后缀表达式求值步骤：
a、循环读出后缀表达式中的每一个字符；
b、若是数字，将对应的字符串转换成整数，入栈；
c、若是运算符，从栈中弹出2个数，将运算结果再压入栈；
d、若表达式输入完毕，栈顶即表达式值；

2、后缀表达式求值子程序
#define L_size 50
void postexp()
{
int st[L_size],top=-1; //定义一个顺序栈，top为栈顶指针
int d; //定义用来字符串转换整数的变量d
char ch;

printf("请输入规范的后缀表达式(操作数、运算符之间使用空格间隔开，eg:15 60 42 2 / - 3 * +):\n");
//输入范例
while((ch=getchar())!='\n') //开始输入字符并赋给ch
{
if(ch==' ') //如果输入的是空格，不做处理

else
switch(ch) //判断输入是否运算符，如果时就进行相应的操作
{
case '+':
; ;break;
case '-':
; ;break;
case '*':
; ;break;
case '/':
if(st[top]!=0)
{
//分母不为零计算才有效

}
else
{
printf("除数为0!\n"); //分母为零计算无效，退出程序
exit(1);
}
break;
default:

while(ch>='0'&&ch<='9')
{

ch=getchar();
}
//将转换后的数值入栈
}
}
printf("运算结果是:%d\n",st[top]);
}
3、编写主函数验证上述求值子函数是否正确。
void main() //自己设计主函数完成
{

｝

（三）链式队列基本操作
1、队列结点定义
根据实际处理数据的类型定义链队中结点的值域类型ElemType

typedef struct node //队列结点类型定义
{ ElemType data; //队列的数据元素类型
struct node *link; //指向后继结点的指针
}NODE;

struct QueueLk{ //定义链队
//定义链队队头和队尾指针
}

2、入队
NODE *ldcr(struct QueueLk *QL,Elemtype x) //将元素x插入到链队列rear中，作为rear的新队尾
{
NODE *p;

p->data=x;
p->link=NULL; //置新结点的指针为空
if(QL->front==NULL) //队列为空

else
//将链队列中最后一个结点的指针指向新结点
//将队尾指向新结点
return QL->rear;
}

3、出队
ElemType ldsc(struct QueueLk *QL) //若链队列不为空，则删除队头元素，返回其元素值
{
NODE *s;
ElemType x;
if( ) //队空，退出程序
exit(1);

s=QL->front; //取队头保存在s中
//删除队头结点
if( ) //如果删除后队列为空，则处理队尾指针
QL->rear=QL->front;
x=s->data; //将刚才出队的结点值给x
//释放出对结点的空间
return x;
}

4、编写主函数验证上述子函数是否正确。
void main() //自己设计主函数完成
{

｝

四、实验小结(自己总结本次实验的重难点及心得、体会、收获)

得 分_____________

评阅日期_____________

教师签名__ __________
湖北汽车工业学院实验报告
班 号 序 号 姓 名
课程名称 数据结构与算法实验 第 3 号实验 完成日期 年 月 日 午
实验三 二叉树的应用
一、 实验目的
1．熟悉二叉树结点的结构和对二叉树的基本操作。
2．在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。
3．掌握构造哈夫曼树以及哈夫曼编码的方法。

二、 实验内容
1．建立一棵二叉树，编写二叉树前序遍历、中序遍历、后序遍历的递归算法与非递归算法。
2．构造一颗哈夫曼树并进行哈夫曼编码。

三、实验操作（在空白处填上合适的代码）
（一）按先序遍历序列建立二叉树的二叉链表
1、二叉树结点定义
typedef datatype char;
typedef struct node
{ datatype data; //数据域
struct node *lchild; //指向左孩子位置
struct node *rchild; //指向右孩子位置
} BiTree;

2、构建二叉树子程序（依据字符串s递归创建二叉树bt，输入方式：ABC##DE#G##F###，先序方式，#号用于表示子树为空）
A
B
C
D
E
G
F
BiTree *crt_bt_pre(BiTree *bt;)
{
char ch;
ch=getchar();

if(ch=='#') bt=NULL;
else
{
bt=(BiTree*)malloc(sizeof(BiTree));
bt->data=ch;
//递归创建左子树
//递归创建右子树
}

return(bt);
}

（二）二叉树前序遍历、中序遍历、后序遍历的递归和非递归算法
1、算法思想
先序遍历：先访问根结点,然后分别先序遍历左子树、右子树
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后序遍历：先后序遍历左、右子树，然后访问根结点

2、递归遍历子程序
void PreOrder(BiTree *bt) //先序遍历二叉树bt
{
if(bt!=NULL)
{
printf("%c",bt->data); //访问结点的数据域
//先序递归遍历bt的左子树
//先序递归遍历bt的右子树
}
}

void InOrder(BiTree *bt) //中序遍历二叉树bt
{
if(bt!=NULL)
{
//中序递归遍历bt的左子树
//访问结点的数据域
//中序递归遍历bt的右子树
}
}

void PostOrder(BiTree *bt) //后序遍历二叉树bt
{
if(bt!=NULL)
{
//后序递归遍历bt的左子树
//后序递归遍历bt的右子树
//访问结点的数据域
}
}
3、非递归遍历子程序（需要借助栈来实现）
(1)非递归先序遍历子程序
算法的思想：当树不为空的时候，访问根结点p的数据域data后，将p入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为p，出栈，再先序遍历p的右子树。

#define MAXNODE 50 //定义保存二叉树结点指针的栈的最大空间
void NRPreOrder(BiTree *bt) //非递归先序遍历二叉树
{
BiTree *stack[MAXNODE],*p;
int top=-1; //栈初始化
p=bt;

while(p || top!=-1) //树不为空或者没有遍历完成
{
while(p) //树不空的时候，访问完p结点后，p结点入栈，再遍历左子树
{
printf("%c",p->data);

p=p->lchild;
}

//遍历完左子树后，栈顶元素为p出栈，再先序遍历右子树
p=p->rchild;
}
}

（2）中序遍历的非递归实现
中序遍历的非递归算法的实现，只需将先序遍历的非递归算法中的访问根结点操作移到p=stack[top--]和p=p->rchild之间即可。自己参照(1)完成该子程序。
void NRInOrder(BiTree *bt)
{

}

（3）后序遍历的非递归实现(课后思考并验证)
后序遍历算法稍微复杂一点：当树不为空的时候，要求遍历完左右子树后，再访问根，所以我们需要加一个标记指示根结点p已经遍历完左右子树，首先将p和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；返回后，访问根结点。
void NRPostOrder(BiTree *bt) //非递归先序遍历二叉树
{
struct
{
BiTree *s;
int tag;
}stack[50]; //保存结点指针及标志的栈
BiTree *p;

int top=-1; //栈初始化
p=bt;

while(p || top!=-1) //树不为空或者没有遍历完成
{
while(p) //树不空的时候，p结点入栈，标志置0，先遍历左子树
{
stack[++top].s=p;
stack[top].tag=0;
p=p->lchild;
}

while(stack[top].tag==1) //左右子树均遍历完成，访问p结点,p结点出栈
{
p=stack[top].s;
printf("%c",p->data);
top--;
}

if(top!=-1)
{
stack[top].tag=1; //遍历完左子树后，标志置1，再后序遍历右子树
p=stack[top].s;
p=p->rchild;
}
else
break;
}
}

3、编写主函数验证（一）、（二）中所编写的各个子函数是否正确。
void main() //自己设计主函数完成
{

｝
(三) 构造一棵哈夫曼树求带权路径长度并进行哈夫曼编码。
1、哈夫曼树的构造算法思想与子程序
根据课本P169所提供的哈夫曼算法，仔细理解并完成下面程序。
typedef datatype int;
typedef struct node
{ datatype data; //数据域
struct node *lchild; //指向左孩子位置
struct node *rchild; //指向右孩子位置
} BiTree;

struct BiTree * CreateHuffman(datatype a[], int n)
{
struct BiTree **b,*q;
int i,j;

b=(struct BiTree **)malloc(n*sizeof(struct BiTree *)); /*动态分配一个由b指向的指针数组*/

for(i=0;i<n;i++) /*初始化b数组，使每个元素存放n棵树的根结点指针*/
{

}

/*进行n-1次循环建立哈夫曼树*/
for(i=1;i<n;i++)
{
int k1,k2; /*用k1和k2分别表示森林中具有最小权值和次最小权值的树根结点指针的下标*/
/***************在此添加自己的算法***********/

/******************结束********************/

/*由最小权值树和次最小权值树建立一棵新树，q指向树根结点，新树根结点权值为两个孩子权值和，并且左孩子结点权值小于右孩子*/

b[k1]=q;b[k2]=NULL; /*将指向新树的指针q存入b指针数组中的k1位置，k2位置置空*/
}

free(b);
return q;
}
2、计算哈夫曼树的带权路径长度的算法思想与子程序(非递归)
算法思路：根据树带权路径长度的定义，关键是找到哈夫曼树中的叶