数据结构与算法实验内容
实验1.1 顺序表的操作及其应用
实验目的
掌握线性表的顺序存储结构；
熟练掌握顺序表基本算法的实现；
掌握利用线性表数据结构解决实际问题的方法和基本技巧；
按照实验题目要求独立正确地完成实验内容。
实验环境
硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP；
软件：visual c++6.0；
实验内容
要求：数据元素类型ElemType 取整型int 或者char 。顺序存储实现如下算法： 创建一顺序表；
输出该顺序表；
在顺序表中查找第i 个元素，并返回其值；
在顺序表中第i 个元素之前插入一已知元素；
在顺序表中删除第i 个元素；
实现顺序表的合并。（选做）
实验1.2 链表的操作及其应用
实验目的
掌握线性表的链式存储结构；
熟练掌握链式基本算法的实现；
掌握利用线性表数据结构解决实际问题的方法和基本技巧；
按照实验题目要求独立正确地完成实验内容。
实验环境
硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP；
软件：visual c++6.0；
实验内容
要求：数据元素类型ElemType 取字符型char 或者int 。按照动态单链表结构实 现如下算法：
创建单链表；
输出该链表；
在链表中查找第i 个元素，i 合法返回元素值，否则，返回FALSE ；
在线性表中删除第i 个结点；
两个有序链表的合并；（选做题）
一元多项式求和；（选做题）
实验2.1栈的操作及其应用
实验目的
掌握栈的基本操作；
掌握应用栈解决问题的方法；
掌握利用栈进行后缀表达式求值的算法。
实验环境
硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP；
软件：visual c++6.0；
实验内容
实现如下算法：
利用栈实现数制转换算法；
输入后缀表达式（通过键盘输入，表达式以字符‘#’结束），计算表达式的值，在屏幕中输出。（选做）
实验提示：
先补充完成入栈和出栈的函数，再编写进制转换函数。
判断是否为数字函数isdigit
实验2.2 队列的操作及其应用
实验目的
掌握队列的基本定义；
掌握循环队列基本操作的实现；
掌握利用栈和循环队列进行回文字符串的判定。
实验环境
硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP；
软件：visual c++6.0；
实验内容
回文字符串的判定
要求：数据元素类型 ElemType 取字符型 char 。实现如下算法：
创建一循环队列；
创建一个顺序栈；
利用栈和队列实现回文字符串的判定。
实验提示：
在实验2.1的基础上（利用已完成的栈的类型定义和基本操作的实现）完成循环队列的存储结构定义（取名为SqQueue ）。
完成循环队列的基本操作（参数可根据实际需要来确定）
初始化队列InitQueue
销毁队列ClearQueue
入队列enQueue
出队列deQueue
利用栈和队列的特性，将输入的字符串分别进栈和队列，完毕后再依次出栈和出队，比较输出内容是否相等，若不相等则判别为非回文字符串，若栈空且队列空则是回文字符串。 如何实现接受用户从键盘输入的字符串？
cout请输入一个字符序列，回车换行结束！"
cin.getline(str,80);
int h=strlen(str);
实验3 二叉树的操作及其应用
实验内容
创建二叉树；
实现二叉树的水平输出算法；
完成对二叉树进行深度和叶子数目统计的算法；
完成对二叉树的中序遍历输出算法。
实验4 图的遍历及应用
实验目的
掌握图的邻接矩阵存储；
利用邻接矩阵存储图；
掌握图的邻接表存储；
利用邻接表存储图并实现图的遍历；
实验内容
已知图1，分别用邻接矩阵，邻接表表示两种表示法创建g1,g2.
0 1 0 1 Edges= 1 0 1 1 0 1 0 0 1 0 0 1
图1无向图
无向图对应的邻接表表示如下图所示：
序号
1 3 ∧
0 2 3 ∧
0 1 ∧
一个无向图的邻接表表示
利用邻接矩阵存储图1。
要求：数据元素类型ElemType 取char 。
利用邻接矩阵存储一个图。
利用邻接表存储图1并实现图的遍历。
要求：数据元素类型ElemType 取char 。实现如下算法：
1）利用邻接表存储一个图；
2）输出邻接表；
3）对创建的图进行深度优先遍历（选做）
4）对创建的图进行广度优先遍历（选做）
实验5 查找算法
实验目的
掌握有序表、无序表查找的基本思想及存储、运算的实现
深刻理解各种算法的特点，并加以灵活应用
加深对查找的理解，逐步培养解决实际问题的编程能力
实验内容
建立一个无序表并实现其上的顺序查找；
建立一个有序表并实现其上的折半查找（用递归和非递归两种算法实现）；