数据结构与算法
这里主要用于托管数据结构与算法八次实验
实验一
一、实验目的
1.掌握使用Turbo C2.0/C++/VC环境上机调试线性表的基本方法；
2.掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构上的运算。
二、实验内容
1.实现线性表顺序存储的各种基本运算（假设元素额类型为char）,设计完成第61页－62页实验题。
2.分别用两个顺序存储的线性表对集合进行表示，将其中一个集合并到另一个集合。
3.设计一个算法，将X插入到一个有序的线性表（按顺序存储从小到大），同时保持线性表有序。
4.基于顺序存储结构,设计一个算法,删除元素值在［x,y］之间的所有元素。
实验二
一、实验目的
1.掌握单链表、双链表、循环链表的基本操作。
2.掌握链表的插入、删除、查找、排序等操作。
3. 加深对线性表的理解，逐步培养解决实际++问题的能力。
二、实验内容
1.编写程序实现单链表的各种基本操作（假设数据元素类型为ｉｎｔ ），实现实验题2.2。调用上述函数实现下列操作，操作步骤如下：
①从键盘输入一个数据元素x，插入到线性表中第i（包含1号位置）个位置；
②从键盘输入一个数据元素关键字x或位置i（包含1号位置），从线性表中删除相应数据元素。
2.基于单链表的基本操作，实现线性链表的逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，以此类推。
3.将两个带头结点的循环单链表ha和hb合并为带头结点的循环单链表hc。
4．用单链表ha 存储多项式A（x）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。
5．约瑟夫环问题
(1) 约瑟夫（Joeph）问题的一种描述：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
(2) 编程实现约瑟夫环问题，利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。试设计一个程序求出出列顺序。并设m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
实验三
一、实验目的
1.掌握栈的表示与实现，完成栈的入栈、出栈等操作
2.掌握队列的表示与实现，完成队列的入队、出队等操作
3.利用栈与队列的基本特征，完成简单问题的模拟实现
二、实验内容
1.编写栈顺序存储定义及基本操作，完成实验题３.１。
2.利用顺序栈实现输入整数n的八进制转换。
3.编写循环队列的基本操作函数，完成实验题３.３。
4.利用栈实现迷宫问题。
（1）问题描述：
从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过， 数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。
（2）基本要求
输入数据
a.输入迷宫的大小m行和n列，两者为整数
b.由随机数产生0或1，建立迷宫。
输出数据
首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：
(m，n)， ……， (I，j)， ……， (1，1)
如无通道，则打印：
THERE IS NO PATH.
实验四
一、实验目的
1. 熟悉串类型的实现方法。
2. 模式匹配算法实现。
二、实验内容
1. 统计指定字符串在主串中出现的次数和位置。
（1）编写算法，顺序串的操作StrCompare(S,T),Strlength(S)。
（2）求主串S的指定子串T出现的次数和位置indexmod(s,t)；(例如对于串S=”abcdeab”,T=”ab”,则输出结果应该是：串T在S中共出现2次，位置是1，6。
2. 实现基于定长顺序存储的KMP 算法。
实验五
一、实验目的
1. 深入了解数组的存储表示和实现。
2．掌握稀疏矩阵的特点(三元组存储方法)。
二、实验内容
1.实现二维数组的元素求和、转置操作。
2.实现对称矩阵的压缩存储。
3.稀疏矩阵的存储及转置运算。
（1）稀疏矩阵以三元组表输入，以通常的阵列形式输出；
（2）实现稀疏矩阵的转置。
三、实验要求
1.课下完成实验程序的编写，实验室调试验证；
2.实验完成后填写实验报告。
实验六
一、实验目的
1.掌握二叉树的非线性和递归性特点；
2.理解二叉树的存储结构；
3.掌握二叉树遍历操作。
二、实验内容
1.使用二叉链表，创建一个如图7.9（a）的二叉树。
2.可以用先序、中序和后序方式遍历二叉树并将结点输出。
3.统计出一个二叉树叶子节点及树的深度。
4.对于给定的w={2,3,4,7,8,9}权值，试构造一棵哈夫曼树，并给出各个节点的huffman编码及huffman数组的值。（选做）
实验七
一、实验目的
1. 熟悉各种图的存储结构。
2．掌握图的各种搜索路径的遍历方法。
二、实验内容
1.实现教程247页实验题8.1，完成图8.41的邻接矩阵与邻接表的存储与输出。
2.基于第一题，完成图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作，并输出遍历结果。
3.求教程247页图8.41中任意两点之间最短路径。
4.输出教程247页图8.41其拓扑排序结果。
实验八
一、实验目的
1．掌握顺序表和有序表的查找算法及特点；
2．理解排序的基本概念和各种排序方法的特点；
3．理解插入排序、交换排序、选择排序、归并排序基本原理；
4. 能灵活应用以上方法对数据进行排序。
二、实验内容
1. 对数据序列{3,6,2,10,1,8,5,7,4,9}，请分别用顺序表和二分查找算法进行数据元素的查找。
2. 对数据序列{9,8,7,6,5,4,3,2,1,0}和{49,38,65,97,76,13,27,49}，请用直接插入排序算法分别对两个数据序列进行排序。
3. 对数据序列{6,8,7,9,0,1,3,2,4,5}，请用分别冒泡排序和快速排序算法对数据序列进行排序。
4．对数据序列{6,8,7,9,0,1,3,2,4,5}，请用直接选择排序算法对数据序列进行排序。