数据结构族谱树自用

guhusf

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tree
{
        char data[20];
        tree* firstchild;
        tree* nextborther;
};
typedef tree* point;
struct queen
{
        point position[30];
        int first;
        int afterlast;
};
struct stack
{
        point position[30];
        int stacksize;
        int top;
};
void initstack(stack** s)
{
        (*s)->top=-1;
        (*s)->stacksize=30;
}
void push(stack* s,point p)
{
        s->top++;
        s->position[s->top]=p;
}
void printstack(stack* s)
{
        int i;
        for(i=0;i<=s->top;i++)
        {
                puts(s->position[i]->data);
        }
}
void pop(stack* s)
{
        s->top--;
}
void initqueen(queen* q)
{
        q->first=q->afterlast=0;
}
void insertqueen(queen* q,point p)
{
        q->position[q->afterlast]=p;
        q->afterlast++;
}
void getfirst(queen* q,point* p)
{
        *p=q->position[q->first];
}
void outqueen(queen* q)
{
        q->first++;
}
int queenempyt(queen* q)
{
        if(q->first==q->afterlast)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}
void gratetree(point* t)
{
        queen q;
        initqueen(&q);
        char father[20];
        char child[20];
        point p,p1,r;
        printf("please input father,child");
        gets(father);
        gets(child);
        while(strcmp(child,"#")!=0)
        {
                p=(point)malloc(sizeof(tree));
                p->firstchild=p->nextborther=NULL;
                strcpy(p->data,child);
                insertqueen(&q,p);
                if(strcmp(father,"#")==0)
                {
                        *t=p;
                }
                else
                {
                        getfirst(&q,&p1);
                        while(strcmp(p1->data,father)!=0)
                        {
                                outqueen(&q);
                                getfirst(&q,&p1);
                        }
                        if(p1->firstchild==NULL)
                        {
                                p1->firstchild=p;
                                r=p;
                        }
                        else
                        {
                                r->nextborther=p;
                                r=p;
                        }
                }
                printf("please input father,child");
            gets(father);
            gets(child);        
        }         
}
void search(point p,char goal[],point* P)
{
        if(strcmp(p->data,goal)==0)
        {
                puts(p->data);
                *P=p;
                printf("searchsuccessful,and position has been reserve\n");
                return ;
        }
        else
        {
                if(p->firstchild)search(p->firstchild,goal,P);
                if(p->nextborther)search(p->nextborther,goal,P);
        }
}
int insert(point p,char father[],char child[])
{
        point faposition=NULL;
        point q=NULL;
        int i=0;
        search(p,father,&faposition);
        if(faposition)
        {
                q=(point)malloc(sizeof(tree));
                strcpy(q->data,child);
                q->firstchild=q->nextborther=NULL;
                if(faposition->firstchild==NULL)
                {
                        faposition->firstchild=q;
                }
                else
                {
                        faposition=faposition->firstchild;
                        while(faposition->nextborther)
                        {
                                faposition=faposition->nextborther;
                        }
                        faposition->nextborther=q;
                }
                i=1;
        }
        return i;
}
int deletree(point p,char father[],char child[])
{
        void postree(point );
        void delet(point ,point );
        point a=NULL,b=NULL;
        if(strcmp(father,"#")==0)
   {
              postree(p);
              return 1;
   }
   else
   {
            search(p,father,&a);
            search(p,child,&b);
            if(a==NULL||b==NULL)
            { 
            printf("data wrong");
                return 0;        
            }
            else
            {
                    if(a->firstchild!=b)
                    {
                       a=a->firstchild;
                       while(a)
                       {
                               if(a->nextborther==b)break;
                               a=a->nextborther;
                       }
             }
            }
            delet(a,b);
            return 1;
   }
}
void delet(point a,point b)
{
        void postree(point );
        if(a->firstchild==b)
        {
                a->firstchild=b->nextborther;
                b->nextborther=NULL;
                postree(b);
        }
        else
        {
                a->nextborther=b->nextborther;
                b->nextborther=NULL;
                postree(b);        
        }
}
void postree(point p)
{
        if(p->firstchild)postree(p->firstchild);
        if(p->nextborther)postree(p->nextborther);
        free(p);
        p=NULL;
}
void printbyouru(point p,int level)
{
        int len,i,n,k;
        if(p)
        {
                len=strlen(p->data);
                for(i=0;i<level;i++)
                {
                        putchar(' ');
                }
                printf("%s",p->data);
                for(k=len;k<60;k++)
                {
                        putchar('-');
                }
                printf("\n");
                if(p->firstchild)printbyouru(p->firstchild,level+4);
            if(p->nextborther)        printbyouru(p->nextborther,level);
        }
}
void printleafrood(point p,stack* s)
{
        while(p)
        {
                push(s,p);
                if(p->firstchild==NULL)
                {
                        printstack(s);
                        printf("\n");
                }
                else
                {
                        printleafrood(p->firstchild,s);
                }
                pop(s);
                p=p->nextborther;
        }
} 
main()
{
        int choice;
        point root=NULL;
        lable:printf("choice function\n1.grate 2.search 3.insert 4.delete 5.print 6.printleafrood");
        scanf("%d",&choice);
        getchar();
        if(choice==1)
        {
                gratetree(&root);
                goto lable;
        }
        else if(choice==2)
        {
                char s[20];
                gets(s);
                point position;
                search(root,s,&position);
                goto lable;
        }
        else if(choice==3)
        {
                char fa[20];
                char ch[20];
                printf("input fa and ch\n");
                gets(fa);
                gets(ch);
                if(insert(root,fa,ch))
                {
                        printf("success");
                }
                else
                {
                        printf("fault");
                }
                goto lable;
        }
        else if(choice==4)
        {
                char fa[20];
                char ch[20];
                printf("input fa and ch\n");
                gets(fa);
                gets(ch);
                if(deletree(root,fa,ch))
                {
                        printf("success\n");
                }
                goto lable;
        }
        else if(choice==5)
        {
                printbyouru(root,0);
                goto lable;
        }
        else if(choice==6)
        {
                stack* s;
                initstack(&s);
                printleafrood(root,s);
                goto lable;
        }
        else 
        {
                exit(1);
        }
}