线性表、检查是否有环、逐个、快慢指针

奥普瓯江

对不对就这么着了往下学（蒙圈中）

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. #define MAXSIZE 12
   
5. 
   
6. typedef struct Like
   
7. {
   
8.     int T;
   
9.     struct Like *next;
   
10. 
    
11. }Like, *Likes;
    
12. 
    
13. void Explain();     //程序说明
    
14. void InitList(Likes *E);    //初始化程序创建头节点
    
15. void HeadList(Likes *E);    //头插法创建链表（无环）
    
16. void TailList(Likes *E);    //尾插法创建链表（有环）
    
17. void AbFiList(Like *E);    //逐个查找链表中是否有环
    
18. void AaFiList(Like *E);     //快慢指针查找链表中是否有环
    
19. 
    
20. void AaFiList(Like *E)      //快慢指针查找链表中是否有环
    
21. {
    
22.     Like *temp = E->next, *temps = E->next;
    
23. 
    
24.     while(temp != NULL && temps != NULL )
    
25.     {
    
26. 
    
27.         temp = temp->next;
    
28.         temps = temps->next->next;
    
29.         printf("%d<->%d\n", temp->T, temps->T);
    
30. 
    
31.         if(temp == temps)
    
32.         {
    
33.                 return;
    
34.         }
    
35.     }
    
36. }
    
37. 
    
38. void AbFiList(Like *E)      //逐个查找链表中是否有环
    
39. {
    
40.     Like *temp = E->next->next, *temps;
    
41. 
    
42.     while(temp != NULL)
    
43.     {
    
44.         temps = temp;
    
45.         do
    
46.         {
    
47.             temps = temps->next;
    
48.             if(temps == temp)
    
49.             {
    
50.                 printf("已找到环其存在与%d\n", temp->T);
    
51.                 return;
    
52.             }
    
53. 
    
54.         }while(temps != NULL || temps != E->next);
    
55.         temp = temp->next;
    
56.     }
    
57.     if(temp == NULL)
    
58.     {
    
59.         printf("本链表是个无环链表\n");
    
60.     }
    
61. }
    
62. 
    
63. 
    
64. void TailList(Likes *E)     //尾插法创建链表（有环）
    
65. {
    
66.     Like *temp, *tail;
    
67. 
    
68.     srand((unsigned)time(NULL));
    
69. 
    
70.     for(int i = 0; i < MAXSIZE; i++)
    
71.     {
    
72.         temp = (Likes )malloc(sizeof(Like ));
    
73.         temp->T = (rand() % 100);
    
74.         temp->next = (*E)->next;
    
75. 
    
76.         if((*E)->next == *E)
    
77.         {
    
78.             (*E)->next = temp;
    
79.         }
    
80.         else
    
81.         {
    
82.             tail->next = temp;
    
83.         }
    
84.         tail = temp;
    
85.     }
    
86.     (*E)->next = tail;
    
87. 
    
88.    temp = (*E)->next->next;
    
89.     printf("尾插法：");
    
90.     do
    
91.     {
    
92.         printf("<%d>", temp->T);
    
93.         temp = temp->next;
    
94.     }while(temp != (*E)->next->next);
    
95.     putchar('\n');
    
96. 
    
97.     tail->next = tail->next->next->next;
    
98. 
    
99. 
    
100. }
     
101. 
     
102. void HeadList(Likes *E)              //头插法创建链表（无环）
     
103. {
     
104.     Like *temp;
     
105.     srand((unsigned)time(NULL));
     
106. 
     
107.     for(int i = 0; i < MAXSIZE; i++)
     
108.     {
     
109.         temp = (Likes )malloc(sizeof(Like ));
     
110.         temp->T = (rand() % 100);
     
111. 
     
112.         if((*E)->next == *E)
     
113.         {
     
114.             (*E)->next = temp;
     
115.             temp->next = NULL;
     
116. 
     
117.         }
     
118.         else
     
119.         {
     
120.             temp->next = (*E)->next;
     
121.             (*E)->next = temp;
     
122.         }
     
123.     }
     
124. 
     
125.     temp = (*E)->next;
     
126.      printf("头插法：");
     
127.     do
     
128.     {
     
129.         printf("<%d>", temp->T);
     
130.         temp = temp->next;
     
131. 
     
132.     }while(temp != NULL);
     
133.      putchar('\n');
     
134. 
     
135. }
     
136. void InitList(Likes *E)                  //初始化程序创建头节点
     
137. 
     
138. {
     
139.     Like *temp, *temps;
     
140. 
     
141.     if(*E != NULL)
     
142.     {
     
143.         temp = (*E)->next;
     
144.         do
     
145.         {
     
146.             temps = temp;
     
147.             temp = temp->next;
     
148.             if(temp == NULL)
     
149.             {
     
150.                 break;
     
151.             }
     
152.             free(temps);
     
153.         }while((*E)->next != temp);     //放在这里  temp ！= NULL 编译会出现错误所以在temp=temp->next下面加上了一个if语句
     
154.     }
     
155.     else
     
156.     {
     
157.         *E = (Likes )malloc(sizeof(Like ));
     
158.     }
     
159.     (*E)->next = *E;
     
160. 
     
161. }
     
162. 
     
163. void Explain()                              //程序说明
     
164. {
     
165.     printf("1、初始化程序创建头节点\n");
     
166.     printf("2、创建头插法无环链表\n");
     
167.     printf("3、创建尾插法有环链表\n");
     
168.     printf("4、逐个查找链表中是否有环\n");
     
169.     printf("5、快慢指针查找链表中是否有环\n");
     
170.     printf("9、打印两个链表\n");
     
171.     printf("0、结束本程序\n");
     
172. 
     
173. }
     
174. 
     
175. 
     
176. int main()
     
177. {
     
178.     int i;
     
179.     Like *F = NULL;
     
180. 
     
181.     Explain();
     
182. 
     
183.     while(1)
     
184.     {
     
185.         printf("输入选项：");
     
186.         scanf("%d", &i);
     
187.         getchar();
     
188. 
     
189.         switch(i)
     
190.         {
     
191.             case 1:{
     
192.                 InitList(&F);
     
193.             }
     
194.             break;
     
195.              case 2:{
     
196.                 HeadList(&F);
     
197.             }
     
198.             break;
     
199.              case 3:{
     
200.                 TailList(&F);
     
201.             }
     
202.             break;
     
203.             case 4:{
     
204.                 AbFiList(F);
     
205.             }
     
206.             break;
     
207.             case 5:{
     
208.                 AaFiList(F);
     
209.             }
     
210.             break;
     
211.              case 0:{
     
212.                 return 0;
     
213.             }
     
214.             break;
     
215. 
     
216.             default :{
     
217.                 printf("你输入的选项不在可选范围内请仔细阅读说明\n");
     
218.             }
     
219.         }
     
220.     }
     
221. 
     
222. 
     
223. 
     
224.     return 0;
     
225. }
     

复制代码