Algorithm-Experiment

一、实验目的
 1.掌握使用Turbo C2.0/C++/VC环境上机调试线性表的基本方法;
 2.掌握线性表的基本操作:插入、删除、查找以及线性表合并等运算在顺序存储结构上的运算。
 
二、实验内容
1.实现线性表顺序存储的各种基本运算(假设元素额类型为char),设计完成第61页-62页实验题。
2.分别用两个顺序存储的线性表对集合进行表示,将其中一个集合并到另一个集合。
3.设计一个算法,将X插入到一个有序的线性表(按顺序存储从小到大),同时保持线性表有序。 
4.基于顺序存储结构,设计一个算法,删除元素值在[x,y]之间的所有元素。

一、实验目的
1.掌握单链表、双链表、循环链表的基本操作。
2.掌握链表的插入、删除、查找、排序等操作。
3. 加深对线性表的理解,逐步培养解决实际++问题的能力。
二、实验内容
1.编写程序实现单链表的各种基本操作(假设数据元素类型为int ),实现实验题2.2。调用上述函数实现下列操作,操作步骤如下:
 1从键盘输入一个数据元素x,插入到线性表中第i(包含1号位置)个位置; 
 2从键盘输入一个数据元素关键字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.编写栈顺序存储定义及基本操作,完成实验题3.1。
2.利用顺序栈实现输入整数n的八进制转换。
3.编写循环队列的基本操作函数,完成实验题3.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},请用直接选择排序算法对数据序列进行排序。