数据结构与算法D实验指导书

《数据结构与算法D》实验指导书武汉理工大学教材中心2009年7月实验一线形链表的运算一、实验目的掌握线性表在顺序分配下的插入与删除运算。二、实验原理线性表是数据元素的有限序列，在日常生活中有很多相关的例子，如1、人民币面值构成线性表2、一年由4个季节构成3、一个n维向量x=(x1,x2,x3,……,xn)。线性表的结构特点是：数据元素之间是线性关系，即在线性表中必存在唯一的一个“第一个”元素，必存在唯一的一个“最后一个”元素；除第一个元素外，每一个元素有且只有一个前趋元素；除最后一个元素外，每个元素有且只有一个后续元素。若线性表中的数据元素之间可比较，则称该线性表为有序表，否则称为无序表。三、实验内容编写程序完成单链表的下列基本操作：(1)建立一个长度为n的单链表。(2)插入新结点。(3)删除某一个结点。(4)打印输出La中的结点元素值。四、实验方法1、数据产生通过随机数函数获得数据，或通过赋值方法确定数据。2、线性表的插入与删除线性表在本次实验中是动态变化，插入、删除元素，为使线性表任保持有序性，必须要找到元素插入或删除的位置。插入算法：Insert_Link(LinkList*L,inti,datatypee){LinkList*p,*s;intj;s=(LinkList*)malloc(sizeof(Lnode));s-data=e;s-next=NULL;p=L;j=0;while(p!=NULL&&ji-1){p=p-next;++j;/*寻找第i-1个结点*/}if(!p||ji-1)returnERROR;s-next=p-next;p-next=s;returnOK;}删除算法Delete_Link(LinkList*L,inti,datatypee){LinkList*p,*q;intj;p=L;j=0;while(p-next&&ji-1){p=p-next;++j;}if(!p-next||ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;}五、实验步骤和要求1、确定构成线性表的数据；2、根据给出算法编制程序，调试通过；3、运行程序，检查程序是否完成实验内容中的要求。六、实验报告要求1、原理说明；2、算法说明；3、程序清单。七、思考题比较指针和数组实现线性表的插入、删除的异同。实验二堆栈/队列结构及运算一、实验目的用循环队列的链式结构求解约瑟夫问题。二、实验原理队是一种特殊的线性表，它只允许在一端进行插入，在另一端进行删除，允许插入的一端称为队尾，通常用一个队尾指示器指向队尾元素；允许删除的一端称为排头，用一个排头指示器指向排头元素。在队列中，最先插入的元素将最先删除，因此又称队为先进先出线性表。从存储结构看，队分为顺序队与链队两种。顺序队用一维数组连续存放队列元素，容量固定；链队的容量无法预先估计，可动态变化。在链队中我们设一个头结点，头指针始终指向头结点，尾指针指向队尾元素。三、实验内容：n个人围坐在圆桌周围，从某个人开始编号为1，2，3，4,…,n，编号为1的位置上的人从1开始报数，数到m的人出列，从下一个人又从1开始报数，数到m的人便是第二个出列的人。如此重复下去，直到最后一个人出列为止。四、实验方法：1、初始化循环单链表voidinit_linklist(LinkList*L)/*循环单链表进行初始化*/{(*L)=(POINTER)malloc(sizeof(structLNode));(*L)-data=-1;(*L)-next=(*L);}2、入队操作算法Inert_sque(LinkList*L){intnum;/*插入队列的结点值*/LinkListp;while(num!=XX)/*XX表示退出循环条件*/{p=(LinkList*)malloc(sizeof(Lnode));p-data=num;p-next=(*L)-next;(*L)-next=p;/*插入队尾*/}}3、出队操作算法del_sque(LinkListL){intm,k;pointerp,front,u;scanf(“%d”,&m);/*设置报数值*/while(p-next!=p){front=p;p=p-next;if(p==L){front=p;p=p-next;}++k;if(k==m){printf(%d,p-data);front-next=p-next;u=p;free(u);p=front;k=0;}}}五、实验步骤和要求1、根据给出算法编制程序，调试通过；2、运行程序，检查程序是否完成实验内容中的要求。六、实验报告要求1、原理说明；2、算法说明；3、程序清单。七、思考题试比较顺序表和链表的优缺点。实验三构造二叉树一、实验目的掌握二叉排序树的构造与存储、二叉排序树的查找。二、实验原理树型结构是一类很重要的非线性数据结构，元素结点之间存在明显的分支和层次关系。树型结构在客观世界中广泛存在。数是由n个（n=0）结点组成的有限集合，其中有且仅有一个结点称为根结点（root）,其余结点构成根结点的子树或叶子。二叉树是由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。二叉树的性质1、二叉树的第i层上至多有2i-1(i=1)个结点。2、深度为h的二叉树中至多含有2h-1个结点。3、在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0=n2+1三、实验内容：用任意十个整数将其构建成一个二叉树并输出该二叉树。四、实验方法：构造二叉树：1、读入一个数据元素，建立一个新结点；2、若二叉树为空，则新结点为根结点；3、若二叉树非空，下标模二余0的作为左结点，否则作为右结点。具体算法如下：StatusCreateBiTree(BiTree*T){intch,n,i,j,f;BiTNode*p,*nar[100];scanf(%d\n,&n);for(i=0;in;i++){scanf(%d:%c,,&j,&ch);p=(BiTNode*)malloc(sizeof(BiTNode));p-data=ch;p-lchild=NULL;p-rchild=NULL;nar[j]=p;if(j==1)*T=p;else{f=j/2;if((j%2)==0)nar[f]-lchild=p;/*插入左子树*/elsenar[f]-rchild=p;/*插入右子树*/}}}五、实验步骤和要求1、根据给出算法编制程序，调试通过；2、运行程序，检查程序是否完成实验内容中的要求。六、实验报告要求1、原理说明；2、算法说明；3、程序清单。七、思考题试说明树与二叉树有何不同？为何要将一般树转换为二叉树？实验四求解皇后问题一、实验目的通过对求解皇后问题的分析，进一步熟悉和了解深度优先搜索DFS（DepthFirstSearch）技术，提高解决实际问题的能力。二、实验内容由n2个方块排列成n行和n列的正方形“n元棋盘”。如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上，则称他们在互相攻击。现要求找出使棋盘上的n个皇后互不攻击的布局。三、实验步骤和要求：1、仔细预习本实验中对于求解皇后问题的方法说明，并根据实验要求事先编制好程序。2、上机调试你所编写的程序，并最后输出结果。3、n的取值可任意选取。4、整理程序清单和运行结果，并写好实验报告。四、实验方法：解决这个问题一个很简单的方法是穷举法，即先不考虑是否互相攻击，于是在每一行上皇后可选择的位置由n种，而现在有n个皇后分别在每一行上，因此共有nn种方案。然后对此nn种方案逐个检查，从中找到互不攻击的布局。但这个穷举法对于较小n是可行的，但对于较大n，工作量将急剧地增加。实际上我们发现，逐一穷举是没有必要的。例如，如果第一行的皇后在第一列，则第二行上的皇后就不可能在第一列。因此，我们可以设计一种更快的算法。首先定义一个数组A(1:n)，其中的每一个元素A(i)(i=1,2,3,……,n)随时记录了第i行上的皇后所在的列数。容易验证，第i行上的皇后和第j行上的皇后正好在某一对角线上的充要条件为|A(i)-A(j)|-|i-j|=0在初始时，我们将每一行上的皇后均放在第一列，即置A(i)=1(i=1,2,……,n)。然后在第一行（即i=1）开始进行以下过程。设前i-1行上的皇后已布局好，即他们互不攻击。现在考虑安排第i行上的皇后的位置，使得与前i-1行上的皇后也互不攻击。为了实现这一点，可以从第i行皇后的当前位置A(i)开始向右进行搜索：（1）若A(i)n，则将第i行皇后放在第一列，且回退一行，考虑第i-1行皇后与第i-2行上的皇后均不互相攻击的下一个位置。此时如果已退到第0行，则过程结束。（2）若A(i)≤n，则需检查第i行皇后与前i-1行的皇后是否互不攻击。若有攻击，则将第i行皇后右移一个位置，重新进行这个过程，若无攻击，则考虑安排下一行皇后的位置。（3）若当前安排好的皇后是在最后一行（即第n行），则说明已找到了n个皇后互不攻击的一个布局，将这个布局打印输出。然后将第n行的皇后右移一个位置，重新进行这个过程，以便另一种布局。综合以上过程，可以形象地概括成一句话“向前走，碰壁回头”。下面给出详细的算法描述语句。输入：n。输出：n个皇后互不攻击的各种布局。定义数组A(1:n)FORi=1TOnDOA(i)←1i←1loop:IFA(i)≤nTHEN{k←1WHILE(k≤i-1)and[(A(k)-A(i))*(|A(k)-A(i)|-|k-i|)]≠0DOk←k+1IFk≤i-1THEN{A(i)←A(i)+1;GOTOloop}i←i+1IFi≤nTHENGOTOloopOUTPUTA(i)(i=1,2,……,n)A(n)←A(n)+1;i←n;GOTOloop}ELSE{A(i)←1;i←i-1IFi1THENRETURNA(i)←A(i)+1;GOTOloop}五、实验报告要求1、原理说明；2、算法说明；3、程序清单。实验五排序方法的比较一、实验目的掌握“冒泡”排序法和快速排序法。二、实验内容产生1000个随机整数，分别用“冒泡”法和快速法编制程序进行排序，并比较他们的运行时间。三、实验步骤和要求：1、首先产生1000个0到999之间的随机整数。2、编写一个程序：（1）将数据文件中的1000个数据赋给数组L(1:1000)；（2）用“冒泡”法进行排序。运行这个程序，并记下运行时间。3、编写一个程序：（1）将数据文件中的1000个数据赋给数组L(1:1000)；（2）用快速法进行排序。运行这个程序，并记下运行时间。4、整理程序清单和运行结果，并写好实验报告。四、实验方法：C语言教材中对“冒泡”排序已有较详细的叙述，下面只对快速排序法作一说明。快速排序的基本思路是：通过一轮排序将线性表L分成两部分，其中前一部分的元素值均不大于后一部份的元素值；然后对每一部分再进行分解，直到排序完成为止。由此看出，快速排序实际上是对线性表逐步进行分割，其分割过程如下：（1）设置两个指针i和j，他们分别指向线性表的第一个和最后一个元素位置；（2）选取一个元素L(k)→T，且L(i)→L(k)；（3）将i逐渐减小，逐次比较L(j)与T，直到L(j)T，将L(j)移动到L(i)的位置；（4）将i逐渐减小，逐次比较L(j)与T，直到L(j)T，将L(j)移动到L(i)的位置；（5）反复进行(3)、(4)，直到i=为止，将T移到L(i)的位置。经过以上过程，以T为界线将线性表分成了两部分，前一部分元素值均不大于T，后一部分值均不小于T。以此类推，对分割后的每一部分再进行这个过程，直到所有子表的长度为1。线性表分割的算法如下：SPLIT(L,m,n,i)输入：L(m:n)输出：分割后的分界线位置i。选取L(m)，L[(m+n)/2]，L(n)的中项，设为L(k)T←L(k)；L(k)←L(m)；i←m；j←nWHIL