「C语言干货」 超详细的数据结构链表详解

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。

小编是一个有着6年工作经验的工程师，关于C++编程，自己有做材料的整合，一个完整的C++编程学习路线，学习资料和工具，能够进我的群10048，-83029收取，免费送给大家，希望你也能凭着自己的努力，成为下一个优秀的程序员

链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，它可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。

链表都有一个头指针，一般以head来表示，存放的是一个地址。

链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。

链表中每个节点都分为两部分，一个数据域，一个是指针域。

说到这里小伙伴们应该就明白了，链表就如同车链子一样，head指向第一个元素：

第一个元素又指向第二个元素；……，直到最后一个元素。

该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

作为有强大功能的链表，对它的操作当然有许多。

比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。

初学链表，一般从单向链表开始

-→NULL

head

这是一个空链表。

---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next

有n个节点的链表。

创建链表

typedef struct student{
int score;
struct student *next;
} LinkList;

一般创建链表我们都用typedef struct，因为这样定义结构体变量时，我们就可以直接用LinkList *a;定义结构体类型变量了。

初始化一个链表，n为链表节点个数。

LinkList creat(int n){
LinkList head, node, end;//定义头节点，普通节点，尾部节点；
head = malloc(sizeof(LinkList));//分配地址
end = head; //若是空链表则头尾节点一样
for (int i = 0; i < n; i++) {
node = malloc(sizeof(LinkList));
scanf(“%d”, &node->score);
end->next = node;
end = node;
}
end->next = NULL;//结束创建
return head;
}

修改链表节点值

修改链表节点值很简单。下面是一个传入链表和要修改的节点，来修改值的函数。

void change(LinkList list,int n) {//n为第n个节点
 LinkList t = list;
 int i = 0;
 while (i < n && t != NULL) {
 t = t->next;
 i++;
 }
 if (t != NULL) {
 puts(“输入要修改的值”);
 scanf(“%d”, &t->score);
 }
 else {
 puts(“节点不存在”);
 }
 }

删除链表节点

删除链表的元素也就是把前节点的指针域越过要删除的节点指向下下个节点。

即：p->next = q->next;然后放出q节点的空间，即free(q);

void delet(LinkList list, int n) {
 LinkList t = list, *in;
 int i = 0;
 while (i < n && t != NULL) {
 in = t;
 t = t->next;
 i++;
 }
 if (t != NULL) {
 in->next = t->next;
 free(t);
 }
 else {
 puts(“节点不存在”);
 }
 }
 }

我们可以看出来，插入节点就是用插入前节点的指针域链接上插入节点的数据域，再把插入节点的指针域链接上插入后节点的数据域。

根据图，插入节点也就是：head->next = e->next; head->next = e;

增加链表节点用到了两个结构体指针和一个int数据。

void insert(LinkList *list, int n) {
LinkList *t = list, *in;
int i = 0;
while (i < n && t != NULL) {
 t = t->next;
 i++;
}
if (t != NULL) {
 in = malloc(sizeof(LinkList));
 puts("输入要插入的值");
 scanf("%d", &in->score);
 in->next = t->next;//填充in节点的指针域，也就是说把in的指针域指向t的下一个节点
 t->next = in;//填充t节点的指针域，把t的指针域重新指向in
}
else {
 puts("节点不存在");
}
}

输出链表

输出链表很简单，边遍历边输出就行了。

while (h->next != NULL) { h = h->next; printf("%d ", h->score); }