数据结构--链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
相较于数组，链表有以下长处：
逻辑结构

（1）链表接纳动态内存分配的方式，在内存中不连续 (2)支持动态增长大概删除元素 (3)需要时可以使用malloc大概new来申请内存，不消时使用free大概delete来释放内存
内存结构

链表从堆上分配内存，自由度大，但是要注意内存泄漏
访问效率

链表访问效率低，如果想要访问某个元素，需要从头遍历
越界问题

指针一般使用$ malloc $关键字申请动态内存，只要可以申请得到链表空间，链表就无越界风险
链表的根本操作

创建链表

这里用结构体（struct）存储链表。不同于C++，C语言中新定义结构体变量需要以下格式

1. struct Data a;

复制代码

使用typedef关键字后可直接用Sqlist来定义变量
next指针指向表中下一个数据

1. typedef struct Data {
2.         int value;
3.         struct Data* next;
4. }Sqlist;

复制代码

malloc 为库中的函数，用于动态分配内存，传入所需内存大小，返回值为范例为void的指针，这里使用（Sqlist *）逼迫转换

1. Sqlist* Init()
2. {
3.         Sqlist* t = (Sqlist*)malloc(sizeof(Sqlist));
4.         t->value = 1;
5.         t->next = NULL;
6.         return t;
7. }

复制代码

在pos后插入数值

传入参数为插入数值的位置pos和数值，从头开始遍历链表直到第pos个位置，新建一个节点，将pos指向新节点，新节点指向pos的下一个节点（pos->next）

1. Sqlist* Create_node()
2. {
3.         Sqlist* node = (Sqlist*)malloc(sizeof(Sqlist));;
4.         return node;
5. }
6. Sqlist* getPos(Sqlist*head,int pos)
7. {
8.         Sqlist* t = head;
9.         int i = 1;
10.         while (i != pos && t != NULL)
11.         {
12.                 t = t->next; i++;
13.         }
14.         return t;
15. }
16. void Insert(Sqlist* head, int pos, int value)
17. {
18.         Sqlist* t = getPos(head,pos), * newNode = Create_node;
19.         newNode->value = value;
20.         t->next = newNode;
21.         if (t == NULL)//t 为最后一个节点，没有next
22.         {
23.                 return;
24.         }
25.         newNode->next = t->next;
26. }

复制代码

删除节点pos

记载下当前节点的前一个节点pre，将pre->next指向pos->next，释放pos的内存

1. void Delete(Sqlist* head, int pos)
2. {
3.         Sqlist* t = head,*pre=head; int i = 1;
4.         while (i != pos && t != NULL)
5.         {
6.                 pre = t;
7.                 t = t->next;
8.                 i++;
9.         }
10.         if (t != NULL)
11.         {
12.                 pre->next = t->next;
13.                 free(t);
14.         }
15. }

复制代码

根本操作大概就这些，根据实际问题机动运用。
提供luogu上的一道练习题luogu
由于用指针维护链表每次操作都需要从头遍历，导致效率不尽人意，想要AC这道题可以考虑使用数组模仿链表
如果出现了RE，可能是调用了NULL->next
附70ptsCODE
  睁开查看

2. #include<stdio.h>
3. #include<stdlib.h>
4. using namespace std;
5. typedef struct data
6. {
7.         int value;
8.         struct data* next;
9. }Sqlist;
10. int Length = 0;
11. Sqlist* Create()
12. {
13.         Sqlist* node = (Sqlist*)malloc(sizeof(Sqlist));
14.         Length++;
15.         return node;
16. }
17. Sqlist* Init()
18. {
19.         Sqlist* head;
20.         head = Create();
21.         head->value = 1;
22.         head->next = NULL;
23.         return head;
24. }
25. void Delete(Sqlist* head, int ith)
26. {
27.         Sqlist* t = head, * pre=head;
28.         int i = 1;
29.         while (i != ith && t != NULL)
30.         {
31.                 pre = t;t = t->next; i++;
32.         }
33.         pre->next = t->next;
34.         free(t); Length--;
35. }
36. void Insert(Sqlist* head, int ith, int data)
37. {
38.         Sqlist* t = head,*newnode = Create();
39.         int i = 1;
40.         while (i != ith && t != NULL)
41.         {
42.                 t = t->next; i++;
43.         }
44.         newnode->value = data;
45.         newnode->next = t->next;
46.         t->next = newnode;
47. }
48. int Locate(Sqlist* head, int Target)
49. {
50.         Sqlist* t = head; int pos=1;
51.         while (t != NULL)
52.         {
53.                 if (t->value == Target)return pos;
54.                 t = t->next; pos++;
55.         }
56.         return 0;
57. }
58. int Query(Sqlist* head, int pos)
59. {
60.         Sqlist* t = head;
61.         int i = 1;
62.         while (t != NULL && i != pos)
63.         {
64.                 t = t->next; i++;
65.         }
66.         return t->value;
67. }
68. void print(Sqlist* head)
69. {
70.         Sqlist* t = head;
71.         while (t != NULL)
72.         {
73.                 printf("%d ", t->value);
74.                 t = t->next;
75.         }
76.         puts("");
77. }
78. inline int read()
79. {
80.         char c = getchar(); int res = 0;
81.         while (c < '0' || c>'9')c = getchar();
82.         while (c >= '0' && c <= '9') {
83.                 res = (res << 1) + (res << 3) + (c - '0'); c = getchar();
84.         }
85.         return res;
86. }
87. void work()
88. {
89.         int q = read();
90.         Sqlist* L = Init();
91.         for (int i = 1; i <= q; ++i)
92.         {
93.                 int var = read(),x,y;
94.                 if (var == 1)
95.                 {
96.                         x = read(), y = read();
97.                         int pos= Locate(L, x);
98.                         Insert(L, pos, y);
99.                 }
100.                 if (var == 2)
101.                 {
102.                         x = read();
103.                         int pos=Locate(L, x);
104.                         if (pos == Length)printf("0\n");
105.                         else {
106.                                 printf("%d\n",Query(L,pos+1));
107.                         }
108.                 }
109.                 if (var == 3)
110.                 {
111.                         x = read();
112.                         int pos = Locate(L, x);
113.                         Delete(L, pos+1);
114.                 }
115.         }
116. }
117. int main()
118. {
119.         work();
120.         return 0;
121. }
122.   </stdlib.h></stdio.h>

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。