数据结构与算法实验内容

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