算法与数据结构实验报告

1、算法与数据结构实验报告算法与数据结构实验报告学院：计算机与信息学院专业班级：姓名：学号：实验目的：掌握栈和队列特点、逻辑结构和存储结构熟悉对栈和队列的一些基本操作和具体的函数定义。利用栈和队列的基本操作完成一定功能的程序。实验任务：给出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数与其它进制数的转换。（如）实验原理：将十进制数转换为八进制时，采用的是“除取余数法”，即每次用除所得的余数作为八进为新的值重复上述计算，直到为为止。最后的转换结果。程序清单：DATA_TYPE;DATA_TYPEx);DATA_TYPEdataMAXLEN;DATA_TYPES;请输入一个十进制数和所需转换的

2、进制输出转换结果输出转换结果测试数据：运行结果：给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前行的内容。一个数是，从第三行开始的其余的数是上一行个数求出下一行的一个数时，其中的前一个便需要删除，而新求出的数就要入队。程序清单：DATA_TYPE;get_front(DATA_TYPEDATA_TYPEx);DATA_TYPEdataMAXLEN;(front%MAXLEN=rear%MAXLEN);DATA_TYPEdatarear%MAXLEN=x;Q;运行结果：给出链栈的类定义和函数实现，并设计程序完成如下功能：读入一个有限大小的整数，并读入各元素的值。个特点就是先进后出

3、，这样，当将原栈为空时，输出与输入次序相反，从而实现了本题的要求。程序清单：DATA_TYPE;DATA_TYPEDATA_TYPEx);DATA_TYPE;DATA_TYPEu;L;n;请任意输入一个整数;测试数据：运行结果：实验目的：理解线性表的链式存储结构。熟练掌握动态链表结构及有关算法的设计。链表结构，并设计相关算法。实验任务：在一个递增有序的链表L中插入一个值为的元素，并保持其递增有序特性。实验数据：链表元素为（）,x分别为，和。实验原理:给出了要插入的条件，但没有给定插置的前驱结点而不是序号。程序清单:;list();i,*x);list:list()=-=NULL;=0;x;*s

4、,*rear;x;=)=-=x;-=s;=s;x;*p;(p!=NULL);u,*P;L;x;请输入要插入的值L.insert(x);运行结果：将单链表中的奇数项和偶数项结点分解开，显示结果，以便对照求解结果。实验测试数据：第一组数据：链表为（）第二组数据：链表为（）数字来控制，把他们取出来并重新连起来。程序清单：;list();*;list:list()=-=NULL;=0;x;*s,*rear;x;=)=-=x;-=s;=s;x;*p;(p!=NULL);A,&C)*PA,*PB,*PC,*s;PA=-PANULL=s;=s;L,L1,L2;divide(L,L1,L2);原链表：偶链表：

5、奇链表：实验结果：第一组数据：第二组数据：求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。实验测试数据：第一组数据：第一个链表为（，）第二个链表为（，）第二组数据：第一个链表元素为（，）第二个链表元素为（，）实验原理：设置两个指针怕，分别依次指示A,B表中的元素，其初始值分别为和均非空时，根据其值的大小关系可能有如下三种情况。C继续A同时也往后移。表明A表中这一元素可能在B表当前元素的后面,因此要往B表的后面搜索,故而执行然后继续搜索。表明A中这一元素在B以继续对A表中下一个元素的判断。反复执行上述比较，直到至少有一个为空为止。此时，剩余的非空部分没有所需要的公共元素，因

6、而搜索结束。程序清单：list();&x);i);&L2);list:list()x;*s;输入一个值：;输入一个值：;&L2)*u;p;NULL;&C)*u;*s;i)*u;u;L1,L2,L3;共有的元素为：;运行结果;第一组数据：第二组数据：实验目的：掌握二叉树的动态链表存储结构及表示。掌握二叉树的三种遍历算法。运用二叉树三种遍历的方法求解有关问题。二叉树。后序遍历。结点的数目。前k（）个结点的值。包括存储结点值的数据部分及指向两个孩子结点的指针，不妨设为和。对二叉树的遍历是在对各子树分别遍历的基础之上法来实现对左、右子树的遍历。程序清单：;*rchild;*T);*T);*T);*T)

7、;*&T);*T);*T);*T)*T)if(T!=NULL)visit(T);*T)if(T!=NULL)visit(T);*T)if(T!=NULL)visit(T);*&T)T=NULL;b;a;*T)T=NULL),+;*TT=NULLT-+T-+1;t;#表示空：;先序序列：中序序列：;t.inorder();后序序列：二叉树的高度为：结点数为：运行结果：实验目的：掌握图的基本概念。掌握图的存储结构的设计与实现，基本运算的实现。掌握图的两种遍历算法，以及遍历算法的应用。实验任务：以邻接矩阵邻接表的存储结构建立图。对图进行深度优先遍历广度优先遍历。求图中边的数目。判断无向图是否是连通的

8、。A为阶的，其中Aij表示顶点到vj之间是否有边或弧：若存在，则Aij为，否则为。邻接表的表示方式是将每个顶点的邻接点连成执行遍历时，搜索下一个访问顶点是从当前访问顶点到一个邻接点即意味着搜索到一条以为一个端点的边或弧，故应在算法中计数。程序清单：;E;);Travel_DFS();v););v););i,j;i,j,k;请输入顶点数请输入各顶点的值请输入边：ij，i为时结束w;i;i;k;无向图不连通。无向图连通。i;E=0;G;深度遍历的访问序列为：;无向图G的边数为：运行结果：实验目的：掌握顺序表的查找方法，尤其是二分查找方法。掌握二叉排序树的建立及查找。实验任务：对下列数据表，分别采用

9、二分查找算法实现查并以二分查找的判定树来解释。实验测试数据：数据表为查找的元素分别为：，实验原理：设查找区域的首尾下标分别用变量和和该区域的中间元素的关键字进行比较。程序清单：or;list();/初始化list:list()/求表长/求关键值表长/建表x;请依次输入顺序表中各个元素的值，结束符为/建立关键值表x;请依次输入所搜索的关键字，结束符为/显示表i;/二分查找法list:j;/初始化查找区域元素下标是：查找失败/返回查找失败的标志0;L;运行结果:实验任务：遍历序列。实验测试数据：构建二叉排序树的输入序列如下：，设计算法在二叉排序树中查找指定值的结点。在任务所建立的二叉排序树中分别查找下列元素：，程序清单：;*;*if(t!=NULL)*T,int查找失败！0;查找成功！0;*p=NULL;n;输入数据个数输入数据：a;中序遍历:输入要查找的值：实验结果：实验任务：取方法对排序过程中数据的比较和移动次数的影响。测试数据：数组元素分别为：（）后再对整个序列进行直接插入排序。程序清单：;list();list:list()x;请依次输入顺序表中各个元素的值，结束符为i;/希尔排序i,j,dh;n;实验结果：实验任务：实现堆排序算法，给出排序结果。测试数据：）用筛选