指针逆序

h-b-z-d-j-s-m

[img]%5Burl=https://imgse.com/i/z8I8XV%5D

                               
登录/注册后可看大图

[/url][/img]

1. typedef int datatype;
   
2. typedef struct node
   
3.         {
   
4.                 datatype data;
   
5.                 struct node *next;
   
6. }linklist;
   
7. 
   
8. INVERT(linklist *head)
   
9. {
   
10.         linklist *p,*q;
    
11.         p=head->next;
    
12.         if(p!=NULL)
    
13.         {
    
14.                 head->next=NULL;
    
15.                 do
    
16.                 {
    
17.                         q=p->next;
    
18.                         p->next=head->next;
    
19.                         head->next=p;
    
20.                         p=q;
    
21.                 }
    
22.                 while(p!=NULL);
    
23.         }
    
24. }
    

复制代码

这个逆序怎么实现的啊，没咋看懂

jackz007

1. void INVERT(linklist ** head)                // head 头结点指针肯定会被修改，所以，这里应该传入二级指针
   
2. {
   
3.         linklist * p , * q , * next ;
   
4.         for(p = * head , q = NULL ; p ;) {
   
5.                 next = p -> next             // 保存下一个节点信息，准备改变 p -> next 指针，
   
6.                 p -> next = q       ;        // 让 p -> next 指向上一个遍历的节点，如果是原来的头结点，那么，q = NULL，成为新的尾节点
   
7.                 q = p               ;        // 让 p 成为前一个节点，准备进入下一个节点
   
8.                 p = next            ;        // 进入下一个节点，如果是原来的尾节点，那么，p = NULL，q 就是新的头结点
   
9.         }
   
10.         * head = q                  ;        // 循环结束后，q 自然就是新的头结点，必须把新的头结点指针返回主程序
    
11. }

复制代码

        完整程序请参考此帖：https://fishc.com.cn/forum.php?m ... 095&pid=6058652

两手空空儿

小甲鱼老师的课后作业答案
这是代码

1. struct Node *reversed(struct Node *head)
   
2. {
   
3.         struct Node *pre;
   
4.         struct Node *cur;
   
5.    
   
6.         pre = NULL;
   
7.         cur = head;
   
8.         while(cur)
   
9.         {
   
10.                 struct Node *next = cur->next;
    
11.                 cur->next = pre;
    
12.                 pre = cur;
    
13.                 cur = next;
    
14.         }
    
15.    
    
16.         return pre;
    
17. }

复制代码

链接：
https://fishc.com.cn/forum.php?m ... peid%26typeid%3D570

人造人

最简单的方法，对链表逆序遍历，然后把每一个元素都添加到另一个新链表里面
这很简单，但是效率不高

1. sh-5.1$ ls
   
2. list.c        list.h        main.c
   
3. sh-5.1$ cat main.c
   
4. #include "list.h"
   
5. #include <stdio.h>
   
6. #include <stdint.h>
   
7. 
   
8. void output(const list_t *list) {
   
9.     for(size_t i = 0; i < list_size(list); ++i) {
   
10.         size_t temp; list_get(list, i, &temp, sizeof(temp));
    
11.         printf("%zu ", temp);
    
12.     }
    
13.     puts("");
    
14. }
    
15. 
    
16. list_t *list_reverse(const list_t *list, size_t elem_size) {
    
17.     list_t *result = list_init();
    
18.     for(size_t i = list_size(list) - 1; i != -1; --i) {
    
19.         uint8_t buff[elem_size];
    
20.         list_get(list, i, buff, elem_size);
    
21.         list_append(result, buff, elem_size);
    
22.     }
    
23.     return result;
    
24. }
    
25. 
    
26. int main(void) {
    
27.     list_t *list = list_init();
    
28.     for(size_t i = 1; i <= 10; ++i) {
    
29.         list_append(list, &i, sizeof(i));
    
30.     }
    
31.     list_t *lr = list_reverse(list, sizeof(size_t));
    
32.     output(list);
    
33.     output(lr);
    
34.     list_deinit(lr);
    
35.     list_deinit(list);
    
36.     return 0;
    
37. }
    
38. sh-5.1$ cat list.h
    
39. #ifndef _LIST_H_
    
40. #define _LIST_H_
    
41. 
    
42. #include <stddef.h>
    
43. #include <stdbool.h>
    
44. 
    
45. struct list_node_tag {
    
46.     void *data; size_t size;
    
47.     struct list_node_tag *next;
    
48. };
    
49. 
    
50. typedef struct {
    
51.     struct list_node_tag *head;
    
52.     size_t size;
    
53. } list_t;
    
54. 
    
55. list_t *list_init(void);
    
56. void list_deinit(list_t *list);
    
57. bool list_clean(list_t *list);
    
58. bool list_insert(list_t *list, size_t index, const void *data, size_t size);
    
59. bool list_delete(list_t *list, size_t index);
    
60. bool list_get(const list_t *list, size_t index, void *data, size_t size);
    
61. bool list_set(list_t *list, size_t index, const void *data, size_t size);
    
62. bool list_append(list_t *list, const void *data, size_t size);
    
63. size_t list_size(const list_t *list);
    
64. bool list_empty(const list_t *list);
    
65. 
    
66. #endif
    
67. sh-5.1$ cat list.c
    
68. #include "list.h"
    
69. #include <stdlib.h>
    
70. #include <memory.h>
    
71. 
    
72. list_t *list_init(void) {
    
73.     list_t *list = malloc(sizeof(*list));
    
74.     if(!list) return NULL;
    
75.     list->head = NULL;
    
76.     list->size = 0;
    
77.     return list;
    
78. }
    
79. 
    
80. void list_deinit(list_t *list) {
    
81.     if(!list) return;
    
82.     list_clean(list);
    
83.     free(list);
    
84. }
    
85. 
    
86. bool list_clean(list_t *list) {
    
87.     if(!list) return false;
    
88.     while(!list_empty(list)) if(!list_delete(list, 0)) return false;
    
89.     return true;
    
90. }
    
91. 
    
92. bool list_insert(list_t *list, size_t index, const void *data, size_t size) {
    
93.     if(!list) return false;
    
94.     if(list_size(list) < index) return false;
    
95.     if(!data) return false;
    
96.     struct list_node_tag **current = &list->head;
    
97.     while(index--) current = &(*current)->next;
    
98.     struct list_node_tag *node = malloc(sizeof(*node));
    
99.     if(!node) return false;
    
100.     node->data = malloc(size);
     
101.     if(!node->data) {free(node); return false;}
     
102.     memcpy(node->data, data, size);
     
103.     node->size = size;
     
104.     node->next = *current;
     
105.     *current = node;
     
106.     ++list->size;
     
107.     return true;
     
108. }
     
109. 
     
110. bool list_delete(list_t *list, size_t index) {
     
111.     if(!list) return false;
     
112.     if(list_size(list) <= index) return false;
     
113.     struct list_node_tag **current = &list->head;
     
114.     while(index--) current = &(*current)->next;
     
115.     struct list_node_tag *temp = *current;
     
116.     *current = temp->next;
     
117.     free(temp->data); free(temp);
     
118.     --list->size;
     
119.     return true;
     
120. }
     
121. 
     
122. bool list_get(const list_t *list, size_t index, void *data, size_t size) {
     
123.     if(!list) return false;
     
124.     if(list_size(list) <= index) return false;
     
125.     if(!data) return false;
     
126.     struct list_node_tag *const *current = &list->head;
     
127.     while(index--) current = &(*current)->next;
     
128.     struct list_node_tag *temp = *current;
     
129.     if(temp->size > size) return false;
     
130.     memcpy(data, temp->data, temp->size);
     
131.     return true;
     
132. }
     
133. 
     
134. bool list_set(list_t *list, size_t index, const void *data, size_t size) {
     
135.     bool res = list_delete(list, index);
     
136.     return res ? list_insert(list, index, data, size) : res;
     
137. }
     
138. 
     
139. bool list_append(list_t *list, const void *data, size_t size) {
     
140.     if(!list) return false;
     
141.     return list_insert(list, list_size(list), data, size);
     
142. }
     
143. 
     
144. size_t list_size(const list_t *list) {
     
145.     if(!list) return 0;
     
146.     return list->size;
     
147. }
     
148. 
     
149. bool list_empty(const list_t *list) {
     
150.     if(!list) return true;
     
151.     return list_size(list) == 0;
     
152. }
     
153. sh-5.1$ gcc -g -Wall -o main main.c list.c
     
154. sh-5.1$ ls
     
155. list.c        list.h        main  main.c
     
156. sh-5.1$ ./main
     
157. 1 2 3 4 5 6 7 8 9 10
     
158. 10 9 8 7 6 5 4 3 2 1
     
159. sh-5.1$
     

复制代码

人造人

这次用递归的方式逆序，效率也不高
其实我是想把逆序链表的函数写到list.c里面的，这样可以直接操作底层结构，效率更高，但是最终还是没有这样做，因为这违背了我写这个代码的初衷，我写这个代码的目的并不是为了效率
因为做了这样的尝试，所以list.c内部的逻辑也发生了有点大的变化，不过对外没有改变，外面是看不到这个变化的，这就是定义良好的接口带来的好处

1. sh-5.1$ ls
   
2. list.c        list.h        main.c
   
3. sh-5.1$ cat main.c
   
4. #include "list.h"
   
5. #include <stdio.h>
   
6. 
   
7. void output(const list_t *list, size_t index) {
   
8.     if(index >= list_size(list)) return;
   
9.     size_t temp; list_get(list, index, &temp, sizeof(temp));
   
10.     printf("%zu ", temp);
    
11.     output(list, index + 1);
    
12. }
    
13. 
    
14. list_t *list_reverse(const list_t *list, size_t index) {
    
15.     if(index >= list_size(list)) return list_init();
    
16.     list_t *result = list_reverse(list, index + 1);
    
17.     size_t temp; list_get(list, index, &temp, sizeof(temp));
    
18.     list_append(result, &temp, sizeof(temp));
    
19.     return result;
    
20. }
    
21. 
    
22. int main(void) {
    
23.     list_t *list = list_init();
    
24.     for(size_t i = 0; i < 10; ++i) {
    
25.         list_append(list, &i, sizeof(i));
    
26.     }
    
27.     list_t *lr = list_reverse(list, 0);
    
28.     output(list, 0); puts("");
    
29.     output(lr, 0); puts("");
    
30.     list_deinit(lr);
    
31.     list_deinit(list);
    
32.     return 0;
    
33. }
    
34. sh-5.1$ cat list.h
    
35. #ifndef _LIST_H_
    
36. #define _LIST_H_
    
37. 
    
38. #include <stddef.h>
    
39. #include <stdbool.h>
    
40. 
    
41. struct list_node_tag {
    
42.     void *data; size_t size;
    
43.     struct list_node_tag *next;
    
44. };
    
45. 
    
46. typedef struct {
    
47.     struct list_node_tag *head;
    
48.     size_t size;
    
49. } list_t;
    
50. 
    
51. list_t *list_init(void);
    
52. void list_deinit(list_t *list);
    
53. bool list_clean(list_t *list);
    
54. bool list_insert(list_t *list, size_t index, const void *data, size_t size);
    
55. bool list_delete(list_t *list, size_t index);
    
56. bool list_get(const list_t *list, size_t index, void *data, size_t size);
    
57. bool list_set(list_t *list, size_t index, const void *data, size_t size);
    
58. bool list_append(list_t *list, const void *data, size_t size);
    
59. size_t list_size(const list_t *list);
    
60. bool list_empty(const list_t *list);
    
61. 
    
62. #endif
    
63. sh-5.1$ cat list.c
    
64. #include "list.h"
    
65. #include <stdlib.h>
    
66. #include <string.h>
    
67. 
    
68. static struct list_node_tag *new_node(const void *data, size_t size) {
    
69.     struct list_node_tag *result = malloc(sizeof(*result));
    
70.     if(!result) return NULL;
    
71.     result->data = malloc(size);
    
72.     if(!result->data) {free(result); return NULL;}
    
73.     memcpy(result->data, data, size);
    
74.     result->size = size;
    
75.     result->next = NULL;
    
76.     return result;
    
77. }
    
78. 
    
79. static void free_node(struct list_node_tag *n) {
    
80.     free(n->data);
    
81.     free(n);
    
82. }
    
83. 
    
84. static struct list_node_tag *const *locate_node_const(const list_t *list, size_t index) {
    
85.     struct list_node_tag *const *result = &list->head;
    
86.     while(index--) result = &(*result)->next;
    
87.     return result;
    
88. }
    
89. 
    
90. static struct list_node_tag **locate_node(list_t *list, size_t index) {
    
91.     return (struct list_node_tag **)locate_node_const(list, index);
    
92. }
    
93. 
    
94. list_t *list_init(void) {
    
95.     list_t *list = malloc(sizeof(*list));
    
96.     if(!list) return NULL;
    
97.     list->head = NULL;
    
98.     list->size = 0;
    
99.     return list;
    
100. }
     
101. 
     
102. void list_deinit(list_t *list) {
     
103.     if(!list) return;
     
104.     list_clean(list);
     
105.     free(list);
     
106. }
     
107. 
     
108. bool list_clean(list_t *list) {
     
109.     if(!list) return false;
     
110.     while(!list_empty(list)) if(!list_delete(list, 0)) return false;
     
111.     return true;
     
112. }
     
113. 
     
114. bool list_insert(list_t *list, size_t index, const void *data, size_t size) {
     
115.     if(!list) return false;
     
116.     if(list_size(list) < index) return false;
     
117.     if(!data) return false;
     
118.     struct list_node_tag **current = locate_node(list, index);
     
119.     struct list_node_tag *node = new_node(data, size);
     
120.     if(!node) return false;
     
121.     node->next = *current;
     
122.     *current = node;
     
123.     ++list->size;
     
124.     return true;
     
125. }
     
126. 
     
127. bool list_delete(list_t *list, size_t index) {
     
128.     if(!list) return false;
     
129.     if(list_size(list) <= index) return false;
     
130.     struct list_node_tag **current = locate_node(list, index);
     
131.     struct list_node_tag *temp = *current;
     
132.     *current = temp->next;
     
133.     free_node(temp);
     
134.     --list->size;
     
135.     return true;
     
136. }
     
137. 
     
138. bool list_get(const list_t *list, size_t index, void *data, size_t size) {
     
139.     if(!list) return false;
     
140.     if(list_size(list) <= index) return false;
     
141.     if(!data) return false;
     
142.     struct list_node_tag *current = *locate_node_const(list, index);
     
143.     if(current->size > size) return false;
     
144.     memcpy(data, current->data, current->size);
     
145.     return true;
     
146. }
     
147. 
     
148. bool list_set(list_t *list, size_t index, const void *data, size_t size) {
     
149.     bool res = list_delete(list, index);
     
150.     return res ? list_insert(list, index, data, size) : res;
     
151. }
     
152. 
     
153. bool list_append(list_t *list, const void *data, size_t size) {
     
154.     if(!list) return false;
     
155.     return list_insert(list, list_size(list), data, size);
     
156. }
     
157. 
     
158. size_t list_size(const list_t *list) {
     
159.     if(!list) return 0;
     
160.     return list->size;
     
161. }
     
162. 
     
163. bool list_empty(const list_t *list) {
     
164.     if(!list) return true;
     
165.     return list_size(list) == 0;
     
166. }
     
167. sh-5.1$ gcc -g -Wall -o main main.c list.c
     
168. sh-5.1$ ./main
     
169. 0 1 2 3 4 5 6 7 8 9
     
170. 9 8 7 6 5 4 3 2 1 0
     
171. sh-5.1$
     

复制代码