数据结构课程设计报告

辽宁科技大学课程设计说明书设计题目： 数据结构课程设计ProjectforDataStructure学院、系： 软件学院 专业班级： 学生姓名： 指导教师： 成绩： 2012年01月06日目录TOC\o"1-5"\h\z1、 数据结构程序训练说明书 -2-1.1、 题目 -2-二叉树 -2-进制转换 -2-链表 -2-1.2、 设计要求 -2-\o"CurrentDocument"2、需求分析 -2-\o"CurrentDocument"2.1、 二叉树 -2-\o"CurrentDocument"2.2、 进制转换 -3-\o"CurrentDocument"2.3、 链表 -3-\o"CurrentDocument"3、概要设计: -5-3.1、 二叉树 -5-3.2、 进制转换 -5-3.3、 链表 -6-\o"CurrentDocument"4、详细设计: -6-\o"CurrentDocument"4.1二叉树实现的程序设计 -6-\o"CurrentDocument"4.2进制转换实现的程序设计 -7-\o"CurrentDocument"4.3链表相关功能实现的程序设计 -8-\o"CurrentDocument"5、调试分析 -10-\o"CurrentDocument"5.1二叉树实现的程序设计结果 -10-5.2进制转换实现的程序设计结果 -10-5.3链表相关功能实现的程序设计结果 -10-\o"CurrentDocument"6、程序设计总结 -11-\o"CurrentDocument"7、参考文献 -11-1、数据结构程序训练说明书1・1、题目二叉树进制转换链表1・2、设计要求二叉树：设计算法，在二叉树输入规则下，可以求出二叉树的叶子个数与结点总个数。进制转换：设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。链表：在一个有序表中插入一个元素，使得该表仍然有序。将一个链表中的元素进行拆分，将所有奇数放到一个链表中，将所有的偶数放到另个链表中。将两个链表合并成一个链表。将一个链表中的所有元素逆序存储并显示。2、需求分析2L二叉树分析算法：

二叉树的输入规则为：ABC##D##F###则输出结果为ABCDEF,2.2二叉树的输入规则为：ABC##D##F###则输出结果为ABCDEF,2.2、进制转换分析算法：设定一个十进制数，例如20,要将其转化二到九进制之间的任注：这里我使用的是转化为二进制第一步：取20与2的余，得到0第二步：取10与2的余，得到0第三步：取5与2的余，得到1第四步：取2与2的余，得到0第五步：取1与2的余，得到1至此为止，算法结束。进制20除以2得10。10除以2得5。5除以2得2。2除以2得1。1除以2得0。链表分析算法：使得该表仍然有序在一个有序表中插入一个元素，

使得该表仍然有序通过判断条件找到指定的插入位置然后通过进行插入新的结点插入到链表中。将一个链表中的元素进行拆分，将所有奇数放到一个链表中，将所有的偶数放到另一个链表中。判定a[i]中存放的数为奇数还是偶数，开辟不同的链表空间，用不同的指针的数据域进行存储。将两个链表合并成一个链表。顺序输出数组中奇数，定义一个指针跟随着奇数的移动而移动到奇数结束，然后，将该指针的next域指向偶数的头指针的next域，然后一次输出偶数链表中偶数，通过此种方法就可以将奇数链表和偶数链表链接起来输出。将一个链表中的所有元素逆序存储并显示。元素要按逆序存储，采用尾差法进行新链表的生成。(如图所示)3、概要设计3.1、 二叉树设计二叉树实现算法，利用递归实现前序遍历，采用先序遍历非递归方法求二叉树叶子节点的个数，采用递归方法求节点总个数。求该二叉树的叶子节点的个数：树的叶子节点为树中没有孩子节点的节点，该二叉树中叶子节点为：CDF。将二叉树中的所有节点定义为根节点，如果节点既没有左孩子也没有右孩子则可以断定该节点为叶子节点，累加。其中先序遍历非递归的方法来判断节点是否为叶子节点。求二叉树的节点总数：求节点的总数采用的是递归的算法实现函数功能，二叉树中所有非空的节点的个数即为二叉树的节点总数。所以只需要从根节点开始判定节点是否为空，左孩子和右孩子均设定为根节点，采用的是递归的算法判断其是否为空，然后采用累加的方法就可以求出输入的二叉树中节点的总数。3.2、 进制转换设计算法利用栈类实现，因为栈存储的特点是前进后出。在本题当中，我们需要将第一次与转换的进制数相余得到的结果排放在剩余相余得到的结果的前面，所以我们应该用栈进行存放。3.3、链表在一个有序表中插入一个元素，使得该表仍然有序单链表的插入算法：按从小到大的顺序输入，当插入的数大于数组中的某一个数时，循环结束，这时发现指针q指向的是比输入的数要大的数据域中，所以必须设定一个指针p使得其保存工作指针q的上一个位置，这样保证循环结束的时候要插入的位置为比数e要大得的数前一个数的后面。将一个链表中的元素进行拆分，将所有奇数放到一个链表中，将所有的偶数放到另一个链表中。判定条件为：判定a[i]中存放的数为奇数还是偶数，判定条件为：如果a[i]与2取余，得到的数为1则说明a[i]为奇数，否则为偶数。开辟不同的链表空间，用不同的指针的数据域进行存储。将两个链表合并成一个链表。顺序输出数组中奇数，定义一个指针跟随着奇数的移动而移动到奇数结束，然后，将该指针的next域指向偶数的头指针的next域，然后一次输出偶数链表中偶数，通过此种方法就可以将奇数链表和偶数链表链接起来输出。将一个链表中的所有元素逆序存储并显示。元素要按逆序存储，所以在设计算法时，只需要将数组中的最后一个数存放到单链表中的第一个位置，输出。就可以完成逆序存储的效果。4、详细设计4.1二叉树实现的程序设计/*递归实现前序遍历*/template<classT>voidBiTree<T>::PreOrder(BiNode<T>*root)(if(root==NULL)return;else(cout<<root->data<<"";PreOrder(root->lchild);PreOrder(root->rchild);}/*求二叉树叶子节点的个数(先序遍历非递归)*/；template<classT>intBiTree<T>::CountLeaf(BiNode<T>*root)(SeqStack<BiNode<T>*>S;BiNode<T>*x;intn=0;if(root)S.Push(root);while(!S.Empty())(x=S.Pop();if(!x->lchild&&!x->rchild)n++;if(x->rchild)S.Push(x->rchild);if(x->lchild)S.Push(x->lchild);}returnn;}/*求节点的总数*/template<classT>intBiTree<T>::Count(BiNode<T>*root)(if(!root)return0;elsereturnCount(root->lchild)+Count(root->rchild)+1;}4.2进制转换实现的程序设计voidSeqsteak::Push(inte)(if(top==Maxsize-1)throw"上溢〃；top++;inti;cout<<"输入要转化的进制数："<<"\n";cin>>i;cout<<"\n";while(e!=0)(data[top]=e%i;e=e/i;top++;}top二top-1;}intSeqsteak::pop()(if(top==-1)throw"下溢〃；inte;e=data[top--];returne;}4.3链表相关功能实现的程序设计〃实现长度为n的链表的构造函数，使用尾插法实现template<classT>LinkList<T>::LinkList(Ta[],intn)(inti;first=newNode<T>;//申请头结点；Node<T>*r,*e;//定义尾指针r,每个新结点er=first;for(i=0;i<n;i++)(e=newNode<T>;//为每个新结点申请空间e->data=a[i];r->next=e;r=e;//将指针p移动到新结点的位置}r->next=NULL;//循环结束后将最后一个元素即尾指针r的next域置为空〃逆序存储,尾插法Node<T>*l,*m;nixu=newNode<T>;l=nixu;for(i=n-1;i>=0;i--)(m=newNode<T>;m->data=a[i];l->next=m;l=m;}l->next=NULL;〃按奇数和偶数存储Node<T>*t,*s,*p;jishu=newNode<T>;oushu=newNode<T>;t=jishu;s=oushu;for(i=0;i<n;i++)(e=newNode<T>;p=newNode<T>;if(a[i]%2==1)(e->data=a[i];t->next=e;t=e;}else(p->data=a[i];s->next=p;s=p;}t->next=NULL;s->next=NULL;}}〃在链表中插入指定元素template<classT>voidLinkList<T>::Insert(Te)(Node<T>*s,*p,*q;//s为新插入元素结点，p为工作指针q=first;p=q;while(q&&e>q->data)(p=q;q=q->next;}s=newNode<T>;//给新元素结点申请空间s->data=e;s->next=p->next;//先将s指向p的下一个元素位置x即a[x-1]p->next=s;〃再将p指向新元素结点位置}

5、调试分析5.1二叉树实现的程序设计结果响C:\W5ndows\syste响C:\W5ndows\system32\cmd.exe输入一颗二叉树的前序遍历二riBCttttDttttEFttft#二叉树的煎序遍历加。BCDEF二叉变的叶子节点留个款加3二荟城B穗的个教泓&按任意铤继续---.5.25.2进制转换实现的程序设计结果5.35.3链表相关功能实现的程序设计结果函C:\Windows\system32\cmd.exe539_L5-L±.4>^中？表篆表蓄2429421i函C:\Windows\system32\cmd.exe539_L5-L±.4>^中？表篆表蓄2429421i152345223415295214522ii1251344523fr方果元-:>S8A•,兀剧苛餐插要-6、程序设计总结本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不会正确输出结果、不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善，并且给出正确答案。在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发