安徽工业大学计算机学院《数据结构》实验报告书
《数据结构》实验报告
—— 安徽工业大学计算机学院
数据结构
姓名： 陈白杨
学号： 099074177
学院： 计算机学院
班级： 软件092
指导老师：王森玉
2011年6月29日
第 1 页 完成日期： 安徽工业大学计算机学院《数据结构》实验报告书
正文
一．[栈的应用（数值转换）]
1．问题描述
利用栈的数据结构和不同进制的转换结合，将十进制转换为二进制。
2．算法实现
#include
#define maxsize 100 typedef struct linklist {
long data[maxsize];
long top; }stack,*stacklist; void change(long n) {
stacklist S;
//初始化栈
if((S=(stacklist)malloc(sizeof(stack)))==NULL)
{
printf(\"申请内存空间失败!\");
return;
}
S->top=-1;
while(n>0)
{
S->top++;
S->data[S->top]=n%2; //进栈
n=n/2;
}
while(S->top>=0)
{
printf(\"%ld\",S->data[S->top]); //出栈
S->top--;
}
free(S);
//销毁栈
} int main() {
long n;
printf(\"输入测试数据:\");
scanf(\"%ld\",&n);
if(n==0)
printf(\"%d\",n);
else change(n);
getch();
return 0; } 3．运行结果
数据结构 第 2 页 安徽工业大学计算机学院《数据结构》实验报告书
二．[二叉树的遍历] 1．问题描述
二叉树的遍历主要有先序、中序、后序遍历。对已建立的二叉树，使用递归算法对二叉树进行遍历较为方便。同时，可以使用栈模拟递归。本次实验主要使用递归来演示二叉树的遍历。
2．算法实现
先序遍历
void Get_Fdata(tree_n *p) {
} 中序遍历
void Get_Mdata(tree_n *p) {
} 后序遍历
void Get_Ldata(tree_n *p) {
if(p) {
第 3 页
if(p) {
} printf(\"%d \",p->data); Get_Fdata(p->lchild); Get_Fdata(p->rchild); if(p) {
} Get_Mdata(p->lchild); printf(\"%d \",p->data); Get_Mdata(p->rchild); 数据结构 安徽工业大学计算机学院《数据结构》实验报告书
}
} Get_Ldata(p->lchild); Get_Ldata(p->rchild); printf(\"%d \",p->data); 3．运行结果
三．[图的建立及遍历] 1．问题描述
图的建立和遍历是图的一个基本的使用。图是非线性的结构，建立和遍历图只是图的操作中的一个部分。图的存储结构只要有邻接矩阵、邻接表、十字链表、临界多重表。图的遍历主要有深度优先遍历、广度优先遍历。
2．算法实现
图的建立
G.vertexNum=rand()%10; for(i=1;i
G.edgeNum=rand()%48; sum=sum+i; }while(G.edgeNum
{ G.vertex[i]=i+\'0\'; for(j=0;j
i=rand()%10;
} for(i=0;i
} printf(\"V%c \",G.vertex[i]); for(j=0;j
\",G.arcs[i][j]); printf(\"\\n\"); j=rand()%10; if(i>-1&&i-1&&j
} G.arcs[i][j]=1; k++;
图的遍历(广度优先) void BFStraverse(MGraph G) {
} void BFS(MGraph G,int v) {
int i,j; PQ Q; Q=Init_s(); Visit(v); visited[v]=1; In_s(Q,v);
while(!Empty_s(Q))
{ int visted[MaxVertextNUm]; int v; for(v=0;v
}
} Out_s(Q,&i);
for(j=0;j
if(G.arc[i][j]==1&&!visted[j])
{
} Visit(j); visited[j]=1; In_s(Q,j);
3．运行结果
四．[查找算法设计]
1．问题描述
本次实验主要是查找算法，查找算法主要有顺序查找、折半查找（有序表的查找）、分块查找、树表查找、哈希表查找。下面将介绍几种查找算法。
2．算法实现
顺序查找：
int Search(int a[],int key) {
}
数据结构
第 6 页
int i; for(i=0;i
if(a[i]==key) return 1; return 0; 安徽工业大学计算机学院《数据结构》实验报告书
折半查找
while(right>=left)
{
} printf(\"No Find!\"); mid=(right+left)/2; if(key==a[mid]) {
} if(key>a[mid]) { } if(key
printf(\"Find!\\n\\n\"); getch(); return 0; 树表查找
void Getkey(Treenode *p,Datetype key) {
if(p==NULL) return; else if(p->Key==key) {
} else if(p->Key>key) Getkey(p->Lchild,key); Getkey(p->Rchild,key); else if(p->Key
3．运行结果
顺序查找：
数据结构 第 7 页 安徽工业大学计算机学院《数据结构》实验报告书
折半查找：
五．[排序算法设计] 1．问题描述
本次实验只要是排序算法，主要的排序算法有直接插入排序，折半插入排序，Shell排序，冒泡排序，快速排序，简单选择排序，堆排序，二路归并排序，基数排序。算法的好坏只要是有算法的平均时间，辅助空间，稳定性决定的。不同的算法，适用于不同的情况，本次实验只要是比较不同排序算法的好坏。下面将介绍几种排序算法。
2．算法实现
直接插入排序：
for(i=1;i
} temp=a[i]; j=i-1; while(j>=0&&a[j]>temp) j--; a[k]=a[k-1]; for(k=i;k>j+1;k--) a[j+1]=temp; 冒泡排序改进：
数据结构 第 8 页 安徽工业大学计算机学院《数据结构》实验报告书
for(i=Max_Size-1;i>=0;i--) //筛选
{
} Change=0; for(j=0;j
} if(Change==0) break; count++; if(a[j]>a[j+1]) //交换 {
} temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; Change=1; 简单选择排序：
for(i=0;i
} min=a[i]; tag=i; for(j=i+1;j
} a[tag]=a[i]; a[i]=min; if(min>a[j]) {
} min=a[j]; tag=j; 二路归并排序：
void merge(int c[],int d[],int l,int m,int r) //将已排好序的数组合并
{
int i=l,j=m+1,k=l,q;
while((i
第 9 页
安徽工业大学计算机学院《数据结构》实验报告书
if(c[i]
d[k++]=c[i++];
else d[k++]=c[j++];
if(i>m)
for(q=j;q
d[k++]=c[q];
else
for(q=i;q
d[k++]=c[q];
for(i=l;i
c[i]=d[i];
} void mergePa(int x[],int y[],int s,int n) {
int i=0,j;
while(i
{
merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i+s
merge(x,y,i,i+s-1,n-1);
else
for(j=i;j
y[j]=x[j]; }
void Mer_s(int a[],int b[],int m) {
int s=1;
while(s
{
mergePa(a,b,s,m);
s+=s;
mergePa(b,a,s,m);
s+=s;
} } 快速排序：
int Get_sort(int a[],int l,int r) 数据结构 第 10 页 安徽工业大学计算机学院《数据结构》实验报告书
{
} void Quick(int a[],int l,int r) {
} Shell 排序：
d=N/2;
while(d>=1)
{
for(i=0;i
for(j=i+d;j
{
if(a[j]
{
k=j;
temp=a[j];
while(k-d>=0&&temp
{
a[k]=a[k-d]; int q=Get_sort(a,l,r);
if(l
} Quick(a,l,q); //q 针对于左边1位数字时 Quick(a,q+1,r); int t=a[l];
int i=l; int j=r;
while(1) {
} a[j]=t;
return j; while(j>=l&&i=t)
j--; a[i]=a[j]; if(j
break; while(i
i++; a[j]=a[i]; 数据结构 第 11 页 安徽工业大学计算机学院《数据结构》实验报告书
k-=d;
}
a[k]=temp;
}
}
d/=2;
} 运行结果
直接插入排序：
冒泡排序：
简单选择排序：
二路归并排序：
快速排序：
数据结构 第 12 页 安徽工业大学计算机学院《数据结构》实验报告书
Shell 排序：
六．实验总结[心得体会] 通过这许多实验使我逐步了解了许多关于数据结构的算法设计，看着简单，平常会眼高手低，不过敢想，敢尝试，努力就会有收获啊。 我觉得课程设计这种样式真是需要的，可以学到很多，包括书上的，书外的等等。理论永远！=实际。
数据结构 第 13 页
