数据结构实验指导书11-12-1.doc

实验一 顺序表的建立和基本运算一、实验目的1、 掌握顺序表存储结构的定义及C/C+语言实现2、 掌握顺序表的各种基本操作及C/C+语言实现3、 设计并实现有序表的遍历、插入、删除等常规算法二、实验环境PC微机，Windows，DOS，Turbo C或Visual C+三、实验内容1、顺序表的建立和基本运算（1）问题描述 顺序表经常进行的运算包括：创建顺序表、销毁顺序表、求顺序表的长度、在顺序表中查找某个数据元素、在某个位置插入一个新数据元素、在顺序表中删除某个数据元素等操作。试编程实现顺序表的这些基本运算。（2）基本要求顺序表的每个运算要求用一个函数实现。要求至少实现顺序表的建立、删除元素、插入元素、显示顺序表函数，并定义主函数进行验证。（3）算法实现实验二 链表的建立和基本运算一、实验目的1、 掌握单链表存储结构的定义及C/C+语言实现2、 掌握单链表的基本操作及C/C+语言实现3、 建立并显示链表结点数据，并执行结点插入、删除操作二、实验环境PC微机，Windows，DOS，Turbo C或Visual C+三、实验内容1、实现链表的运算（1）问题描述 链表经常进行的运算操作有创建链表、求链表的长度、在链表中查找某个数据元素、在某个位置插入一个新数据元素、在链表中删除某个数据元素等操作。试编程实现链表的这些基本运算。（2）基本要求链表的每个运算要求用一个函数实现。要求至少实现链表的建立、插入、删除、显示函数，并定义主函数进行验证。（3）算法描述在设计链表的各种运算之前，最重要的准备工作是定义链式存储（即链表）的结点类型，最简单的链表的结点类型可由数据域data和指针域next两部分组成。然后再分别设计各种运算的具体函数。最后在主函数中实现链表的各种运算时，分别调用相应的函数即可。首先，在主函数中创建一个包含若干个结点的链表，在此基础上，就可以调用插入函数在链表的某个位置插入结点，调用删除函数删除某个位置的结点，调用求长度函数求出链表的长度，当然其他运算依次类推。为方便地实现上述的个种基本运算，可以再设计一个操作方便的主菜单。 在整个算法中有一个贯穿各个运算函数之间的线索，那就是链表。因此各个函数中的运算对象都是针对同一个链表的。可以把链表头指针定义为引用参数，也可以把指向链表的表头指针设定为全局变量。（4）算法实现实验三 栈结构及其应用一、实验目的1、 掌握栈的存储结构表示方法2、 掌握栈基本运算实现3、 设计用栈实现十进制到二进制的转换算法二、实验环境PC微机，Windows，DOS，Turbo C或Visual C+三、实验内容1、进制转换的实现（1）问题描述进行十二进制转换时涉及到余数的存储问题，存储的顺序与读写的顺序相逆。（2）基本要求利用栈实现算法。（3）算法描述首先，建立一个栈结构，且初始化为空，即令栈顶指针top=base。然后由键盘上随机输入一个整数，利用取模运算求余数，并入栈保存起来，直到商为零为止。在输出转换结果时进行出栈运算，判断栈是否为空，出栈并输出直到栈为空。（4）算法实现示例程序实验四 队列的应用一、实验目的：1、 了解队列的概念、队列的特性2、 掌握在两种存储结构上如何实现队列的基本操作以及队列在程序设计中的应用3、 通过在VC6.0中实现队列的插入和删除加深理解链队列和循环队列的意义。二、实验环境PC微机，Windows，DOS，Turbo C或Visual C+三、实验内容1、队的基本操作（1）问题描述队列是操作受限的线性表，是只允许仅在表的一端进行插入，而在另一端进行删除操作的线性表。在队列中，允许插入的一端称为队尾（rear），允许删除的一端称为对头（front）；链队列的插入删除即入队和出队分别在队列的尾和头进行。注意在循环队列中队满和队空的描述方法。 （2）基本要求实现链队列的入队和出队算法，循环队列的插入删除算法。（3）算法描述 分别建立链队列和循环队列，实现在不同队列中的入队和出队操作。实验五 数组和广义表一、实验目的：1、 熟悉数组类型的实现2、 掌握使用数组实现特殊矩阵的压缩存储3、 掌握稀疏矩阵的三元组表示法的实现二、实验环境PC微机，Windows，DOS，Turbo C或Visual C+三、实验内容1、完成对称矩阵的压缩存储，并能够在压缩存储的数组中根据矩阵上某结点的下标得到此结点的值2、定义矩阵的三元组顺序表结构，用三元组表示法来实现矩阵的转置运算实验六 二叉树一、实验目的：1、掌握二叉树链式存储的类型定义及实现。2、掌握二叉树链式存储的各种基本运算方法。如二叉树的创建、遍历、查找等运算。3、掌握二叉树用不同方法表示所对应的不同输入形式。4、掌握二叉树中各重要性质在解决实际问题中的应用。二、实验环境PC微机，Windows，DOS，Turbo C或Visual C+三、实验内容建立二叉树并实现各种遍历（1）问题描述 对二叉树的各种结点都访问，而且每个结点只访问一次的过程称为二叉树的遍历。根据访问二叉树中左子树、根、右子树的不同顺序，可先分为先根遍历、中根遍历、后根遍历三种访问方法。另外，由于二叉树中所有结点有相应的层次顺序，则按照从第1层到最后一层的访问顺序，并且每层都从左到右进行访问，又可得到层序遍历的访问方法。试编程完成： 用递归方法完成二叉树的创建、先根遍历、中根遍历、后根遍历。（必做） 用非递归方法完成完成二叉树的创建、按层遍历、中根遍历、后根遍历。（选作）（2）基本要求程序运行时，输入二叉树结