01 线性表

首页 > 代码库 > 01 线性表

2024-09-08 07:02:34 217人阅读

一、线性表之顺序存储---顺序表

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 // 数据结构
  6 #define MAX 100
  7 typedef struct
  8 {
  9     int buf[MAX];
 10     int length;
 11 }seqList;
 12 
 13 // 创建一个顺序表，并初始化
 14 seqList *seqList_init(void)
 15 {
 16     seqList *list = (seqList *)malloc(sizeof(seqList));
 17 
 18     if (list == NULL)
 19     {
 20         return NULL; 
 21     }
 22 
 23     list->length = 0;
 24 
 25     return list;
 26 }
 27 
 28 // 在表尾添加一个数据
 29 int seqList_add(seqList *list, int data)
 30 {
 31     // 参数检查
 32     if (list == NULL || list->length >= MAX)
 33     {
 34         return -1; 
 35     }
 36 
 37     list->buf[list->length] = data;
 38     list->length++;
 39 
 40     return 0;
 41 }
 42 
 43 // 从表尾删除一个数据，并保存到data
 44 int seqList_del(seqList *list, int *data)
 45 {
 46     // 参数检查
 47    if (list == NULL || list->length == 0)
 48    {
 49         return -1;  
 50    }
 51 
 52    list->length--;
 53    *data = http://www.mamicode.com/list->buf[list->length];
 54 
 55     return 0;
 56 }
 57 
 58 // 在指定位置插入一个数据
 59 int seqList_insert_post(seqList *list, int post, int data)
 60 {
 61     // 参数检查
 62     if (list == NULL || list->length >= MAX)
 63     {
 64         return -1;
 65     }
 66 
 67     if (post <= 0 || post > list->length)
 68     {
 69         return -2;  
 70     }
 71 
 72     int i = 0;
 73 
 74     for (i = list->length; i >=post; i--)
 75     {
 76         list->buf[i] = list->buf[i-1]; 
 77     }
 78 
 79     list->buf[post-1] = data;
 80     list->length++;
 81 
 82     return 0;
 83 }
 84 
 85 // 删除指定位置数据
 86 int seqList_del_post(seqList *list, int post, int *data)
 87 {
 88     // 参数检查
 89     if (list == NULL || list->length == 0)
 90     {
 91         return -1; 
 92     }
 93 
 94     if (post <= 0 || post > list->length)
 95     {
 96         return -2; 
 97     }
 98 
 99     *data = http://www.mamicode.com/list->buf[post-1];
100 
101     int i = 0;
102 
103     for (i = post; i <= list->length-1; i++)
104     {
105         list->buf[i-1] = list->buf[i];
106     }
107 
108     list->length--;
109 
110     return 0;
111 }
112 
113 int seqList_printf(seqList *list)
114 {
115     // 参数检查
116     if (list == NULL || list->length == 0)
117     {
118         return -1; 
119     }
120 
121     int i = 0;
122 
123     for (i = 0; i < list->length; i++)
124     {
125         printf("%d-", list->buf[i]); 
126     }
127     printf("\n");
128 
129     return 0;
130 }
131 
132 int main(void)
133 {
134     int i = 0;
135     int data = http://www.mamicode.com/0;
136     seqList *list = NULL;
137 
138     list = seqList_init();
139 
140     for (i = 0; i < 10; i++)
141     {
142         seqList_add(list, i); 
143     }
144     
145     seqList_printf(list);
146 
147     seqList_del(list, &data);
148     printf("data:%d\n", data);
149 
150     seqList_printf(list);
151 
152     seqList_insert_post(list, 1, 10);
153 
154     seqList_printf(list);
155     
156     seqList_del_post(list, 1, &data);
157     printf("data:%d\n", data);
158 
159     seqList_printf(list);
160     return 0;
161 }

顺序表

二、线性表之链式存储---单链表

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 // 数据结构
  6 typedef struct node
  7 {
  8     int data;
  9     struct node *next;
 10 }linkList;
 11 
 12 // 创建单链表，并初始化
 13 linkList *linkList_init(void)
 14 {
 15     linkList *list = (linkList *)malloc(sizeof(linkList));
 16 
 17     if (list == NULL)
 18     {
 19         return NULL; 
 20     }
 21 
 22     list->next = NULL;
 23 
 24     return list;
 25 }
 26 
 27 // 添加到链表头
 28 int linkList_add_head(linkList *list, int data)
 29 {
 30     // 参数检查
 31     if (list == NULL)
 32     {
 33         return -1; 
 34     }
 35 
 36     linkList *node = (linkList *)malloc(sizeof(linkList));
 37     if (node == NULL)
 38     {
 39         return -2; 
 40     }
 41 
 42     node->data =http://www.mamicode.com/ data;
 43     node->next = list->next;
 44     list->next = node;
 45 
 46     return 0;
 47 }
 48 
 49 // 添加到链表尾 
 50 int linkList_add_tail(linkList *list, int data)
 51 {
 52     // 参数检查
 53     if (list == NULL)
 54     {
 55         return -1; 
 56     }
 57 
 58     linkList *node = (linkList *)malloc(sizeof(linkList));
 59     if (node == NULL)
 60     {
 61         return -2; 
 62     }
 63 
 64     node->data =http://www.mamicode.com/ data;
 65     node->next = NULL;
 66 
 67     // 找到最后一个节点
 68     linkList *tmp = NULL;
 69     for (tmp = list; tmp->next != NULL; tmp = tmp->next)
 70     {
 71         ;
 72     }
 73 
 74     tmp->next = node;
 75 
 76     return 0;
 77 }
 78 
 79 // 从头开始删除第一个节点，并保存到node中
 80 int linkList_del_head(linkList *list, linkList **node)
 81 {
 82     // 参数检查
 83     if (list == NULL || list->next == NULL)
 84     {
 85         return -1; 
 86     }
 87 
 88     *node = list->next;
 89 
 90     list->next = list->next->next;
 91 
 92     (*node)->next = NULL;
 93     return 0;
 94 }
 95 
 96 // 从尾部开始删除第一个节点，并保存到node中
 97 int linkList_del_tail(linkList *list, linkList **node)
 98 {
 99     // 参数检查
100     if (list == NULL || list->next == NULL)
101     {
102         return -1; 
103     }
104 
105     // 记录最后一个节点的前一个节点
106     linkList *tmp = NULL;
107     for (tmp = list; tmp->next->next != NULL; tmp = tmp->next)
108     {
109         ;
110     }
111 
112     *node = tmp->next;
113     (*node)->next = NULL;
114 
115     tmp->next = NULL;
116 
117     return 0;
118 }
119 
120 int linkList_printf(linkList *list)
121 {
122     // 参数检查
123     if (list == NULL || list->next == NULL)
124     {
125         return -1; 
126     }
127 
128     linkList *tmp = NULL;
129     for (tmp = list->next; tmp != NULL; tmp = tmp->next)
130     {
131         printf("%d-", tmp->data);
132     }
133     printf("\n");
134 
135     return 0;
136 }
137 
138 int linkList_destroy(linkList *list)
139 {
140     linkList *tmp = NULL;
141 
142     while (list != NULL)
143     {
144         tmp = list;
145         list = list->next;
146         free(tmp);
147         tmp = NULL;
148     }
149 
150     return 0;
151 }
152 
153 int main(void)
154 {
155     int i = 0;
156     linkList *list = NULL;
157     linkList *node = NULL;
158 
159     list = linkList_init();
160 
161     for (i = 0; i < 10; i++)
162     {
163         linkList_add_head(list, i); 
164     }
165 
166     linkList_printf(list);
167 
168     for (i = 0; i < 10; i++)
169     {
170         linkList_add_tail(list, i); 
171     }
172 
173     linkList_printf(list);
174 
175     linkList_del_head(list, &node);
176     printf("node:%d\n", node->data);
177     free(node);
178     node = NULL;
179 
180     linkList_printf(list);
181 
182     linkList_del_tail(list, &node);
183     printf("node:%d\n", node->data);
184     free(node);
185     node = NULL;
186 
187     linkList_printf(list);
188 
189     linkList_destroy(list);
190 
191     return 0;
192 }

单链表

三、单链表逆置

方法：

<1>断开第一个数据节点和第二个数据节点的链接

<2>将后面的节点通过头插法的思想插在头节点后面

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 // 数据结构
  6 typedef struct node
  7 {
  8     int data;
  9     struct node *next;
 10 }linkList;
 11 
 12 // 创建单链表，并初始化
 13 linkList *linkList_init(void)
 14 {
 15     linkList *list = (linkList *)malloc(sizeof(linkList));
 16 
 17     if (list == NULL)
 18     {
 19         return NULL; 
 20     }
 21 
 22     list->next = NULL;
 23 
 24     return list;
 25 }
 26 
 27 // 添加到链表头
 28 int linkList_add_head(linkList *list, int data)
 29 {
 30     // 参数检查
 31     if (list == NULL)
 32     {
 33         return -1; 
 34     }
 35 
 36     linkList *node = (linkList *)malloc(sizeof(linkList));
 37     if (node == NULL)
 38     {
 39         return -2; 
 40     }
 41 
 42     node->data =http://www.mamicode.com/ data;
 43     node->next = list->next;
 44     list->next = node;
 45 
 46     return 0;
 47 }
 48 
 49 // 添加到链表尾 
 50 int linkList_add_tail(linkList *list, int data)
 51 {
 52     // 参数检查
 53     if (list == NULL)
 54     {
 55         return -1; 
 56     }
 57 
 58     linkList *node = (linkList *)malloc(sizeof(linkList));
 59     if (node == NULL)
 60     {
 61         return -2; 
 62     }
 63 
 64     node->data =http://www.mamicode.com/ data;
 65     node->next = NULL;
 66 
 67     // 找到最后一个节点
 68     linkList *tmp = NULL;
 69     for (tmp = list; tmp->next != NULL; tmp = tmp->next)
 70     {
 71         ;
 72     }
 73 
 74     tmp->next = node;
 75 
 76     return 0;
 77 }
 78 
 79 // 从头开始删除第一个节点，并保存到node中
 80 int linkList_del_head(linkList *list, linkList **node)
 81 {
 82     // 参数检查
 83     if (list == NULL || list->next == NULL)
 84     {
 85         return -1; 
 86     }
 87 
 88     *node = list->next;
 89 
 90     list->next = list->next->next;
 91 
 92     (*node)->next = NULL;
 93     return 0;
 94 }
 95 
 96 // 从尾部开始删除第一个节点，并保存到node中
 97 int linkList_del_tail(linkList *list, linkList **node)
 98 {
 99     // 参数检查
100     if (list == NULL || list->next == NULL)
101     {
102         return -1; 
103     }
104 
105     // 记录最后一个节点的前一个节点
106     linkList *tmp = NULL;
107     for (tmp = list; tmp->next->next != NULL; tmp = tmp->next)
108     {
109         ;
110     }
111 
112     *node = tmp->next;
113     (*node)->next = NULL;
114 
115     tmp->next = NULL;
116 
117     return 0;
118 }
119 
120 int linkList_printf(linkList *list)
121 {
122     // 参数检查
123     if (list == NULL || list->next == NULL)
124     {
125         return -1; 
126     }
127 
128     linkList *tmp = NULL;
129     for (tmp = list->next; tmp != NULL; tmp = tmp->next)
130     {
131         printf("%d-", tmp->data);
132     }
133     printf("\n");
134 
135     return 0;
136 }
137 
138 int linkList_destroy(linkList *list)
139 {
140     linkList *tmp = NULL;
141 
142     while (list != NULL)
143     {
144         tmp = list;
145         list = list->next;
146         free(tmp);
147         tmp = NULL;
148     }
149 
150     return 0;
151 }
152 
153 int linkList_reverse(linkList *list)
154 {
155     linkList *current = NULL;
156     linkList *tmp = NULL;
157 
158     // 参数检查
159     if (list == NULL || list->next == NULL)
160     {
161         return -1; 
162     }
163 
164     // 保存第二个节点
165     // 将第一个节点和第二个节点断开
166     current = list->next->next;
167     list->next->next = NULL;
168 
169     while (current != NULL)
170     {
171         // 记录current的下一个节点
172         tmp = current->next; 
173 
174         // 头插法
175         current->next = list->next;
176         list->next = current;
177 
178         // 更新current
179         current = tmp;
180     }
181 
182 
183     return 0;
184 }
185 
186 int main(void)
187 {
188     int i = 0;
189     linkList *list = NULL;
190     linkList *node = NULL;
191 
192     list = linkList_init();
193 
194     for (i = 0; i < 10; i++)
195     {
196         linkList_add_head(list, i); 
197     }
198 
199     linkList_printf(list);
200 
201     linkList_reverse(list);
202 
203     linkList_printf(list);
204 
205     linkList_destroy(list);
206 
207     return 0;
208 }

逆置链表

01 线性表

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 01 线性表

01 线性表

一、线性表之顺序存储---顺序表

二、线性表之链式存储---单链表

三、单链表逆置

看完仍有疑问？有类似问题直接问程序猿