数据结构实验必备实验教程..doc

数据结构实验教程 主 编 郭 群 辽宁对外经贸学院 信息技术系 内容简介 《数据结构实验教程》为了使学生能够尽快地掌握数据结构中的各种算法而编写的。本教材所写算法结构清晰、可读性强、易于调试、符合软件工程的规范要求等特点。所有实验项目都给出了完整的C语言程序，对关键的算法及语句都给出了详细的注释。所有程序都在Visual C++环境下调试运行通过。 对于数据结构的每个知识点给出了多个实验项目，分为验证实验前 言 《数据结构》是计算机相关专业的一门实践性很强。验证实验：其主要内容是将书上的重要数据结构上机实现，深化理解和掌握理论知识，这部分的实验不需要学生自己设计，只须将给定的方案实现即可；设计实验：其主要内容是针对具体问题，应用某一个知识点，自己设计方案，并上机实现，目的是培养学生对数据结构的简单应用能力；综合实验：其主要内容是针对具体问题，应用某几个知识点，自己设计方案，并上机实现，目的是培养学生对数据结构的综合应用能力第1章 线性表 1 1.1 知识点概述 1 1.2 线性表的顺序存储结构 1 1.3 线性表的链式存储结构 7 1.4 小结 11 第2章 栈与队列 12 2.1 知识点概述 12 2.2 栈及其应用 12 2.3 队列及其应用 17 2.4 小结 23 第3章 数组 24 3.1 知识点概述 24 3.2 数组的基本操作 24 3.3 矩阵的压缩存储 26 3.4 小结 28 第4章 串 29 4.1 知识点概述 29 4.2 字符串的基本操作 29 4.3 小结 32 第5章 树和二叉树 33 5.1 知识点概述 33 5.2 二叉树的基本操作及应用 35 5.3 小结 41 第6章 图 42 6.1 知识点概述 42 6.2 图的基本操作及应用 43 6.3 小结 50 第7章 查找 51 7.1 知识点概述 51 7.2 查找实验 52 7.3 小结 55 第8章 排序 56 8.1 知识点概述 56 8.2 排序实验 57 8.3 小结 66 第9章 文件 67 9.1 知识点概述 67 9.2 综合实验 67 9.3 小结 98 参考文献 99 第1章 线性表 1.1 知识点概述 线性表是最基本最常用的一种线性结构。其特点是除了第一个元素和最后一个元素以外，其他数据元素都只有一个前驱和一个后继。一个线性表中的数据元素应具有相同的描述性质，即属于同一个数据对象。 在实际应用中，必须将线性表中的数据存放在计算机中。常用的存储方式有两种：顺序存储和链式存储，线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各个元素，使得数据元素逻辑上的相邻关系与物理上的相邻关系一致。链式存储是指用一组任意的存储单元来存储线性表中的数据元素，这一组存储单元可以是连续的，也可以是不连续的。因而必须在存储每个元素的同时，也要存储元素之间的逻辑关系。 顺序存储的线性表又称顺序表，可以随机地存取表中的任意一个元素；也无需为表示结点之间的逻辑关系而额外增加存储空间。但是，顺序表在进行插入和删除操作时需要移动大量的元素，影响运行的效率；同时表的最大容量事先无法估计，如果对表长估计的过长，可能会浪费空间，相反则可能会发生溢出的现象。 链式存储的线性表又称链表，查找表中任一元素时需要从头结点的指针域开始逐步向后（前）查找；每个结点需要增加指针域；动态分配存储空间，存储空间得到了充分利用；易于插入和删除元素。 线性表的主要基本操作有初始化、判断表空、求表长、插入、删除和查找等。 1.2 线性表的顺序存储结构 一、实验目的 1、熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2、掌握线性表的顺序存储结构的定义及C语言实现。 3、掌握线性表在顺序存储结构即顺序表中的各种基本操作。 4、利用线性表的顺序存储结构解决实际问题。 二、实验内容 （一）验证实验 1、定义顺序表类型 typedef int datatype; typedef struct { datatype elem[MAX]; int Last; }List,*SeqList; 2、完成顺序表中的基本操作的实现初始化、插入、删除、求表长、按值查找、按位置查找#include stdio.h #includestdlib.h #define MAX 100 typedef int datatype; typedef struct { datatype elem[MAX]; int Last; }List,*SeqList; //定义顺序表类型 SeqList InitList() //初