第一篇：数据结构实验_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<=sum);for(i=0;i { 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 } 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<=m)&&(j<=r))数据结构 第 9 页 安徽工业大学计算机学院《数据结构》实验报告书 if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++]; if(i>m) for(q=j;q<=r;q++) d[k++]=c[q]; else for(q=i;q<=m;q++) d[k++]=c[q]; for(i=l;i<=r;i++) c[i]=d[i]; } void mergePass(int x[],int y[],int s,int n){ int i=0,j; while(i<=n-2*s) { 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 { mergePass(a,b,s,m); s+=s; mergePass(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 j--;a[i]=a[j];if(j<=i) break;while(i<=r&&i i++;a[j]=a[i];数据结构 第 11 页 安徽工业大学计算机学院《数据结构》实验报告书 k-=d; } a[k]=temp; } } d/=2; } 运行结果 直接插入排序： 冒泡排序： 简单选择排序： 二路归并排序： 快速排序： 数据结构 第 12 页 安徽工业大学计算机学院《数据结构》实验报告书 Shell 排序： 六．实验总结[心得体会] 通过这许多实验使我逐步了解了许多关于数据结构的算法设计，看着简单，平常会眼高手低，不过敢想，敢尝试，努力就会有收获啊。我觉得课程设计这种样式真是需要的，可以学到很多，包括书上的，书外的等等。理论永远！=实际。 数据结构 第 13 页 实验七 稀疏矩阵的实现基本操作 班级：1208341 4学号：1208141姓名：陈峰 一、实验内容 （1）掌握稀疏矩阵的压缩存储；（2）掌握稀疏矩阵的转置算法； 二、实验目的 （1）实现上三角阵的压缩存储； （2）用三元组书序表存储稀疏矩阵，并实现矩阵的转置； 三、设计思想 （1）创建一个数组；（2）输入数据； （3）给定矩阵任一元素的下标；（4）打印给定下标所对应的数据；（5）创建三元组顺序表；（6）输入矩阵中的数据；（7）输出对应的矩阵； 四、程序源代码 （1）三元组顺序表存储稀疏矩阵并实现矩阵的转置； #include # define MAXSIZE 100 # define MAXRC 10 struct Triple { int i,j; /*该非零元的行下标和列下标*/ int e;};struct TSMtrix { struct Triple data[MAXSIZE+1]; /*非零元三元组表，data[0]未用*/ int rpos[MAXRC+1]; /*各行第一个非零元的位置表*/ int cpos[MAXRC+1]; /*各列第一个非零元的位置表*/ int num[MAXRC+1]; /*各列非零元的个数*/ int mu,nu,tu; /*矩阵的行数、列数和非零元个数*/ }; void CreateMtrix(struct TSMtrix *M){ /*创建一个稀疏矩阵*/ int i,elem,col,row,mu,nu,tu; printf(“please input matrix col,row,unzeroed numbers:n”); scanf(“%d%d%d”,&mu,&nu,&tu); M->mu=mu; M->nu=nu; M->tu=tu; for(i=1;i<=tu;i++) { printf(“please input element col,row,value:n”); scanf(“%d%d%d”,&col,&row,&elem); if(mu<0 || nu<0 || mu>M->mu || nu>M->nu) { printf(“error!”); i--; } else { M->data[i].i=col; M->data[i].j=row; M->data[i].e=elem; } } } void ShowMtrix(struct TSMtrix M){ /*打印出矩阵*/ int i=1,j=1,dir=1; printf(“The matrix is:n”); for(i=1;i<=M.mu;i++) { for(j=1;j<=M.nu;j++) { if(M.data[dir].i==i && M.data[dir].j==j) { printf(“%d ”,M.data[dir].e); /*存在非零元*/ dir++; } else printf(“0 ”); } printf(“n”); } } void FastTransposeSMtrix(struct TSMtrix M,struct TSMtrix *T){ /*矩阵的快速转置*/ int t=1,p=1,q,col=M.nu; T->mu=M.mu; T->nu=M.nu; T->tu=M.tu; if(T->tu) { for(col=1;col<=M.nu;col++) M.num[col]=0; for(t=1;t<=M.nu;t++) ++M.num[M.data[t].j]; M.cpos[1]=1; /*找到M中cpos的位置*/ for(col=2;col<=M.nu;col++) M.cpos[col]=M.cpos[col-1]+M.num[col-1]; for(p=1;p<=M.tu;p++) { col=M.data[p].j; q=M.cpos[col]; T->data[q].i=M.data[p].j; T->data[q].j=M.data[p].i; T->data[q].e=M.data[p].e; ++M.cpos[col]; } } } main(){ struct TSMtrix M; struct TSMtrix N; CreateMtrix(&M); ShowMtrix(M); printf(“n”); FastTransposeSMtrix(M,&N); ShowMtrix(N); getch();} （2）实现矩阵的经典转置算法并测试； #include typedef struct { int i,j;Elemtype e;}te; typedef struct { te data[maxsize+1];//存储非0元素的数组，该数组是从1开始，所以下面的p从等于1开始// int mu,nu,tu;//mu 表示行数，nu 表示列数，tu 表示该矩阵中非0的个数// }tx; //向矩阵中输入元素 int intput(tx &a){ int row,col,p=1;//row 表示元素的行标，col 表示元素的列标，p表示非0元素的计数器// int temp; printf(“请输入矩阵行数：”); scanf(“%d”,&a.mu); printf(“请输入矩阵列数：”); scanf(“%d”,&a.nu); printf(“请输入原始矩阵的每行每列元素：n”); for(row=1;row<=a.mu;row++)//双重循环// { for(col=1;col<=a.nu;col++) { scanf(“%d”,&temp); if(temp!=0) { a.data[p].i=row; a.data[p].j=col; a.data[p].e=temp; p++; } a.tu=p; } printf(“n”); } return 0;} //输出上面的矩阵 int output(tx &a){ int row,col; int p=1; printf(“输出原始矩阵：n”); for(row=1;row<=a.mu;row++) { for(col=1;col<=a.nu;col++) { if(row==a.data[p].i && col==a.data[p].j) { printf(“t%d”,a.data[p].e); p++; } else //剩余的输出0// printf(“t%d”,0); } printf(“n”);//换行符的位置// } return 0;} //定义了一个新的矩阵b// int transpose(tx a,tx &b) { int row,col; //找出非0元素// int p,q=1; b.mu=a.nu;//矩阵b的行数等于矩阵a的列数// b.nu=a.mu;//矩阵b的列数等于矩阵a的行数// b.tu=a.tu;//非0元素的个数/// if(a.tu!=0)//判断是否有非0元素// { //双重循环// for(col=1;col<=a.nu;col++) // 该循环是以列循环目的是：把非0元素中列标小的元素从头排列// { for(p=1;p<=a.tu;p++){ if(a.data[p].j==col) //循环非0数组中的元素，并找出a.data[p].j等于当时的a矩阵在中的col// { //把矩阵a中非0元素的行标和列标等于矩阵b非0元素的列标和行标// b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].e=a.data[p].e; q++; } } } printf(“n”); } return 0;} //输出转置后的矩阵 int outputtranspose(tx &b){ int q=1; int row,col; printf(“输出转置后的矩阵：n”); for(row=1;row<=b.mu;row++) { for(col=1;col<=b.nu;col++) { if(row==b.data[q].i && col==b.data[q].j)//找出b矩阵非0元素// { printf(“t%d”,b.data[q].e); q++; } else printf(“t%d”,0);//剩余的输出0// } printf(“n”); } return 0;} void main(){ tx a,b;intput(a);output(a);transpose(a,b);outputtranspose(b);} 五、调试及测试数据 （1）三元组顺序表存储稀疏矩阵并实现矩阵的转置； （2）实现矩阵的经典转置算法并测试； 六、实验总结 在本实验中，老师给出了“三元组顺序表存储稀疏矩阵并实现矩阵的转置”的完整实验代码供我们参考。通过对参考例子的代码的理解，看懂之后程序代码之后就能比较轻松地写出题目的代码。在本次实验中能够清楚的知道要做什么，从哪里开始做，怎么做，思路很清晰。经过编程，学会了串的操作与实现，并且对C++也有了新的认识。 《数据结构》实验(训)指导书 电气与信息工程学院实验中心 前 言 《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍线性结构、树型结构、图形结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法分析、设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法的最佳途径是上机实验。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写该实验指导书。 一、实验目的、要求和任务 计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。 1.熟练掌握C语言的编辑、编译、调试程序。2.会书写类C语言的算法，并将算法转变为程序实现。 3.正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。4.有较强的逻辑分析能力。 5.针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。 6.学会分析研究计算机加工的数据结构的特性，以便为应用设计的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。 7.本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力。 8.通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。 二、实验基本内容及学时分配 为了达到实验目的，本课程安排了4个实验单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及到几部分教学内容。总学时：8学时。 1、线性表（2学时） （1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；（2）以线性表的各种操作（建立、插入、删除等）的实现为重点； （3）通过本次实验帮助学生提高C语言的编程能力（特别是函数参数、指针类型、链表的使用）。 2、数组和广义表（2学时）（1）掌握稀疏矩阵的压缩存储 （2）掌握稀疏矩阵的转置算法 3、树与二叉树（2学时） 常见的二叉树遍历算法有先序遍历，中序遍历和后序遍历算法。实现简单的先序遍历，中序遍历和后序遍历算法。 4、排序（2学时） 常见的内部排序算法，插入类排序算法，如直接插入排序和希尔排序；交换类排序算法，如冒泡排序和快速排序；选择类排序算法，如简单选择排序、树形选择类排序和堆排序。实冒泡排序或者直接插入排序算法。 三、说明 该课程采用理论与实践相结合的教学方法，集知识性与趣味性于一体，达到良好的教学效果。硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供电脑等设备。学生每次上机实验都必须遵守实验室的有关规定。 四、实验报告规范 实验报告的内容包括： 1、实验目的：说明实验所验证的知识点。 2、需求分析：以无歧义的陈述说明程序设计的任务、约束条件、输入输出要求、对功能的规定及模型。 3、逻辑设计：说明本程序中用到的所有抽象的数据类型的定义、主程序的流程以及各程序模块之间的层次调用关系。 4、详细设计：逻辑设计中定义的所有数据类型的实现，核心算法的设计描述、人机界面设计、函数之间调用关系的描述，主要功能的算法框架，测试数据设计。 5、测试分析：测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。 6、心得：软件设计与实现过程中的经验与体会，进一步改进的设想。 7、程序清单：源程序中应有足够的注释。如果提交源程序软盘，列出程序文件名。 五、如何提高上机效率 为了提高上机的效率，真正达到实验目的，要求同学做好实验前的准备工作，写好实验预习报告，即实验报告规范中的1）、2）、3）、4）部分，编写好程序，并用一组测试数据手工执行程序静态检查程序是否有错，通过阅读、执行程序或给别人讲解自己的程序而深入全面地理解程序逻辑，提高程序的正确性。对C语言程序不熟悉的同学，上机时最好带上C语言程序设计的教材，以备查阅。调试中遇到问题，应认真分析，确定可疑点，设置调试断点或输出断点处变量的值，以便发现问题，迅速排除问题，加快调试速度。 实验室要求： 不能旷课，不迟到，不穿拖鞋进实验室 实验需预习报告（不能单纯抄写，预习程序代码）实验报告（总结，注释，实验结果） 目 录 实验一 线性表实验（设计性实验）..........................................4 实验二 数组和广义表实验（设计性实验）....................................6 实验三 树与二叉树（设计性实验）..........................................8 实验四 排序（设计性实验）................................................9 实验一 线性表实验（设计性实验） 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 五、实验提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype;/* 线性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 顺序表的长度 */ }sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype;typedef struct node { elemtype data;//数据域 struct node *next;//指针域 }linklist; 注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址： p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。 六、实验总结与思考 1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？ 实验二 数组和广义表实验（设计性实验） 一、实验目的 1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法 二、实验内容 1.实现上三角阵的压缩存储。 2.用三元组顺序表存储稀疏矩阵，并实现矩阵的转置。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.创建一个数组。2.输入数据 3.给定矩阵任一元素的下标，4.打印给定下标所对应的数据。5.创建三元组顺序表。a22 7.A输出对应的矩阵。 21五、实验提示 aaa6.输入矩阵中的数据。11a11a313233a21221.对于如下对称矩阵： Aaaa424341a31a32a331个位置，a21存入到第二个位置，将它们存入到一个线性数组中B，不存非零元素，a11存入到第a41a42aija44aij的位则aij能存到第几个位置，我们要以用梯形公式算面积。置是它上面的元素之和再加上左边的元素之和。 它上面的元素之和为((1+(i-1))×(i-1)/2，左边的元素为(j-1)所以这个元素存储的位置为k=i(i-1)/2+j-1。 因为矩阵A为对称矩阵，(另一部分没有写出)，所以另一部分的元素为 k=j(j-1)/2+i-1.所以存在关系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i 2.结点结构 struct triple{ int i,j;//非零元的行下标和列下标 elemtype e;//非零元数据} 三元组顺序表存储类型 struct tsmatrix{ triple data[12500];aaa44 int mu,nu,tu;} 三元顺序表的转置 方法：(1)将矩阵行列互换，(2)重排矩阵 六、实验总结与思考 1.如何存储三对角阵？ 2.如何用行逻辑链接顺序表及十字链表存储稀疏矩阵？ 实验三 树与二叉树（设计性实验） 一、实验目的 1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法 二、实验内容 1.练习二叉树的建立与存储 2.练习二叉树的遍历 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。 2.建立二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果。 五、实验提示 建立二叉树的代码如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$') {q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一个新结点q*/ q->data = x;q->lchild = NULL;q->rchild = NULL; s[i] = q;/*q新结点地址存入s指针数组中*/ if(i!= 1)/*i = 1，对应的结点是根结点*/ {j = i / 2;/*求双亲结点的编号j*/ if(i % 2 == 0)s[j]->lchild = q;/*q结点编号为偶数则挂在双亲结点j的左边*/ else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(“i,x = ”); scanf(“%d,%c”,&i,&x);} return s[1];/*返回根结点地址*/ } 六、实验总结与思考 1.如何用孩子兄弟表示法存储树？ 2.熟悉及难赫夫曼树。 实验四 排序（设计性实验） 一、实验目的 1.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； 3.了解各种方法的排序过程及其时间复杂度的分析方法。 二、实验内容 统计成绩 给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法： （1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2）按名次列出每个学生的姓名与分数。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.定义结构体。2.定义结构体数组。 3.定出主程序，对数据进行排序。 五、实验提示 #define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n请输入学生成绩: n”);for(i=0;i if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score 六、实验总结与思考 1.快速排序算法解决本问题。2.较各种排序算法的优缺点及。 3.使用其它排序算法实现该问题（直接插入排序、希尔排序、简单选择排序、堆排序等）。 数 据 结 构 实 验 指 导 书 南京工程学院 信息管理与信息系统教研室 2014年3月 实验一 线性表操作 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype;/* 线性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 顺序表的长度 */ }sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype;typedef struct node { elemtype data;//数据域 struct node *next;//指针域 }linklist;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址： p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。 五、思考与提高 1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？ 实验二 栈和队列的应用 一、实验目的 1.掌握栈的顺序表示和实现 2.掌握队列的链式表示和实现 二、实验内容 1.编写一个程序实现顺序栈的各种基本运算。2.实现队列的链式表示和实现。 三、实验步骤 1.顺序栈(1)初始化顺序栈;(2)插入元素(3)删除栈顶元素(4)取栈顶元素(5)遍历顺序栈(6)置空顺序栈 2.链队列 (1)初始化并建立链队列(2.)入链队列(3)出链队列(4)遍历链队列 四、实现提示 1./*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM];int top;}SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack));/*申请空间*/} /*入栈函数*/ void Push(SqStack *p,ElemType x){if(p->top SqStack S; ElemType e; int N; /*初始化顺序栈*/ /*入栈*/ /*出栈*/ /*遍历顺序栈*/ getch();} 2./*定义链队列*/ typedef struct Qnode { ElemType data;struct Qnode *next;}Qnodetype;typedef struct { Qnodetype *front;Qnodetype *rear;}Lqueue; /*初始化并建立链队列函数*/ void creat(Lqueue *q) { h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申请空间*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循环快速输入数据*/ { scanf(“%d”,&x);Lappend(q,x);} /*利用入链队列函数快速输入数据*/ } /*入链队列函数*/ void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;} /*出链队列函数*/ ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*释放空间*/ /*遍历链队列函数*/ void display(Lqueue *q){ while(p!=NULL)/*利用条件判断是否到队尾*/ { printf(“%d-->”,p->data);p=p->next;} } 可参考如下代码： #include “stdio.h” #define MaxSize 100 typedef int ElemType;main(){ LinkQueue Q; ElemType e; /*初始化并建立链队列*/ /*入链队列*/ /*出链队列*/ *遍历链队列*/ } DestoryQueue(&Q); getch();} 五、思考与提高 1.读栈顶元素的算法与退栈顶元素的算法有何区别？ 试写一个算法，判别读入的一个以‘@’为结束符的字符序列是否是‚回文‛。实验三 树操作 一、实验目的 1.通过实验，掌握二叉树的建立与存储 2.通过实验，掌握二叉树的遍历方法 二、实验内容 1.练习二叉树的建立与存储 2.练习二叉树的遍历 三、实验步骤 1.建立二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。 2.建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。 四、实现提示 1.采用递归方法建立二叉树： 首先建立二叉树的根 结点，然后建立其左右子树，直到空子树为止。 2.先序遍历、中序遍历与后序遍历二叉树。#include BiTree CreateBiTree(BiTree &T){ } /*先序遍历*/ Status PreOrderTraverse(BiTree T){ } /*中序遍历*/ Status InOrderTraverse(BiTree T){ } /*后序遍历*/ Status PostOrderTraverse(BiTree T){ } int main(){ BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(“n”);/*先序遍历*/ InOrderTraverse(T);printf(“n”);/*中序遍历*/ PostOrderTraverse(T);printf(“n”);/*后序遍历*/ return 0;} 五、思考与提高 编写递归算法，计算二叉树中叶子结点的数目。 目 录 实验规则················································2 实验环境················································2 实验报告要求············································3 实验一 单链表 （一）······································4 实验二 单链表 （二）······································5 实验三 栈···············································6 实验四 二叉树···········································7 实验五 最短路径·········································8 实验六 内部排序·········································9 实 验 规 则 为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则： 1、实验前必须充分预习，完成指定的预习任务。预习要求如下： （1）认真阅读指导书，进行必要的设计与计算。（2）熟悉实验内容。 （3）预先复习，并按要求编写程序。（4）未完成预习任务者不得进入实验室。 2、遵守以下纪律： （1）在实验室不得做和实验无关的事情。 （2）进行任课老师指定内容以外的实验，必须经指导教师同意。（3）遵守纪律，不迟到。 （4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。 实 验 环 境 本实验在386以上的微机上进行，运行环境为VC6.0。 实验报告要求 1、实验题目 2．实验目的 3．实验环境 4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案 6．实验思考：（学生对本次实验的收获的总结） 实验一 单链表 （一）一、实验目的 掌握线性表的链式存储结构及其基本操作。 二、预习要求 1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。 2、根据要求，编写程序准备上机调试。 三、实验内容 实现一个简单的学生信息管理系统，该系统的功能有： 1、利用单链表建立学生基本信息表 2、浏览每个学生的信息 3、根据学号查询某个学生的基本信息 4、添加学生信息到单链表中 5、删除一个学生的信息 四、实现提示 设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。 实验二 单链表 （二）一、实验目的 掌握线性表的链式存储结构及其基本操作。 二、预习要求 1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。 2、根据要求，编写程序准备上机调试。 三、实验内容 1、实现单链表的就地逆置。 2、建立两个非递减有序单链表，然后合并成一个非递减链表。 3、建立两个非递减有序单链表，然后合并成一个非递增链表。 4、编写一个主函数,调试上述算法。 四、选做题、思考题 1、如何用带表头结点的单链表作为多项式的存储表示，实现两个多项式的相加。 2、约毖夫环的实现。 3、如何利用文件实现学生信息的存取。 实验三 栈 一、实验目的 深入了解并掌握栈的特性及其在实际中的应用；熟练掌握栈的算法实现；运用栈操作求解实际问题。 二、预习要求 1、看懂书上的算法，深入理解栈的特性和存储结构，以便在实际问题背景下灵活运用。 2、根据要求，编写程序准备上机调试。 三、实验内容 利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。 四、实现提示 1、开辟一个连续的存储空间，实现两个栈顺序存储空间的共享；分别在两端设置栈顶指针，并按要求实现栈操作。 2、采用顺序存储实现栈的初始化、入栈、出栈操作。 五、选做题、思考题 1、两栈空间共享时，栈满的条件是什么？ 2、为停车场编制进行管理的模拟程序（习题集P96，2.1）。 3、编写程序，利用栈实现表达式求值。 实验四 二叉树 一、实验目的 通过实践掌握二叉树的存储结构和遍历思想；掌握二叉树的常见算法的程序实现。 二、预习要求 二叉树的三种遍历方法。 三、实验内容 1、输入字符序列，建立二叉链表。 2、利用栈，编写非递归算法，编程实现二叉树的中序遍历。 3、求二叉树的叶子结点个数。 4、在主函数中设计一个简单的菜单，分别调试上述算法。 四、选做题、思考题 1、如何实现二叉树的后序遍历（非递归）。 2、如何求二叉树的高度。 实验五 最短路径（旅游景点导游咨询模拟） 一、实验目的 利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。 二、预习要求 学习了解图的存储结构，掌握求最短路径的两种算法。 三、实验内容 设计一个旅游景点导游模拟程序，为来访的客人提供景点最短路径的信息查询服务，任意选取n城市，构成一个有向带权图，图中顶点表示城市，边上的权值表示两点间的距离，根据用户指定的始点和终点输出相应的最短路径。 四、实现提示 咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的城市。存储结构可选用邻接矩阵。 五、选做题、思考题 1．如何实现对城市信息进行编辑（如：添加或删除）的功能。 2．用邻接表作存储结构，求一指定景点出发，到其余各景点的最短路径。 实验六 内部排序 一、实验目的 直观感受算法的关键字比较次数和关键字移动次数。 二、预习要求 1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。 2、根据要求，编写程序准备上机调试。 三、实验内容 1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。 2、利用链式存储结构，编写程序，实现直接插入排序和冒泡排序。 四、实现提示 测试数据可以为几组典型的数据：正序、逆序、乱序。 五、选做题、思考题 1、快速排序算法的非递归实现。 2、结合实验，理解针对不同待排元素的特点而选择不同排序方法的重要性。 3、如何对本实验进行时间、空间的复杂度分析。第二篇：实验7 数据结构
第三篇：《数据结构》实验指导书
第四篇：《数据结构》实验指导书
第五篇：数据结构实验指导书
点击咨询 