数据结构实验.doc

数据结构与算法
（C语言描述）

实验指导书

谢颂华 编

武汉理工大学物理科学与技术系
光电专业教研室
二○一○年四月
前 言
《数据结构与算法》是电子信息科学与技术专业的一门学科基础课，也是一门本科生必修课。在计算机科学的各领域中，都会或多或少的用到数据结构的相关知识，学好数据结构这门课程，对从事计算机技术、电子技术及相关领域的工作人员来说是非常重要。
《数据结构与算法》主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。
《数据结构与算法》是一门理论和实践相结合的课程，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。
目 录
实验一 线性表的基本操作 1
实验二 栈和队列及其应用 3
实验三 二叉树的基本操作 5
实验四 内部排序的基本操作 7
附录：《数据结构与算法》实验报告格式 9
参考答案 ………………………………………………………………………10

3

实验一 线性表的基本操作
【实验目的】
1. 熟悉C语言的上机环境，进一步掌握C语言的结构特点。
2. 掌握线性表（顺序表和链表）的顺序和链式存储结构的定义及C语言的实现。
3. 掌握线性表（顺序表和链表）的建立、插入、删除、查找等基本操作。

【实验内容】
1. 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：
(1) 从键盘输入10个整数，产生顺序表，并输入结点值。
(2) 从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。
(3) 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。
(4) 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。
2. 报数问题：编号为1，2，···，n的n个人围坐在一圆桌旁，每人持有一个正整数的编号。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，则退席的人的编号依次为6，1，7，5，3，2，4。

【实验安排】
由于该实验是数据结构的第一个实验，建议适当多安排一些时间进行熟悉。建议课时安排如下：
课外 6学时 ，课内2学时

【实验提示】
1. 采用C语言的数组类型实现线性表的顺序存储，用C语言的结构体类型定义顺序表结点：、
#define ListSize 100 //表空间大小可根据实际需要而定，假设为100
typedef int DataType; //DataType可以是任何相应的数据类型如int, float或char
typedef struct
{ DataType data[ListSize]; //向量data用于存放表结点
int length; //当前的表长度
}SeqList;

2. 为了方便调试及编程，可以分析题目，将整个实验分解成若干个小的函数，最后由主函数分别调用子函数即可，建议编写下列子函数：
CreateList // 建立顺序表函数
PrintList // 输出顺序表函数
GetLenList // 顺序表长度函数
LocateList //顺序表的查找
InsertList // 在顺序表中插入结点函数
DeleteList // 在顺序表删除结点函数
如：
//顺序表的建立：
void CreateList(SeqList *L,int n)
{ int i;
for (i=0;i<n;i++)
scanf("%d",&(*L).data[i]);
(*L).length=n;
}

3. 进行实验结果测试时，要注意分别对头结点、尾结点及空表分别进行测试，另外要对满表进行测试，看是否有溢出情况发生。

4. 报数问题的存储结构可以采用以下两种方式：
(1)以顺序表为存储结构：可以用简单的数组
int p[n];
(2) 以循环链表为存储结构：用不带表头结点的循环单链表表示围成圆圈的n个人；建立此循环单链表；某人离席相当于删除一个结点要正确设置程序中循环终止的条件和删除结点时指针的修改变化。
typedef struct lnode{
int data;
struct lnode *next;
} lnode；
要求必须使用链表完成。
实验二 栈和队列及其应用
【实验目的】
1. 深入了解栈和队列的基本特性
2. 熟练掌握栈的基本操作在两种存储结构上的实现。
3. 熟练掌握循环队列的基本操作

【实验内容】
1. 设计一个顺序栈的基本操作的演示程序
2. 设计一个循环队列的基本操作的演示程序
3. 设计一个链队列的基本操作的演示程序
基本要求：实现下列6种基本运算：（1）初始化；（2）入栈（队列）；（3）出栈（队列）；（4）遍历；（5）求栈（队列）的长度

【实验安排】
建议课时安排如下：
课外 4学时 ，课内2学时

【实验提示】
1. 采用C语言的数组类型实现顺序栈的顺序存储，用C语言的结构体类型定义顺序栈：
typedef struct{
int base;
int top;
int st[MAX];
}SqStack;

2. 采用C语言的数组类型实现循环队列的顺序存储，用C语言的结构体类型定义循环队列：
#define MAX 8
typedef struct
{
int base[MAX];
int front;
int rear;
} SqQueue;

3. 用C语言的指针类型定义链队列：
结点类型定义：
typedef Struct QNode{
QElemType data; //元素
Struct QNode *next; //指向下一结点的指针
}Qnode , * QueuePtr ;

链队列类型定义：
typedef struct {
QueuePtr front ; //队首指针
QueuePtr rear ; //队尾指针
} LinkQueue;
实验三 二叉树的基本操作
【实验目的】
1. 掌握二叉树的链式存储结构及实现方法。
2. 掌握二叉树的遍历方法。
3. 掌握二叉树中插入结点、删除结点的方法。
4. 掌握二叉树的结点个数、叶子结点个数和树的深度的计算方法。
5. 掌握建立哈夫曼树的方法，实现哈夫曼编码。

【实验内容】
1. 要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：
(1) 基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。
(2) 分别利用前序遍历、中序遍历、后序遍历所建二叉树。
(3) 统计以上二叉树中叶子结点的个数和结点总数。
2. 实现哈夫曼编码

【实验安排】
建议课时安排如下：
课外 4学时 ，课内2学时

【实验提示】
1. 采用C语言的定义树的存储结构：
//二叉树的链式存储表示
typedef char DataType; //应由用户定义DataType的实际类型
typedef struct node
{ DataType data;
struct node *lchild, *rchild; //左右孩子指针
} BinTNode; //结点类型
typedef BinTNode *BinTree;

2. 可以考虑采用递归的方法先创建根结点，然后分别创建左右子树。在创建二叉树的过程中，要注意结点数是根据输入的字符确定的。
如：
void CreateBinTree(BinTree *T)
{
char ch;
if ((ch=getchar())==' ')
*T=NULL;
else
{ /*读入非空格 */
*T=(BinTNode *)malloc(sizeof(BinTNode)); /*生成结点 */
(*T)->data=ch;
CreateBinTree(&(*T)->lchild ); /*构造左子树 */
CreateBinTree(&(*T)->rchild ); /*构造右子树 */
}
}

3. huffman树的构造方法
(1) 给定{w1,w2,...,wn}, 构成F={T1,T2,...,Tn}, 每个树只有一个根结点;
(2) 选择两个根结点最小的二叉树,作为lchild和rchild, 构成一新的二叉树;……, 直至一棵树止。
4. huffman树的存储结构
typedef struct {
int weight;
int parent, lchild, rchild;　
} HTNode ,*HuffmanTree; // 动态分配数组存储huffman树
实验四 内部排序的基本操作
【实验目的】
1. 掌握排序的有关概念和特点。
2. 熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。。
3. 关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。
4. 了解各种排序方法的优缺点和适用范围。

【实验内容】
1. 从键盘输入上述8个整数，存放在数组quick[8]中，并输出值。
2. 输出各种排序算法每一趟排序的结果，观察关键字次序的变化。
3. 如果上述8个整数按照升序输入，即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 }，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。
4. 如果上述8个整数按照降序输入，即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。
5. 测试各排序算法的执行时间，比较执行效率。
6. 随机产生3万个数，对其进行排序，观察其结果。

【实验安排】
建议课时安排如下：
课外 2学时 ，课内2学时

【实验提示】
1. 采用C语言的定义记录类型的存储结构：
typedef int InfoType;
#define n 10 //假设的文件长度，即待排序的记录数目
typedef int KeyType; //假设的关键字类型
typedef struct { //记录类型
KeyType key; //关键字项
InfoType otherinfo; //其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1]; //SeqList为顺序表类型，表中第0个单元一般用作哨兵

2. 注意哨兵的作用。

附录：《数据结构与算法》实验报告格式
1． 实验目的
2． 实验内容
3． 实验对应算法的描述（解题思路）
4． 源程序
5． 程序运行结果
6． 调试和运行程序过程中产生的问题及采取的措施
7． 实验心得体会

//*************第一次试验*********////
第一个实验
#include<stdio.h>
#define size 12
#define OK 1
#define OVERFLOW 0
struct List
{ int data[size]; //向量data用于存放表结点
int length; //当前的表长度
}list;

/********输入函数*********/
int input()
{
int i;
for(i=0;i<10;i++)
{
printf("List.data[%d]=:",i+1);
scanf("%d",&list.data[i]);
list.length++;
}
return OK;
}

/********输出函数*********/
int output()
{
int i;
if(list.length==0) exit(0);
for(i=0;i<list.length;i++)
printf("%d ",i+1);
printf("\n");
for(i=0;i<list.length;i++)
printf("%d ",list.data[i]);
return OK;

}
/********查找函数*********/
int search()
{
int tt,flag=0,i;
printf("please input a num to be found:");
scanf("%d",&tt);
for(i=0;i<list.length;i++)
if(list.data[i]==tt) {printf("lacation:%d\n",i+1);flag++;}
if(flag==0) printf("not found!\n");
return OK;
}
/********插入函数*********/
int insert()
{
int aa,bb,i;
if(list.length==0) return 0;
printf("please input the location and num to be inserted:");
scanf("%d %d",&aa,&bb);
list.length++;
for(i=list.length;i>aa;i--)
// printf("%d",list.data[i]);
list.data[i-1]=list.data[i-2];
list.data[i-1]=bb;
return OK;
}
/********删除函数*********/
int delete_fun()
{
int aa,i;
if(list.length==0) return 0;
printf("please input the location to be deleted:");
scanf("%d",&aa);

// printf("%d\n",list.length);
// printf("%d\n",list.data[0]);
for(i=aa;i<list.length;i++)
list.data[i-1]=list.data[i];
list.length--;
return OK;
}
void main()
{
// int i;
// list.length=10;
// for(i=0;i<10;i++) list.data[i]=i+1;
input();
output();
search();
insert();
output();
delete_fun();
output();

}

第二个实验
#include<stdio.h>
#define size 100 /* 输入人数的上限 */
void main()
{
int person[size];
int i, j; /* 循环修正变量 */
int arrayLen; /* 数组长度 */
int start, overNum; /* 开始位置各跨过位置 */
int deleNum; /* 出列人所在数组中的下标 */
int name, total; /* 输入时,人的信息以及人的总数 */
printf( "请输入圆桌上人的总数: " );
scanf( "%d", &arrayLen ); printf( "\n" );
if( ( arrayLen > size ) || ( arrayLen < 0 ) )
{
printf( "超出范围,请重新输入: " );
scanf( "%d", &arrayLen ); printf( "\n" );
}

for( i = 0; i < arrayLen; i++ )
person[i] = i+1;
printf("请输入开始号: " );
scanf( "%d", &start );
start = start - 1;
printf( "请输入间隔: " );
scanf( "%d", &overNum );
total = arrayLen;
printf( "出列人的顺序为:\n" );
for( i = 0; i < total; i++ )
{
if ( arrayLen == 1 )
printf( "%d", person[0] );
else
{
deleNum = ( start + overNum - 1 ) % arrayLen;
printf( "%d ==> ", person[deleNum] );
for ( j = deleNum; j < arrayLen; j++ )
person[j] = person[j+1];
start = deleNum;
arrayLen = arrayLen - 1;
}
}
printf( "\n\n" );
}

/////***********第二次试验*******//
2.1
#include<stdio.h>
#include<stdlib.h>
#include"windows.h"
#include<process.h>
#define MAX 200
typedef struct{
int base;
int top;
int st[MAX];
}SqStack;

InitStack(SqStack *s,int aa)
{
int i;
(*s).base=0;
(*s).top=0;
for(i=1;i<=aa;i++)
{
(*s).st[(*s).top]=i;
(*s).top++;
}
printf("initiate succeeded!\n");
}

Push(SqStack *s,int i)
{
if((*s).top<200)
{
(*s).st[(*s).top]=i;
(*s).top++;
}
else
printf("full already!");
}

Pop(SqStack *s,int *p)
{
if(!((*s).top))
printf("stack is empty!");
else
{
*p=(*s).st[(*s).top-1];
(*s).top--;
printf("%d\n",*p);
}
}

Traverse(SqStack *s)
{
int i;
if(!((*s).top))
printf("stack is empty!");
else
{
for(i=0;i<(*s).top;i++)
printf("%d ",(*s).st[i]);
}
}

Getlen(SqStack *s)
{
printf("length of stack is %d\n",(*s).top);
}

main()
{
int x;
int num1,num2;
int nn;
SqStack l;

printf("*************options**************\n");
printf("1.initiate 2.push 3.pop \n");
printf("4.getlen 5.traverse 6.exit \n");
printf("choose :");
scanf("%d",&nn);

while(1)
{
printf("choose :");
scanf("%d",&nn);
switch(nn)
{
case 1:
{
printf("input num:");
scanf("%d",&num1);
InitStack(&l,num1);
system("pause");
}
break;

case 2:
{
printf("input element:");
scanf("%d",&num2);
Push(&l,num2);
system("pause");
}
break;

case 3:
{
printf("pop a num:");
Pop(&l,&x);
printf("the num is:%d",x);
system("pause");
}
break;

case 4:
{
Getlen(&l);
//printf("the length is:%d",)
system("pause");
}
break;

case 5:
{
printf("traverse stack:");
Traverse(&l);
system("pause");
}
break;

case 6: exit(0);
}
}

}

2.2
#include<stdio.h>
#include<stdlib.h>
#include"windows.h"
#include<process.h>
#define MAX 30
typedef struct{
int base[MAX];
int front;
int rear;
}SqQueue;

InitQueue(SqQueue *Q)
{
(*Q).front=0;
(*Q).rear=0;
printf("initiate succeed!\n");
}

EnQueue(SqQueue *Q,int i)
{
if((Q->rear+1)%MAX==Q->front)
printf("full !");
else
{
Q->base[Q->rear]=i;
Q->rear=(Q->rear+1)%MAX;
}
}

DeQueue(SqQueue *Q,int *x)
{
if(Q->front==Q->rear)
printf("empty !");
else
{
*x=Q->base[Q->front]; //临时存放在x中
Q->front=(Q->front+1)%MAX; //将下一个元素给front作为首元素
// printf("Delete element :%d\n",*x);
}
}

Traverse(SqQueue *Q)
{
int i,j,k;
if(Q->front==Q->rear)
printf("empty !");
else
{
j=(Q->rear-Q->front+MAX)%MAX; //避免出现问题
i=Q->front;
for(k=0;k<j;k++)
{
printf("%d ",Q->base[i]);//遍历元素
i=(i+1)%MAX; //i指向下一个元素
}
printf("\n");
}
}

Getlen(SqQueue *Q)
{
printf("length of queue is %d\n",(Q->rear-Q->front+MAX)%MAX);
}

main()
{
int i,x;
int num1;
SqQueue q;

printf("input the num in the cycle:\n");

scanf("%d",&num1);
InitQueue(&q);
for(i=1;i<=num1;i++)
{
EnQueue(&q,i);
}

Traverse(&q);
Getlen(&q);

printf("delete the first element:\n");
DeQueue(&q,&x);
Getlen(&q);

Traverse(&q);

}

2.3
#include<stdio.h>
#include<stdlib.h>
/****************链队列的基本操作***************/

typedef struct QNode
{
int data; //数据
struct QNode *next; //下一地址
}Qnode,*QueuePtr;

typedef struct
{
QueuePtr front;//队首指针
QueuePtr rear;//队尾指针
}LinkQueue;

/*****************chushihua*******************/
InitQueue(LinkQueue *q)
{
q->front=(QueuePtr)malloc(sizeof(Qnode));
q->rear=q->front;
if(!q->front)
printf("error!\n");
else
{
printf("initiate succeed!\n");
q->front->next=NULL;
}
}

/***************************c插入e元素为队尾***************/
EnQueue(LinkQueue *q,int e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(Qnode));
if(!p)
exit(0);

(*p).data=e; //存到开发的内存p中
(*p).next=NULL;
q->rear->next=p;
q->rear=p; //建立连接到队尾
}

DeQueue(LinkQueue *q,int *e)
{
QueuePtr p;
if(q->front==q->rear)
printf("empty !\n");

p=q->front->next; //将第二个给p
*e=p->data; //保留p中的数据
q->front->next=p->next;
if(q->rear==p)
q->rear=q->front;
free(p);
printf("Deleted element is %d",*e);

}

/******************遍历***********************/
Traverse(LinkQueue *q)
{
QueuePtr p;
if(q->front==q->rear)
printf("empty !\n");
else
{
p=q->front->next;
for(p;p!=q->rear;p=p->next)
{
printf("%d ",p->data);
}
printf("%d \n",q->rear->data);
}
}

Getlen(LinkQueue *q)
{
QueuePtr p;
int i=0;
if(q->front==q->rear)
printf("empty ！\n");
else
{
p=q->front->next;
for(p;p!=q->rear;p=p->next)
{
i++;
}
i=i+1; //保证最后一个可以算进来
printf("the length of queue is %d\n",i);
}
}

main()
{

int i,x;
int num1,nn,num2;
LinkQueue Q;

printf("*************options**************\n");
printf("1.initiate 2.add 3.delete \n");
printf("4.getlen 5.traverse 6.exit \n");
printf("choose :");
scanf("%d",&nn);

while(1)
{
printf("choose :");
scanf("%d",&nn);
switch(nn)
{
case 1:
{
// printf("input num:");
// scanf("%d",&num1);
InitQueue(&Q);
system("pause");
}

break;

case 2:
{
printf("input element:");
scanf("%d",&num2);
EnQueue(&Q,num2);
system("pause");
}
break;

case 3:
{
// printf("delete the 1st num:");
DeQueue(&Q,&x);
// printf("the num is:%d",x);
system("pause");
}
break;

case 4:
{
Getlen(&Q);
//printf("the length is:%d",)
system("pause");
}
break;

case 5:
{
printf("traverse stack:");
Traverse(&Q);
system("pause");
}
break;

case 6: exit(0); /*windows("cls");*/
}
}

}

//////*************第三次试验**********//
3.1
///*********************************************************************
///////// * Description:先序创建二叉树,遍历等操作
#include "stdio.h"
#include<stdlib.h>
int count3=0,count4=0;
typedef int DataType; //应由用户定义DataType的实际类型
typedef struct node
{ DataType data;
struct node *lchild, *rchild; //左右孩子指针
} BiTNode,*BiTree; //结点类型
//typedef BiTNode ;
//BiTree T;
int nn=0;/////////////////////////////////////全局变量nn
BiTree CreateBiTree()//
{
char cc;
BiTree T;
printf("input node:");
scanf("%c",&cc);
getchar(); //////////////////////////////必须加上这句话!!!!!!!!!!!!!!!!!
if(cc==' ') T=NULL;
else
{
// flag++;
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(0);
// if(flag==1)treep=T;
T->data=cc;
nn++;
// p