# 链表基础知识介绍 链表是一种常见的数据结构它通过节点之间的指针链接来存储数据。与数组不同链表中的元素在内存中不是连续存储的。 ## 链表的基本概念 ###1.节点结构 链表的基本单位是节点每个节点包含两部分-**数据域**存储实际的数据-**指针域**存储指向下一个节点的地址 在C语言中链表节点通常定义为 cstructnode{intdata;// 数据域structnode*next;// 指针域指向下一个节点};2. 链表的类型单向链表每个节点只有一个指向下一个节点的指针双向链表每个节点有指向前一个和后一个节点的指针循环链表尾节点指向头节点形成环状结构3. 链表的操作创建链表初始化头指针逐个添加节点插入节点在指定位置插入新节点删除节点移除指定位置的节点遍历链表从头节点开始依次访问每个节点查找节点按值或位置查找特定节点4. 链表的优缺点优点动态大小无需预先分配固定空间插入和删除操作效率高O(1)时间复杂度内存利用率高缺点访问元素需要从头遍历O(n)时间复杂度需要额外的内存空间存储指针不支持随机访问5. 链表 vs 数组特性数组链表内存分配连续非连续大小固定动态插入/删除效率低效率高访问随机访问(O(1))顺序访问(O(n))内存开销小较大需要指针下面是一个完整的C语言链表操作示例#includestdio.h#includestring.h#includestdlib.h//复习队列栈//struct queue//{// int data[1000];// int head;// int tail;//};//struct stack//{// char s[1000];// int top;//};struct node{int data;struct node* next;};int main(){/struct queue q;int i;q.head 1;q.tail 1;for (i 1;i 9;i) {scanf_s(“%d”, q.data[q.tail]);q.tail;}while (q.head q.tail){printf(%d , q.data[q.head]);q.head;q.data[q.tail] q.data[q.head];q.head;q.tail;}//*int i;char a[101];int mid, len, next;struct stack s;s.top 0;gets(a);len strlen(a);mid len / 2 - 1;for (i 0;i mid;i){s.s[s.top] a[i];}if (len % 2 0)next mid 1;elsenext mid 2;for (i next;i len - 1;i){if (a[i] ! s.s[s.top]) {break;} s.top--; } if (s.top 0) { printf(Yes); } else printf(No);*/ struct node* head, * p, * q, * t; int i, n, a; scanf_s(%d, n); head NULL; q NULL; for (i 1;i n;i) { scanf_s(%d, a); p (struct node*)malloc(sizeof(struct node));//malloc返回值是void*需要什么类型需要自己强制定义 p-data a; p-next NULL; if (head NULL) { head p; } else q-next p;//引入q,达到前后节点对比的效果 q p; } scanf_s(%d, a); t head; while (t ! NULL) { if (t-next-data a) { p (struct node*)malloc(sizeof(struct node)); p-data a;//假设57之间插入6 p-next t-next;//6指向5指向的7 t-next p;//5指向6 break; } t t-next; } t head; while (t ! NULL) { printf(%d , t-data); t t-next; }return 0;}
