数据结构族谱树自用

guhusf

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. struct tree
   
5. {
   
6.         char data[20];
   
7.         tree* firstchild;
   
8.         tree* nextborther;
   
9. };
   
10. typedef tree* point;
    
11. struct queen
    
12. {
    
13.         point position[30];
    
14.         int first;
    
15.         int afterlast;
    
16. };
    
17. struct stack
    
18. {
    
19.         point position[30];
    
20.         int stacksize;
    
21.         int top;
    
22. };
    
23. void initstack(stack** s)
    
24. {
    
25.         (*s)->top=-1;
    
26.         (*s)->stacksize=30;
    
27. }
    
28. void push(stack* s,point p)
    
29. {
    
30.         s->top++;
    
31.         s->position[s->top]=p;
    
32. }
    
33. void printstack(stack* s)
    
34. {
    
35.         int i;
    
36.         for(i=0;i<=s->top;i++)
    
37.         {
    
38.                 puts(s->position[i]->data);
    
39.         }
    
40. }
    
41. void pop(stack* s)
    
42. {
    
43.         s->top--;
    
44. }
    
45. void initqueen(queen* q)
    
46. {
    
47.         q->first=q->afterlast=0;
    
48. }
    
49. void insertqueen(queen* q,point p)
    
50. {
    
51.         q->position[q->afterlast]=p;
    
52.         q->afterlast++;
    
53. }
    
54. void getfirst(queen* q,point* p)
    
55. {
    
56.         *p=q->position[q->first];
    
57. }
    
58. void outqueen(queen* q)
    
59. {
    
60.         q->first++;
    
61. }
    
62. int queenempyt(queen* q)
    
63. {
    
64.         if(q->first==q->afterlast)
    
65.         {
    
66.                 return 1;
    
67.         }
    
68.         else
    
69.         {
    
70.                 return 0;
    
71.         }
    
72. }
    
73. void gratetree(point* t)
    
74. {
    
75.         queen q;
    
76.         initqueen(&q);
    
77.         char father[20];
    
78.         char child[20];
    
79.         point p,p1,r;
    
80.         printf("please input father,child");
    
81.         gets(father);
    
82.         gets(child);
    
83.         while(strcmp(child,"#")!=0)
    
84.         {
    
85.                 p=(point)malloc(sizeof(tree));
    
86.                 p->firstchild=p->nextborther=NULL;
    
87.                 strcpy(p->data,child);
    
88.                 insertqueen(&q,p);
    
89.                 if(strcmp(father,"#")==0)
    
90.                 {
    
91.                         *t=p;
    
92.                 }
    
93.                 else
    
94.                 {
    
95.                         getfirst(&q,&p1);
    
96.                         while(strcmp(p1->data,father)!=0)
    
97.                         {
    
98.                                 outqueen(&q);
    
99.                                 getfirst(&q,&p1);
    
100.                         }
     
101.                         if(p1->firstchild==NULL)
     
102.                         {
     
103.                                 p1->firstchild=p;
     
104.                                 r=p;
     
105.                         }
     
106.                         else
     
107.                         {
     
108.                                 r->nextborther=p;
     
109.                                 r=p;
     
110.                         }
     
111.                 }
     
112.                 printf("please input father,child");
     
113.             gets(father);
     
114.             gets(child);       
     
115.         }        
     
116. }
     
117. void search(point p,char goal[],point* P)
     
118. {
     
119.         if(strcmp(p->data,goal)==0)
     
120.         {
     
121.                 puts(p->data);
     
122.                 *P=p;
     
123.                 printf("searchsuccessful,and position has been reserve\n");
     
124.                 return ;
     
125.         }
     
126.         else
     
127.         {
     
128.                 if(p->firstchild)search(p->firstchild,goal,P);
     
129.                 if(p->nextborther)search(p->nextborther,goal,P);
     
130.         }
     
131. }
     
132. int insert(point p,char father[],char child[])
     
133. {
     
134.         point faposition=NULL;
     
135.         point q=NULL;
     
136.         int i=0;
     
137.         search(p,father,&faposition);
     
138.         if(faposition)
     
139.         {
     
140.                 q=(point)malloc(sizeof(tree));
     
141.                 strcpy(q->data,child);
     
142.                 q->firstchild=q->nextborther=NULL;
     
143.                 if(faposition->firstchild==NULL)
     
144.                 {
     
145.                         faposition->firstchild=q;
     
146.                 }
     
147.                 else
     
148.                 {
     
149.                         faposition=faposition->firstchild;
     
150.                         while(faposition->nextborther)
     
151.                         {
     
152.                                 faposition=faposition->nextborther;
     
153.                         }
     
154.                         faposition->nextborther=q;
     
155.                 }
     
156.                 i=1;
     
157.         }
     
158.         return i;
     
159. }
     
160. int deletree(point p,char father[],char child[])
     
161. {
     
162.         void postree(point );
     
163.         void delet(point ,point );
     
164.         point a=NULL,b=NULL;
     
165.         if(strcmp(father,"#")==0)
     
166.    {
     
167.               postree(p);
     
168.               return 1;
     
169.    }
     
170.    else
     
171.    {
     
172.             search(p,father,&a);
     
173.             search(p,child,&b);
     
174.             if(a==NULL||b==NULL)
     
175.             {
     
176.            printf("data wrong");
     
177.                 return 0;       
     
178.            }
     
179.            else
     
180.            {
     
181.                     if(a->firstchild!=b)
     
182.                     {
     
183.                        a=a->firstchild;
     
184.                        while(a)
     
185.                        {
     
186.                                if(a->nextborther==b)break;
     
187.                                a=a->nextborther;
     
188.                        }
     
189.             }
     
190.             }
     
191.             delet(a,b);
     
192.             return 1;
     
193.    }
     
194. }
     
195. void delet(point a,point b)
     
196. {
     
197.         void postree(point );
     
198.         if(a->firstchild==b)
     
199.         {
     
200.                 a->firstchild=b->nextborther;
     
201.                 b->nextborther=NULL;
     
202.                 postree(b);
     
203.         }
     
204.         else
     
205.         {
     
206.                 a->nextborther=b->nextborther;
     
207.                 b->nextborther=NULL;
     
208.                 postree(b);       
     
209.         }
     
210. }
     
211. void postree(point p)
     
212. {
     
213.         if(p->firstchild)postree(p->firstchild);
     
214.         if(p->nextborther)postree(p->nextborther);
     
215.         free(p);
     
216.         p=NULL;
     
217. }
     
218. void printbyouru(point p,int level)
     
219. {
     
220.         int len,i,n,k;
     
221.         if(p)
     
222.         {
     
223.                 len=strlen(p->data);
     
224.                 for(i=0;i<level;i++)
     
225.                 {
     
226.                         putchar(' ');
     
227.                 }
     
228.                 printf("%s",p->data);
     
229.                 for(k=len;k<60;k++)
     
230.                 {
     
231.                         putchar('-');
     
232.                 }
     
233.                 printf("\n");
     
234.                 if(p->firstchild)printbyouru(p->firstchild,level+4);
     
235.             if(p->nextborther)        printbyouru(p->nextborther,level);
     
236.         }
     
237. }
     
238. void printleafrood(point p,stack* s)
     
239. {
     
240.         while(p)
     
241.         {
     
242.                 push(s,p);
     
243.                 if(p->firstchild==NULL)
     
244.                 {
     
245.                         printstack(s);
     
246.                         printf("\n");
     
247.                 }
     
248.                 else
     
249.                 {
     
250.                         printleafrood(p->firstchild,s);
     
251.                 }
     
252.                 pop(s);
     
253.                 p=p->nextborther;
     
254.         }
     
255. }
     
256. main()
     
257. {
     
258.         int choice;
     
259.         point root=NULL;
     
260.         lable:printf("choice function\n1.grate 2.search 3.insert 4.delete 5.print 6.printleafrood");
     
261.         scanf("%d",&choice);
     
262.         getchar();
     
263.         if(choice==1)
     
264.         {
     
265.                 gratetree(&root);
     
266.                 goto lable;
     
267.         }
     
268.         else if(choice==2)
     
269.         {
     
270.                 char s[20];
     
271.                 gets(s);
     
272.                 point position;
     
273.                 search(root,s,&position);
     
274.                 goto lable;
     
275.         }
     
276.         else if(choice==3)
     
277.         {
     
278.                 char fa[20];
     
279.                 char ch[20];
     
280.                 printf("input fa and ch\n");
     
281.                 gets(fa);
     
282.                 gets(ch);
     
283.                 if(insert(root,fa,ch))
     
284.                 {
     
285.                         printf("success");
     
286.                 }
     
287.                 else
     
288.                 {
     
289.                         printf("fault");
     
290.                 }
     
291.                 goto lable;
     
292.         }
     
293.         else if(choice==4)
     
294.         {
     
295.                 char fa[20];
     
296.                 char ch[20];
     
297.                 printf("input fa and ch\n");
     
298.                 gets(fa);
     
299.                 gets(ch);
     
300.                 if(deletree(root,fa,ch))
     
301.                 {
     
302.                         printf("success\n");
     
303.                 }
     
304.                 goto lable;
     
305.         }
     
306.         else if(choice==5)
     
307.         {
     
308.                 printbyouru(root,0);
     
309.                 goto lable;
     
310.         }
     
311.         else if(choice==6)
     
312.         {
     
313.                 stack* s;
     
314.                 initstack(&s);
     
315.                 printleafrood(root,s);
     
316.                 goto lable;
     
317.         }
     
318.         else
     
319.         {
     
320.                 exit(1);
     
321.         }
     
322. }

复制代码