第一篇：实验7 数据结构
实验七
稀疏矩阵的实现基本操作
班级：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.熟悉VC集成环境
2.会定义线性表的顺序结构和链式结构
3.熟悉对线性表的基本操作，如插入、删除等
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现线性表的建立、插入、删除等功能。
写出线性表、顺序表、链表的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的顺序表算法有： 1.初始化顺序表 2.顺序表的插入操作 3.顺序表的删除操作 设计的链表算法有： 1.建立链表
2.链表的插入操作 3.链表的删除操作 4.链表数据元素的访问
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第二次实验 栈和队列
（一）实验目的和要求：
1.熟练掌握栈和队列的结构，以及这种数据结构的特点 2.会定义顺序栈、循环队列，能实现栈、队列的基本操作 3.会利用栈解决典型问题，如数制转换等
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现栈（或者队列）的各种基本操作，如初始化、入栈、出栈、判断栈是否为空等
写出栈的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.初始化栈 2.入栈 3.出栈
4.判断栈是否为空 5.十进制转换为八进制
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第三次实验 二叉树
（一）实验目的和要求：
1.熟练掌握二叉树的结构，以及这种数据结构的特点 2.会定义二叉树的链式存储结构
3.能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现二叉树的各种基本操作，如二叉树的建立（头插法或者尾插法），遍历等 写出二叉树的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.递归建立二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第四次实验
查找
（一）实验目的和要求：
1.熟练掌握查找算法的基本思想，以及算法的适用条件
2.会定义静态查找表的顺序结构，能实现顺序查找、二分查找
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现顺序查找、二分查找。
写出静态查找表的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.建立静态查找表 2.顺序查找
3.建立有序的静态查找表 4.二分查找
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第三篇：数据结构实验指导书
目 录
实验规则················································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、如何对本实验进行时间、空间的复杂度分析。
第四篇：数据结构 实验指导书
数 据 结 构 实 验 指 导 书
数据结构实验指导书
目录
数据结构实验指导书.......................................................................................................................1
目录...........................................................................................................................................1 实验指导书概述...............................................................................................................................2 上机实验题目...................................................................................................................................3
实验一 C语言相关知识复习................................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3 实验二 单链表的插入、删除...............................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3
三、实现提示...................................................................................................................4 实验三 栈及其应用.................................................................................................................5
一、实验目的...................................................................................................................5
二、实验内容...................................................................................................................5 实验四 二叉树的递归算法.....................................................................................................6
一、实验目的...................................................................................................................6
二、实验内容...................................................................................................................6 实验五 图的遍历.....................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验六 有序表的查找.............................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验七 哈希表.........................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验八 内部排序算法的应用.................................................................................................8
一、实验目的...................................................................................................................8
二、实验内容...................................................................................................................8
实验指导书概述
“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因，使得掌握这门课程具有较大难度： 内容多，时间短，给学习带来困难；
贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点； 隐含在各部分的技术和方法丰富，也是学习的重点和难点； 先修课程中所介绍的专业性知识不多，加大了学习难度。
由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。
上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。
为了达到上述目的，本指导书安排了8个实验题目，它们与教科书的各章有紧密的关系，使学生在实验后能加深对课程内容的理解，增强动手能力。
每个实验题目采取了统一的格式，由问题描述、基本要求、测试数据、实现提示等部分组成。
问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；
要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；
测试部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和 严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；
实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实现。
下面带*的题目为选做题目。
上机实验题目
实验一 C语言相关知识复习
一、实验目的
复习C语言中函数、数组、结构体、文件等概念，掌握它们的描述与操作方法；熟悉掌握C++中typedef、引用参数调用（&）的概念及使用方法，为理解数据结构课程的后续内容以及算法书写奠定基础。
二、实验内容 问题描述：编写一个函数，求一个整数数组中的最大、最小值。
要求：在函数声明中采用引用参数传递方式实现最大、最小值的返回。测试：在主函数中输入10个数，调用此函数，打印输出最大和最小值。2 关于指针的使用：
用malloc方式分别申请两个指针，并实现两个指针内容的比较大小操作。要求：此功能在一个函数内实现，该函数接受两个整数值，存储到两个指针内容中，输出两者中的最大值。
测试：从主函数中输入两个数，调用该函数，打印输出交换后的值。
实验二 单链表的插入、删除
一、实验目的
1、熟悉某种数据结构在计算机上实现的方法。
2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。
3、体会单链表操作、有序表插入、删除的一般方法。
二、实验内容
问题描述：已知递增有序的单链表A，编写算法实现向A中插入或删除一个元素，并保持A的有序性。
实验要求：
1、结点的数据均为整型。
2、若表中已经存在此元素，则不插入
三、实现提示
1.在已知的线性表中插入或删除，需要下面的辅助函数：线性表的创建、线性表的遍历
2.在单链表表中插入或删除，需依次实现：
a)单链表结构的定义
b)单链表的创建（头插法或尾插法建表）c)单链表的遍历
d)单链表的插入、删除（采用顺序查找方法，顺头指针往后，查找插入或删除位置，再修改指针）
//头文件
#include “stdlib.h” //预定义常量 #define NULL 0
//单链表的定义
typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//单链表的创建
void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;
q=L;
scanf(“%d”,&data);while(data!=0){
p=(LinkList)malloc(sizeof(LNode));
p->data=data;
p->next=q->next;
q->next=p;
q=p;
scanf(“%d”,&data);} }
//单链表的遍历
void TranverseList(LinkList L){
LinkList p;
p=L->next;
if(p==NULL)
{
printf(“niln”);
return;
}
while(p!=NULL)
{
printf(“%d ”,p->data);
p=p->next;
}
printf(“n”);}
实验三 栈及其应用
一、实验目的
1、熟悉栈的顺序表示与实现。
2、熟悉栈的应用。
3、理解并掌握递归函数的设计与实现。
二、实验内容 问题描述：利用栈实现十进制数n转化为d进制数 要求：
1)输入一个n和d，打印输出d进制数序列。
2)利用顺序栈来实现十进制数n转化为其他d进制数。此时，需要同时实现初始化空栈、入栈、出栈、判栈空等辅助功能。测试数据：
（1）输入n:1348
d:8 输出：2504（2）输入n:9
d:8 输出：11（3）输入n:0
d:8 输出：0 2 问题描述：利用栈实现算术表达式求值。要求：
1)参与运算的操作数为10以内的数值。测试数据：
自拟。
实验四 二叉树的递归算法
一、实验目的
1、掌握二叉树的表示与实现。
2、掌握二叉树的定义、创建、遍历等基本操作的实现。
3、熟悉求二叉树深度等递归算法的设计与实现。
二、实验内容
问题描述：已知二叉树t，分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度，并对二叉树分别进行中序遍历。要求：
1、二叉树分别采用顺序或二叉链表存储。
2、树中的数据类型约定为整型。测试数据：
1、输入序列：-+aØØ*bØØ-cØØdØØ/eØØfØØ创建二叉树； 输出：深度：5
前序序列：-+a*b-cd/ef
中序序列：a+b*c-d-e/f
后序序列：abcd-*+ef/-T:d / e f
2、t=nil
输入：Ø
输出：深度：0 实验五 图的遍历
一、实验目的
熟悉图的基本操作，掌握图遍历的设计与实现。
二、实验内容
问题描述：已知的描述校园景点的图，实现对该图的深度优先和广度优先遍历。要求：
图采用邻接矩阵存储，顶点信息包括景点的名称和简单描述。
实验六 有序表的查找
一、实验目的
1、理解各种查找方法的基本思想
2、熟悉有序表查找方法的算法实现
二、实验内容 已知一有序的序列{1,3,5,7,9}，采用折半法分别查找3和6。
2已知输入一无序的序列{5,1,3,9,7}，创建一棵二叉排序树，然后对其遍历，输出递增有序的序列。
实验七 哈希表
一、实验目的
理解哈希表的概念和基本操作；熟悉哈希表的创建、查找、插入的算法实现。
二、实验内容
问题描述：已知11位好友的名字各不相同，设计并实现一个哈希表，根据好友的名字，可以取得其生日。要求：
1、好友的信息包含名字和生日两个数据项，其中好友的名字为主键，用汉语拼音形式存放；
2、哈希函数采取：好友名字中所有拼音字母ASCII码值的和 MOD 11(除以1取余)；
3、采取线性探测再散列的方式处理冲突。
实验八 内部排序算法的应用
一、实验目的
理解各种内部排序方法的基本思想；熟悉各种内部排序方法的算法实现
二、实验内容
问题描述：已知一序列{503，087，512，061，908，170，897，275，653，426}，分别采取下列排序方法对其进行排序：
（1）直接插入排序；
（2）简单选择排序；
（3）起泡排序；（4）快速排序；（5）堆排序。
第五篇：数据结构实验指导书（精选）
石 家 庄 铁 道 大 学
实 验 任 务 书
课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院
石 家 庄 铁 道 大 学
14学年—15学年第 2学期 数据结构实验任务书
专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 王明明 实验题目：线性表的基本操作
实验环境： Visual C++ 实验目的：
1、掌握线性表的定义；
2、掌握线性表的基本操作，如建立、查找、插入和删除等。
实验内容：
定义一个包含学生信息（学号，姓名，成绩）的的顺序表或链表，使其具有如下功能：(1)根据指定学生个数，逐个输入学生信息；(2)逐个显示学生表中所有学生的相关信息；
(3)根据姓名进行查找，返回此学生的学号和成绩；
(4)根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；(5)给定一个学生信息，插入到表中指定的位置；(6)删除指定位置的学生记录；(7)统计表中学生个数。
实验提示：
学生信息的定义： typedef struct { char no[8];//8位学号 char name[20];//姓名 int price;//成绩 }Student;
顺序表的定义
typedef struct { Student *elem;//指向数据元素的基地址
int length;//线性表的当前长度 }SqList；
链表的定义：
typedef struct LNode{ Student data;//数据域 struct LNode *next;//指针域 }LNode,*LinkList;
实验要求：
(1)程序要添加适当的注释，程序的书写要采用缩进格式。
(2)程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。
(3)程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。(4)根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。
石 家 庄 铁 道 大 学
14学年—15学年第 2 学期 数据结构实验任务书
专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 李冬梅
实验题目：栈的应用－算术表达式求值
实验环境： Visual C++ 6.0 实验目的：
1．掌握栈的定义及实现；
2．掌握利用栈求解算术表达式的方法。
实验内容：
通过修改完善教材中的算法3.4，利用栈来实现算术表达式求值的算法。对算法3.4中调用的几个函数要给出其实现过程：
(1)函数In(c)：判断c是否为运算符；
(2)函数Precede(t1,t2)：判断运算符t1和t2的优先级；(3)函数Operate(a,theta,b)：对a和b进行二元运算theta。
程序运行时，输入合法的算术表达式（中间值及最终结果要在0～9之间，可以包括加减乘除和括号），便可输出相应的计算结果。如下图：
实验提示：（仅供参考，每个函数的具体实现可以有多种方法，希望有创新）
1.将栈的定义和实现单独保存在头文件“stack.h”中，然后在表达式求值的源程序sy2.cpp中包含此头文件（即#include“stack.h”）。2.表达式求值源程序sy2.cpp的具体实现(1)主函数如下： void main(){ cout<<“请输入算术表达式,并以#结束.”< (2)函数EvaluateExpression的实现见算法3.10(3)函数In(c)的实现可以采用以下方式： Status In(SElemType c)// 应在前面有定义typedef char SElemType;{ // 判断c是否为运算符 switch(c){ case'+':return TRUE;„„//补充完整 default:return FALSE;} }(4)函数Precede(t1,t2)的实现可以采用以下形式： SElemType Precede(SElemType t1,SElemType t2){ //根据教材表3.1，判断两个运算符的优先关系 SElemType f;switch(t2){ case '+': case '-':if(t1=='('||t1=='#')f='<';else f='>';break;„„//补充完整 } return f;}(5)函数Operate(a,theta,b)的实现可以采用以下方式： SElemType Operate(SElemType a,SElemType theta,SElemType b){ SElemType c;a=a-48;b=b-48;switch(theta){ case'+':c=a+b+48;break;„„//补充完整 } return c;} 选做内容1：进一步改进，使表达式的中间值及最终结果不局限于0～9之间的个位数。（如 果完成要在实验报告中注明），如下图： 选做内容2： 将表达式转化成后缀表达式输出，利用后缀表达式求表达式的值并输出。 将中缀表达式转化成后缀表达式存储在队列中，然后利用后缀表达式求表达式的值并输出。 将中缀表达式转化成后缀的思想： （1）创建一空队列，用来存放后缀表达式，建立并初始化操作符栈OPTR，将表达式起始符“#”压入OPTR栈。 （2）依次读入表达式中每个字符ch，循环执行（3）至（5），直至求出整个表达式转换完毕。 （3）取出OPTR的栈顶元素，当OPTR的栈顶元素和当前读入的字符ch均为“#”时，整个中缀表达式转换完毕。 （4）若ch不是运算符，则进队，读入下一字符ch。 （5）若ch是运算符，则根据OPTR的栈顶元素和ch的优先权比较结果，做不同的处理。 ① 若是小于，则ch压入OPTR栈，读入下一字符ch。② 若是大于，则弹出OPTR栈顶的运算符，进队。③ 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于去掉括号，然后读入下一字符ch。 对后缀表达式进行计算的具体步骤为： 建立一个栈S从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X运算符Y”的形式计算出结果，再压进栈S中。如果后缀表达式未读完，重复执行上面过程，最后输出栈顶的数值即可结束。 实验要求： (1)程序要添加适当的注释，程序的书写要采用缩进格式。 (2)程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。(3)程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。(4)根据实验报告模板详细书写实验报告,在实验报告中给出表达式求值算法的流程图。
鲁公网安备37028302000876号