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

《算法与数据结构》
课 程 设 计 报 告

学 号

姓 名

班 级
计算机
指导教师

河海大学文天学院

2014年6 月

课题一：二叉树的各种算法
一、目的 
1、 掌握二叉树的所有算法 
2、 熟悉计算机英语和术语
3、会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解。
二、实习环境
个人计算机，Windows操作系统，Turbo C 2.0或 WinTC或Visual C++等编译开发环境
三、实习内容与步骤
内容
1、创建二叉树
2、用递归方法实现二叉树的各种遍历
步骤
开始——>用前序输入法构造一颗二叉树——>用中序输入法构造一颗二叉树——>用后序输入法构造一颗二叉树——>用非递归前序输入法构造一颗二叉树——>用非递归中序输入法构造一颗二叉树——>用非递归后序输入法构造一颗二叉树——>释放二叉树——>结束
四 、程序代码：
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100
typedef char DataType;
typedef struct bnode {
DataType data;
struct bnode *lchild, *rchild;
} Bnode, *BTree;
typedef struct {
BTree data[MAXSIZE];
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->data[S->top]=x;
return 1;
}
}
int Pop_SeqStack(PSeqStack S , BTree *x)
{
if (Empty_SeqStack ( S ) )
return 0;
else {
*x=S->data[S->top]; S->top--;
return 1;
}
}
int GetTop_SeqStack(PSeqStack S, BTree *x)
{
if ( Empty_SeqStack ( S ) ) return 0;
else {
*x= S->data[S->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 data[MAXSIZE];
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->data[Q->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->data[Q->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 S[MAXSIZE];
BTree1 Sq;
int top;BTree p=t;
top=-1;
while (p||top!=-1)
{
if (p)
{
Sq.flag=0; Sq.node=p;
top++; S[top]=Sq;
p=p->lchild;
}
else
{Sq=S[top],top--;
p=Sq.node;
if (Sq.flag==0)
{Sq.flag=1;
top++,S[top]=Sq;
p=p->rchild;
}
else
{
printf("%c",p->data);
p=NULL;
}
}
}
}
void LevelOrder(BTree t)
{
BTree queue[MAXSIZE];
int front,rear;
front=0,rear=0;
BTree p;
queue[rear++]=t;
while(front!=rear)
{
p=queue[front++];
printf("%c",p->data);
if(p->lchild!=NULL)
queue[rear++]=p->lchild;
if(p->rchild!=NULL)
queue[rear++]=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");
do
{printf("\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<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef 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(x>35||x<0||n<2);
while(x){
top=pushstack(top,x%n);
x/=n;
}
while(top!=NULL)
{
top=outstack(top,&x);
if(x<10)
printf("%c",x+'0');
else
printf("%c",x+'A'-10);
}
return 0;
}
2、程序运行结果如下：
十进制转换为二进制运行结果：

十进制转换为八进制运行结果：

十进制转换为十六进制运行结果：

五、 知识点、难点及解决办法。
方法：一、不同的进位制数转化为十进制数：按权展开相加。
二、 十进制数化为不同进制数整数部分：除权取余；小数部分：乘权取整。
六、编程小结或体会。
1. 数据结构 是计算机类各专业的核心课程，也是其他诸多类专业的重要选修课。我通过学习这门课，可以为理解、应用和开发程序提供技术和方法支持，为后续课程的学习提供重要思想和方法基础。同时对于我的逻辑思维培养和程序设计思想体系的建立有着重要的影响。 
   2.在调试过程中，碰到诸多问题，比如定义表长过小，处理记录数量错误时程序的异常，记录冲突次数等等。处理这些问题异常麻烦，有时连续错误，摸不清头绪，在不断调试，询问老师,和同学探讨之后，终于解决，运行成功。