主题：求助高手，关于数据结构课程设计(C语言版)
wofy2008
[专家分：0] 发布于 2006-06-26 14:16:00
求助高手，关于数据结构课程设计(C语言版)
1、猴子选大王
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能
2、建立二叉树，层序、先序遍历（ 用递归或非递归的方法都可以）**
任务：
要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；
请高手帮助，在此谢过了！
回复列表 （共3个回复）
沙发
中国台湾 [专家分：2140] 发布于 2006-06-26 18:10:00
#include<stdio.h>
#include<stdlib.h>
#define M 100
#define ERROR 0
#define FALSE 0
#define TURE 1
#define OK 1
typedef int status;
typedef struct Bitree
{
char data;
struct Bitree *lchild, *rchild;
}Bitree,*bitree;
typedef struct
{
bitree a[M];
int top ;
}stack;
status InitStack(stack *s)//初始化栈
{
s->top = 0;
return OK;
}
status PushStack(stack *s,bitree *T)//进栈操作
{
if (s->top > 100)
{
return ERROR;
}
s->a[++s->top] = (*T);
return OK;
}
status PopStack (stack *s, bitree *T)//出栈操作
{
if ( s->top == 0)
{
return ERROR;
}
(*T) = s->a[s->top--];
return OK;
}
status EmptyStack(const stack *s)//判断是否为空
{
if ( s->top == 0)
{
return TURE;
}
else
{
return FALSE;
}
}
status CreatBitree(bitree *T)//建树
{
char ch;
printf("请输入字符:");
scanf("%c",&ch);
getchar();
printf("\n");
if ( ch == ' ')
{
(*T) = NULL;
return 0;
}
else
{
(*T) = (bitree)malloc(sizeof(Bitree));
if(*T==NULL)
{
printf("memory allocation failed ,Goodbye");
exit(1);
}
(*T)->data = ch;
CreatBitree(&(*T)->lchild);
CreatBitree(&(*T)->rchild);
}
return OK;
}
status PreOrderTraverse( bitree *T)//前序遍历
{
stack s;
InitStack(&s);
while ((*T) != NULL || !EmptyStack(&s))
{
while (*T)
{
printf("%c",(*T)->data);
PushStack(&s,&(*T));
(*T) = (*T)->lchild;
}
if (!EmptyStack(&s))
{
PopStack(&s,&(*T));
(*T) = (*T)->rchild;
}
}
return OK;
}
status InorderTraverse( bitree *T)//中序遍历
{
stack s;
InitStack(&s);
while((*T) != NULL || !EmptyStack(&s))
{
while (*T)
{
PushStack(&s,&(*T));
(*T) = (*T)->lchild;
}
if (!EmptyStack(&s))
{
PopStack(&s,&(*T));
printf("%c",(*T)->data);
(*T) = (*T)->rchild;
}
}
return OK;
}
status BefororderTraverse(bitree *T)//后序遍历
{
int flag = 0;
stack s;
InitStack(&s);
while((*T) != NULL || !EmptyStack(&s))
{
while (*T)
{
PushStack(&s,&(*T));
(*T) = (*T)->lchild;
flag = 0;
}
if (!EmptyStack(&s) && flag == 1)
{
printf("%c",(*T)->data);
}
if (!EmptyStack(&s))
{
PopStack(&s,&(*T));
(*T) = (*T)->rchild;
flag = 1;
}
}
return OK;
}
int main(void)
{
bitree T;
int select ;
CreatBitree(&T);
do
{
printf("1: 进行前序遍历\n");
printf("2: 进行中序遍历\n");
printf("3: 进行后序遍历\n");
printf("请选择:");
scanf("%d",&select);
}while( select < 1 || select > 4);
switch(select)
{
case 1:
printf("前序遍历:");
PreOrderTraverse(&T);
printf("\n");
break;
case 2:
printf("\n中序遍历");
InorderTraverse(&T);
printf("\n");
break;
case 3:
printf("\n后序遍历");
BefororderTraverse(&T);
printf("\n");
default:
break;
}
system("pause");
return 0;
}
板凳
中国台湾 [专家分：2140] 发布于 2006-06-26 18:11:00
typedef struct bitnode//定义一个2叉数
{
char data;
struct bitnode *lchild ,*rchild;
}bitnode ,*bitree;
int CreatBitree(bitree *T)//建立一个2叉树
{
char ch;
printf("请输入字符:");
scanf("%c",&ch);
getchar();//吃掉残留的数据
if ( ch ==' ')
{
(*T)=NULL;
return 0;
}
else
{
(*T) = (bitree)malloc(sizeof(bitnode));
if((*T) == NULL)
{
printf("memory allocation failed,goodbye");
exit(1);
}
(*T)->data=ch;
CreatBitree(&(*T)->lchild);
CreatBitree(&(*T)->rchild);
}
return OK;
}
void PreOrderTraverse1(bitree T)// 前序遍历递归形式
{
if(T)
{
printf("%c",T->data);
PreOrderTraverse1((*T).lchild);
PreOrderTraverse1((*T).rchild);
}
}
void PreOrderTraverse2(bitree T)// 前序遍历非递归形式
{
int top = 0;
bitree a[M];
while (T!=NULL||top!=0)
{
while ( T!=NULL)
{
printf("%c",T->data);
a[++top] = T;
T = T->lchild;
}
if(top > 0)
{
T = a[top--];
T = T->rchild;
}
}
}
void InOrderTraverse1(bitree T)//中序递归形式访问
{
if(T)
{
InOrderTraverse1(T->lchild);
printf("%c",T->data);
InOrderTraverse1(T->rchild);
}
}
void InOrderTraverse2(bitree T)//中序非递归形式
{
int top = 0;
bitree s[M];
while(T!=NULL||top!=0)
{
while(T!=NULL)
{
s[++top] = T;
T = T->lchild;
}
if (top>0)
{
T = s[top--];
printf("%c",T->data);
T = T->rchild;
}
}
}
void BerforOrderTraverse1(bitree T)//后序递归形式
{
if(T)
{
BerforOrderTraverse1((*T).lchild);
BerforOrderTraverse1((*T).rchild);
printf("%c",T->data);
}
}
void BerforOrderTraverse2(bitree t) //
{
typedef struct node
{
bitree t;
int tag;
} stack;
stack s[100] ;
int top=0;
while (t!=NULL|| top!=0)
{
while (t!=NULL)
{
s[++top].t=t;
s[top].tag=0;
t=t->lchild;
}
while (top!=0 && s[top].tag==1)
{
printf("%c" ,s[top--].t->data);
}
if (top)
{
s[top].tag=1;
t = s[top].t->rchild ;
}
}
}
3 楼
wofy2008 [专家分：0] 发布于 2006-06-26 19:03:00
非常感谢大家！
猴子问题如果解决了
也请发给偶参考
谢谢
我来回复
您所在位置：