《数据结构》实验指导实验一线性表的操作算法设计（2学时）1．实验目的（1）掌握线性表的操作算法，包括顺序表和链表的建立、插入、删除操作。（2）设计有序顺序表和链表的归并操作算法，学会模块化程序设计方法。2．实验内容（1）写出教材中顺序表和单链表的类实现。（2）输入两组有序序列，建立两个有序表，将它们合并，且保持有序。要求编写一个程序包含上述功能。实验二栈和队列的应用（2学时）1．实验目的（1）掌握栈和队列的操作算法，包括栈和队列的建立、进栈、出栈、进队、出队等操作。（2）了解栈和队列的应用，了解“算符优先算法”求解表达式值的思想。2．实验内容（1）写出教材中栈和队列的类实现。（2）输入一个具有加、减、乘、除运算的算术表达式，编写C++程序模拟计算机求解该表达式的值。实验三字符串的操作算法设计（2学时）1．实验目的（1）掌握字符串的操作算法，包括字符串的输入/输出、查找、插入、删除、比较、模式匹配等操作。（2）了解查找替换操作的应用和KMP算法的思想。2．实验内容（1）实现模式匹配的BF算法。（2）输入3个字符串s，t，x,在字符串s中查找字符串t，并将字符串s中包含的所有字符串t替换为x。实验四二叉树的操作算法设计（4学时）1．实验目的（1）掌握二叉树的操作算法，包括二叉树的建立、遍历、求树高等操作。（2）了解二叉树的应用和Huffman编码的思想。2．实验内容（1）使用二叉链表存储二叉树。（2）建立一棵二叉树、分别按先序、中序、后序、层次对其遍历、并求树高。（3）输入若干个权，建立Huffman树，并对其进行Huffman编码。实验五图的操作算法验证设计（4学时）1．实验目的（1）掌握图的存储结构与操作算法，包括图的邻接矩阵、邻接表的建立、图的遍历等操作。（2）验证PRIM算法、DIJKSTRA算法、拓朴排序算法。了解图的应用算法。2．实验内容（1）建立图的邻接矩阵、邻接表，对图进行深度优先和广度优先遍历。（2）求图的最小生成树、最短路径、拓朴序列。实验六查找算法验证与设计（2学时）1．实验目的（1）掌握查找操作算法，包括顺序查找、二分查找、二叉排序树的查找方法等。（2）比较各种查找算法的性能。2．实验内容（1）输入一组有序数据，用二分查找方法查找关键字。（3）输入一组数据，建立一棵二叉排序树，然后在二叉排序树中查找关键字。实验七排序算法验证与设计（2学时）1．实验目的（1）掌握排序操作算法，包括插入、快速、归并、堆排序等。（2）比较各种排序算法的性能。2．实验内容（1）输入一组数据，分别用插入、快速、归并、堆排序方法进行排序。