目录

一、单链表的建立

1、头插法

2、尾插法

二、插入结点操作

三、删除节点操作

四、单链表操作的一些常见问题

1、结构体变量和结构体指针的区别？

2、什么时候要malloc？

3、形参里面出现了取地址符(&)，有什么作用？

---

        学习并理解单链表，最好先去熟练掌握下C语言的指针，再跟着书本或视频进行练习。本篇文章所有代码都可以运行，读者可以自行调试。数据结构是抽象的，所以最好是看图解教程，才能更清楚的掌握数据结构。当基础知识掌握后，应进行大量练习，去刷题网站练习相关题目。

一、单链表的建立

1、头插法

#include<stdio.h>
#include<stdlib.h>    //malloc需要typedef struct List{int data;struct List* next;
}LinkList;int main() {printf("输入要建立的链表，输入-1停止：\n");LinkList* head, *node;	int x;scanf("%d", &x);head = (LinkList*)malloc(sizeof(LinkList));head->next = NULL;while (x != -1) {node = (LinkList*)malloc(sizeof(LinkList));node->data = x;node->next = head->next;head->next = node;scanf("%d", &x);}printf("头插法建立链表后从头往后输出:\n");LinkList* p = head->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}return 0;
}

输出结果：

 

 

 让我们来从上到下看一下上述代码的执行效果：

1、LinkList* head, *node;     

 

2、head = (LinkList*)malloc(sizeof(LinkList)); head->next = NULL; //新建一个结点作为头结点，让头指针指向它

 

 

3、node = (LinkList*)malloc(sizeof(LinkList));        //为要插入的结点开辟空间

4、node->next = head->next;        

 

5、 head->next = node;

 

 6、整理一下(注意这里head->next指向的是整个node结点而非指向node的next域)：

 7、执行第二次循环，node = (LinkList*)malloc(sizeof(LinkList));

8、node->next = head->next;

9、 head->next = node;

 10、然后进入下一次循环······

2、尾插法

#include<stdio.h>
#include<stdlib.h>typedef struct List{int data;struct List* next;
}LinkList;int main() {printf("输入要建立的链表，输入-1停止：\n");LinkList* head, *rear, *node;int x;head = (LinkList*)malloc(sizeof(LinkList));head->next = NULL;rear = head;scanf("%d", &x);while (x != -1) {node = (LinkList*)malloc(sizeof(LinkList));node->data = x;rear->next = node;rear = node;scanf("%d", &x);}rear->next = NULL;printf("尾插法建立链表后从头往后输出:\n");LinkList* p = head->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}return 0;
}

输出结果：

 

二、插入结点操作

#include<stdio.h>
#include<stdlib.h>typedef struct List{int data;struct List* next;
}LinkList;int main() {printf("输入要建立的链表，输入-1停止：\n");LinkList* head, *rear, *node;int x;head = (LinkList*)malloc(sizeof(LinkList));head->next = NULL;rear = head;scanf("%d", &x);while (x != -1) {node = (LinkList*)malloc(sizeof(LinkList));node->data = x;rear->next = node;rear = node;scanf("%d", &x);}rear->next = NULL;printf("尾插法建立链表后从头往后输出:\n");LinkList* p = head->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}puts("");/*以下是插入操作*/printf("请输入要在第几个结点后面插入:\n");int target;scanf("%d", &target);printf("请输入要插入的数:\n");int num;scanf("%d", &num);LinkList* q = head->next;int i = 1;while (q != NULL && i < target) {q = q->next;++i;}node = (LinkList*)malloc(sizeof(LinkList));node->data = num;node->next = q->next;q->next = node;printf("插入完成后运行结果:\n");LinkList* pp = head->next;while (pp != NULL) {printf("%d ", pp->data);pp = pp->next;}return 0;
}

输出结果

 

三、删除节点操作

删除节点要注意，是查找到第 i-1 个结点再开始操作。

#include<stdio.h>
#include<stdlib.h>typedef struct List{int data;struct List* next;
}LinkList;int main() {printf("输入要建立的链表，输入-1停止：\n");LinkList* head, *rear, *node;int x;head = (LinkList*)malloc(sizeof(LinkList));head->next = NULL;rear = head;scanf("%d", &x);while (x != -1) {node = (LinkList*)malloc(sizeof(LinkList));node->data = x;rear->next = node;rear = node;scanf("%d", &x);}rear->next = NULL;printf("尾插法建立链表后从头往后输出:\n");LinkList* p = head->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}puts("");/*以下是插入操作*/printf("请输入要删除第几个结点:\n");int target;scanf("%d", &target);LinkList* q = head->next;int i = 1;while (q != NULL && i < target - 1) {    //找到第target-1个结点即可q = q->next;++i;}LinkList* temp = q->next;q->next = temp->next;free(temp);printf("删除完成后运行结果:\n");LinkList* pp = head->next;while (pp != NULL) {printf("%d ", pp->data);pp = pp->next;}return 0;
}

输出结果：

 

四、单链表操作的一些常见问题

1、结构体变量和结构体指针的区别？

        有时候我们会看到如下情况：

typedef struct List{int data;struct List* next;
}LNode, *LinkList;

一些初学者会对LNode和*LinkList 表示疑惑，为什么要定义一个结构体变量，一个结构体指针呢？

首先说明下它们的区别：结构体变量定义完后，会自动在内存中开辟一段空间；而结构体指针定义完后，并不会开辟新的空间。要使用结构体指针，你得手动去开辟空间(比如malloc)，然后让结构体指针指向它才行，或者让结构体指针指向其它已经开辟的空间的地址才行。此外，它们的访问结构体成员方式也不同，结构体变量访问用“.”，而结构体指针用“->”，或者 (*p).xx (其中p是结构体指针，xx是结构体中的一个成员)。

        举个例子，比如在头插尾插建立链表中，建立头结点，原来是用结构体指针表示：

LinkList* head;
head = (LinkList*)malloc(sizeof(LinkList));

        我们可以改成用结构体变量表示头结点，因为结构体变量声明后，会自动在内存中开辟空间，这样我们后面就不用手动去malloc了：

LinkList head;
//head = (LinkList*)malloc(sizeof(LinkList)); 不需要了

2、什么时候要malloc？

        需要新建一个结点时。

3、形参里面出现了取地址符(&)，有什么作用？

        形参里面出现“&”，比如 int func(int &a, int &b); 这是C++的语法，不是C的，因此这里不展开。