带表头的单向链表
结构体的声明
1
2
3
4
5
| struct List_node{
struct List_node *head; //链表的头结点
struct List_node *tail; //链表的尾结点
int count; //链表的结点个数
};
|
一些必要的的定义和重命名
1
2
3
4
5
6
7
| #define TRUE (1)
#define FALSE (0)
typedef unsigned char Boolean;
typedef struct List_node List_node;
typedef List_node * List_head;
|
函数的声明
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| List_head init_list(void) ; //链表的初始化
void destroy_list(List_head *head) ; //链表的删除
Boolean push_front(List_head head, int value); //头部插入
Boolean push_back(List_head head, int value) ; //尾部插入
Boolean pop_front(List_head head) ; //头部删除
Boolean pop_back(List_head head) ; //尾部删除
Boolean delete_list_node(List_head head,
List_node *node) ; //删除某个指针的值
Boolean find_value_node(List_head head,
int value, List_node **node); //找到指定值的地址
void show_list(List_head head) ; //显示链表信息
void sort_list_ascend(List_head head) ; //链表的升序排序
void sort_list_descend(List_head head) ; //链表的降序排序
static void swap(void *a, void *b, int length) ; //交换函数
static List_node *buy_node(void) ; //生成一个链表节点
static void *Malloc(size_t size) ; //内存申请
|
链表的初始化
1
2
3
4
5
6
7
8
| List_head init_list(void) //链表的初始化
{
List_head head = NULL;
head = buy_node();
return head;
}
|
链表的删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void destroy_list(List_head *head) //链表的删除
{
List_node *p = NULL;
List_node *q = NULL;
// List_node **
if(head == NULL || *head == NULL){
return ;
}
p = *head;
while(p != NULL){
q = p;
p = p->next;
free(q);
}
*head = NULL;
}
|
头部插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| Boolean push_front(List_head head, int value) //头部插入
{
List_node *node = NULL;
if(head == NULL){
return FALSE;
}
//购买节点并进行赋值
node = buy_node();
node->data = value;
//头部插入节点
node->next = head->next;
head->next = node;
return TRUE;
}
|
尾部插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| Boolean push_back(List_head head, int value) //尾部插入
{
List_node *node = NULL;
List_node *p_node = NULL;
if(head == NULL){
return FALSE;
}
node = buy_node();
node->data = value;
p_node = head;
//1.找到末尾
while(p_node->next != NULL){
p_node = p_node->next;
}
//2.插入到末尾
p_node->next = node;
return TRUE;
}
|
头部删除
1
2
3
4
5
6
7
8
9
10
11
| Boolean pop_front(List_head head)//头部删除
{
List_node *p_node = NULL;
if(head == NULL || head->next == NULL){
return FALSE;
}
p_node = head->next;
head->next = p_node->next;
free(p_node);
p_node = NULL;
}
|
尾部删除
1
2
3
4
5
6
7
8
9
10
11
12
| Boolean pop_back(List_head head)//尾部删除
{
List_node *p_node = NULL;
if(head == NULL || head->next == NULL){
return FALSE;
}
for(p_node = head; p_node->next->next != NULL; p_node = p_node->next){
}
free(p_node->next);
p_node->next = NULL;
return TRUE;
}
|
删除某个指针的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| Boolean delete_list_node(List_head head,
List_node *node) //删除某个结点
{
List_node *p_node = NULL;
if(head == NULL || head->next == NULL || node == NULL){
return FALSE;
}
p_node = head;
while(p_node->next != NULL){
if(p_node->next == node){
p_node->next = p_node->next->next;
free(p_node->next);
return TRUE;
}
}
return FALSE;
}
|
找到指定值的地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| Boolean find_value_node(List_head head,
int value, List_node **node) //找到某个值的结点
{
List_node *p_node = NULL;
if(head == NULL ){
return 0;
}
p_node = head;
while(p_node != NULL){
if(p_node->data == value){
*node = p_node;
return 1;
}
}
return 0;
}
|
打印链表
1
2
3
4
5
6
7
8
| void show_list(List_head head)
{
List_node *p_node = NULL;
for(p_node = head; p_node != NULL; p_node = p_node->next){
printf("%d ", p_node->data);
}
printf("\n");
}
|
链表的升序排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void sort_list_ascend(List_head head)
{
List_node *p_node = NULL;
List_node *q_node = NULL;
if(head == NULL || head->next == NULL || head->next->next == NULL){
return ;
}
for(p_node = head; p_node->next != NULL; p_node = p_node->next){
for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
if(p_node->data > q_node->data){
swap(p_node, q_node, sizeof(*q_node));
swap(&(p_node->next), &(q_node->next), sizeof(&(p_node->next)));
}
}
}
}
|
链表的降序排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void sort_list_descend(List_head head)
{
List_node *p_node = NULL;
List_node *q_node = NULL;
if(head == NULL || head->next == NULL || head->next->next == NULL){
return;
}
for(p_node = head; p_node->next != NULL; p_node = p_node->next){
for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
if(p_node->data < q_node->data){
swap(p_node, q_node, sizeof(*p_node) - sizeof(void *));
}
}
}
}
|
其他函数
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
| //包裹函数的实现
static void Malloc(size_t size)
{
void *result = NULL;
result = malloc(size);
if(result == NULL){
fprintf("the memory is full \n");
}
return result;
}
//交换函数
void swap(void *a, void *b, size_t size)
{
void *temp = Malloc(size);
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
free(temp);
temp = NULL;
}
//创建一个结点
List_node *buy_node(void)
{
List_node *node = NULL;
node = (List_node *)(malloc(sizeof(List_node)));
bzero(node, sizeof(sizeof(List_node)));
return node;
}
|
