上海应用技术学院-数据结构与算法-课程设计报告.doc

《上海应用技术学院-数据结构与算法-课程设计报告.doc》由会员分享，可在线阅读，更多相关《上海应用技术学院-数据结构与算法-课程设计报告.doc（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上海应用技术学院数据结构与算法课程设计报告院 系： *学院 专 业： * 班 级： 091*11 姓 名： 公孙胜天 学 号： 091* 指导老师： 何* 一、 课程设计目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、 课程设计要求1)学生必须仔细阅读数据结构与算法课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。2)学生要发

2、挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。3)课程设计按照教学计划需要两周时间完成，两周中每天至少要上六小时的上机来调试C或C+语言设计的程序，总共至少要上机调试程序30小时。属教师安排上机时间学生不得缺席。三、 课程设计内容1、 建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归的方法都可以）*任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数； 2、 各种排序任务

3、：用程序实现插入法排序、选择法排序、起泡法改进算法排序；利用插入排序、选择法排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。四、 课程设计细节（一）第一题设计：a)需求分析：本程序是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。本程序用C-Free 5编写，可以实现各种二叉树的遍历。包括层序遍历、先序遍历、中序遍历、后序遍历的非递归算法。根据题目知，程序主要是根据给定二叉树的四种遍历结果：(1)先创建二叉树：按括号表示法输入二叉树字符串，然后构造二叉链表表示的二叉树。(2

4、)设计算法：层序遍历、先序遍历、中序遍历、后序遍历. 在做到层序遍历时，应注意算法如下：根结点入队，队头元素出队，左孩子不为空入队右孩子不为空入队的顺序进行。(3)设计main()函数调用以上步骤实现相关功能。根据题目要求，我们主要设计了以下几个函数：（1）typedef struct node定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。（2）BTNode *CreateBTNode(BTNode *&b)此函数的功能是构建二叉树。从键盘上按括号表示法输入

5、二叉树字符串构造二叉链表表示的二叉树T。（3）void LevelOrder(BTNode *b)此函数的功能是用非递归的方法实现二叉树的层序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（4）void PreOrder(BTNode *b) 此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。（5）void InOrder(BTNode *b)此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（6）void PostOrder(BTNode *b)此函数的功能是用非递归的方

6、法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。（7）void DispBTNode(BTNode *b)此函数的功能是先序输出二叉树字符串。b)概要设计：我们的算法设计如下：一、 非递归遍历算法用指针数组stack代替栈，添加一个top来表示进栈出栈的操作，同时还可以判断stack是否为空。1、 先序遍历 每次将节点压入栈，然后弹出，压右子树，再压入左子树，在遍历过程中，遍历序列的右节点依次被存入栈，左节点逐次被访问。2、 中序遍历先寻找最左边的树叶输出（寻找过程中每个根节点都要入栈），然后依次出栈，判断根节点的右孩子是否有左孩子（即每次都要寻找每个根的最左孩子

7、）知道top=-1,即栈空。3、 后序遍历设置一标志，以判断节点是否访问过。先寻找最左边的树叶，但不输出（寻找过程中每个根节点都要入栈）取栈顶元素，判断其有没有右孩子，没有的话则输出，有的话则还要继续判断其有没有左孩子。知道栈为空。二、 非递归层次遍历算法访问元素所指结点，若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。根绝题目要求我们设计main函数流程图为：先定义二叉树，用链式存储结构存储二叉树。其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。定义二叉树结点值的类型为字符型且结点个数不超过20个。定义好二

8、叉树后，创建二叉链表存储的二叉树。按二叉树带空指针的先序次序输入结点值，结点类型为字符型。按先序次序输入，其中*表示空结点。算法是按照先序遍历思想设计的。构造二叉链表表示的二叉树T，星号表示空树。其中mark的值1、2、3、4分别指stri为字母、(、，、)；tag为左、右孩子的标志。建立二叉树的流程图如下：b=null检查str10()，mark=1；b-data=str0,b-lchild=b-rchild=null;p=b;str0是否为字母YNNmark=2?mark=2stri入栈tag=0mark=3?mark=3tag=1Nmark=4pop为空return bNYY)mark=

9、1&栈不空新建结点pp-data=stri p-lchild=p-rchild=nulltag=0?循环结束后return b栈顶-rchild=p栈顶-lchild=pYN二叉树的非递归先序遍历流程图如下：初始化队列，b入队栈非空出栈p；打印p-dataYp-lchild!=nullYp-lchild入栈p-lchild!=nullNYNp-rchild入栈结束N二叉树的层次遍历流程图如下：初始化队列，b入队队列非空出队p；打印p-dataYp-lchild!=nullYp-lchild入队p-lchild!=nullNYNp-rchild入队结束Nc）详细设计：本题的源程序如下：myBTr

10、ee.cpp：/*copyright:孤独的野狼 *版权所有，请勿侵权 *文件名：myBtree.cpp *日期：2012/6/25 */ #include #include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/*数据元素*/struct node *lchild;/*指向左孩子*/struct node *rchild;/*指向右孩子*/ BTNode;BTNode *CreateBTNode(BTNode *&b)/*外部输入建立创建二叉链*/BTNode *

11、StMaxSize,*p=NULL;char ch,str300;int top=-1,k,j=0; scanf(%s,str);b=NULL;/*建立的二叉树初始时为空*/ch=strj;while (ch!=0)/*str未扫描完时循环*/ switch(ch) case (:top+;Sttop=p;k=1; break;/*为左结点*/case ):top-;break;case ,:k=2; break; /*为右结点*/default:p=(BTNode *)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL; if (b=

12、NULL) /*p指向二叉树的根结点*/b=p;else /*已建立二叉树根结点*/switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;return b;void DispBTNode(BTNode *b) /*二叉树输出函数*/if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();/*有孩子结点时才输出(*/DispBTNode(b-lchild);/*递归处理左子树*/if (b-rchild!

13、=NULL) printf(,);/*有右孩子结点时才输出,*/DispBTNode(b-rchild);/*递归处理右子树*/printf();/*有孩子结点时才输出)*/void LevelOrder(BTNode *b) /*层次遍历算法*/BTNode *p;BTNode *quMaxSize;/*定义环形队列,存放结点指针*/int front,rear;/*定义队头和队尾指针*/front=rear=-1;/*置队列为空队列*/rear+;qurear=b;/*根结点指针进入队列*/while (front!=rear)/*队列不为空*/front=(front+1)%MaxSiz

14、e;p=qufront;/*队头出队列*/printf(%c ,p-data);/*访问结点*/if (p-lchild!=NULL)/*有左孩子时将其进队*/rear=(rear+1)%MaxSize;qurear=p-lchild;if (p-rchild!=NULL)/*有右孩子时将其进队*/rear=(rear+1)%MaxSize;qurear=p-rchild; void PreOrder(BTNode *b)/*先序非递归遍历算法*/BTNode *p;struct BTNode *pt;int tag; StMaxSize;int top=-1;top+;Sttop.pt=b;

15、Sttop.tag=1;while (top-1)/*栈不空时循环*/if (Sttop.tag=1)/*不能直接访问的情况*/p=Sttop.pt;top-;if (p!=NULL)/*(2)式*/top+;/*右孩子结点进栈*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子结点进栈*/Sttop.pt=p-lchild;Sttop.tag=1;top+;/*根结点进栈*/Sttop.pt=p;Sttop.tag=0;if (Sttop.tag=0)/*直接访问的情况*/printf(%c ,Sttop.pt-data);top-; /*while*/voi

16、d InOrder(BTNode *b)/*中序非递归遍历算法*/BTNode *p;struct BTNode *pt;int tag; StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/*栈不空时循环*/if (Sttop.tag=1)/*不能直接访问的情况*/p=Sttop.pt;top-;if (p!=NULL)top+;/*右孩子结点进栈*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*根结点进栈*/Sttop.pt=p;Sttop.tag=0;top+;/*左孩子结点进栈*/St

17、top.pt=p-lchild;Sttop.tag=1;if (Sttop.tag=0)/*直接访问的情况*/printf(%c ,Sttop.pt-data);top-; /*while*/void PostOrder(BTNode *b)/*后序非递归遍历算法*/BTNode *p;struct BTNode *pt;int tag; StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/*栈不空时循环*/if (Sttop.tag=1)/*不能直接访问的情况*/p=Sttop.pt;top-;if (p!=NULL)

18、top+;/*根结点进栈*/Sttop.pt=p;Sttop.tag=0;top+;/*右孩子结点进栈*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子结点进栈*/Sttop.pt=p-lchild;Sttop.tag=1;if (Sttop.tag=0)/*直接访问的情况*/printf(%c ,Sttop.pt-data);top-; /*while*/FirstProg.cpp:/*copyright:孤独的野狼 *版权所有，请勿侵权 *文件名：FirstProg.cpp *日期：2012/6/25 */ #include #include myBTre

19、e.cppextern BTNode *CreateBTNode(BTNode *&b); /*建立二叉树*/extern void DispBTNode(BTNode *b); /*二叉树输出函数*/extern void LevelOrder(BTNode *b); /*层次遍历算法*/extern void PreOrder(BTNode *b); /*先序非递归遍历算法*/extern void InOrder(BTNode *b); /*中序非递归遍历算法*/extern void PostOrder(BTNode *b); /*后序非递归遍历算法*/int main(void) B

20、TNode *b,*p,*lp,*rp;char c,x;printf(copyright:孤独的野狼，All rights reserved！n);printf(请输入二叉树: );b=CreateBTNode(*&b);printf(您输入的二叉树为:);DispBTNode(b);printf(n);printf(层次遍历序列:);LevelOrder(b);printf(n);printf(先序遍历序列:);PreOrder(b);printf(n);printf(中序遍历序列:);InOrder(b);printf(n);printf(后序遍历序列:);PostOrder(b);pr

21、intf(n);d）调试分析本程序输入的字符串为A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)，其对应的二叉树为：测试所得结果为：本程序按非递归遍历所耗费的时间复杂度为O（n），其所耗费的空间复杂度也为O（n）。（二）第二题设计：a)需求分析：排序的方法很多，根据排序文件所处位置的不同，可将排序分为内部排序和外部排序两大类，本篇课程设计针对内部排序的实现程序展开。内部排序是指待排序的数据量不大，在内存中进行的排序，内部排序的种类很多，本文主要应用的是直接插入排序、冒泡排序、直接选择排序。衡量排序算法的性能指标有时间复杂度、空间复杂度和稳定性。各种排序方法所需的附加空间量一般都不

22、大，所以时间复杂度是衡量排序算法好坏的重要因素。对内部排序而言，其时间主要用在关键字的比较和交换上，因此比较次数和交换次数的多少直接影响排序方法的效率。在本程序中我们设计如下几个函数：（1）直接选择排序函数void SelectSort(RecType R,int n)该函数实现按对R的直接选择排序，并输出排序过程。（2）直接插入排序函数void InsertSort(RecType R,int n)该函数实现按对R的直接插入排序，并输出排序过程。（3）冒泡排序函数void BubbleSort(RecType R,int n)该函数实现按对R的冒泡排序，并输出排序过程。（4）R还原函数voi

23、d rollback(RecType backup,RecType R,int n)该函数对R进行回滚，即将R还原为初始值。b)概要设计：根据题目我们设计如下算法：1、插入排序算法： 将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。 排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个

24、大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。2、选择排序算法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从arrayk开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array

25、k-1更小的元素，则把arrayminlIndex和ak-1对调，这时arrayk到最后一个元素中最小的元素就换到了arrayk-1的位置。 如此反复进行第二轮、第三轮直到循环至最后一元素3、冒泡排序算法：设待排序的文件为r1.n，第1趟(遍)：从r1开始,依次比较两个相邻记录的关键字ri.key和ri+1.key,若ri.keyri+1.key，则交换记录ri和ri+1的位置；否则,不交换。 (i=1,2,.n-1)，第1趟之后,n个关键字中最大的记录移到了rn的位置上。第2趟：从r1开始,依次比较两个相邻记录的关键字ri.key和ri+1.key,若ri.keyri+1.key，则交换记录

26、ri和ri+1的位置；否则,不交换。(i=1,2,.n-2)第2趟之后,前n-1个关键字中最大的记录移到了rn-1的位置上，作完n-1趟,或者不需再交换记录时为止。我们设计的main函数流程图如下：根据算法得到的插入排序的流程图为：开始i=2i=ni+R0=Ri;j=i-1Rj+1=Rjj-Rj+1=R0结束R0RjNYYN选择排序的流程图为：开始i=1i=n-1i+j=i+1结束NYNj=nj+RjRkk=jNk=ij=i+1YYm=RiRi=RkRk=mYN冒泡排序的流程图为：开始i=1i=ij-Rj+1RjR0=Rj+1Rj+1=RjRj=R0NY我们使用的存储结构为：typedef i

27、nt KeyType;typedef char InfoType10;typedef struct RecType /*记录类型*/KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为InfoType*/ RecType;c）详细设计：本题的源程序为：Sort.cpp;/*copyright:孤独的野狼 *版权所有，请勿侵权 *文件名：sort.cpp *日期：2012/6/25 */ #include #define MAXE 20/*线性表中最多元素个数*/typedef int KeyType;typedef char InfoType10;t

28、ypedef struct RecType /*记录类型*/KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为InfoType*/ RecType;void SelectSort(RecType R,int n)/*直接选择排序算法*/int i,j,k,l;RecType temp;for (i=0;in-1;i+) /*做第i趟排序*/k=i;for (j=i+1;jn;j+) /*在当前无序区Ri.n-1中选key最小的Rk */if (Rj.keyRk.key)k=j; /*k记下目前找到的最小关键字所在的位置*/if (k!=i) /*交

29、换Ri和Rk */temp=Ri;Ri=Rk;Rk=temp; printf( i=%d ,i);/*输出每一趟的排序结果*/for (l=0;ln;l+)printf(%2d ,Rl.key);printf(n);void InsertSort(RecType R,int n) /*按递增有序进行直接插入排序*/int i,j,k;RecType temp;for (i=1;i=0 & temp.keyRj.key) Rj+1=Rj;/*将关键字大于Ri.key的记录后移*/j-; Rj+1=temp;/*在j+1处插入Ri*/printf( i=%d ,i);/*输出每一趟的排序结果*/f

30、or (k=0;kn;k+)printf(%2d ,Rk.key);printf(n);void BubbleSort(RecType R,int n)/*冒泡排序算法*/int i,j,k,exchange;RecType temp;for (i=0;ii;j-)/*比较,找出本趟最小关键字的记录*/if (Rj.keyRj-1.key) temp=Rj; /*Rj与Rj-1进行交换,将最小关键字记录前移*/Rj=Rj-1;Rj-1=temp;exchange=1;printf( i=%d ,i);/*输出每一趟的排序结果*/for (k=0;kn;k+)printf(%2d ,Rk.key

31、);printf(n);if(exchange=0)return; void rollback(RecType backup,RecType R,int n) /*还原*/int i=0;for(i=0;in;i+)Ri.key=backupi.key;int main(void)int i,n,m=5;RecType RMAXE;RecType backupMAXE;printf(CopyRight:孤独的野狼，All Rights Reserved！n);printf(请输入您要排序的数字的个数：);scanf(%d,&n);for (i=0;in;i+)printf(请输入第%d个数字：

32、,i+1);scanf(%d,&m);Ri.key=m;backupi.key=m;printf(您输入的数字序列为：);for (i=0;in;i+) /*输出初始关键字序列*/printf(%2d ,Ri.key);printf(n);printf(插入法排序:n);InsertSort(R,n); rollback(backup,R,n);printf(选择法排序:n);SelectSort(R,n);rollback(backup,R,n);printf(起泡法改进算法排序:n);BubbleSort(R,n);printf(排好序的序列为：);/*输出初始关键字序列*/for (i=

33、0;in;i+)printf(%2d ,Ri.key);printf(n);d）调试分析本次测试输入的数字序列为：54、43、32、67、21、23、78、89测试所得结果为：插入排序的效率分析：空间效率：仅用了一个辅助单元。时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较2次移动。总比较次数=n-1次总移动次数=2(n-1)次最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。平均情况

34、下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，移动记录的次数为j/2+2次。由此，直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法选择排序的效率分析：空间效率：仅用了一个辅助单元。时间效率：简单选择排序中，所需进行记录移动的操作次数较小，其最小值为0，最大值为3（n-1）。然而，无论记录的初始排列如何，所需进行的关键字之间的比较次数相同，均为n(n-1)/2。因此，总的时间复杂度也是O(n2)。冒泡排序的效率分析：空间效率：仅用了一个辅助单元。时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。移动次数：最好情况下：待排序列已有序，

35、不需移动。三种排序方法的效率对比表如下：排序方法最好时间平均时间最坏时间稳定性插入排序O(n)O(n2)O(n2)稳定选择排序O(n2)O(n2)O(n2)不稳定冒泡排序O(n)O(n2)O(n2)稳定五、用户使用说明1本程序在C-Free 5环境下运行。2程序运行之时，请按括号表示法正确输入二叉树字符串，如：A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)六、参考文献1.数据结构教程（第3版），李春葆，清华大学出版社，20102.数据结构，杨剑，清华大学出版社，20113.数据结构(C语言版)，严蔚敏 吴伟民，清华大学出版社，19974.数据结构(用面向对象方法与C+描述) ，殷人昆，清华大学出版社，19985.C+数据结构与程序设计 （美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译， 清华大学出版社，2004 6.计算机算法设计与分析（第2版），王晓东， 电子工业出版社， 2004