第2章 实验内容
2.1 实验1 线性表应用
一、顺序表
目的要求
1．掌握线性表顺序存储结构的特点。 2．掌握线性表顺序存储结构的常见算法。 实验内容
1．输入一组整型元素序列（不少于10个），建立顺序表。
2．在该顺序表中进行顺序查找某一元素，查找成功返回 1，否则返回 0。 3．判断该顺序表中元素是否对称，对称返回 1，否则返回 0。
4．实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。 5．输入整型元素序列（不少于10个），利用有序表插入算法建立一个有序表。 6．利用算法5建立两个非递减有序表，并把它们合并成一个非递减有序表。 7．在主函数中设计一个简单菜单，调用上述算法。 实验说明
1. 算法 1至算法6的有关函数用头文件方式存储，主函数包含该头文件。 2. 存储定义
const int MAXSIZE=15 ; // 表中元素的最大个数 typedef int ElemType； // 元素类型 typedef struct list
{
ElemType elem[MAXSIZE]; // 静态分配 int length; // 表的实际长度 } SqList ; // 顺序表的类型名 3. 建立顺序表时，利用随机函数自动产生数据。
二、单向链表
目的要求
1．掌握单链表的存储特点及其实现。 2．掌握单链表的插入与删除算法的程序实现。 实验内容
1．随机产生或键盘输入一组元素（不少于10个元素），建立一个带头结点的单链表。 2．把单链表中的元素逆置（不允许申请新的结点空间）。 3．删除单链表中所有的偶数元素结点。
4．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，利用该函数建立一个 非递减有序单链表。
5．利用算法4建立两个非递减有序单链表，然后合并成一个非递增链表。
6．把算法1建立的链表分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量 利用已有存储空间）。
7．在主函数中设计一个简单菜单，调用上述算法。 实验说明 1．结点类型定义
typedef int ElemType； // 元素类型 typedef struct LNode
{
ElemType data ;
struct LNode * next ; } LNode, *pLinkList ; 2．为了简单，采用带头结点的单链表。
三、双向链表
目的要求
１．掌握双向链表的存储结构及其实现。 ２．掌握双向链表的插入与删除算法的程序实现。 实验内容
１．利用尾插法建立一个双向链表。 ２．遍历双向链表。
３．实现双向链表中删除一个指定元素。
４．在非递减有序双向链表中实现插入元素e仍有序的算法。 ５．判断双向链表中元素是否对称，若对称返回 1，否则返回 0。 ６．设元素为正整型，实现算法把所有奇数排列在偶数之前。 ７．在主函数中设计一个简单菜单，调用上述算法。 实验说明
1. 双向链表的类型定义
typedef int ElemType； // 元素类型 typedef struct DuLNode {
ElemType data; DuLNode *prior, *next; } DuLNode, *pDuLinkList;
四、栈与队列
目的要求
1．掌握栈、队列的思想及其存储实现。 2．掌握栈、队列的常见算法的程序实现。 实验内容
1．采用链式存储实现栈的初始化、入栈、出栈操作。 2．采用顺序存储实现栈的初始化、入栈、出栈操作。 3．采用链式存储实现队列的初始化、入队、出队操作。 4．采用顺序存储实现循环队列的初始化、入队、出队操作。 5．在主函数中设计一个简单菜单，调用上述算法。 实验说明
1．顺序栈类型定义
const int MAX=20 ; // 栈的最大值 typedef struct {
ElemType *base； int top； } SqStack； 2. 顺序队列类型定义
const int MAX=20 ; // 队列的最大长度 typedef struct {
ElemType *base； int front，rear； } SqQueue；
2.2 实验2 二叉树应用
目的要求
1．掌握二叉树的存储实现。 2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。 实验内容
1．输入字符序列，建立二叉链表。 2．中序遍历二叉树：递归算法。
3．中序遍历二叉树：非递归算法。（最好也实现先序，后序非递归算法） 4．求二叉树的高度。 5．求二叉树的叶子数。
6．借助队列实现二叉树的层次遍历。
7．在主函数中设计一个简单的菜单，调用上述算法。 实验说明
1. 类型定义 // 二叉链表存储
#define ElemType char // 元素类型
数据结构与算法设计实验指导书
