关于链表

w349695434051

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct _node{                                                                        //定义链表节点
   
5.         int value;                                                                                        //每个节点中包含两个元素 他存储的值value 还有便于检索的下标index
   
6.         int index;
   
7.         struct _node* next;
   
8. }Node;
   
9. 
   
10. typedef struct _list{                                                                        //定义链表
    
11.         int number;                                                                                        //每个链表包含number 代表他一共含有几个节点
    
12.         Node* head;                                                                                        //链表的头
    
13.         Node* tail;                                                                                        //链表的tail 指向链表最后一个节点 用来延长链表的
    
14. }List;
    
15. 
    
16. Node* list_add(List* list, int number);                                        //定义链表延长函数
    
17. int list_print(List *list);                                                                //链表输出节点的值的函数
    
18. Node* list_at(List* list, int index);                                        //根据下标定位节点的函数
    
19. Node* list_insert(List* list, int index, int number);        //再链表中插入结点的函数
    
20. int list_retrieval(List* list);                                                        //插入或者删除节点后 对链表节点重新排下标的函数
    
21. int list_delete(List* list, int index);                                        //输出链表结点的函数
    
22. Node* list_found(List* list, int number);                                //根据链表的值输出节点地址的函数
    
23. void list_free(List* list);                                                                //free链表的函数
    
24. 
    
25. Node* list_add(List* list, int number)
    
26. {
    
27.         Node* p = (Node*)malloc(sizeof(Node));
    
28.         p -> value = number;
    
29.         p -> next = NULL;
    
30.         if(list -> head)                                                                        //判断链表是否为空链表
    
31.         {                                                                                               
    
32.                 list -> tail -> next = p;                                                //不是的话让指向最后一个节点的tail的next指向新定义的节点
    
33.                 p -> index = list -> tail -> index + 1;                        //他的下标就是最后节点下标加一
    
34.                 list -> number++;                                                                //链表节点数量加一
    
35.         }else                                                                                                       
    
36.         {                                                                                                        //链表是空链表
    
37.                 list -> head = p;                                                                //链表头指向新定义的节点
    
38.                 p -> index = 0;                                                                        //下标为零
    
39.                 list -> number = 1;                                                                //节点数量初始化为一
    
40.         }
    
41.         list -> tail = p;                                                                        //最后让tail指向新定义的节点 作为链表最后一个节点
    
42. }
    
43. 
    
44. int list_print(List *list)
    
45. {
    
46.         int ret = 0;
    
47.         if(list -> head)                                                                        //打印函数 如果为空链表不调用函数返回值为零
    
48.         {
    
49.                 ret = 1;
    
50.                 Node *p = NULL;
    
51.                 for(p = list -> head; p; p = p -> next)
    
52.                 {
    
53.                         printf("%d", p -> value);
    
54.                         if(p -> next)                                                                //链表除了最后一个节点都打印一个tab
    
55.                                 printf("\t");
    
56.                 }
    
57.                 printf("\n");
    
58.         }
    
59.         return ret;
    
60. }
    
61. 
    
62. Node* list_at(List* list, int index)
    
63. {
    
64.         Node* p = NULL;
    
65.         if(index < list -> number && index >= 0)                        //输入有效下表进入函数 否则返回零地址
    
66.                 for(p = list -> head; p; p = p -> next)
    
67.                         if(p -> index == index)
    
68.                                 break;
    
69.         return p;
    
70. }
    
71. 
    
72. Node* list_insert(List* list, int index, int number)        //链表插入函数
    
73. {
    
74.         Node* p = NULL;
    
75.        
    
76.         if(index <= list -> number && index >= 0)                        //判断述如下表是否有效
    
77.         {
    
78.                 p = (Node*)malloc(sizeof(Node));
    
79.                 p -> value = number;
    
80.                 p -> next = NULL;
    
81.                
    
82.                 if(index <= list -> number && index)                        //当插入的位置 不为第一个时
    
83.                         list_at(list, index - 1) -> next = p;                //调用取址函数让插入的前一个节点指向新插入的节点
    
84.                 else if(index == 0)                                                                //当插入位置 为第一个时
    
85.                         list -> head = p;                                                        //链表头指向新节点
    
86.                        
    
87.                 if(index == list -> number)                                                //当插入位置为最后一个 相当于延长了一个节点
    
88.                         p -> next = NULL;                                                        //新节点next指向null
    
89.                 else
    
90.                         p -> next = list_at(list, index);                        //否则的话 next指向被插入的节点
    
91.                        
    
92.                 list_retrieval(list);                                                        //调用排序函数对链表下标在排序
    
93.         }
    
94. }
    
95. 
    
96. int list_retrieval(List* list)
    
97. {
    
98.         int ret = 0;
    
99.         int reindex = 0;
    
100.         Node* rep = NULL;
     
101.         if(list -> head)
     
102.         {
     
103.                 ret = 1;
     
104.                 for(rep = list -> head; rep ！= NULL; rep = rep -> next)                //重点就是这个排序函数 进到for循环之后就死循环了 但我看着也没有问题啊 ！！
     
105.                 {
     
106.                         int a;
     
107.                         rep -> index = reindex++;
     
108.                 }
     
109.         }
     
110.         return ret;
     
111. }
     
112. 
     
113. int list_delete(List* list, int index)                                                //节点删除函数
     
114. {
     
115.         int ret = 0;
     
116.         if(list -> head && list -> number > index && index >= 0)        //如果链表为空链表并且下标无效的话不调用函数
     
117.         {
     
118.                 ret = 1;
     
119.                 Node* p = NULL;
     
120.                 if(index > 0)                                                                                //删除的节点不是第一个节点
     
121.                         list_at(list, index - 1) -> next =  list_at(list, index)-> next;        //调用取址函数
     
122.                 else
     
123.                         list -> head = list_at(list, index) -> next;        //删除的是第一个节点
     
124.                 free(p);
     
125.                 list_retrieval(list);                                                                                //对删除之后的链表下标排序
     
126.         }
     
127.         return ret;
     
128. }
     
129. 
     
130. Node* list_found(List* list, int number)                                        //根据链表的值输出节点地址的函数
     
131. {
     
132.         Node* p = NULL;
     
133.         for(p = list -> head; p; p = p -> next)
     
134.                 if(p -> value == number)
     
135.                         break;
     
136.         return p;
     
137. }
     
138. 
     
139. void list_free(List* list)                                                                        //free链表的函数
     
140. {
     
141.         Node* p = list -> head;
     
142.         Node* q = NULL;
     
143.         while(p)
     
144.         {
     
145.                 q = p -> next;
     
146.                 free(p);
     
147.                 p = q;
     
148.         }
     
149. }
     
150. 
     
151. int main()
     
152. {
     
153.         List list;
     
154.         list.head = NULL;
     
155.         list.tail = NULL;
     
156.        
     
157.         list_add(&list, 1);
     
158.         list_add(&list, 2);
     
159.         list_add(&list, 3);
     
160.        
     
161.         list_print(&list);
     
162.        
     
163.         list_insert(&list, 0, 4);
     
164.         list_insert(&list, 4, 5);
     
165.        
     
166.         list_delete(&list, 0);
     
167.         list_print(&list);
     
168.         list_delete(&list, 1);
     
169.         list_print(&list);
     
170.         list_delete(&list, 0);
     
171.         list_print(&list);
     
172.        
     
173.         list_print(&list);
     
174.        
     
175.         list_free(&list);
     
176.        
     
177.         return 0;
     
178. }

复制代码

调用insert函数还有delete函数
进入retrieval的for语句就死循环了
链表这几天刚学的
求大佬指点一下
有别的问题也劳烦修改一下

isdkz

问题出在list_retrieval函数中的for循环中，循环条件应该是 rep != NULL 而不是 rep 。修改后的代码如下：

1. int list_retrieval(List* list)
   
2. {
   
3.     int ret = 0;
   
4.     int reindex = 0;
   
5.     Node* rep = NULL;
   
6.     if(list -> head)
   
7.     {
   
8.         ret = 1;
   
9.         for(rep = list -> head; rep != NULL; rep = rep -> next)
   
10.         {
    
11.             rep -> index = reindex++;
    
12.         }
    
13.     }
    
14.     return ret;
    
15. }
    

复制代码

此外，list_insert函数中的 p -> next == NULL 应该修改为 p -> next = NULL ，list_delete函数中的 list_retrieval; 应该修改为 list_retrieval(list); 。

修改后的代码如下：

1. Node* list_insert(List* list, int index, int number)
   
2. {
   
3.     Node* p = NULL;
   
4.    
   
5.     if(index <= list -> number && index >= 0)
   
6.     {
   
7.         p = (Node*)malloc(sizeof(Node));
   
8.         p -> value = number;
   
9.         p -> next = NULL;
   
10.         
    
11.         if(index <= list -> number && index)
    
12.             list_at(list, index - 1) -> next = p;
    
13.         else if(index == 0)
    
14.             list -> head = p;
    
15.         
    
16.         if(index == list -> number)
    
17.             p -> next = NULL;
    
18.         else
    
19.             p -> next = list_at(list, index);
    
20.         
    
21.         list_retrieval(list);
    
22.     }
    
23. }
    
24. 
    
25. int list_delete(List* list, int index)
    
26. {
    
27.     int ret = 0;
    
28.     if(list -> head && list -> number > index && index >= 0)
    
29.     {
    
30.         ret = 1;
    
31.         Node* p = NULL;
    
32.         if(index > 0)
    
33.             list_at(list, index - 1) -> next = list_at(list, index)-> next;
    
34.         else
    
35.             list -> head = list_at(list, index) -> next;
    
36.         
    
37.         free(p);
    
38.         list_retrieval(list);
    
39.     }
    
40.     return ret;
    
41. }
    

复制代码

修改后的代码应该可以正常运行了。

w349695434051

isdkz 发表于 2023-10-25 16:35
问题出在list_retrieval函数中的for循环中，循环条件应该是 rep != NULL 而不是 rep 。修改后的代码如下：
...

其他两处错已经改了
但改成 ！=NULL 以后还是死循环

yinda_peng

w349695434051 发表于 2023-10-25 17:04
其他两处错已经改了
但改成 ！=NULL 以后还是死循环

他是脚本GPT回答，你这里rep和rep!=NULL就是一样的……我没有仔细看（没有那么多时间），只注意了你的list_retrieval函数，逻辑上说应该没有问题，有可能你的链表初始化或者在插入删除操作中没有注意最后一个要指向NULL，我建议你可以将其改写为while循环并且设置循环退出条件为rep == NULL来测试一下是不是最后一个没有指向NULL的问题