数据结构族谱树自用
本帖最后由 guhusf 于 2021-5-17 13:23 编辑#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tree
{
char data;
tree* firstchild;
tree* nextborther;
};
typedef tree* point;
struct queen
{
point position;
int first;
int afterlast;
};
struct stack
{
point position;
int stacksize;
int top;
};
void initstack(stack** s)
{
(*s)->top=-1;
(*s)->stacksize=30;
}
void push(stack* s,point p)
{
s->top++;
s->position=p;
}
void printstack(stack* s)
{
int i;
for(i=0;i<=s->top;i++)
{
puts(s->position->data);
}
}
void pop(stack* s)
{
s->top--;
}
void initqueen(queen* q)
{
q->first=q->afterlast=0;
}
void insertqueen(queen* q,point p)
{
q->position=p;
q->afterlast++;
}
void getfirst(queen* q,point* p)
{
*p=q->position;
}
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;
char child;
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;
gets(s);
point position;
search(root,s,&position);
goto lable;
}
else if(choice==3)
{
char fa;
char ch;
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;
char ch;
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);
}
}
页:
[1]