第一篇：《数据结构》实验指导书
《数据结构》实验(训)指导书
电气与信息工程学院实验中心
前 言
《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍线性结构、树型结构、图形结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法分析、设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法的最佳途径是上机实验。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写该实验指导书。
一、实验目的、要求和任务
计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。
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.使用其它排序算法实现该问题（直接插入排序、希尔排序、简单选择排序、堆排序等）。 数 据 结 构 实 验 指 导 书 数据结构实验指导书 目录 数据结构实验指导书.......................................................................................................................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）堆排序。 目 录 实验规则················································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 实验二 二叉树的基本操作................................................................................3 实验三 内部排序的基本操作............................................................................5 附录：《数据结构与算法》实验报告格式..........................................................6 实验一 线性表、栈和队列的基本操作 【实验目的】 1.掌握线性表（顺序表和链表）的顺序和链式存储结构的定义及C语言的实现。 2.掌握线性表（顺序表和链表）的建立、插入、删除、查找等基本操作。3.深入了解栈和队列的基本特性。 4.熟练掌握栈和队列的基本操作在两种存储结构上的实现。5.熟练掌握循环队列的基本操作。 【实验内容】 1.报数问题：编号为1，2，···，n的n个人围坐在一圆桌旁，每人持有一个正整数的编号。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，则退席的人的编号依次为6，1，7，5，3，2，4。 2.设计一个顺序栈的基本操作的程序，包括初始化顺序栈、判断栈空、求顺序栈中的元素个数、取顺序栈栈顶元素、入栈、出栈，并测试十进制转换成16进制的运算。 3.设计一个循环队列的基本操作的程序，包括实现下列6种基本运算：初始化、入队、出队、遍历、求队列的长度，并测试用队列实现杨辉三角的输出显示。 【实验安排】 由于该实验是数据结构的第一个实验，建议适当多安排一些时间进行熟悉。建议课时安排如下： 课外 2学时，课内2学时 【实验提示】 1.报数问题的存储结构可以采用以下两种方式： (1)以顺序表为存储结构：可以用简单的数组 int p[n]; (2)以循环链表为存储结构：用不带表头结点的循环单链表表示围成圆圈的n个人；建立此循环单链表；某人离席相当于删除一个结点要正确设置程序中循环终止的条件和删除结点时指针的修改变化。 typedef struct LNode{ int data; 实验二 二叉树的基本操作 【实验目的】 1.掌握二叉树的链式存储结构及实现方法。2.掌握二叉树的遍历方法。 3.掌握二叉树中插入结点、删除结点的方法。 4.掌握二叉树的结点个数、叶子结点个数和树的深度的计算方法。5.掌握建立哈夫曼树的方法，实现哈夫曼编码。 【实验内容】 1.要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：(1)基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。(2)分别利用前序遍历、中序遍历、后序遍历所建二叉树。(3)统计以上二叉树中叶子结点的个数和结点总数。2.熟练掌握哈夫曼树的构建，并实现哈夫曼编码。 【实验安排】 建议课时安排如下： 课外 4学时，课内2学时 【实验提示】 1.采用C语言的定义树的存储结构： //二叉树的链式存储表示 typedef char DataType;//应由用户定义DataType的实际类型 typedef struct node { DataType data;struct node *lchild, *rchild;//左右孩子指针 } BinTNode; //结点类型 typedef BinTNode *BinTree; 2.可以考虑采用递归的方法先创建根结点，然后分别创建左右子树。在创建二叉树的过程中，要注意结点数是根据输入的字符确定的。如： void CreateBinTree(BinTree &T){ 实验三 内部排序的基本操作 【实验目的】 1.掌握排序的有关概念和特点。 2.熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。 3.关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。 4.了解各种排序方法的优缺点和适用范围。 【实验内容】 1.从键盘输入上述8个整数，存放在数组quick[8]中，并输出值。2.输出各种排序算法每一趟排序的结果，观察关键字次序的变化。 3.如果上述8个整数按照升序输入，即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 }，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。4.如果上述8个整数按照降序输入，即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。5.测试各排序算法的执行时间，比较执行效率。 6.随机产生3万个数，对其进行排序，观察其结果。 【实验安排】 建议课时安排如下： 课外 2学时，课内2学时 【实验提示】 1.采用C语言的定义记录类型的存储结构： typedef int InfoType;#define n 10 typedef int KeyType;typedef struct { //假设的文件长度，即待排序的记录数目 //假设的关键字类型 //记录类型 //关键字项 //其它数据项，类型InfoType依赖于具体应用而 KeyType key; InfoType otherinfo;定义 } RecType;typedef RecType SeqList[n+1];作哨兵 2.注意哨兵的作用。 //SeqList为顺序表类型，表中第0个单元一般用 数 据 结 构 实 验 指 导 书 南京工程学院 信息管理与信息系统教研室 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;} 五、思考与提高 编写递归算法，计算二叉树中叶子结点的数目。第二篇：数据结构 实验指导书
第三篇：数据结构实验指导书
第四篇：数据结构实验指导书
第五篇：《数据结构》实验指导书
点击咨询 