【c】链表

链表即链式存储结构，有单链表、双链表，以单链表为例讲解

链表定义了节点 结构体内有数据域 存储值 和指针域 存储指针，单链表即只有一个指针指向下一个节点，双链表即有两个指针，另一个指针指向上一个节点。

typedef struct Node{
    int val;
    struct Node* next;
}Node;
1
2
3
4

一个完整的链表需要由以下几部分构成： 1. 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据； 2. 节点：链表中的节点又细分为头节点、首元节点和其他节点： 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题； 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义； 其他节点：链表中其他的节点

注意：链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。
明白了链表的基本结构，下面我们来了解如何创建一个链表。

    int nums[3] = { 1, 2, 3 };
	Node* list = (Node*)malloc(sizeof(Node));
	list->val = 1;
	list->next = NULL;
	Node* dummy = list;
	for (int col = 1; col < 3; col++){
		Node* nextv = (Node*)malloc(sizeof(Node));
		nextv->val = nums[col];
		nextv->next = NULL;
		dummy->next = nextv;
		dummy = dummy->next;
	}
1
2
3
4
5
6
7
8
9
10
11
12

插入新节点： 1. 将新结点的 next 指针指向插入位置后的结点； 2. 将插入位置前结点的 next 指针指向插入结点；

    int nums[3] = { 1, 2, 3 };
	Node* list = (Node*)malloc(sizeof(Node));
	list->val = 1;
	list->next = NULL;
	Node* dummy = list;
	for (int col = 1; col < 3; col++){
		Node* nextv = (Node*)malloc(sizeof(Node));
		nextv->val = nums[col];
		nextv->next = NULL;
		dummy->next = nextv;
		dummy = dummy->next;
	}
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->val = 9;
	newNode->next = NULL;
	int pos = 1;//insert pos 1
	dummy = list;
	while (pos--){
		dummy = dummy->next;
	}
	newNode->next = dummy->next;
	dummy->next = newNode;
	
	
	
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

删除节点需要进行以下 2 步操作： 1. 将结点从链表中摘下来; 2. 手动释放掉结点，回收被结点占用的存储空间;

    int nums[3] = { 1, 2, 3 };
	Node* list = (Node*)malloc(sizeof(Node));
	list->val = 1;
	list->next = NULL;
	Node* dummy = list;
	for (int col = 1; col < 3; col++){
		Node* nextv = (Node*)malloc(sizeof(Node));
		nextv->val = nums[col];
		nextv->next = NULL;
		dummy->next = nextv;
		dummy = dummy->next;
	}
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->val = 9;
	newNode->next = NULL;
	int pos = 1;//insert pos 1
	dummy = list;
	while (pos--){
		dummy = dummy->next;
	}
	newNode->next = dummy->next;
	dummy->next = newNode;

	pos = 1;//free pos 1 
	dummy = list;
	while (pos--){
		dummy = dummy->next;
	}
	newNode = dummy->next;
	dummy->next = dummy->next->next;
	free (newNode);
	
	
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

链表实现队列

#include <stdio.h>
#include <stdlib.h>
 
#define ElementType int
#define ERROR -99 //ElementType的特殊值，标志错误
 
typedef struct Node {
    ElementType data;
    struct Node* next;
}QNode;
 
typedef struct {
    QNode* front; //指向对头节点
    QNode* rear; //指向队尾节点
}Queue;
 
Queue* CreateQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (!q) {
        printf("空间不足！\n");
        return NULL;
    }
    q->front = NULL;
    q->rear = NULL;
    return q;
}
 
void AddQ(Queue* q, ElementType item) {
    QNode* qNode = (QNode*)malloc(sizeof(QNode));
    if (!qNode) {
        printf("空间不足！\n");
        return;
    }
    qNode->data = item;
    qNode->next = NULL;
    if (q->front == NULL) {
        q->front = qNode;
    }
    if (q->rear == NULL) {
        q->rear = qNode;
    }
    else {
        q->rear->next = qNode;
        q->rear = qNode;
    }
}
 
int IsEmptyQ(Queue* q){
    return (q->front == NULL);
}
 
ElementType DeleteQ(Queue* q) {
    if (IsEmptyQ(q)) {
        printf("空队列\n");
        return ERROR;
    }
    QNode* temp = q->front;
    ElementType item;
    if (q->front == q->rear) { //若队列只有一个元素
        q->front = NULL;
        q->rear = NULL;
    }
    else {
        q->front = q->front->next;
    }
    item = temp->data;
    free(temp);
    return item;
}
 
void PrintQueue(Queue* q) {
    if (IsEmptyQ(q)) {
        printf("空队列\n");
        return;
    }
    printf("打印队列数据元素：\n");
    QNode* qNode = q->front;
    while (qNode != NULL) {
        printf("%d " , qNode->data);
        qNode = qNode->next;
    }
    printf("\n");
}
 
int main(int argc, const char * argv[]) {
    Queue* q = CreateQueue();
    
    AddQ(q, 1);
    PrintQueue(q);
    
    DeleteQ(q);
    PrintQueue(q);
    
    AddQ(q, 2);
    AddQ(q, 3);
    AddQ(q, 4);
    PrintQueue(q);
    
    DeleteQ(q);
    DeleteQ(q);
    PrintQueue(q);
    
    AddQ(q, 5);
    AddQ(q, 6);
    PrintQueue(q);
    
    return 0;
   }

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

ref https://blog.csdn.net/Trance95/article/details/116205556