| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 993 人关注过本帖
标题:是这个函数的问题吗Status NodeCountCSTree
取消只看楼主 加入收藏
yf879326915
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2017-4-12
收藏
 问题点数:0 回复次数:0 
是这个函数的问题吗Status NodeCountCSTree
#include<stdio.h>
#include<stdlib.h>
#define FLASE 0
#define OK 1
#define TRUE 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INT_SIZE 100  
#define STACKINCREMENT 10
typedef char ElemType;
typedef int Status;
typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
typedef CSTree SElemType;
typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;  
}SqStack;
typedef CSTree QElemType;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
int Nodenum=0;
int Count=0;

Status InitStack(SqStack &S) {
    S.base = (SElemType*) malloc(STACK_INT_SIZE*sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INT_SIZE;
    return OK;
}

Status StackEmpty(SqStack &S) {
     if(S.top == S.base) return TRUE;
     else return FLASE;
 }

Status GetTop(SqStack &S, SElemType&e) {
    if(S.top == S.base) return ERROR;
    e = *(S.top-1);
    return OK;
}


Status Push(SqStack &S, SElemType e) {
    if(S.top - S.base >= S.stacksize) {  
        S.base = (SElemType  *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        if(!S.base) exit (OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}

Status Pop(SqStack &S,SElemType &e) {
    if(S.base == S.top) return ERROR;
    e=*--S.top;
    return OK;
}


Status InitQueue(LinkQueue &Q)//队列函数
{
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;
    return OK;
}

Status QueueEmpty(LinkQueue &Q)
{
    if(Q.front==Q.rear) return TRUE;
    else return FLASE;
}

Status EnQueue(LinkQueue &Q,QElemType e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e;p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

Status DeQueue(LinkQueue Q,QElemType &e)
{
    QueuePtr p;
    if(Q.front==Q.rear) return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
    free(p);
    return OK;
}

Status CreateCSTree(CSTree &T){
    CSTree head, t, stack[100];
    char ch[50];
    int i=0, top=0;
    int flag=0;
    scanf("%s",ch);
    if(ch[i]=='#') T=NULL;
    else {
        if(!(T=(CSNode*)malloc(sizeof(CSNode)))) exit(OVERFLOW);
        T->data=ch[i]; T->firstchild=NULL; T->nextsibling=NULL;
        stack[top]=T; top++; i++; head=T;
        while(ch[i]!='\0'&&top!=0) {
            if(ch[i]=='#'&&flag==1) {
                top--; t=stack[top];
                while(top!=0&&stack[top-1]->nextsibling==t){
                    top--; t=stack[top];
            }
        }
        else if(ch[i]=='#'&&flag==0)
            flag=1;
        else {
            if(!(T=(CSNode*)malloc(sizeof(CSNode))))exit(OVERFLOW);
            T->data=ch[i]; T->firstchild=NULL; T->nextsibling=NULL;
            if(flag==0){
                stack[top-1]->firstchild=T; stack[top]=T; top++;
            }
            else {
                stack[top-1]->nextsibling=T;
                flag=0; stack[top]=T; top++;
            }
        }
        i++;
        }
        T=head;
        
    }return OK;
}

Status PreOrderTraverse(CSTree T)
{
    SqStack S;
    CSTree p;
    InitStack(S);
    p = T;
    while(p||!StackEmpty(S)) {
        if(p){
            printf("%s",p->data); Push(S,T);
            p=p->firstchild;
        }
        else {Pop(S,p);
              p=p->nextsibling;
        }
    }
    return OK;
}
   
Status PostOrderTraverse(CSTree T)
{
    SqStack S;
    CSTree p;
    InitStack(S);
    p=T;
    while(p||!StackEmpty(S)) {
        if(p) {Push(S,p); p=p->firstchild;}
        else {
            Pop(S,p);
            printf("%s",p->data);
            p=p->nextsibling;
        }
    }
    return OK;
}

Status LeavelOrderTraverse(CSTree T)
{
    CSTree p=NULL;
    LinkQueue Q;
    InitQueue(Q);
    if(T) EnQueue(Q,T);
    while(!QueueEmpty(Q)||p){
        if(!p) DeQueue(Q,p);
        printf("%c",p->data);
        if(p->firstchild) EnQueue(Q,p->firstchild);
        p=p->nextsibling;
    }
    return OK;
}

int CSTreeDepth1(CSTree T) {
    CSTree Q[100], p;
    int front=0, rear=0;
    int dep=0, MAXQSIZE=100;
    int num,Qlength;
    if(T==NULL) return 0;
    else {
        Q[rear]=T;
        rear=(rear+1)%MAXQSIZE;
        while(front!=rear) {
            ++dep;
            num=1;
            Qlength=(rear-front+MAXQSIZE)%MAXQSIZE;
            while(num<=Qlength) {
                num++;
                p=Q[front];
                front=(front+1)%MAXQSIZE;
                while(p!=NULL) {
                    if(p->firstchild) {Q[rear]=p->firstchild; rear=(rear+1);}
                        p=p->nextsibling;
                }
            }
        }
        return dep;
    }
}

int CSTreeDepth2(CSTree T) {         /* 非递归遍历求以孩子兄弟链表表示的树的深度 */
  CSTree Q[100], p;
  int front=0, rear=0;         /* front,rear是队列Q的队头队尾元素的指针 */
  int last, dep;                 /* last指向树中同层结点中最后一个结点,dep是树的深度 */
  if(T==NULL)  return 0;
  else {
    last = 0;
    dep = 1;
    Q[rear++] = T;
    while(front<=last && front!=rear) {
      p=Q[front++];   /* 队头出列 */         
      while(p!=NULL) {   /* 层次遍历 */
        if(p->firstchild) Q[rear++] = p->firstchild;   /* 第一个孩子入队 */
        p = p->nextsibling;   /* 同层兄弟指针后移 */
      }
      if(front>last) {     /* 本层结束,深度加1(初始深度为0)*/
        dep++; last = rear;    /* last再移到指向当前层最右一个结点 */
      }
    }
    return dep;
  }
} // CSTreeDepth2

Status NodeCountCSTree(CSTree T){
    CSTree p=NULL;
    LinkQueue Q;
    InitQueue(Q);
    if(T)EnQueue(Q,T);
    while(!QueueEmpty(Q)||p){
        if(!p)DeQueue(Q,p);
        Nodenum++;
        if(p->firstchild)EnQueue(Q,p->firstchild);
        p=p->nextsibling;
    }
    return OK;
}

Status LeafCountCSTree(CSTree T) {
    //输出树的叶子结点,并统计叶子结点个数
    CSTree s[100];       /* s是栈,栈中元素是树结点指针 */
    int top=0;
    while(T || top!=0)
    {
        if (T) {
            s[top++]=T; T=T->firstchild;   /* 沿左分支向下 */
        }  
        else {
            T=s[--top];
            if(T->firstchild==NULL) {
                printf("%c", T->data);
                Count++;      /* 叶子结点 */
            }
            T=T->nextsibling;
        }
    }
    return OK;
} // LeafCountCSTree

void main()
{
    CSTree T;
    printf("创建树,按先序次序输入数中的结点的值: \n");
    CreateCSTree(T);
    printf("树的深度为: %d\n",CSTreeDepth1(T));
    printf("树的深度为: %d\n",CSTreeDepth2(T));
    NodeCountCSTree(T);
    printf("输出树的结点个数 :%d\n",Nodenum);
    printf("先根遍历树,结果是: \n");
    PreOrderTraverse(T);
    printf("\n");
    printf("后根遍历树,结果是: \n");
    PostOrderTraverse(T);
    printf("\n");
    printf("层次遍历树,结果是: \n");
    if(!LeavelOrderTraverse(T)){
        printf("\n");
        printf("遍历出错! ");
    }
    printf("\n");
    LeafCountCSTree(T);
    printf("输出树的叶子节点数 :%d\n",Count);
    printf("\n");}




搜索更多相关主题的帖子: include 
2017-04-22 21:20
快速回复:是这个函数的问题吗Status NodeCountCSTree
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.037060 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved