算法于数据结构 河海大学文天学院.doc

算法与数据结构课 程 设 计 报 告学 号 姓 名 班 级计算机指导教师河海大学文天学院2014年6 月 课题一：二叉树的各种算法一、目的1、 掌握二叉树的所有算法2、 熟悉计算机英语和术语3、会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解。二、实习环境个人计算机，Windows操作系统，Turbo C 2.0或 WinTC或Visual C+等编译开发环境三、实习内容与步骤内容1、创建二叉树2、用递归方法实现二叉树的各种遍历步骤开始用前序输入法构造一颗二叉树用中序输入法构造一颗二叉树用后序输入法构造一颗二叉树用非递归前序输入法构造一颗二叉树用非递归中序输入法构造一颗二叉树用非递归后序输入法构造一颗二叉树释放二叉树结束四 、程序代码：#include stdio.h#include stdlib.h#define MAXSIZE 100typedef char DataType; typedef struct bnode DataType data; struct bnode *lchild, *rchild; Bnode, *BTree;typedef struct BTree dataMAXSIZE;int top;SeqStack, *PSeqStack;PSeqStack Init_SeqStack() PSeqStack S; S=(PSeqStack)malloc(sizeof(SeqStack); if (S) S-top=-1; return S;int Empty_SeqStack(PSeqStack S) if (S-top=-1) return 1; else return 0; int Push_SeqStack (PSeqStack S,BTree x) if (S-top=MAXSIZE-1) return 0; else S-top+; S-dataS-top=x; return 1; int Pop_SeqStack(PSeqStack S , BTree *x) if (Empty_SeqStack ( S ) ) return 0; else *x=S-dataS-top; S-top-; return 1; int GetTop_SeqStack(PSeqStack S, BTree *x) if ( Empty_SeqStack ( S ) ) return 0; else *x= S-dataS-top; return (1); BTree CreateBinTree() char ch; BTree t; ch=getchar(); if (ch=#) t=NULL; else t=(BTree)malloc(sizeof(Bnode); t-data=ch; t-lchild=CreateBinTree(); t-rchild=CreateBinTree(); return t;#define MAXSIZE 100 typedef struct BTree dataMAXSIZE; int front, rear; SeqQueue,*PSeqQueue;PSeqQueue Init_SeqQueue( ) PSeqQueue Q; Q=( PSeqQueue )malloc(sizeof(SeqQueue); if (Q) Q-front=0; Q-rear=0; return Q;int Empty_SeqQueue(PSeqQueue Q) if (Q & Q-front=Q-rear) return (1); else return (0); int In_SeqQueue ( PSeqQueue Q , BTree x) if (Q-rear+1)%MAXSIZE=Q-front) printf(对满); return -1; else Q-rear=(Q-rear+1) % MAXSIZE; Q-dataQ-rear=x; return 1; int Out_SeqQueue (PSeqQueue Q,BTree *x) if (Empty_SeqQueue(Q) printf(对空); return -1; else Q-front=(Q-front+1) % MAXSIZE; *x=Q-dataQ-front; return 1; int Front_SeqQueue(PSeqQueue Q ,BTree *x) if (Q-front=Q-rear) printf(对空); return -1; else *x=Q-data(Q-front+1)% MAXSIZE; return 1; void PreOrder (BTree t) if (t) printf(%c,t-data); PreOrder( t-lchild ); PreOrder( t-rchild ); void InOrder (BTree t) if (t) InOrder( t-lchild ); printf(%c,t-data); InOrder( t-rchild ); void PostOrder (BTree t) if (t) PostOrder( t-lchild ); PostOrder( t-rchild ); printf(%c,t-data); void PreOrder1 (BTree t) PSeqStack S; BTree p=t; S=Init_SeqStack( ); while (p|!Empty_SeqStack (S) if (p) printf(%c,p-data); Push_SeqStack (S, p); p=p-lchild; else Pop_SeqStack (S,&p ); p=p-rchild; void InOrder1(BTree t) PSeqStack S; BTree p=t; S=Init_SeqStack( ); while (p|!Empty_SeqStack (S) if (p) Push_SeqStack (S, p); p=p-lchild; else Pop_SeqStack (S,&p ); printf(%c,p-data); p=p-rchild; typedef struct Bnode *node; int flag;BTree1; void PostOrder1(BTree t) BTree1 SMAXSIZE; BTree1 Sq;int top;BTree p=t;top=-1;while (p|top!=-1) if (p) Sq.flag=0; Sq.node=p;top+; Stop=Sq; p=p-lchild;elseSq=Stop,top-; p=Sq.node; if (Sq.flag=0) Sq.flag=1; top+,Stop=Sq; p=p-rchild; else printf(%c,p-data); p=NULL; void LevelOrder(BTree t)BTree queueMAXSIZE;int front,rear;front=0,rear=0;BTree p;queuerear+=t;while(front!=rear)p=queuefront+;printf(%c,p-data);if(p-lchild!=NULL)queuerear+=p-lchild;if(p-rchild!=NULL)queuerear+=p-rchild;void main()BTree t; int i=11;printf(创建一个二叉树n);t=CreateBinTree();PreOrder(t);printf(1-递归先序遍历n);printf(2-递归中序遍历n);printf(3-递归后序遍历n);printf(4-非递归先序遍历n);printf(5-非递归中序遍历n);printf(6-非递归后序遍历n);doprintf(n请选择:n);scanf(%d,&i);switch(i)case 1: PreOrder(t);break; case 2: InOrder(t);break; case 3: PostOrder(t);break; case 4: PreOrder1(t);break; case 5: InOrder1(t);break; case 6: PostOrder1(t);break;while(i);运行结果五、知识点、难点及解决办法。知识点：二叉树的定义，先序，中序，后序的遍历通过递归和非递归的方法实现，以及层次遍历二叉树的方法。难点：使用非递归的方法实现二叉树的后序遍历。解决方法：跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。 课题二：十进制转换为其他进制数一、目的1.学习并掌握各进制之间的转换二、实习环境个人计算机，Windows操作系统，Turbo C 2.0或 WinTC或Visual C+等编译开发环境三、实习内容与步骤1、十进制转换为二进制2、十进制转换为八进制3、十进制转换为十六进制四、程序及运行结果1、程序代码：#include#include#includetypedef int INT;typedef struct dd INT data; struct dd *next; LNode,*LStack;LStack pushstack(LStack top,int x) LStack p; p=(LStack)malloc(sizeof(LNode); if(x)!=-1) p-data=(x); p-next=top; top=p; return top; LStack outstack(LStack top,int *x) LStack p=top; *x=p-data; top=p-next; free(p); return top; main() int x,n; LStack top=NULL; printf(请输入十进制数及要转换的进制：); do scanf(%d%d,&x,&n); while(x35|x0|n2); while(x) top=pushstack(top,x%n); x/=n; while(top!=NULL) top=outstack(top,&x); if(x10) printf(%c,x+0); else printf(%c,x+A-10); return 0; 2、程序运行结果如下：十进制转换为二进制运行结果：十进制转换为八进制运行结果：十进制转换为十六进制运行结果：5、 知识点、难点及解决办法。方法：一、不同的进位制数转化为十进制数：按权展开相加。2、 十进制数化为不同进制数整数部分：