图-十字链表

奥普瓯江

原理：



备注：
        感谢“人造人”给与的帮助，并细心对代码予以的回复，在代码更改中使我对递归的应用打开了一个新的世界。

        “递归的循环和释放是可以分开使用的”

        十字链表是，一个类与两个链表的合理组合与链接，并使用链表尾插法使其排列，注意链表的头容易在逆邻接表数据载入时被替换，对指针的使用有待提高与练习



代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #define MAX 4
   
4. 
   
5. typedef struct list
   
6. {
   
7.     int taildata, headdata;
   
8.     struct list *headlink, *taillink;
   
9. }list,*lists;
   
10. 
    
11. typedef struct like
    
12. {
    
13.     char data[MAX][MAX];
    
14.     list *doin, *doout;
    
15. }like;
    
16. 
    
17. void loop_list (list **doin);
    
18. void prin_list (list *doout);
    
19. void print_list (list *doin);
    
20. //void free_list(list *l);              //“人造人”借鉴释放语句
    
21. void free_list(list *doout);
    
22. 
    
23. /*void free_list(list *l)
    
24. {
    
25.     if(!l) return;
    
26.     free_list(l->taillink);
    
27.     free(l);
    
28. }*/
    
29. 
    
30. void free_list(list *doout)
    
31. {
    
32.     if(doout != NULL)                   //“!doout”当doout不等于0时，doout为真，!doout就为假，递归结束条件
    
33.     {
    
34.         return;
    
35.     }
    
36.     free_list(doout->taillink);         //递归循环
    
37.     free(doout);                        //释放malloc申请的动态内存，当递归循环释放时执行该语句
    
38. 
    
39. }
    
40. 
    
41. void print_list (list *doin)
    
42. {
    
43.     while(doin != NULL)
    
44.     {
    
45.         printf("%d ", doin->taildata);
    
46.         printf("%d ", doin->headdata);
    
47.         doin = doin->headlink;
    
48.     }
    
49. }
    
50. 
    
51. void prin_list (list *doout)
    
52. {
    
53.     while(doout != NULL)
    
54.     {
    
55.         printf("%d ", doout->taildata);
    
56.         printf("%d ", doout->headdata);
    
57.         doout = doout->taillink;
    
58.     }
    
59. }
    
60. 
    
61. 
    
62. void loop_list (list **doout)
    
63. {
    
64.     list *temp, *tail;
    
65.     int tail_vex, head_vex;
    
66. 
    
67. 
    
68.     while(1)
    
69.     {
    
70.         scanf("%d", &tail_vex);
    
71.         scanf("%d", &head_vex);
    
72. 
    
73.         if(tail_vex >= 0 && tail_vex <= 9)          //输入9以上的数字结束本函数
    
74.         {
    
75.             temp = (lists )malloc(sizeof(list ));
    
76.             temp->taildata = tail_vex;
    
77.             temp->headdata = head_vex;
    
78.             temp->taillink = NULL;
    
79.             temp->headlink = NULL;
    
80. 
    
81.             if(*doout == NULL)
    
82.             {
    
83.                 *doout = temp;
    
84.             }
    
85.             else
    
86.             {
    
87.                 tail->taillink = temp;
    
88.             }
    
89.             tail = temp;
    
90.         }
    
91.         else
    
92.         {
    
93.             break;
    
94.         }
    
95.     }
    
96. }
    
97. int main()
    
98. {
    
99.     like diss[MAX];
    
100.     list*temp, *nice, *kiss;
     
101. 
     
102.     for(int i = 0; i < MAX; i++)
     
103.     {
     
104.         scanf("%s", &diss[i].data[0][0]);
     
105.         diss[i].doin = NULL;
     
106.         diss[i].doout = NULL;
     
107.         loop_list(&diss[i].doout);
     
108.     }
     
109. 
     
110.     for(int i = 0; i < MAX; i++)
     
111.     {
     
112.         temp = diss[i].doout;               //先把diss数组中的邻接表传给临时变量指针temp这样temp就能指向diss数组中的doout邻接表
     
113. 
     
114.         while(temp)                        //判断temp是否为空指针如果不是空指针就执行该循环
     
115.         {
     
116.             if(diss[temp->headdata].doin == NULL)       //判断temp->headdata数组中doin逆邻接表是否为空如果是空执行该判断
     
117.             {
     
118.                 diss[temp->headdata].doin = temp;
     
119.             }
     
120.             else
     
121.             {
     
122.                 nice = diss[temp->headdata].doin;           //生成一个逆邻接表的指针变量把有数据的temp->headdata数组传给变量
     
123. 
     
124.                 while(nice)                                 //循环变量nice直至他成为空，因为在生成邻接表的时候逆邻接表和邻接表的结尾我都赋予了NULL变量
     
125.                 {
     
126.                     kiss = nice;                            //把逆邻接表的前一个存在数据的逆邻接表的地址传给kiss指针，以便在循环结束时使用
     
127.                     nice = nice->headlink;
     
128.                 }
     
129.                 kiss->headlink = temp;                      //循环结束把temp地址插入上一个逆邻接表中
     
130. 
     
131.             }
     
132.             temp = temp->taillink;             //temp作为临时变量向diss数组储存的邻接表向后搜索
     
133.         }
     
134. 
     
135.    }
     
136. 
     
137.     for(int i = 0; i < MAX; i++)
     
138.     {
     
139. 
     
140.         printf("%s ", diss[i].data[0]);
     
141.         prin_list(diss[i].doout);
     
142.         putchar('\n');
     
143.     }
     
144. 
     
145.     putchar('\n');
     
146. 
     
147.     for(int i = 0; i < MAX; i++)
     
148.     {
     
149.         printf("%s ", diss[i].data[0]);
     
150.         print_list(diss[i].doin);
     
151.         putchar('\n');
     
152.     }
     
153. 
     
154.      for(int i = 0; i < MAX; i++)
     
155.     {
     
156.         free_list(diss[i].doout);
     
157.     }
     
158. 
     
159.     return 0;
     
160. }
     

复制代码