《数据结构》实验指导书_数据结构实验指导书c
《数据结构》实验指导书由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验指导书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;iR[max].score)max=j;
if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score
六、实验总结与思考
1.快速排序算法解决本问题。2.较各种排序算法的优缺点及。
3.使用其它排序算法实现该问题（直接插入排序、希尔排序、简单选择排序、堆排序等）。
目 录 实验一线性表、栈和队列的基本操作............................................................1 实验二二叉树的基本操作............................................
目 录 实验规则················································2 实验环境····················......
石 家 庄 铁 道 大 学实 验 任 务 书课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院 石 家 庄 铁 道 大 学14学年—15学年第 2学期 数......
数 据 结 构 实 验 指 导 书数据结构实验指导书目录数据结构实验指导书 ...................................................................................................
数据结构实验指导书信息工程学院计算机系实验一 线性表实验实验目的熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现，其中重点熟悉链表的各种操作。 时间要求：4学......
