数据结构实验
实验内容和目的：
掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。
实验教材：
数据结构题集（C语言版） 清华大学出版社 20##年
实验项目：
实验一、栈和循环队列
㈠、实验内容：
1 栈
掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。
2 循环队列
掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。
㈡、实验代码
1 栈
程序代码：
#include ＜stdio.h＞
#include ＜malloc.h＞
#define Stack_Size 6
#define ERROR 0
#define OK 1
typedef int SElemType;
typedef struct SNode
{
SElemType data;
struct SNode *next;
}SNode,*LinkStack;
int CreatTwo(LinkStack &head,int n)
{
int i;
SNode *p;
head=(LinkStack)malloc(sizeof(SNode));
head-＞next=NULL;
printf("请输入数据(数字):\n");
for(i=n;i＞0;--i)
{
p=(SNode *)malloc(sizeof(SNode));
scanf("%d",&p-＞data);
p-＞next=head-＞next;
head-＞next=p;
}
return 1;
}
int menu_select()
{
int sn;
for(;;)
{
scanf("%d",&sn);
if(sn＜1||sn＞6)
printf("\n\t输入错误，请重新输入\n");
else
break;
}
return sn;
}
int Push(LinkStack &top,SElemType e)
{
SNode *q;
q=(LinkStack)malloc(sizeof(SNode));
if(!q)
{
printf("溢出!\n");
return(ERROR);
}
q-＞data=e;
q-＞next=top-＞next;
top-＞next=q;
return(OK);
}
int Pop(LinkStack &top,SElemType &e)
{
SNode *q;
if(!top-＞next)
{printf("error!\n");
return(ERROR);}
e=top-＞next-＞data;
q=top-＞next;
top-＞next=q-＞next;
free(q);
return(OK);
}
void main()
{ int e;
LinkStack top;
printf("1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n");
while(1)
{
switch(menu_select())
{
case 1:
if(CreatTwo(top,Stack_Size))printf("Success!\n");break;
case 2:
printf("Push:\n");
scanf("%d",&e);
if(Push(top,e))printf("Success!\n");
break;
case 3:
if(Pop(top,e))printf("Success!\n");
printf("%d\n",e);
break;
case 4:
LinkStack p;
printf("所有栈里的元素:\n");
p=top;
while(p-＞next)
{p=p-＞next;
printf("%7d",p-＞data);
}
printf("\n");
break;
case 5:
return;
}
}
}
运行结果：
2 循环队列
程序代码：
#include＜stdlib.h＞
#include＜stdio.h＞
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef struct
{
int *elem;//队列存储空间
int front;
int rear;
}SqQueue;
//判断选择是否正确
int menu_select()
{
int sn;
for(;;)
{
scanf("%d",&sn);
if(sn＜1||sn＞6)
printf("\n\t输入错误，请重新输入\n");
else
break;
}
return sn;
}
//参数(传出)SqQueue &Q,循环队列(空)
int InitQueue(SqQueue &Q)
{
Q.elem=(int *)malloc(MAXSIZE*sizeof(int));
if(!Q.elem)exit(OVERFLOW);
Q.front=Q.rear=-1;
for(int i=0;i＜MAXSIZE;i++)
Q.elem[i]=-1;
return OK;
}
//返回Q的元素个数
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
//显示队列的元素
void Display(SqQueue Q)
{
for(int i=0;i＜=QueueLength(Q);i++)
if(Q.elem[i]!=-1)printf("%d ",Q.elem[i]);
printf("\n");
}
//入队
int EnQueue(SqQueue &Q,int e)
{
Q.rear=(Q.rear+1)%MAXSIZE;
if(Q.rear==Q.front)return ERROR;
Q.elem[Q.rear]=e;
return OK;
}
//出队
int DeQueue(SqQueue &Q,int &e)
{
if(Q.front==Q.rear)return ERROR;
e=Q.elem[Q.front+1];
Q.elem[Q.front+1]=-1;
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}
void main()
{
SqQueue Q;
InitQueue(Q);
int elem,e;
printf("请输入队列元素(以0结束):\n");
scanf("%d",&elem);
while(elem!=0)
{
EnQueue(Q,elem);
scanf("%d",&elem);
}
printf("队列为：\n");
Display(Q);
printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n");
while(1)
{
switch(menu_select())
{
case 1:
printf("请输入队列元素(以0结束):\n");
scanf("%d",&elem);
while(elem!=0)
{EnQueue(Q,elem);
scanf("%d",&elem);}
printf("队列为：\n");
Display(Q);
fflush(stdin);
break;
case 2:
scanf("%d",&elem);
EnQueue(Q,elem);
printf("队列为：\n");
Display(Q);
fflush(stdin);
break;
case 3:
DeQueue(Q,elem);
printf("队列为：\n");
Display(Q);
break;
case 4:
printf("\n队列的所有元素:\n");
Display(Q);
break;
case 5:
printf("%d\n",QueueLength(Q));
break;
case 6:
return;
}
}
}
运行结果：
实验二、数组
㈠、实验内容：
数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。本程序数组的大小定义为3*3，可以通过修改“#define M”来变动。本程序具有矩阵相加、矩阵A转置、矩阵B转置、矩阵相乘四个功能。
㈡、实验代码：
#include ＜stdio.h＞
#define M 3
void MatrixAdd(int m1[M][M],int m2[M][M],int result[M][M])//两个矩阵m1和m2相加,结果放到result
{
int i,j;
for (i=0;i＜M;i++)
{
for(j=0;j＜M;j++)
result[i][j]=m1[i][j]+m2[i][j];
}
}
void MatrixTrams(int m1[M][M],int result[M][M])//矩阵转置
{
int i,j;
for (i=0;i＜M;i++)
{
for (j=0;j＜M;j++)
result[i][j]=m1[j][i];
}
}
void MatrixMultiply(int m1[M][M],int m2[M][M],int result[M][M])
{
int i,j;
for (i=0;i＜M;i++)
{
for (j=0;j＜M;j++)
{
result[i][j]=0;
for (int k=0;k＜M;k++)
result[i][j]+=m1[i][k]*m2[k][j];
}
}
}
void Display(int result[M][M])//显示矩阵
{
int i,j;
for (i=0;i＜M;i++)
{
for(j=0;j＜M;j++)
printf("%-5d",result[i][j]);
printf("\n");
}
}
void main()
{
int A[M][M],B[M][M];
int i,j;
printf("请输入第一个矩阵：\n");
for(i=0;i＜M;i++)
for(j=0;j＜M;j++)
scanf("%d",&A[i][j]);
printf("请输入第二个矩阵：\n");
for(i=0;i＜M;i++)
for(j=0;j＜M;j++)
scanf("%d",&B[i][j]);
int result[M][M];
/*printf("\n 矩阵A:\n");
Display(A);
printf("\n 矩阵B:\n");
Display(B);*/
printf("请选择：\n1.矩阵相加：\n2.矩阵A转置：\n3.矩阵B转置：\n4.矩阵相乘：\n5.退出。\n\n");
while (1)
{int l;
scanf("%d",&l);
switch(l)
{
case 1:
printf("矩阵相加的运算结果：\n");
MatrixAdd(A,B,result);
Display(result);
printf("\n");
break;
case 2:
printf("矩阵A转置的运算结果：\n");
MatrixTrams(A,result);
Display(result);
printf("\n");
break;
case 3:
printf("矩阵B转置的运算结果：\n");
MatrixTrams(B,result);
Display(result);
printf("\n");
break;
case 4:
printf("矩阵相乘的运算结果：\n");
MatrixMultiply(A,B,result);
Display(result);
printf("\n");
break;
case 5:
printf("退出。\n");
return;
default:
printf("输入错误！");
printf("\n");
}
}
}
实验结果：
实验三、查找
1 、实验内容
掌握各种查找（顺序、二分法、查找树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。本实验采用二分查找。二分查找又称折半查找，它是一种效率较高的查找方法。折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。本程序具有找出数据位置和显示查找次数两个功能。
㈡、实验代码：
#include ＜stdio.h＞
#define MAX 100
void main()
{
int r[MAX],i,k,low,high,mid,m,n;
printf("\n\n 建立递增有序的查找顺序表（以-1结束）：\n");
for(i=0;i＜MAX;i++)
{
scanf("%d",&r[i]);
if(r[i]==-1)
{
n=i;
break;
}
}
printf("\n 请输入要查找的数据：\n");
scanf("%d",&k);
low=0;high=n-1;m=0;
while(low＜=high)
{
mid=(low+high)/2;
m++;
if(r[mid]＞k)
high=mid-1;
else
if(r[mid]＜k)
low=mid+1;
else
break;
}
if(low＞high)
{
printf("没有找到\n");
printf("共进行%d次比较。\n",m);
if(r[mid]＜k)
mid++;
printf("可将这个数插入到第%d个数的后面。\n",mid);
}
else
{
printf("\n 要找的数据=%d在第%d个数的位置上。\n",k,mid+1);
printf("\n\n 共进行了%d次比较。\n",m);
}
}
实验结果：
实验四、树
1 、实验内容：
进一步掌握树的结构及非线性特点，递归特点和动态性；进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。本程序将第一个元素作为树根，其余元素若小于树根则为左子树，若大于树根则为右子树。本程序具有求左子树、求右子树、求深度、先序遍历、中序遍历（递归算法）、中序遍历（非递归算法）、后序遍历六个功能。
㈡、实验代码
//描述：两个指针指向左右孩子，算法见教材
#include ＜stdio.h＞
#include ＜stdlib.h＞
#define MAX 50
typedef struct btnode
{
int Data;
struct btnode *Llink;
struct btnode *Rlink;
}btnode,*btreetype;
btreetype CreatTree(int n)//传入数据数量，返回根结点指针
{
int i;
btreetype root=NULL;
for (i=0;i＜n;i++)
{
btreetype newNode,currentNode,parentNode;
newNode=(btreetype)malloc(sizeof(btnode));
scanf("%d",&newNode-＞Data);
newNode-＞Llink=NULL;
newNode-＞Rlink=NULL;
currentNode=root;
if(currentNode==NULL)root=newNode;
else{
while (currentNode!=NULL)
{
parentNode=currentNode;
if(newNode-＞Data＜currentNode-＞Data)
currentNode=currentNode-＞Llink;
else
currentNode=currentNode-＞Rlink;
}
if(newNode-＞Data＜parentNode-＞Data)
parentNode-＞Llink=newNode;
else
parentNode-＞Rlink=newNode;
}
}
return root;
}
void OutputTree(btreetype &root)
{
btreetype p;
p=root-＞Llink;
printf("建立的二叉树的左子树为：\n");
while (p!=NULL)
{
printf("%-8d",p-＞Data);
p=p-＞Llink;
}
p=root-＞Rlink;
printf("\n建立的二叉树的右子树为：\n");
while (p!=NULL)
{
printf("%-8d",p-＞Data);
p=p-＞Rlink;
}
}
int depth(btreetype root)
{
btreetype p;
p=root;
int dep1;
int dep2;
if(root==NULL)return 0;
else
{
dep1=depth(p-＞Llink);
dep2=depth(p-＞Rlink);
if(dep1＞dep2)return(dep1+1);
else return(dep2+1);
}
}
void PreOrder(btreetype &root)//先序遍历（递归）
{
btreetype p;
p=root;
if (p!=NULL)
{
printf("%-5d",p-＞Data);
PreOrder(p-＞Llink);
PreOrder(p-＞Rlink);
}
}
void InOrder(btreetype &root)//中序遍历（递归）
{
btreetype p;
p=root;
if (p!=NULL)
{
InOrder(p-＞Llink);
printf("%-5d",p-＞Data);
InOrder(p-＞Rlink);
}
}
void InOrder_Norecuision(btreetype &root)
{
btreetype stack[MAX];
btreetype p;
int top=0;
p=root;
do
{
while (p!=NULL)
{
top++;
stack[top]=p;
p=p-＞Llink;
}
if (top＞0)
{
p=stack[top];
top--;
printf("%-5d",p-＞Data);
p=p-＞Rlink;
}
} while (p!=NULL||top!=0);
}
void PostOrder(btreetype &root)
{
btreetype p;
p=root;
if (p!=NULL)
{
PostOrder(p-＞Llink);
PostOrder(p-＞Rlink);
printf("%-5d",p-＞Data);
}
}
void main()
{
btreetype btree;
int count;
printf("请输入元素个数：\n");
scanf("%d",&count);
printf("请输入数据：\n");
btree=CreatTree(count);
OutputTree(btree);
printf("\n建立的二叉树的深度为:%d\n",depth(btree));
printf("\n先序遍历：\n");
PreOrder(btree);
printf("\n中序遍历（递归算法）：\n");
InOrder(btree);
printf("\n中序遍历（非递归算法）：\n");
InOrder_Norecuision(btree);
printf("\n后序遍历：\n");
PostOrder(btree);
printf("\n");
}
实验结果：
