数据结构实验指导书new

《数据结构实验指导书new》由会员分享，可在线阅读，更多相关《数据结构实验指导书new（16页珍藏版）》请在金锄头文库上搜索。

1、数据结构实验指导书数据结构是计算机几相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写试验指导书；

2、同时，为每个主要的知识点配有精选的典型习题。希望学生对习题要注意理解。为了提高学生的实验效率，书后附有部分实验的源程序清单。一、实验目的更好的理解算法的思想、培养编程能力。二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。3、实验结束后总结实验内容、书写实验报告。4、遵守实验室规章制度、不缺席、按时上、下机。5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣 10 分。6、实验报告有一次不合格，扣 5 分，两次以上不合格者，平时成绩以零分记。

3、三、实验环境 Turbo C 或 VC+6.0四、说明1、本实验的所有算法中元素类型可以根据实际需要选择。2、实验题目中带者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成 70%，否则实验不合格） 。3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。五、实验报告的书写要求1. 明确实验的目的及要求;2. 记录实验的输入数据和输出结果;3. 说明实验中出现的问题和解决过程;4. 写出实验的体会和实验过程中没能解决的问题;六、成绩考评办法1期末考试占 70 分，闭卷。2平时考评占 30 分。其中

4、实验环节占 20 分（实验准备、上机、报告、考试等） ；平时占 10 分（出勤，作业，测验等）七、参考书目数据结构 （语言版） 严蔚敏等 清华大学出版社 数据结构题集 （C 语言版） 严蔚敏等 清华大学出版社 DATA STRUCTURE WITH C+ William Ford,William Topp清华大学出版社（影印版）实验一 线性表的顺序存储结构实验学时 2 学时背景知识:顺序表的插入、删除及应用。目的要求：1掌握顺序存储结构的特点。2掌握顺序存储结构的常见算法。实验内容1输入一组整型元素序列，建立顺序表。2实现该顺序表的遍历。3在该顺序表中进行顺序查找某一元素,查找成功返回 1,否

5、则返回 0。4判断该顺序表中元素是否对称,对称返回 1,否则返回 0。5实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。6输入整型元素序列利用有序表插入算法建立一个有序表。7利用算法 6 建立两个非递减有序表并把它们合并成一个非递减有序表。8编写一个主函数,调试上述算法。* 9综合训练：利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）实验说明1.算法 1 至算法 7 可以以头文件的方式存储,主函数实现该头文件的包含即可调用2.存储定义#define MAXSIZE 100 /表中元素的最大个数typedef int ElemType；/元素类型typed

6、ef struct listElemType elemMAXSIZE;/静态线性表int length; /表的实际长度SqList;/顺序表的类型名3.建立顺序表时可利用随机函数自动产生数据。注意问题插入、删除时元素的移动原因、方向及先后顺序。解不同的函数形参与实参的传递关系。实验二 链式存储结构（一）-单向链表的有关操作实验学时 学时背景知识：单向链表的插入、删除及应用。目的要求1掌握单向链表的存储特点及其实现。2掌握单向链表的插入、删除算法及其应用算法的程序实现。实验内容1随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序） 。2遍历单向链表。 3把单向链表中元素逆置（不允许申

7、请新的结点空间） 。4在单向链表中删除所有的偶数元素结点。5编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。6利用算法 5 建立两个非递减有序单向链表，然后合并成一个非递增链表。7利用算法 5 建立两个非递减有序单向链表，然后合并成一个非递减链表。8利用算法 1 建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间） 。* 9采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。10在主函数中设计一个简单的菜单，分别调试上述算法。*11综合训练：利用链表实现一个班级学生信息管理（数据录入、插

8、入、删除、排序、查找等，并能够实现将数据存储到文件中）实验说明1类型定义#include typedef int ElemType；/元素类型typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;2为了算法实现简单，最好采用带头结点的单向链表。注意问题1重点理解链式存储的特点及指针的含义。2注意比较顺序存储与链式存储的各自特点。3注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 4单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。实验三 链式存储结构（二）-双向链表的有关操作实验学时

9、 学时背景知识：双向链表的插入、删除及应用。目的要求掌握双向链表的存储特点及其实现。掌握双向链表的插入、删除算法及其应用算法的程序实现。实验内容利用尾插法建立一个双向链表。遍历双向链表。实现双向链表中删除一个指定元素。在非递减有序双向链表中实现插入元素 e 仍有序算法。判断双向链表中元素是否对称若对称返回 1 否则返回 0。设元素为正整型,实现算法把所有奇数排列在偶数之前。在主函数中设计一个简单的菜单调试上述算法。双向链表的类型定义typedef int ElemType；/元素类型 typedef struct DuLNodeElemType data;struct DuLNode *pri

10、or,*next;DuLNode,*DuLinkList;注意问题注意比较单向、双向链表的特点。实验四 栈队列实验学时 学时背景知识：入栈、出栈，入队、出队。目的要求1掌握栈、队列的思想及其存储实现。2掌握栈、队列的常见算法的程序实现。实验内容1采用链式存储实现栈的初始化、入栈、出栈操作。2采用顺序存储实现栈的初始化、入栈、出栈操作。3采用链式存储实现队列的初始化、入队、出队操作。4采用顺序存储实现循环队列的初始化、入队、出队操作。5在主函数中设计一个简单的菜单，分别测试上述算法。*6综合训练:1)利用栈实现表达式求值算法。2)利用栈实现迷宫求解。实验说明1基本要求：实现算法 1、3 或算法

11、2、4 即可。2类型定义顺序栈示例#define MAX 100 /栈的最大值typedefstruct ElemType *base；int top；SqStack； 顺序队列示例#define MAX 100 /队列的最大长度typedefstruct ElemType *base；int front，rear；SqQueue； 3算法 6 的每个子功能尽可能写成函数形式。注意问题1重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。2注意算法 6 的各个函数之间值的传递情况。 3栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等） 。实验五 二叉树的常见操作实验学时

12、 学时背景知识：二叉树的存储、建立、遍历及其应用。目的要求1掌握二叉树的存储实现。2掌握二叉树的遍历思想。3掌握二叉树的常见算法的程序实现。实验内容1输入字符序列，建立二叉链表。 2中序遍历二叉树:递归算法。3中序遍历二叉树:非递归算法。 （最好也能实现先序，后序非递归算法）4求二叉树的高度 。5求二叉树的叶子个数。*6将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。*7建立中序线索二叉树，并实现中序遍历。8借助队列实现二叉树的层次遍历。 9在主函数中设计一个简单的菜单，分别调试上述算法。*10综合训练：为 N 个权值设计哈夫曼编码。实验说明类型定义 /二叉链表存储#define Ele

13、mType char/元素类型typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;元素类型可以根据实际情况选取。注意问题1注意理解递归算法的执行步骤。2注意字符类型数据在输入时的处理。3重点理解如何利用栈结构实现非递归算法。实验六 图的有关操作实验学时 学时背景知识：图的存储、遍历、及其应用。目的要求掌握图的存储思想及其存储实现。掌握图的深度、广度优先遍历算法思想及其程序实现。掌握图的常见应用算法的思想及其程序实现。实验内容键盘输入数据，建立一个有向图的邻接表。输出该邻接表。*建立

14、一个无向图的十字链表。在有向图的邻接表的基础上计算各顶点的度，并输出。以有向图的邻接表为基础实现输出它的拓扑排序序列。*采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。 采用邻接表存储实现无向图的深度优先非递归遍历。采用邻接表存储实现无向图的广度优先遍历。*采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法。*10判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。11在主函数中设计一个简单的菜单，分别调试上述算法。*12综合训练：为计算机专业设计教学计划：4 个学年，每学年 2 个学期，开设 50 门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。实

15、验说明类型定义（邻接表存储）#define MAX_VERTEX_NUM 8 /顶点最大个数typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int weight; /边的权ArcNode; /表结点#define VertexType int /顶点元素类型typedef struct VNodeint degree,indegree;/顶点的度，入度VertexType data;ArcNode *firstarc;VNode/*头结点*/,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;/顶点的实际数，边的实际数ALGraph; 上述类型定义可以根据实际情况适当调整。算法、分别利用栈、队列实现非递归算法。注意问题注意理解各算法实现时所采用的存储结构。注意区别正、逆邻接。实验七 查找的有关操作实验学时 2 学时背景知识:顺序查找、树表查找、散列查找。目的要求：1掌握折半查找算法的思想及程序实现。2掌握二叉排序树、AVL 树的查找、插入、删除