数据结构实验_177由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验课”。
安徽工业大学计算机学院《数据结构》实验报告书
《数据结构》实验报告
—— 安徽工业大学计算机学院
数据结构
姓名： 陈白杨
学号： 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!nn");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 页
实验七稀疏矩阵的实现基本操作班级：12083414学号：12081411 姓名：陈峰一、实验内容（1） 掌握稀疏矩阵的压缩存储； （2） 掌握稀疏矩阵的转置算法；二、实验目的（1） 实现上三角阵的压缩存储；（2）......
武汉纺织大学《数据结构》实验报告班级： 信管 专业 班 姓名： 学号： 实验时间： 2016 年 5 月 6 日 指导教师： 宋泽源 实验七：线性查找操作与应用一、实验目的：1、掌握顺序查找、折半......
目 录 实验一线性表、栈和队列的基本操作............................................................1 实验二二叉树的基本操作............................................
目 录 实验规则················································2 实验环境····················......
《数据结构》实验(训)指导书电气与信息工程学院实验中心 前 言《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍......
