Chapter 3(线性表)-LMLPHP

1.单链表
//单链表代码,手打纯手工

//***********************************link.h***********************************
#ifndef LINK_H
#define LINK_H #include <stdbool.h>
#include <stdio.h>
#include <stdlib.h> typedef int datatype; typedef struct link
{
datatype data;
struct link *next; }Node,*Link; //创建单链表
Link linkCreate(); //获得链表长度
size_t length(Link link); //判断链表是否为空
bool isEmpty(Link link); //获得第i个前的地址
Node *addressFront(Link link,size_t i); //获取第i个节点的值
datatype getElement(Link link,size_t i); //查找元素num是否存在
bool isExist(Link link,datatype num); //插入元素
bool insert(Link link,size_t i,datatype num); //在链表头插入元素
bool pushFront(Link link,datatype num); //在链表尾插入元素
bool pushBack(Link link,datatype num); //删除第i个元素
bool deleteI(Link link,size_t i); //删除包含元素num的第一个节点
bool deleteNum(Link link,datatype num); //遍历打印整个链表
void travel(Link link); //清空链表
bool clear(Link link); //销毁链表
bool destroy(Link link); //链表翻转
bool reverse(Link link); //链表指定长度反转
void reverseN(Link link,int n); #endif //LINK_H //*************************link.c****************************************
#include "link.h" //创建单链表头
Link linkCreate()
{
Node *p = (Node *)malloc(sizeof(Node));
p->next = NULL;
return p;
} //获得链表长度
size_t length(Link link)
{
size_t count = 0;
Node *node = link->next;
while(node)
{
count++;
node = node->next;
}
return count;
} //判断链表是否为空
bool isEmpty(Link link)
{
if(NULL == link->next)return true;
return false;
} //获得第i个前的地址,供内部使用
Node *addressFront(Link link,size_t i)
{
if(NULL == link)return NULL;//头节点为空,返回NULL if(i > (length(link)+1))return NULL;//i越界,len+1是可取的,相当于最后加上这个数,i不能为0.返回于NULL if(isEmpty(link))return link;//当链表为空时,返回头节点地址 Node *pre = link; //保存前一个节点的地址
Node *curr = link->next;
for(size_t j = 1;j < i;j++)
{
pre = curr;
curr = curr->next;
} return pre;
} //获取第i个节点的值
datatype getElement(Link link,size_t i)
{
Node *node = addressFront(link,i);
return node->next->data;
} //查找元素num是否存在
bool isExist(Link link,datatype num)
{
if(NULL == link)return false; Node *node = link->next; while(node)
{
if(num == node->data)return true;
node = node->next;
}
return false;
} //插入元素
bool insert(Link link,size_t i,datatype num)
{
if(NULL == link)return false;
if(i > (length(link)+1)||i <= 0)return false; Node *pre = addressFront(link,i);//获得第i-1个节点的地址
Node *node = (Node *)malloc(sizeof(Node));//申请内存存放新节点
Node *save = pre->next; //将原来的第i个节点的地址保存在save中 pre->next = node; //将原来的第i-1个节点指向新节点 node->data = num; //为新节点的数据域赋值
node->next = save;//将新节点指向原来的第i个节点 return true;
} //在链表头插入元素
bool pushFront(Link link,datatype num)
{
return insert(link,1,num);
} //在链表尾插入元素
bool pushBack(Link link,datatype num)
{
return insert(link,length(link)+1,num);
} //删除第i个元素
bool deleteI(Link link,size_t i)
{
if(NULL == link)return false;
if(i>length(link) || i<=0)return false; Node *pre = addressFront(link,i);
Node *node= pre->next; pre->next = node->next;
free(node);
node = NULL;
return true;
} //删除包含元素num的第一个节点
bool deleteNum(Link link,datatype num)
{
if(NULL == link)return false; Node *pre = link;
Node *curr = link->next;
while(curr)
{
if(num == curr->data)
{
pre->next = curr->next;
free(curr);
curr = NULL;
return true;
}
pre = curr;
curr= curr->next;
} return false;
} //遍历打印整个链表
void travel(Link link)
{
if(NULL == link)return; Node *node = link->next;
while(node)
{
printf("%d ",node->data);
node = node->next;
}
printf("\n");
} //清空链表
bool clear(Link link)
{
if(NULL == link)return false; Node *node = link->next;//从头节点开始释放 while(node)
{
Node *temp = node->next;//保存下一个节点的地址
free(node);//释放当前节点
node = temp;//将下一个节点地址赋给node
}
link->next = NULL;//头节点指向空 return true;
} //销毁链表
bool destroy(Link link)
{
if(NULL == link)return false; clear(link);
free(link);
link = NULL;
return true;
} //链表翻转
bool reverse(Link link)
{
if(NULL == link)return false; Node *pre = link->next;
Node *curr= pre->next; while(curr)
{
Node *temp = curr->next;//保存当前节点的下一个节点地址
curr->next = pre;//将当前节点指向上一个节点 pre = curr;//将上一个节点指向当前节点
curr= temp;//将当前节点指向喜爱一个节点
} link->next->next = NULL;//将原来第一个节点指向空
link->next = pre;//将头节点指向原来的最后一个节点
return true;
} //链表指定长度反转工具
void reverseTool(Node *prev,Node *curr,int num)
{
if(NULL == curr)return; Node *prevNode = curr;
Node *currNode = curr->next; int count = 1;
while(currNode)
{
Node *nextNode = currNode->next;
currNode->next = prevNode;
prevNode = currNode;
currNode = nextNode;
count++; if(num == count)
{
Node *temp = prev->next;
prev->next->next =currNode;
prev->next = prevNode;
reverseTool(temp,currNode,num);
return;
}
} prev->next->next = currNode;
prev->next = prevNode;
} //链表指定长度反转
void reverseN(Link link,int n)
{
Node *node = link->next;
reverseTool(link,node,n);
} //************************linkTest.c***************************************** #include "link.h" int main(int argc,char *argv[])
{
Link head = linkCreate();
travel(head);
insert(head,1,77);
travel(head);
insert(head,1,777);
travel(head);
insert(head,3,7777);
travel(head);
printf("length = %d\n",length(head)); pushFront(head,52);
travel(head);
printf("length = %d\n",length(head)); pushBack(head,00);
travel(head);
printf("length = %d\n",length(head)); //deleteNum(head,777);
//deleteI(head,2);
travel(head);
printf("length = %d\n",length(head)); printf("-----\n");
reverseN(head,2);
//clear(head);
travel(head);
return 0;
}
377
 
1
//单链表代码,手打纯手工
2
3
4
//***********************************link.h***********************************
5
#ifndef LINK_H
6
#define LINK_H
7
8
9
#include <stdbool.h>
10
#include <stdio.h>
11
#include <stdlib.h>
12
13
14
typedef int datatype;
15
16
typedef struct link
17
{
18
    datatype data;
19
    struct link *next;
20
21
22
}Node,*Link;
23
24
25
//创建单链表
26
Link linkCreate();
27
28
29
//获得链表长度
30
size_t length(Link link);
31
32
//判断链表是否为空
33
bool isEmpty(Link link);
34
35
//获得第i个前的地址
36
Node *addressFront(Link link,size_t i);
37
38
//获取第i个节点的值
39
datatype getElement(Link link,size_t i);
40
41
42
//查找元素num是否存在
43
bool isExist(Link link,datatype num);
44
45
//插入元素
46
bool insert(Link link,size_t i,datatype num);
47
48
//在链表头插入元素
49
bool pushFront(Link link,datatype num);
50
51
//在链表尾插入元素
52
bool pushBack(Link link,datatype num);
53
54
//删除第i个元素
55
bool deleteI(Link link,size_t i);
56
57
58
//删除包含元素num的第一个节点
59
bool deleteNum(Link link,datatype num);
60
61
//遍历打印整个链表
62
void travel(Link link);
63
64
//清空链表
65
bool clear(Link link);
66
67
//销毁链表
68
bool destroy(Link link);
69
70
//链表翻转
71
bool reverse(Link link);
72
73
//链表指定长度反转
74
void reverseN(Link link,int n);
75
76
77
78
79
#endif //LINK_H
80
81
82
83
//*************************link.c****************************************
84
#include "link.h"
85
86
87
88
89
//创建单链表头
90
Link linkCreate()
91
{
92
    Node *p = (Node *)malloc(sizeof(Node));
93
    p->next = NULL;
94
    return p;
95
}
96
97
98
//获得链表长度
99
size_t length(Link link)
100
{
101
    size_t count = 0;
102
    Node *node = link->next;
103
    while(node)
104
    {
105
        count++;
106
        node = node->next;
107
    }
108
    return count;
109
}
110
111
//判断链表是否为空
112
bool isEmpty(Link link)
113
{
114
    if(NULL == link->next)return true;
115
    return false;
116
}
117
118
119
//获得第i个前的地址,供内部使用
120
Node *addressFront(Link link,size_t i)
121
{
122
    if(NULL == link)return NULL;//头节点为空,返回NULL
123
    
124
    if(i > (length(link)+1))return NULL;//i越界,len+1是可取的,相当于最后加上这个数,i不能为0.返回于NULL
125
126
    if(isEmpty(link))return link;//当链表为空时,返回头节点地址
127
128
    Node *pre  = link; //保存前一个节点的地址
129
    Node *curr = link->next;
130
    for(size_t j = 1;j < i;j++)
131
    {
132
        pre  = curr;
133
        curr = curr->next; 
134
    }
135
136
    return pre;
137
}
138
139
//获取第i个节点的值
140
datatype getElement(Link link,size_t i)
141
{
142
    Node *node = addressFront(link,i);
143
    return node->next->data;
144
}
145
146
147
//查找元素num是否存在
148
bool isExist(Link link,datatype num)
149
{
150
    if(NULL == link)return false;
151
152
    Node *node = link->next;
153
    
154
    while(node)
155
    {
156
        if(num == node->data)return true;
157
        node = node->next;
158
    }
159
    return false;
160
}
161
162
//插入元素
163
bool insert(Link link,size_t i,datatype num)
164
{
165
    if(NULL == link)return false;
166
    if(i > (length(link)+1)||i <= 0)return false;
167
168
169
    Node *pre  = addressFront(link,i);//获得第i-1个节点的地址
170
    Node *node = (Node *)malloc(sizeof(Node));//申请内存存放新节点
171
    Node *save = pre->next; //将原来的第i个节点的地址保存在save中
172
    
173
    pre->next = node; //将原来的第i-1个节点指向新节点
174
175
    node->data = num; //为新节点的数据域赋值
176
    node->next = save;//将新节点指向原来的第i个节点
177
    
178
    return true;
179
}
180
181
//在链表头插入元素
182
bool pushFront(Link link,datatype num)
183
{
184
    return insert(link,1,num);
185
}
186
187
//在链表尾插入元素
188
bool pushBack(Link link,datatype num)
189
{
190
    return insert(link,length(link)+1,num);
191
}
192
193
//删除第i个元素
194
bool deleteI(Link link,size_t i)
195
{
196
    if(NULL == link)return false;
197
    if(i>length(link) || i<=0)return false;
198
199
200
    Node *pre = addressFront(link,i);
201
    Node *node= pre->next;
202
203
    pre->next = node->next;
204
    free(node);
205
    node = NULL;
206
    return true;
207
}
208
209
210
//删除包含元素num的第一个节点
211
bool deleteNum(Link link,datatype num)
212
{
213
    if(NULL == link)return false;
214
    
215
    Node *pre  = link;
216
    Node *curr = link->next;
217
    while(curr)
218
    {
219
        if(num == curr->data)
220
        {
221
            pre->next = curr->next;
222
            free(curr);
223
            curr = NULL;
224
            return true;
225
        }
226
        pre = curr;
227
        curr= curr->next;
228
    }
229
230
    return false;
231
}
232
233
//遍历打印整个链表
234
void travel(Link link)
235
{
236
    if(NULL == link)return;
237
238
    Node *node = link->next;
239
    while(node)
240
    {
241
        printf("%d ",node->data);
242
        node = node->next;
243
    }
244
    printf("\n");
245
}
246
247
//清空链表
248
bool clear(Link link)
249
{
250
    if(NULL == link)return false;
251
252
    Node *node = link->next;//从头节点开始释放
253
    
254
    while(node)
255
    {
256
        Node *temp = node->next;//保存下一个节点的地址
257
        free(node);//释放当前节点
258
        node = temp;//将下一个节点地址赋给node
259
    }
260
    link->next = NULL;//头节点指向空
261
262
    return true;
263
}
264
265
//销毁链表
266
bool destroy(Link link)
267
{
268
    if(NULL == link)return false;
269
270
    clear(link);
271
    free(link);
272
    link = NULL;
273
    return true;
274
}
275
276
277
//链表翻转
278
bool reverse(Link link)
279
{
280
    if(NULL == link)return false;
281
282
    Node *pre = link->next;
283
    Node *curr= pre->next;
284
285
    while(curr)
286
    {
287
        Node *temp = curr->next;//保存当前节点的下一个节点地址
288
        curr->next = pre;//将当前节点指向上一个节点
289
290
        pre = curr;//将上一个节点指向当前节点
291
        curr= temp;//将当前节点指向喜爱一个节点
292
    }
293
    
294
    link->next->next = NULL;//将原来第一个节点指向空
295
    link->next = pre;//将头节点指向原来的最后一个节点
296
    return true;
297
}
298
299
300
//链表指定长度反转工具
301
void reverseTool(Node *prev,Node *curr,int num)
302
{
303
    if(NULL == curr)return;
304
305
    Node *prevNode = curr;
306
    Node *currNode = curr->next;
307
308
    int count = 1;
309
    while(currNode)
310
    {
311
        Node *nextNode = currNode->next;
312
        currNode->next = prevNode;
313
        prevNode = currNode;
314
        currNode = nextNode;
315
        count++;
316
317
        if(num == count)
318
        {
319
            Node *temp = prev->next;
320
            prev->next->next =currNode;
321
            prev->next = prevNode;
322
            reverseTool(temp,currNode,num);
323
            return;
324
        }
325
    }
326
327
    prev->next->next = currNode;
328
    prev->next = prevNode;
329
}
330
331
//链表指定长度反转
332
void reverseN(Link link,int n)
333
{   
334
    Node *node = link->next;
335
    reverseTool(link,node,n);
336
}
337
338
339
340
//************************linkTest.c*****************************************
341
342
343
#include "link.h"
344
345
int main(int argc,char *argv[])
346
{
347
    Link head = linkCreate();
348
    travel(head);
349
    insert(head,1,77);
350
    travel(head);
351
    insert(head,1,777);
352
    travel(head);
353
    insert(head,3,7777);
354
    travel(head);
355
    printf("length = %d\n",length(head));
356
357
    pushFront(head,52);
358
    travel(head);
359
    printf("length = %d\n",length(head));
360
361
362
    pushBack(head,00);
363
    travel(head);
364
    printf("length = %d\n",length(head));
365
366
    //deleteNum(head,777);
367
    //deleteI(head,2);
368
    travel(head);
369
    printf("length = %d\n",length(head));
370
    
371
372
    printf("-----\n");
373
    reverseN(head,2);
374
    //clear(head);
375
    travel(head);
376
    return 0;
377
}

2.静态链表
//静态链表代码,纯手打

//********************static_link.h***********************
#ifndef STATIC_LINK_H
#define STATIC_LINK_H #include <stdio.h>
#include <stdbool.h>
#define MAXSIZE 1000 typedef int datatype; typedef struct Static_linklist
{
datatype data;
int curr;
}Node,static_link[MAXSIZE]; //初始化静态链表
bool InitList(static_link link); //获取链表长度
size_t length(static_link link); //Malloc_SLL若备用链表非空,则返回分配的节点下标,否则返回0
int Malloc_SLL(static_link link); //Free_SSL将下标为K的空闲节点回收到备用链表
void Free_SSL(static_link link,int k); //插入元素
bool insert(static_link link,int i,datatype num); //删除元素
bool Delete(static_link link,int i ); //判断链表是否为空
bool isEmpty(static_link link); //获取第i个对象的值
datatype getElement(static_link link,int i); //历遍整个链表
void travel(static_link link); #endif //STATIC_LINK_H //********************static_link.c***********************
#include "static_link.h" //初始化静态链表
bool InitList(static_link link)
{
if(NULL == link)return false;
for(int i = 0;i < MAXSIZE-1;i++)
{
link[i].curr = i+1;
}
link[MAXSIZE-1].curr = 0;
return true;
} //获取链表长度
size_t length(static_link link)
{
if(NULL == link)return false; size_t index = link[MAXSIZE-1].curr;
size_t count = 0; while(index)
{
count++;
index = link[index].curr;
} return count;
} //Malloc_SLL若备用链表非空,则返回分配的节点下标,否则返回0
int Malloc_SLL(static_link link)
{
if(0 == link[0].curr)return 0; int result = link[0].curr;
link[0].curr = link[link[0].curr].curr;
return result;
} //Free_SSL将下标为K的空闲节点回收到备用链表
void Free_SSL(static_link link,int k)
{
link[k].curr = link[0].curr;
link[0].curr = k;
} //插入元素
bool insert(static_link link,int i,datatype num)
{
if(i<1 || i > length(link)+1)return false; //当输入的i小于1或者比链表长度+1大,则非法。
int index = Malloc_SLL(link); if(index)
{
link[index].data = num; int index_front = MAXSIZE-1;
for(int j = 1;j < i;j++)
{
index_front = link[index_front].curr;
}
link[index].curr = link[index_front].curr;
link[index_front].curr = index;
return true;
}
return false;
} //删除元素
bool Delete(static_link link,int i )
{
if(i<1 || i > length(link))return false;
size_t index = MAXSIZE-1;
for(int j =1;j < i;j++)
{
index = link[index].curr;
}
size_t tmp = link[index].curr;
link[index].curr = link[tmp].curr;
Free_SSL(link,i);
return true;
} //判断链表是否为空
bool isEmpty(static_link link)
{
return !link[MAXSIZE-1].curr;
} //获取第i个对象的值
datatype getElement(static_link link,int i)
{
if(i<1 || i>length(link))return ~(1<<(sizeof(datatype)*8-1))+1;//这里由于函数的返回值是数据类型,因此不能返回false来报告输入错误,因此后面取了这个数据类型的最大值+1输出表示输入下标不合法 size_t index = link[MAXSIZE-1].curr;
for(size_t j = 1;j < i;j++)
{
index = link[index].curr;
}
return link[index].data;
} //历遍整个链表
void travel(static_link link)
{
size_t index = link[MAXSIZE-1].curr;
while(index)
{
printf("%d ",link[index].data);
index = link[index].curr;
}
printf("\n");
} //********************static_linkTest.c***********************
#include "static_link.h" int main() { Node arr[MAXSIZE]; InitList(arr); printf("isEmpty: %d \n",isEmpty(arr)); travel(arr); insert(arr,1,77); insert(arr,2,25); printf("isEmpty: %d \n",isEmpty(arr)); travel(arr); //Delete(arr,2); //travel(arr); //printf("isEmpty: %d \n",isEmpty(arr)); printf("arr[2]:%d \n",getElement(arr,2)); printf("arr[3]:%d \n",getElement(arr,3)); return 0; }
220
 
1
//静态链表代码,纯手打
2
3
//********************static_link.h***********************
4
#ifndef STATIC_LINK_H
5
#define STATIC_LINK_H
6
7
#include <stdio.h>
8
#include <stdbool.h>
9
#define MAXSIZE 1000
10
11
typedef int datatype;
12
13
14
typedef struct Static_linklist
15
{
16
    datatype data;
17
    int curr;
18
}Node,static_link[MAXSIZE];
19
20
21
//初始化静态链表
22
bool InitList(static_link link);
23
24
25
26
//获取链表长度
27
size_t length(static_link link);
28
29
//Malloc_SLL若备用链表非空,则返回分配的节点下标,否则返回0
30
int Malloc_SLL(static_link link);
31
32
//Free_SSL将下标为K的空闲节点回收到备用链表
33
void Free_SSL(static_link link,int k);
34
35
//插入元素
36
bool insert(static_link link,int i,datatype num);
37
38
//删除元素
39
bool Delete(static_link link,int i );
40
41
//判断链表是否为空
42
bool isEmpty(static_link link);
43
44
//获取第i个对象的值
45
datatype getElement(static_link link,int i);
46
47
48
//历遍整个链表
49
void travel(static_link link);
50
51
#endif //STATIC_LINK_H
52
53
54
55
//********************static_link.c***********************
56
#include "static_link.h"
57
58
59
//初始化静态链表
60
bool InitList(static_link link)
61
{
62
    if(NULL == link)return false;
63
    for(int i = 0;i < MAXSIZE-1;i++)
64
    {
65
        link[i].curr = i+1;
66
    }
67
    link[MAXSIZE-1].curr = 0;
68
    return true;
69
}
70
71
72
73
//获取链表长度
74
size_t length(static_link link)
75
{
76
    if(NULL == link)return false;
77
78
    size_t index = link[MAXSIZE-1].curr;
79
    size_t count = 0;
80
    
81
    while(index)
82
    {
83
        count++;
84
        index = link[index].curr;
85
    }
86
87
    return count;
88
}
89
90
//Malloc_SLL若备用链表非空,则返回分配的节点下标,否则返回0
91
int Malloc_SLL(static_link link)
92
{
93
    if(0 == link[0].curr)return 0;
94
95
    int result = link[0].curr;
96
    link[0].curr = link[link[0].curr].curr;
97
    return result;
98
}
99
100
//Free_SSL将下标为K的空闲节点回收到备用链表
101
void Free_SSL(static_link link,int k)
102
{
103
    link[k].curr = link[0].curr;
104
    link[0].curr = k;
105
}
106
107
//插入元素
108
bool insert(static_link link,int i,datatype num)
109
{
110
    if(i<1 || i > length(link)+1)return false; //当输入的i小于1或者比链表长度+1大,则非法。
111
    int index = Malloc_SLL(link);
112
113
    if(index)
114
    {
115
        link[index].data = num;
116
        
117
        int index_front = MAXSIZE-1;
118
        for(int j = 1;j < i;j++)
119
        {
120
            index_front = link[index_front].curr;
121
        }
122
        link[index].curr = link[index_front].curr;
123
        link[index_front].curr = index;
124
        return true;
125
    }
126
    return false;
127
}
128
129
//删除元素
130
bool Delete(static_link link,int i )
131
{
132
    if(i<1 || i > length(link))return false;
133
    size_t index = MAXSIZE-1;
134
    for(int j =1;j < i;j++)
135
    {
136
        index = link[index].curr;
137
    }
138
    size_t tmp = link[index].curr;
139
    link[index].curr = link[tmp].curr;
140
    Free_SSL(link,i);
141
    return true;
142
}
143
144
//判断链表是否为空
145
bool isEmpty(static_link link)
146
{
147
    return !link[MAXSIZE-1].curr;
148
}
149
150
//获取第i个对象的值
151
datatype getElement(static_link link,int i)
152
{
153
    if(i<1 || i>length(link))return ~(1<<(sizeof(datatype)*8-1))+1;//这里由于函数的返回值是数据类型,因此不能返回false来报告输入错误,因此后面取了这个数据类型的最大值+1输出表示输入下标不合法
154
155
    size_t index = link[MAXSIZE-1].curr;
156
    for(size_t j = 1;j < i;j++)
157
    {
158
        index = link[index].curr;
159
    }
160
    return link[index].data;
161
}
162
163
//历遍整个链表
164
void travel(static_link link)
165
{
166
    size_t index = link[MAXSIZE-1].curr;
167
    while(index)
168
    {
169
        printf("%d ",link[index].data);
170
        index = link[index].curr;
171
    }
172
    printf("\n");
173
}
174
175
176
177
//********************static_linkTest.c***********************
178
#include "static_link.h"
179
180
181
182
183
184
int main()
185
186
{
187
188
    Node arr[MAXSIZE];
189
190
    InitList(arr);
191
192
    
193
194
    printf("isEmpty: %d \n",isEmpty(arr));
195
196
197
198
    travel(arr);
199
200
    insert(arr,1,77);
201
202
    insert(arr,2,25);
203
204
    printf("isEmpty: %d \n",isEmpty(arr));
205
206
    travel(arr);
207
208
    //Delete(arr,2);
209
210
    //travel(arr);
211
212
    //printf("isEmpty: %d \n",isEmpty(arr));
213
214
    printf("arr[2]:%d \n",getElement(arr,2));
215
216
    printf("arr[3]:%d \n",getElement(arr,3));
217
218
    return 0;
219
220
}


3.循环链表
//******************************circular_link.h**************************************
#ifndef CIRCULAR_LINK_H
#define CIRCULAR_LINK_H #include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype; typedef struct circular_link
{
datatype data;
struct circular_link *next;
}Node,*Link; //创建链表
Link create(); //获取链表长度
size_t length(Link link); //获取第i-1个节点的地址,工具函数内部使用
Node *addressTool(Link link,size_t i); //插入节点
bool insert(Link link,size_t i,datatype data); //删除节点
bool Delete(Link link,size_t i); //历遍节点
void travel(Link link); //判断节点是否为空
bool isEmpty(Link link); //获取第i个节点的数据
datatype getElement(Link link,size_t i); #endif //CIRCULAR_LINK_H //******************************circular_link.c**************************************
#include "circular_link.h" //创建链表 创建失败返回NULL
Link create()
{
Link link = (Link)malloc(sizeof(Node));
link->next = link;
return link;
} //获取链表长度
size_t length(Link link)
{
if(NULL==link || NULL==link->next)return false; Node *node = link->next;
int count = 0;
while(node != link)
{
count++;
node = node->next;
} return count;
} //获取第i-1个节点的地址,工具函数内部使用
Node *addressTool(Link link,size_t i)
{
Node *node = link;
for(size_t j = 1;j < i;j++)
{
node = node->next;
}
return node;
} //插入节点
bool insert(Link link,size_t i,datatype data)
{
if(i<1 || i > length(link)+1)return false;
if(NULL == link)return false; Node *prev = addressTool(link,i);//获取第i-1个节点地址
Node *curr = prev->next;//获取第i个节点地址 Node *node = (Node *)malloc(sizeof(Node));//创建新节点
node->data = data; prev->next = node;
node->next = curr; return true;
} //删除节点
bool Delete(Link link,size_t i)
{
if(i<1 || i>length(link))return false;
if(NULL == link)return false; Node *prev = addressTool(link,i);
Node *curr = prev->next;
Node *temp = curr->next; prev->next = temp;
free(curr);
curr = NULL;
return true;
} //历遍节点
void travel(Link link)
{
Node *node = link->next;
while(node != link)
{
printf("%d ",node->data);
node = node->next;
}
printf("\n");
} //判断节点是否为空
bool isEmpty(Link link)
{
return link->next == link;
} //获取第i个节点的数据
datatype getElement(Link link,size_t i)
{
if(i<1 || i > length(link) || NULL == link)return !(1<<(sizeof(datatype)-1))+1; Node *node = link->next; for(size_t j = 1;j < i;j++)
{
node = node->next;
}
return node->data;
} //******************************circular_linkTest.c************************************** #include "circular_link.h" int main() { Link head = create(); printf("isEmpty: %d \n",isEmpty(head)); printf("%d \n",length(head)); travel(head); insert(head,1,77); travel(head); printf("isEmpty: %d \n",isEmpty(head)); insert(head,1,52); insert(head,1,44); travel(head); printf("%d \n",length(head)); printf("head:1:%d \n",getElement(head,1)); printf("head:2:%d \n",getElement(head,2)); printf("head:3:%d \n",getElement(head,3)); // Delete(head,1); // travel(head); // Delete(head,1); // travel(head); // Delete(head,1); // travel(head); return 0; }
x
 
1
//******************************circular_link.h**************************************
2
#ifndef CIRCULAR_LINK_H
3
#define CIRCULAR_LINK_H
4
5
#include <stdio.h>
6
#include <stdbool.h>
7
#include <stdlib.h>
8
typedef int datatype;
9
10
typedef struct circular_link
11
{
12
    datatype data;
13
    struct circular_link *next;
14
}Node,*Link;
15
16
17
//创建链表
18
Link create();
19
20
//获取链表长度
21
size_t length(Link link);
22
23
//获取第i-1个节点的地址,工具函数内部使用
24
Node *addressTool(Link link,size_t i);
25
26
27
//插入节点
28
bool insert(Link link,size_t i,datatype data);
29
30
//删除节点
31
bool Delete(Link link,size_t i);
32
33
//历遍节点
34
void travel(Link link);
35
36
//判断节点是否为空
37
bool isEmpty(Link link);
38
39
//获取第i个节点的数据
40
datatype getElement(Link link,size_t i);
41
42
43
44
45
#endif //CIRCULAR_LINK_H
46
47
48
//******************************circular_link.c**************************************
49
#include "circular_link.h"
50
51
52
53
//创建链表 创建失败返回NULL
54
Link create()
55
{
56
    Link link = (Link)malloc(sizeof(Node));
57
    link->next = link;
58
    return link;
59
}
60
61
//获取链表长度
62
size_t length(Link link)
63
{
64
    if(NULL==link || NULL==link->next)return false;
65
66
67
    Node *node = link->next;
68
    int count = 0;
69
    while(node != link)
70
    {
71
        count++;
72
        node = node->next;
73
    }
74
75
    return count;
76
}
77
78
//获取第i-1个节点的地址,工具函数内部使用
79
Node *addressTool(Link link,size_t i)
80
{
81
    Node *node = link;
82
    for(size_t j = 1;j < i;j++)
83
    {
84
        node = node->next;
85
    }
86
    return node;
87
}
88
89
90
//插入节点
91
bool insert(Link link,size_t i,datatype data)
92
{   
93
    if(i<1 || i > length(link)+1)return false;
94
    if(NULL == link)return false;
95
96
    Node *prev = addressTool(link,i);//获取第i-1个节点地址
97
    Node *curr = prev->next;//获取第i个节点地址
98
    
99
    Node *node = (Node *)malloc(sizeof(Node));//创建新节点   
100
    node->data = data;
101
102
    prev->next = node;
103
    node->next = curr;
104
105
    return true;
106
}
107
108
//删除节点
109
bool Delete(Link link,size_t i)
110
{
111
    if(i<1 || i>length(link))return false;
112
    if(NULL == link)return false;
113
114
    Node *prev = addressTool(link,i);
115
    Node *curr = prev->next;
116
    Node *temp = curr->next;
117
118
    prev->next = temp;
119
    free(curr);
120
    curr = NULL;
121
    return true;
122
}
123
124
//历遍节点
125
void travel(Link link)
126
{
127
    Node *node = link->next;
128
    while(node != link)
129
    {
130
        printf("%d ",node->data);
131
        node = node->next;
132
    }
133
    printf("\n");
134
}
135
136
//判断节点是否为空
137
bool isEmpty(Link link)
138
{
139
    return link->next == link;
140
}
141
142
//获取第i个节点的数据
143
datatype getElement(Link link,size_t i)
144
{
145
    if(i<1 || i > length(link) || NULL == link)return !(1<<(sizeof(datatype)-1))+1;
146
147
    Node *node = link->next;
148
149
    for(size_t j = 1;j < i;j++)
150
    {
151
        node = node->next;
152
    }
153
    return node->data;
154
}
155
156
157
//******************************circular_linkTest.c**************************************
158
159
#include "circular_link.h"
160
161
162
163
164
165
int main()
166
167
{
168
169
    Link head = create();
170
171
    printf("isEmpty: %d \n",isEmpty(head));
172
173
    printf("%d \n",length(head));
174
175
    travel(head);
176
177
178
179
    insert(head,1,77);
180
181
    travel(head);
182
183
    printf("isEmpty: %d \n",isEmpty(head));
184
185
    insert(head,1,52);
186
187
    insert(head,1,44);
188
189
    travel(head);
190
191
    printf("%d \n",length(head));
192
193
194
195
    printf("head:1:%d \n",getElement(head,1));
196
197
    printf("head:2:%d \n",getElement(head,2));
198
199
    printf("head:3:%d \n",getElement(head,3));
200
201
    
202
203
//  Delete(head,1);
204
205
//  travel(head);
206
207
//  Delete(head,1);
208
209
//  travel(head);
210
211
//  Delete(head,1);
212
213
//  travel(head);
214
215
    return 0;
216
217
}

4.双向循环链表
//**********************************double_link.h************************************
#ifndef DOUBLE_LINK_H
#define DOUBLE_LINK_H #include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype; typedef struct double_link
{
datatype data;
struct double_link *prior;
struct double_link *next;
}DulNode,*DulLink; //创建链表
DulLink create(); //链表长度
size_t length(DulLink link); //链表是否为空
bool isEmpty(DulLink link); //获取第i-1和节点的地址,工具函数,内部使用
DulNode *addressTool(DulLink link,size_t i); //插入节点
bool insert(DulLink link,size_t i,datatype data); //删除节点
bool Delete(DulLink link,size_t i); //历遍节点
void travel(DulLink link); #endif //DOUBLE_LINK_H //**********************************double_link.c************************************
#include "double_link.h" //创建双向循环链表
DulLink create()
{
DulLink link = (DulLink)malloc(sizeof(DulNode));
link->prior = link;
link->next = link;
return link;
} //链表长度
size_t length(DulLink link)
{
if(NULL == link)return 0; DulNode *node = link->next;
size_t count = 0;
while(node != link)
{
count++;
node = node->next;
} return count;
} //链表是否为空
bool isEmpty(DulLink link)
{
return (link->next == link);
} //获取第i-1和节点的地址,工具函数,内部使用
DulNode *addressTool(DulLink link,size_t i)
{
DulNode *prev = link;
for(int j = 1;j < i;j++)
{
prev = prev->next;
}
return prev;
} //插入节点
bool insert(DulLink link,size_t i,datatype data)
{
if(i<1 || i > length(link)+1)return false;
if(NULL == link)return false; DulNode *prev = addressTool(link,i);//获得第i-1个节点的地址
DulNode *old = prev->next;//获得原来第i个地址 DulNode *node = (DulNode *)malloc(sizeof(DulNode));//创建新节点
node->data = data; prev->next = node; //新节点与prev节点的连接
node->prior= prev; node->next = old;
old->prior = node; return true;
} //删除节点
bool Delete(DulLink link,size_t i)
{
if(i<1 || i>length(link))return false;
if(NULL == link)return false; DulNode *prev = addressTool(link,i);//获取第i-1个节点地址
DulNode *curr = prev->next;
DulNode *behind = curr->next; prev->next = behind;//将第i-1个节点和i+1个节点连接起来
behind->prior = prev; free(curr);//释放第i个节点
curr = NULL; return true;
} //历遍节点
void travel(DulLink link)
{
DulNode *node = link->next;
while(node != link)
{
printf("%d ",node->data);
node = node->next;
}
printf("\n");
} //**********************************double_linkTest.c************************************
#include "double_link.h" int main()
{
DulLink head = create();
printf("length: %d \n",length(head));
printf("isEmpty: %d \n",isEmpty(head)); insert(head,1,77);
travel(head);
insert(head,1,52);
travel(head);
insert(head,3,1314);
travel(head); insert(head,1,74);
insert(head,1,75);
travel(head);
Delete(head,2);
travel(head);
Delete(head,1);
travel(head);
return 0;
}
x
144
 
1
//**********************************double_link.h************************************
2
#ifndef DOUBLE_LINK_H
3
#define DOUBLE_LINK_H
4
5
#include <stdio.h>
6
#include <stdbool.h>
7
#include <stdlib.h>
8
typedef int datatype;
9
10
typedef struct double_link
11
{
12
    datatype data;
13
    struct double_link *prior;
14
    struct double_link *next;
15
}DulNode,*DulLink;
16
17
18
//创建链表
19
DulLink create();
20
21
//链表长度
22
size_t length(DulLink link);
23
24
//链表是否为空
25
bool isEmpty(DulLink link);
26
27
//获取第i-1和节点的地址,工具函数,内部使用
28
DulNode *addressTool(DulLink link,size_t i);
29
30
//插入节点
31
bool insert(DulLink link,size_t i,datatype data);
32
33
//删除节点
34
bool Delete(DulLink link,size_t i);
35
36
//历遍节点
37
void travel(DulLink link);
38
39
40
#endif //DOUBLE_LINK_H
41
42
43
44
45
46
//**********************************double_link.c************************************
47
#include "double_link.h"
48
49
50
//创建双向循环链表
51
DulLink create()
52
{
53
    DulLink link = (DulLink)malloc(sizeof(DulNode));
54
    link->prior = link;
55
    link->next  = link;
56
    return link;
57
}
58
59
//链表长度
60
size_t length(DulLink link)
61
{
62
    if(NULL == link)return 0;
63
64
    DulNode *node = link->next;
65
    size_t count = 0;
66
    while(node != link)
67
    {
68
        count++;
69
        node = node->next;
70
    }
71
72
    return count;
73
}
74
75
//链表是否为空
76
bool isEmpty(DulLink link)
77
{
78
    return (link->next == link);
79
}
80
81
//获取第i-1和节点的地址,工具函数,内部使用
82
DulNode *addressTool(DulLink link,size_t i)
83
{   
84
    DulNode *prev = link;
85
    for(int j = 1;j < i;j++)
86
    {
87
        prev = prev->next;
88
    }
89
    return prev;
90
}
91
92
//插入节点
93
bool insert(DulLink link,size_t i,datatype data)
94
{
95
    if(i<1 || i > length(link)+1)return false;
96
    if(NULL == link)return false;
97
98
    DulNode *prev = addressTool(link,i);//获得第i-1个节点的地址
99
    DulNode *old  = prev->next;//获得原来第i个地址
100
101
    DulNode *node = (DulNode *)malloc(sizeof(DulNode));//创建新节点
102
    node->data = data;
103
104
    prev->next = node;  //新节点与prev节点的连接
105
    node->prior= prev;
106
107
    node->next = old;
108
    old->prior = node;
109
110
    return true;
111
}
112
113
//删除节点
114
bool Delete(DulLink link,size_t i)
115
{
116
    if(i<1 || i>length(link))return false;
117
    if(NULL == link)return false;
118
119
    DulNode *prev = addressTool(link,i);//获取第i-1个节点地址
120
    DulNode *curr = prev->next;
121
    DulNode *behind = curr->next;
122
123
    prev->next = behind;//将第i-1个节点和i+1个节点连接起来
124
    behind->prior = prev;
125
126
    free(curr);//释放第i个节点
127
    curr = NULL;
128
129
    return true;
130
}
131
132
//历遍节点
133
void travel(DulLink link)
134
{
135
    DulNode *node = link->next;
136
    while(node != link)
137
    {
138
        printf("%d ",node->data);
139
        node = node->next;
140
    }
141
    printf("\n");
142
}
143
144
145
146
//**********************************double_linkTest.c************************************
147
#include "double_link.h"
148
149
150
int main()
151
{
152
    DulLink head = create();
153
    printf("length: %d \n",length(head));
154
    printf("isEmpty: %d \n",isEmpty(head));
155
156
    insert(head,1,77);
157
    travel(head);
158
    insert(head,1,52);
159
    travel(head);
160
    insert(head,3,1314);
161
    travel(head);
162
    
163
    insert(head,1,74);
164
    insert(head,1,75);
165
    travel(head);
166
    Delete(head,2);
167
    travel(head);
168
    Delete(head,1);
169
    travel(head);
170
    return 0;
171
}

附件列表

05-08 15:41