算法之链表2

# 链表基础知识介绍 链表是一种常见的数据结构，它通过节点之间的指针链接来存储数据。与数组不同，链表中的元素在内存中不是连续存储的。 ## 链表的基本概念 ###1.节点结构 链表的基本单位是节点，每个节点包含两部分：-**数据域**：存储实际的数据-**指针域**：存储指向下一个节点的地址 在C语言中，链表节点通常定义为： ```cstructnode{intdata;// 数据域structnode*next;// 指针域，指向下一个节点};

2. 链表的类型

• 单向链表：每个节点只有一个指向下一个节点的指针
• 双向链表：每个节点有指向前一个和后一个节点的指针
• 循环链表：尾节点指向头节点，形成环状结构

3. 链表的操作

1. 创建链表：初始化头指针，逐个添加节点
2. 插入节点：在指定位置插入新节点
3. 删除节点：移除指定位置的节点
4. 遍历链表：从头节点开始，依次访问每个节点
5. 查找节点：按值或位置查找特定节点

4. 链表的优缺点

优点：

• 动态大小，无需预先分配固定空间
• 插入和删除操作效率高（O(1)时间复杂度）
• 内存利用率高

缺点：

• 访问元素需要从头遍历（O(n)时间复杂度）
• 需要额外的内存空间存储指针
• 不支持随机访问

5. 链表 vs 数组

下面是一个完整的C语言链表操作示例：

#include<stdio.h>
#include<string.h>
#include<stdlib.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;
else
next = 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;
}