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

上海应用技术学院上海应用技术学院上海应用技术学院上海应用技术学院《数据结构与算法》课程设计报告院系：*学院专业：******班级：091****11姓名：公孙胜天学号：091****指导老师：何****一、一、一、一、课程设计目的课程设计目的课程设计目的课程设计目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、二、二、二、课程设计要求课程设计要求课程设计要求课程设计要求1)学生必须仔细阅读《数据结构与算法》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。2)学生要发挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。3)课程设计按照教学计划需要两周时间完成，两周中每天至少要上六小时的上机来调试C或C++语言设计的程序，总共至少要上机调试程序30小时。属教师安排上机时间学生不得缺席。三、三、三、三、课程设计内容课程设计内容课程设计内容课程设计内容1、建立二叉树，层序、先序、中序、后序遍历（用递归或非递归的方法都可以）**任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；2、各种排序任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序；利用插入排序、选择法排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。四、四、四、四、课程设计细节课程设计细节课程设计细节课程设计细节（一）第一题设计：（一）第一题设计：（一）第一题设计：（一）第一题设计：a)需求分析：本程序是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。本程序用C-Free5编写，可以实现各种二叉树的遍历。包括层序遍历、先序遍历、中序遍历、后序遍历的非递归算法。根据题目知，程序主要是根据给定二叉树的四种遍历结果：(1)先创建二叉树：按括号表示法输入二叉树字符串，然后构造二叉链表表示的二叉树。(2)设计算法：层序遍历、先序遍历、中序遍历、后序遍历.在做到层序遍历时，应注意算法如下：根结点入队，队头元素出队，左孩子不为空入队右孩子不为空入队的顺序进行。(3)设计main()函数调用以上步骤实现相关功能。根据题目要求，我们主要设计了以下几个函数：（1）typedefstructnode定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。（2）BTNode*CreateBTNode(BTNode*&b)此函数的功能是构建二叉树。从键盘上按括号表示法输入二叉树字符串构造二叉链表表示的二叉树T。（3）voidLevelOrder(BTNode*b)此函数的功能是用非递归的方法实现二叉树的层序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（4）voidPreOrder(BTNode*b)此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。（5）voidInOrder(BTNode*b)此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（6）voidPostOrder(BTNode*b)此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。（7）voidDispBTNode(BTNode*b)此函数的功能是先序输出二叉树字符串。b)概要设计：我们的算法设计如下：一、非递归遍历算法用指针数组stack[]代替栈，添加一个top来表示进栈出栈的操作，同时还可以判断stack是否为空。1、先序遍历每次将节点压入栈，然后弹出，压右子树，再压入左子树，在遍历过程中，遍历序列的右节点依次被存入栈，左节点逐次被访问。2、中序遍历先寻找最左边的树叶输出（寻找过程中每个根节点都要入栈），然后依次出栈，判断根节点的右孩子是否有左孩子（即每次都要寻找每个根的最左孩子）知道top=-1,即栈空。3、后序遍历设置一标志，以判断节点是否访问过。先寻找最左边的树叶，但不输出（寻找过程中每个根节点都要入栈）取栈顶元素，判断其有没有右孩子，没有的话则输出，有的话则还要继续判断其有没有左孩子。知道栈为空。二、非递归层次遍历算法访问元素所指结点，若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。根绝题目要求我们设计main函数流程图为：开始输入二叉树节点层序遍历并输出前序遍历并输出中序遍历并输出后序遍历并输出结束先定义二叉树，用链式存储结构存储二叉树。其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。定义二叉树结点值的类型为字符型且结点个数不超过20个。定义好二叉树后，创建二叉链表存储的二叉树。按二叉树带空指针的先序次序输入结点值，结点类型为字符型。按先序次序输入，其中*表示空结点。算法是按照先序遍历思想设计的。构造二叉链表表示的二叉树T，星号表示空树。其中mark的值1、2、3、4分别指str[i]为字母、‘(’、‘，’、‘)’；tag为左、右孩子的标志。建立二叉树的流程图如下：b=null检查str[1~’\0’]‘(’‘)’‘，’mark=1；b-data=str[0],b-lchild=b-rchild=null;p=b;str[0]是否为字母YNNmark==2mark=2str[i]入栈tag=0mark==3mark=3tag=1Nmark=4pop为空returnbNYY‘)’mark==1&&栈不空新建结点pp-data=str[i]p-lchild=p-rchild=nulltag==0?循环结束后returnb栈顶-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入结束Ncccc）详细设计：本题的源程序如下：myBTree.cpp：/*copyright:孤独的野狼*版权所有，请勿侵权*文件名：myBtree.cpp*日期：2012/6/25*/#includestdio.h#includemalloc.h#includestdlib.h#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;/*指向右孩子*/}BTNode;BTNode*CreateBTNode(BTNode*&b)/*外部输入建立创建二叉链*/{BTNode*St[MaxSize],*p=NULL;charch,str[300];inttop=-1,k,j=0;scanf(%s,str);b=NULL;/*建立的二叉树初始时为空*/ch=str[j];while(ch!='\0')/*str未扫描完时循环*/{switch(ch){case'(':top++;St[top]=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==NULL)/*p指向二叉树的根结点*/b=p;else/*已建立二叉树根结点*/{switch(k){case1:St[top]-lchild=p;break;case2:St[top]-rchild=p;break;}}}j++;ch=str[j];}returnb;}voidDispBTNode(BTNode*b)/*二叉树输出函数*/{if(b!=NULL){printf(%c,b-data);if(b-lchild!=NULL||b-rchild!=NULL){printf(();/*有孩子结点时才输出(*/DispBTNode(b-lchild);/*递归处理左子树*/if(b-rchild!=NULL)printf(,);/*有右孩子结点时才输出,*/DispBTNode(b-rchild);/*递归处理右子树*/printf());/*有孩子结点时才输出)*/}}}voidLevelOrder(BTNode*b)/*层次遍历算法*/{BTNode*p;BTNode*qu[MaxSize];/*定义环形队列,存放结点指针*/intfront,rear;/*定义队头和队尾指针*/front=rear=-1;/*置队列为空队列*/rear++;qu[rear]=b;/*根结点指针进入队列*/while(front!=rear)/*队列不为空*/{front=(front+1)%MaxSize;p=qu[front];/*队头出队列*/printf(%c,p-data);/*访问结点*/if(p-lchild!=NULL)/*有左孩子时将其进队*/{rear=(rear+1)%MaxSize;qu[rear]=p-lchild;}if(p-rchild!=NULL)/*有右孩子时将其进队*/{rear=(rear+1)%MaxSize;qu[rear]=p-rchild;}}}voidPreOrder(BTNode*b)/*先序非递归遍历算法*/{BTNode*p;struct{BTNode*pt;inttag;}St[MaxSize];inttop=-1;top++;St[top].pt=b;St[top].tag=1;while(top-1)/*栈不空时循环*/{if(St[top].tag==1)/*不能直接访问的情况*/{p=St[top].pt;top--;if(p!=NULL)/*(2)式*/{top++;/*右孩子结点进栈*/St[top].pt=p-rchild;St[top].tag=1;top++;/*左孩子结点进栈*/St[top].pt=p-lchild;St[top].tag=1;top++;/*根结点进栈*/St[top].pt=p;St[top].tag=0;}}if(St[top].tag==0)/*直接访问的情况*/{printf(%c,St[top].pt-data);top--;}}/*while*/}voidInOrder(BTNode*b)/*中序非递归遍历算法*/{BTNode*p;struct{BTNode*pt;inttag;}St[MaxSize];inttop=-1;top++;St[top].pt=b;St[top].tag=1;while(top-1)/*栈不空时循环*/{if(St[top].tag==1)/*不能直接访问的情况*/{p=St[top].pt;top--;if(p!=NUL