数据结构 - 链表
Intro
链表是一个非常基础的数据结构，包括二叉树，所谓的环等都是链表变种。无论是上位机还是下位机多少都能看到它的影子。
Q&A
Q.为什么不用数组
A1: 数组编译的时候要确认大小，不能动态插入A2: 链表非连续存储，插入速度更快A3: 动态分配堆内存，避免爆栈StackOverflow(常见于上位机开发)
Example
链表示例(基于Linux Shell代码)
假设你需要处理一个别名，比如将a替换为b，那么这时候有两个字符串，如果要动态插入动态删除这时候链表就派上用场了
类型定义
1
2
3
4
5
6
7
| struct alias
{
char *alias_name;
char *alias_command;
struct alias *next;
};
typedef struct alias *alias_t;
|
- 上述代码新建一个结构体，内含两个指向char类型的指针，定义一个新类型alias_t -> struct alias *
1
2
3
4
5
| struct head_alias
{
struct alias *next;
};
typedef struct head_alias *head_alias_t;
|
这里多一个head_alias_t看似多此一举，实际上假设你的链表头是alias_t类型，刚好你要free()的就是链表头那就会Segmentation fault(段错误了)
创建链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| static alias_t init_alias(alias_t alias_chain, const char *alias_name, const char
*alias_command)
{
alias_chain = (alias_t)malloc(sizeof(struct alias));
alias_chain->alias_name = mstrcpy(NULL, alias_name);
alias_chain->alias_command = mstrcpy(NULL, alias_command);
alias_chain->next = NULL;
return alias_chain;
}
head_alias_t init_alias_head(head_alias_t alias_head)
{
alias_head = (head_alias_t)malloc(sizeof(struct head_alias));
if (alias_head != NULL)
{
alias_head->next = NULL;
return alias_head;
}
else
return NULL;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| static inline unsigned short count_for_strlcpy(const char *pointer)
{
return pointer != NULL ? (sizeof(char) * strlen(pointer) + sizeof(char)) : 0;
}
char *mstrcpy(char *dest, const char *src)
{
if (src != NULL)
{
if (dest == NULL)
dest = (char *)calloc(count_for_strlcpy(src), sizeof(char));
else if (sizeof(dest) != sizeof(src))
dest = (char *)realloc((void *)dest, count_for_strlcpy(src) * sizeof(char));
strlcpy(dest, src, count_for_strlcpy(src));
return dest;
}
else
return (char *)NULL;
}
|
- 实际上用到的代码mstrcpy()在init_alias()等效为
1
2
3
4
5
6
| char *alias_name_upload = (char *)calloc(count_for_strlcpy(alias_name), sizeof(char));
char *alias_command_upload = (char *)calloc(count_for_strlcpy(alias_command), sizeof(char));
strlcpy(alias_name_upload, alias_name, count_for_strlcpy(alias_name));
strlcpy(alias_command_upload, alias_command, count_for_strlcpy(alias_command));
alias_chain->alias_name = alias_name_upload;
alias_chain->alias_command = alias_command_upload;
|
链表的插入和删除
插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| head_alias_t upload_alias_node(head_alias_t alias_head, const char *alias_name, const char *alias_command)
{
if (alias_head->next != NULL)
{
alias_t current = alias_head->next;
while (1)
{
if (!strcmp(current->alias_name, alias_name))
{
current->alias_command = mstrcpy(current->alias_command, alias_command);
return alias_head;
}
else if (current->next != NULL)
current = current->next;
else if (current->next == NULL)
{
current->next = init_alias(current->next, alias_name, alias_command);
return alias_head;
}
}
}
else
{
alias_head->next = init_alias(alias_head->next, alias_name, alias_command);
return alias_head;
}
}
|
- 依次索引，首先查看alias_head指向的第一个元素是否为空，是的话就alias_head的next指向它，否的话就依次索引查找，如果查找到匹配的就替换，如果查找不到对应的名字就新建一个节点在链表尾部
删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| head_alias_t remove_alias_node(head_alias_t alias_head, const char *alias_name)
{
alias_t current = alias_head->next, prev = alias_head->next;
if (current == NULL)
{
printf("fshell : unalias : no alias\n");
return alias_head;
}
if (strcmp(current->alias_name, alias_name))
{
if (current->next != NULL)
{
current = current->next;
while (1)
{
if (!strcmp(current->alias_name, alias_name))
{
prev->next = current->next;
free(current->alias_name);
free(current->alias_command);
free(current);
return alias_head;
}
else if (current->next != NULL)
{
prev = current;
current = current->next;
}
else
return alias_head;
}
}
else
return alias_head;
}
else
{
alias_head->next = current->next;
return alias_head;
}
}
|
- 和插入一样的索引方法，直到找到匹配的名称free()
深入讲解
void *calloc(size_t nitems, size_t size)函数申请堆内存
nitems – 要被分配的元素个数
size – 元素的大小
void free(void *ptr)函数用于释放堆内存
size_t strlcpy(char *dst, const char *src, size_t size)函数是BSD提供的，在BSD和Linux API均提供，类似于strncpy()但是会在结尾最后一个添加’\0’
Linux ManPage : “The strlcpy() function copies up to size - 1 characters from the NUL-terminated string src to dst, NUL-terminating the result.”
