线性表的链式存储实现称为链表。
每一个节点都需要一个结构体变量存储。
前一个节点的指针域指向下一个节点的数据域起始位置。
最后一个节点的指针域内存储的是NULL（即0）。
::: tip
为了简单，考研设计时，单链表都会包含头节点，业界不使用。
头指针L指向的空间称为头节点，认为是0号位置，a1称为第一个节点。考研时认为头节点的数据域为空。
列表为空表示a1-an不存在。
:::
链表的初始化插入：
如下图，插入时的新节点q需要使用malloc申请一个结构体大小的空间（sizeof(LNode)），再强转成结构体指针的类型：
上图中，q->data为数据域，q->next为指针域。p->next为第一个节点a1的地址，保存在头节点p中。
链表的删除、查询：
上图中的第一二行代码作用是确定p和q节点的位置，i为删除位置，
::: warning
每一个节点的空间都是malloc出来的，删除节点后必须free。
:::
上图中while循环中的p用来控制是否遍历到列表的尾部（最后一个元素的指针域是NULL）
::: tip
while循环中的p!=NULL和p等价。
:::
头插法新建链表
头插法是每次新增节点时从头节点后的位置插入链表。
流程如下：
头插法代码：
1#include <stdio.h> 2#include <stdlib.h> 3 4typedef int Elemtype; 5typedef struct LNode 6{ 7 Elemtype data; 8 struct LNode* next; 9}LNode,*LinkList; 10//LNode*是结构体指针，等同于LinkList，写*LinkList只是为了方便认为是链表而非结构体节点指针 11 12//void list_head_insert(LNode* &L) 13//{ 14// L = (LinkList)malloc(sizeof(LNode)); //申请头节点空间（头指针指向头节点） 15// //malloc开辟的空间默认是void类型，上述代码中LinkList可以换成LNode* 16// Elemtype x; //读取的元素值放在第一个节点上（头节点是空的），需要再申请一个节点 17// L->next = NULL; 18// scanf("%d", &x); 19// //申请第一个节点空间 20// LNode* s = (LinkList)malloc(sizeof(LNode)); 21// s->data = x; 22// s->next = NULL; //头插法中第一个创建的节点会变为最后一个节点，需要将next设置成NULL 23// L->next = s; //使得L的next（指针域）指向第一个节点 24// while (x!=9999) 25// { 26// scanf("%d", &x); 27// s = (LinkList)malloc(sizeof(LNode)); //s指向新开辟的节点 28// s->data = x; 29// s->next = L->next; //新节点的next值为头节点L的next，即指向上一个创建的节点 30// L->next = s; //头节点的next指向新建的节点 31// } 32//} 33 34//上述函数在插入节点时会插入最后一个作为结束标志的9999的数据，函数改进如下： 35void list_head_insert(LNode*& L) 36{ 37 L = (LinkList)malloc(sizeof(LNode)); //申请头节点空间（头指针指向头节点） 38 //malloc开辟的空间默认是void类型，上述代码中LinkList可以换成LNode* 39 Elemtype x; //读取的元素值放在第一个节点上（头节点是空的），需要再申请一个节点 40 L->next = NULL; //循环中将L的next赋给第一次循环创建的节点的next，即链表最后一个节点 41 scanf("%d", &x); //供while循环判断是否结束 42 //申请第一个节点空间 43 LNode* s = (LinkList)malloc(sizeof(LNode)); 44 while (x != 9999) 45 { 46 s = (LinkList)malloc(sizeof(LNode)); //s指向新开辟的节点 47 s->data = x; 48 s->next = L->next; //新节点的next值为头节点L的next，即指向上一个创建的节点 49 L->next = s; //头节点的next指向新建的节点（头插法新建的节点在头节点后面一个位置） 50 scanf("%d", &x); 51 } 52} 53 54void print_list(LinkList L) 55{ 56 L = L->next; 57 while (L != NULL) 58 { 59 printf("%3d", L->data); 60 L = L->next; 61 } 62} 63int main() 64{ 65 LinkList L; //等同于LNode* L 66 list_head_insert(L); 67 print_list(L); 68 return 0; 69}
尾插法新建链表
流程如下：
链表的增删查改操作：
1//输入9999表示输入结束 2#include <stdio.h> 3#include <stdlib.h> 4 5typedef int Elemtype; 6typedef struct LNode 7{ 8 Elemtype data; 9 struct LNode* next; 10}LNode, * Linklist; 11//尾插法插入 12void list_tail_insert(Linklist& L) 13{ 14 L = (LNode*)malloc(sizeof(LNode)); //头节点 15 L->next = NULL; 16 LNode* s, * r = L; //r->next=NULL; 17 Elemtype x; 18 scanf("%d", &x); 19 while (x != 9999) 20 { 21 s = (LNode*)malloc(sizeof(LNode)); 22 r->next = s; 23 s->data = x; 24 r = s; 25 scanf("%d", &x); 26 } 27 r->next = NULL; 28} 29//节点查找 30LNode* value_find(LNode* L,Elemtype x) 31{ 32 Elemtype a = 0; 33 if (x < 0) 34 { 35 return NULL; 36 } 37 while (L && a < x) 38 { 39 L = L->next; 40 a++; 41 } 42 /*printf("%d\n", L->data);*/ 43 return L; 44} 45//值插入 46bool value_insert(LNode* L, Elemtype x, Elemtype y) //在某位置上插入节点 47{ 48 Elemtype i = 0; 49 LNode* s = value_find(L, x - 1); //找到要插入位置的前一个节点 50 if (s == NULL) 51 { 52 return false; 53 } 54 LNode* q = (LNode*)malloc(sizeof(LNode)); //新节点 55 q->data = y; 56 q->next = s->next; 57 s->next = q; 58 return true; 59} 60//删除节点 61bool Dele_list(LNode* L, Elemtype x) 62{ 63 //1.调用位置查找函数 64 LNode* p = value_find(L, x - 1); //要删除节点的前一个节点 65 if (p == NULL) 66 { 67 return false; 68 } 69 LNode* q = p->next; //要删除的节点 70 p->next = q->next; 71 free(q); 72 return true; 73 //2.直接遍历查找 74 //Elemtype i = 0; 75 //while (L && i < x - 1) 76 //{ 77 // L = L->next; 78 // i++; 79 //} 80 //LNode* s = L; 81 //L = L->next; 82 //s->next = L->next; 83 //free(L); 84 //return true; 85} 86//打印节点 87void Print_list(LNode* L) 88{ 89 L = L->next; 90 while (L) 91 { 92 printf("%3d", L->data); 93 L = L->next; 94 } 95 printf("\n"); 96} 97 98int main() 99{ 100 LNode* L; 101 list_tail_insert(L); 102 LNode* search = value_find(L, 2); 103 if (search != NULL) 104 { 105 printf("%d\n", search->data); 106 } 107 int ret = 0; 108 ret = value_insert(L, 2, 99); 109 if (ret) 110 { 111 Print_list(L); 112 } 113 else 114 { 115 printf("false\n"); 116 } 117 ret = Dele_list(L, 4); 118 if (ret) 119 { 120 Print_list(L); 121 } 122 return 0; 123}