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

1、数据结构与算法D实验指导书武汉理工大学教材中心2009年7月实验一 线形链表的运算一、实验目的 掌握线性表在顺序分配下的插入与删除运算。二、实验原理线性表是数据元素的有限序列，在日常生活中有很多相关的例子，如1、人民币面值构成线性表2、一年由4个季节构成3、一个n维向量x=(x1,x2,x3,xn)。线性表的结构特点是：数据元素之间是线性关系，即在线性表中必存在唯一的一个“第一个”元素，必存在唯一的一个“最后一个”元素；除第一个元素外，每一个元素有且只有一个前趋元素；除最后一个元素外，每个元素有且只有一个后续元素。 若线性表中的数据元素之间可比较，则称该线性表为有序表，否则称为无序表。三、实验

2、内容编写程序完成单链表的下列基本操作： (1) 建立一个长度为n的单链表。 (2) 插入新结点。 (3) 删除某一个结点。 (4) 打印输出La中的结点元素值。四、实验方法1、数据产生 通过随机数函数获得数据，或通过赋值方法确定数据。2、线性表的插入与删除线性表在本次实验中是动态变化，插入、删除元素，为使线性表任保持有序性，必须要找到元素插入或删除的位置。插入算法：Insert_Link(LinkList * L,int i,datatype e) LinkList *p,*s; int j; s=(LinkList *)malloc(sizeof(Lnode); s-data=e; s-ne

3、xt=NULL; p=L; j=0; while(p!=NULL & jnext; +j;/*寻找第i-1个结点*/ if(!p|ji-1) return ERROR; s-next=p-next; p-next=s; return OK; 删除算法Delete_Link(LinkList *L,int i,datatype e) LinkList *p,*q; int j; p=L; j=0; while(p-next & jnext; +j; if(!p-next|ji-1) return ERROR; q=p-next; p-next=q-next; e=q-data; free(q);

4、 return OK; 五、实验步骤和要求1、确定构成线性表的数据；2、根据给出算法编制程序，调试通过；3、运行程序，检查程序是否完成实验内容中的要求。六、实验报告要求1、原理说明；2、算法说明；3、程序清单。七、思考题比较指针和数组实现线性表的插入、删除的异同。实验二 堆栈/队列结构及运算一、实验目的用循环队列的链式结构求解约瑟夫问题。二、实验原理队是一种特殊的线性表，它只允许在一端进行插入，在另一端进行删除，允许插入的一端称为队尾，通常用一个队尾指示器指向队尾元素；允许删除的一端称为排头，用一个排头指示器指向排头元素。在队列中，最先插入的元素将最先删除，因此又称队为先进先出线性表。从存储结

5、构看，队分为顺序队与链队两种。顺序队用一维数组连续存放队列元素，容量固定；链队的容量无法预先估计，可动态变化。在链队中我们设一个头结点，头指针始终指向头结点，尾指针指向队尾元素。三、实验内容：n个人围坐在圆桌周围，从某个人开始编号为1，2，3，4,n，编号为1的位置上的人从1开始报数，数到m的人出列，从下一个人又从1开始报数，数到m的人便是第二个出列的人。如此重复下去，直到最后一个人出列为止。四、实验方法：1、初始化循环单链表void init_linklist(LinkList *L)/*循环单链表进行初始化*/ (*L)=(POINTER)malloc(sizeof(struct LNod

6、e); (*L)-data=-1; (*L)-next=(*L); 2、 入队操作算法 Inert_sque(LinkList * L) int num; /*插入队列的结点值*/ LinkList p; while(num!=XX) /*XX表示退出循环条件*/ p=(LinkList *)malloc(sizeof(Lnode); p-data=num; p-next=(*L)-next; (*L)-next=p; /*插入队尾*/ 3、出队操作算法 del_sque(LinkList L) int m, k; pointer p, front,u; scanf(“%d”,&m);/*设置

7、报数值*/ 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、程序清单。七、思考题试比较顺序表和链表的优缺点。实验三 构造二叉树一、实验目的掌握二叉排序树的构造与存储、二叉排序树的查找。二、实验原理树型结构是一类很重

8、要的非线性数据结构，元素结点之间存在明显的分支和层次关系。树型结构在客观世界中广泛存在。数是由n个（n=0）结点组成的有限集合，其中有且仅有一个结点称为根结点（root）,其余结点构成根结点的子树或叶子。二叉树是由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。二叉树的性质 1、二叉树的第i层上至多有2i-1(i=1)个结点。 2、深度为h的二叉树中至多含有2h-1个结点。 3、在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有： n0 = n2 +1三、实验内容：用任意十个整数将其构建成一个二叉树并输出该二叉树。四、实验方法：构造二叉树： 1、读入一个数据元素，建立

9、一个新结点； 2、若二叉树为空，则新结点为根结点； 3、若二叉树非空，下标模二余0的作为左结点，否则作为右结点 。具体算法如下： Status CreateBiTree(BiTree *T) int ch,n,i,j,f; BiTNode *p,*nar100; scanf(%dn,&n); for(i=0;idata=ch; p-lchild=NULL; p-rchild=NULL; narj=p; if(j=1) *T=p; else f=j/2; if(j%2)=0) narf - lchild=p; /*插入左子树*/ else narf - rchild=p; /*插入右子树*/ 五

10、、实验步骤和要求1、根据给出算法编制程序，调试通过；2、运行程序，检查程序是否完成实验内容中的要求。六、实验报告要求1、原理说明；2、算法说明；3、程序清单。七、思考题试说明树与二叉树有何不同？为何要将一般树转换为二叉树？实验四 求解皇后问题一、实验目的通过对求解皇后问题的分析，进一步熟悉和了解深度优先搜索DFS（Depth First Search）技术，提高解决实际问题的能力。二、实验内容由n2个方块排列成n行和n列的正方形“n元棋盘”。如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上，则称他们在互相攻击。现要求找出使棋盘上的n个皇后互不攻击的布局。三、实验步骤和要求：1、仔细预习

11、本实验中对于求解皇后问题的方法说明，并根据实验要求事先编制好程序。2、上机调试你所编写的程序，并最后输出结果。3、n的取值可任意选取。4、整理程序清单和运行结果，并写好实验报告。四、实验方法：解决这个问题一个很简单的方法是穷举法，即先不考虑是否互相攻击，于是在每一行上皇后可选择的位置由n种，而现在有n个皇后分别在每一行上，因此共有nn种方案。然后对此nn种方案逐个检查，从中找到互不攻击的布局。但这个穷举法对于较小n是可行的，但对于较大n，工作量将急剧地增加。实际上我们发现，逐一穷举是没有必要的。例如，如果第一行的皇后在第一列，则第二行上的皇后就不可能在第一列。因此，我们可以设计一种更快的算法。

12、首先定义一个数组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行皇

13、后与第i-2行上的皇后均不互相攻击的下一个位置。此时如果已退到第0行，则过程结束。（2）若A(i)n，则需检查第i行皇后与前i-1行的皇后是否互不攻击。若有攻击，则将第i行皇后右移一个位置，重新进行这个过程，若无攻击，则考虑安排下一行皇后的位置。（3）若当前安排好的皇后是在最后一行（即第n行），则说明已找到了n个皇后互不攻击的一个布局，将这个布局打印输出。然后将第n行的皇后右移一个位置，重新进行这个过程，以便另一种布局。综合以上过程，可以形象地概括成一句话“向前走，碰壁回头”。下面给出详细的算法描述语句。输入：n。输出：n个皇后互不攻击的各种布局。定义数组 A(1:n)FOR i = 1 TO

14、 n DO A(i) 1i 1loop: IF A(i) n THEN k 1 WHILE(ki-1) and (A(k)-A(i)*(|A(k)-A(i)|-|k-i|)0 DO k k+1 IF ki-1 THEN A(i) A(i)+1; GOTO loop i i+1 IF in THEN GOTO loop OUTPUT A(i)(i=1,2,n)A(n) A(n)+1; i n; GOTO loop ELSE A(i) 1; i i-1 IF i 1 THEN RETURN A(i) A(i)+1; GOTO loop五、实验报告要求1、原理说明；2、算法说明；3、程序清单。实验五

15、 排序方法的比较一、实验目的掌握“冒泡”排序法和快速排序法。二、实验内容产生1000个随机整数，分别用“冒泡”法和快速法编制程序进行排序，并比较他们的运行时间。三、实验步骤和要求：1、首先产生1000个0到999之间的随机整数。2、编写一个程序：（1）将数据文件中的1000个数据赋给数组L(1:1000)；（2）用“冒泡”法进行排序。运行这个程序，并记下运行时间。3、编写一个程序：（1）将数据文件中的1000个数据赋给数组L(1:1000)；（2）用快速法进行排序。运行这个程序，并记下运行时间。4、整理程序清单和运行结果，并写好实验报告。四、实验方法：C语言教材中对“冒泡”排序已有较详细的叙述

16、，下面只对快速排序法作一说明。快速排序的基本思路是：通过一轮排序将线性表L分成两部分，其中前一部分的元素值均不大于后一部份的元素值；然后对每一部分再进行分解，直到排序完成为止。由此看出，快速排序实际上是对线性表逐步进行分割，其分割过程如下：（1）设置两个指针i和j，他们分别指向线性表的第一个和最后一个元素位置；（2）选取一个元素L(k)T，且L(i) L(k)；（3）将i逐渐减小，逐次比较L(j)与T，直到L(j)T，将L(j)移动到L(i)的位置；（5）反复进行(3)、(4)，直到i=为止，将T移到L(i)的位置。经过以上过程，以T为界线将线性表分成了两部分，前一部分元素值均不大于T，后一部

17、分值均不小于T。以此类推，对分割后的每一部分再进行这个过程，直到所有子表的长度为1。线性表分割的算法如下：SPLIT(L,m,n,i)输入：L(m:n)输出：分割后的分界线位置i。选取L(m)，L(m+n)/2，L(n)的中项，设为L(k)TL(k)；L(k) L(m)；im；jnWHILE ij DO WHILE (L(j)T) and (ij) DO j j-1 If ij THEN L(i) L(j)；ii+1 WHILE (L(i)T) and (ij) DO ii+1 If ij THEN L(j) L(i)；jj-1 L(i) TRETURN由上所述，快速排序是一个递归过程，其递归

18、算法如下：QKSORT(L,m,n)输入：L(m:n)输出：有序表L(m:n)IF mn THEN SPLIT(L,m,n,i) QKSORT(L,m,i-1) QKSORT(L,i+1,n) RETURN为了消去递归，要用到一个栈S。其非递归算法如下：QKSORT(L,1,n)top1；S(top) (1,n)WHILE top0 DO (k,m) S(top)；toptop-1 WHILE km DO SPLIT(L,k,m,i) toptop+1；S(top) (i+1,m)；mi-1 RETURN五、实验报告要求1、原理说明；2、算法说明；3、程序清单。实验六 最短距离问题一、实验目的

19、通过求解最短距离问题，进一步熟悉数组、队列、链接表的应用。二、实验内容设有n个结点，依次编号为1，2，n；m个三元组(i1，j1，f1)，(i2，j2，f2)，(im，jm，fm)中的每个三元组(it，jt，ft)(1tm)表示两个结点it(1itn)和jt(1jtn)之间有着双向的直接的联结（即它们之间没有别的结点），其距离为ft。编写一个程序，对于输入的结点g(1gn)算出可以由g到达的每个结点j的最短距离。三、实验步骤和要求：1、详细阅读本实验中的方法说明，读懂其算法，并编写好程序。2、调试程序：以n=7，g=6，10个三元组(1,2,13)， (1,3,8)， (1,5,30)， (1

20、,7,32) ，(2,6,9) ，(2,7,7)， (3,4,5) ，(4,5,6) ，(5,6,2)， (6,7,17)为例运行程序得出结果，并验证其正确性。3、自己确定一组输入的数据，再次运行上述程序。4、整理程序清单和运行结果，并写好实验报告。四、实验方法：假设输入的是数偶(n,m)，然后是m个三元组(i1，j1，f1)，(i2，j2，f2)，(im，jm，fm)以及整数g。对于每一个三元组(it，jt，ft)(1tm)，不妨假定itjt。首先，我们定义以下一些数组。(1:n)每个数组元素E(i)(1in)表示到目前为止已找到的由g到i的最短距离。初始状态时，E(g)=0，E(i)W(i

21、g)，其中W为比问题中可能出现的任何距离大得多的一个数，因此E(i)=W意味着还未发现由g到i的联接。S(1:n,1:2)这个数组提供了一个作为链式结构的循环队列空间。其中在初始状态时，S(g,1)=g，S(i,1)=-i，S(i,2)为链接指针。另外，用SE表示此队列的尾指针，Sl表示此队列的长度，其初值为：S(g,2)=g，SE=g，Sl=1X(1:n)这是一个索引数组，其中X(i)链接了第i个结点所能直接到达的结点j与它们之间的直接距离f，其初值为X(i)=0(表示相应的链接表为空)。所有这些链接表中的每个元素有三个域，即jfnextA(1:2m,1:3)这个数组提供了上述链接表中各元素

22、的存储空间，用于存放输入m个三元组(it，jt，ft)后所构成的信息 (jt，ft，next) 与(it，ft，next)，它们分别被链接到X(it)与X(jt)为头指针的链接表中。下面考虑解决这个问题的具体过程：(1)输入数偶(n,m)及m个三元组(it，jt，ft) (1tm,itjt)。对于每一个输入的三元组(i,j,f)，依次从数组A中摘取两行以存储数偶(j,f)与(i,f)，并分别链接到以X(i)与X(j)为头指针的链接表的链头。(2)输入g，并置以下初值：E(g)=0，E(k)=W(k=1,2,n,kg)；S(g,1)=g，S(g,2)=g，S(k,1)=-k(k=1,2,n, kg)；SE=g，Sl=1。(3)对于出现在队列S中的每一个结点i（初始时，在队列S中只含有一个值为g的元素），g可以到达，且其距离为E(i)。我们考虑由g经过i后直接到达的每一个