链表的存储结构
我们首先看看链表是什么样子的
然后我们在看看详细的代码：
1
2
3
4
5
6
| typedef int Elemtype;
typedef struct {
Elemtype data;
struct node *next;
}Node;
|
我们可以看到我们在 node 这个结构体中有两个数据，一个是用来保存我们每个节点中的元素，一个是用于连接后面一个 node 的节点，里面放的是地址，用于指向下一个节点。
我们第一个节点称之为头结点，里面会放入一个特殊的值。由于我们现在学习的是一个单链表，有头节点和没有头结点的情况，那我们写的代码可能会不太一样。
单链表-初始化
现在让我们自己思考一下，我们这个初始化应该怎么做？
首先我们得开辟一块内存用于存放链表的头结点，而这块内存我们可以使用动态内存分配。
然后我们需要让 head 头结点中存储的数据为 0，头结点的 next 指向 NULL，因为目前链表为空，还没有确定下一个节点。
1
2
3
4
5
6
7
8
9
10
11
|
Node *InitList() {
Node *head = (Node *)malloc(sizeof(Node));
if (head == NULL) {
printf("malloc failed\n");
exit(1);
}
head->data = 0;
head->next = NULL;
return head;
}
|
单链表-插入节点
头插法
这里我可能会讲的有点绕，首先链表的插入和 next 的指向是很有关系。可以看看我们画的图
我们只需要让我们的 newnode.next 指向的是我们 head.next 所指向的那个 next，然后我们再让 head.next 来指向我们的 newnode 就可以完成头插了
代码实现：
1
2
3
4
5
6
7
| int InsertElem(Node *head, Elemtype e) {
Node *newnode = (Node *)malloc(sizeof(Node));
newnode->data=e;
newnode->next=head->next;
head->next=newnode;
return 1;
}
|
这种插入方式是一种典型的头插法。
尾插法
尾插法会稍微麻烦一点，头插法我们只需要在头节点的后面插入就可以了，但是，尾插法的话，我们需要找到尾在哪里，所以我们这里需要一个便利，让我们的 newnode.next=NULL 的时候，才可以找到尾部。
那我们代码就可以这样来写了
1
2
3
4
5
6
7
8
9
10
11
| int InsertTail(Node *head, Elemtype e) {
Node *newnode = (Node *)malloc(sizeof(Node));
newnode->data=e;
newnode->next=NULL;
Node *temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next=newnode;
return 1;
}
|
在指定位置插入
我们现在要添加要给新的节点 e，我们需要先给他分配内存，然后我们让节点中的 data=我们要插入的元素
然后我们需要找到我们想要插入的这个位置，也就是我们需要传入一个 POS 进去，但是如果说我们哲哥 pos 是小于 0 的话
那么他是一个非法的插入位置，所以我们这里会直接 return 0；如果说我们 pos 的位置在我们遍历完整个链表都没有找到的话，那么就 return 0；并且我们需要释放这个刚初始化的 newnode， 现在我们传入的 pos 是一个正常的位置，可以被便利找到的位置，那么我们将新节点的 next 指向 temp 的下一个节点，在讲 temp 的 next 指向的新节点
图片可以参考头插法的那个图片
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int Insert(Node *head, Elemtype e, int pos) {
if (pos < 0) return 0;
Node *newnode = (Node *)malloc(sizeof(Node));
if (newnode == NULL) return 0;
newnode->data = e;
newnode->next = NULL;
Node *temp = head;
for (int i = 0; i < pos && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
free(newnode);
return 0;
}
newnode->next = temp->next;
temp->next = newnode;
return 1;
}
|
遍历
遍历其实也没有太多需要讲的，尾插法怎么遍历思路，这里也是一样的
1
2
3
4
5
6
7
8
9
| void PrintList(Node *head) {
Node *temp = head;
printf("List: ");
while (temp->next != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
|
这里我们需要提醒一个东西就是，尾插法和头插法遍历出来的顺序是不一样的。
删除
这个也很好理解，我们让 del 节点的前一个节点指向 del 后一个节点，这样我们就可以直接把 del 这个节点给释放掉了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int Delete(Node *head, int pos) {
if (pos < 0) return 0;
Node *temp = head;
for (int i = 0; i < pos - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) return 0;
Node *del = temp->next;
temp->next = del->next;
free(del);
return 1;
}
|
获取链表长度
我们便利整个链表，每经过一个节点，就让 length+1.
1
2
3
4
5
6
7
8
9
| void NodeLength(Node *head) {
Node *temp = head;
int Length = 0;
while (temp != NULL) {
temp = temp->next;
Length++;
}
printf("Length=%d\n",Length);
}
|
释放链表
指针 p 指向头结点后的第一个节点，然后判断指针 p 是否指向空节点，如果 p 不为空，用指针 q 记录指针 p 的后继节点。释放指针 p 指向的节点，指针 p 和指针 q 指向同一个节点，然后循环上面的操作。
1
2
3
4
5
6
7
8
9
10
| void FreeList(Node *head) {
Node *current = head;
Node *next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
}
|
