第3章顺序表的链式存储第3章顺序表的链式存储
⽬录
⼀、链式存储
解决问题：对于线性结构，使⽤顺序存储，需要⾜够⼤的连续存储区域
链式存储：结点除了存放信息，并且附设指针，⽤指针体现结点之间的逻辑关系
注：c语⾔的动态分配函数malloc()和free()分别实现内存空间的动态分配和回收，所以不必知道某个结点的具体地址注：链式存储中，必须有⼀个指针指向第⼀个结点的存储位置，⼀般为head标⽰
顺序存储和链式存储的区别：顺序存储更适合查询量⼤的程序设计；链式存储更适合需要频繁插⼊和删除的程序⼆、单链表
2.1 单链表的基本概念及描述
单链表结点构造：两个域，⼀个存放数据信息的info域；另⼀个指向该结点的后继结点的next域
2.2 单链表的实现
单链表的常⽤操作：
建⽴⼀个空的单链表
输出单链表中各个结点的值
在单链表中查找第i个结点
2.2.1 单链表的存储结构
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
2.2.2 单链表的插⼊操作（算法）
算法步骤（插⼊结点为p，插⼊到结点q后⾯）：
通过 find(head,i) 查找q结点，查不到打印报错信息
给插⼊结点p分配空间，并设置信息
如果在单链表的最前⾯插⼊新结点，让单链表的⾸指针指向新插⼊的结点
p->next = head;
head = p;
6. 如果在单链表中间插⼊新结点：
p->next = q->next;
q->next=p;
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
node *inrt(node *head, datatype x, int i) {
node *p, *q;
q = find(head, i); // 查找第i个结点
if (!q && i != 0) {
printf("\n找不到第%d个结点，不能插⼊%d！", i, x);
} el {
p = (node *) malloc(sizeof(node)); // 分配空间
p->info = x; // 设置新结点
if (i == 0) // 插⼊的结点作为单链表的第⼀个结点
{
p->next = head;
head = p;
} el {
p->next = q->next; // 后插
q->next = p;
}
}
return head;
}
2.2.3 单链表的删除操作（算法）
算法步骤（被删除结点q，被删除结点前⼀个结点pre）
判断链表是否为空
循环查找被删除结点q，并且设置⼀个结点pre标⽰被删除结点的前⼀个结点
如果删除结点为第⼀个结点
head = head->next;
free(p)
6. 如果删除结点为其他结点
Processing math: 100%
pre->next = q->next;
free(p)
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
node *dele(node *head, datatype x) {
node *pre = NULL, *p;
if (!head) {
printf("单链表是空的");
return head;
}
p = head;
while (p && p->info != x) // 寻找被删除结点p
{
pre = p; // pre指向p的前驱结点
p = p->next;
}
if (p) {
if (!pre) // 被删除结点没有上⼀个结点，则是要删除的是第⼀个结点
{
head = head->next;
} el {
英雄情结
pre->next = p->next;
}
free(p)
}
return head;
}
三、带头结点的单链表
童年的发现3.1 带头结点的单链表的基本概念及描述
头结点的作⽤：单链表的插⼊和删除需要对空的单链表进⾏特殊处理，因此可以设置head指针指向⼀个永远不会被删除的结点——头结点注：head指⽰的是所谓的头结点，它不是实际结点，第⼀个实际结点应该是 head->next 指⽰的
3.2 带头结点的单链表的实现
带头结点的单链表的常⽤操作：
建⽴⼀个空的带头结点的单链表
输出带头结点的单链表中各个结点的值
在带头结点的单链表中查找第i个结点
3.2.1 带头结点的单链表的存储结构
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
3.2.2 带头结点的单链表的插⼊（算法）
算法步骤（p为插⼊结点，q为插⼊前⼀个结点）：
通过 find(head,i) 查找带头结点的单链表中的第i个结点（i=0 表⽰新结点插⼊在头结点之后）
如果没找到结点q，打印报错信息
如果在⾮空的带头结点的单链表最前⾯插⼊⼀个新结点
p->next = q->next;
q->next = p;
6. 如果在⾮空的带头结点的单链表的内部插⼊⼀个新结点
p->next = q->next;
q->next = p;
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
node *inrt(node *head, datatype x, int i) {
node *p, *q;
q = find(head, i); // 查找带头结点的单链表中的第 i 个结点，i=0 时表⽰新结点插⼊在头结点之后
if (!q) // 没有找到
{
printf("\n带头结点的单链表中不存在第%d个结点！不能插⼊%d！", i, x);
return head;
}
p = (node *) malloc(sizeof(node)); // 为准备插⼊的新结点分配空间
p->info = x; // 为新结点设置值
p->next = q->next;
q->next = q; // i=0 时，本语句等价于 head->next=p
return head;
}
3.2.3 带头结点的单链表的删除（算法）
算法步骤（被删除结点为q，被删除结点的前⼀个结点为pre）：
设置pre指向头结点
q从带头结点的单链表的第⼀个实际结点开始循环寻找值为x的结点
删除带头结点的单链表的第⼀个实际结点：
pre->next = q->next;
free(q)
6. 删除带头结点的单链表的内部结点：
pre->next = q->next;
free(q)
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
node *dele(node *head, datatype x) {
node *pre = head, *q; // pre 指向头结点
q = head->next; // q 从带头结点的单链表的第⼀个实际结点开始找值为 x 的结点 while (q && q->info != x) // 循环查找值为 x 的结点
{
pre = q; // pre 指向 q 的前驱
q = q->next;
}
if (q) {
pre->next = q->next; // 删除
free(q); // 释放内存空间
}
return head;
}
四、循环单链表
4.1 循环单链表的基本概念及描述
单链表存在的问题：从表中的某个结点开始，只能访问该结点后⾯的结点
循环单链表解决的问题：从表中的任意⼀个结点开始，使其都能访问到表中的所有的结点
循环单链表：在单链表的基础上，设置表中最后⼀个结点的指针域指向表中的第⼀个结点
4.2 循环单链表的实现
循环单链表的常⽤操作：
建⽴⼀个空的循环单链表
获得循环单链表的最后⼀个结点的存储地址
输出循环单链表中各个结点的值
在循环单链表中查找⼀个值为x的结点
循环单链表的插⼊操作
循环单链表的删除操作
循环单链表的整体插⼊与删除操作
4.2.1 循环单链表的存储结构
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
五、双链表
5.1 双链表的基本概念及描述
双链表解决的问题：设置⼀个llink指针域，通过这个指针域直接找到每⼀个结点的前驱结点
5.2 双链表的实现
双链表的常⽤操作：
建⽴⼀个空的双链表
输出双链表中各个结点的值
查找双链表中第i个结点
双链表的插⼊操作
双链表的删除操作
5.2.1 双链表的存储结构
typedef int datatype;
任人唯亲typedef struct dlink_node {
datatype info;
struct dlink_node *llink, *rlink;
} dnode;
六、链式栈
6.1 链式栈的基本概念及描述
链式栈：使⽤链式存储的栈
注：链式栈的栈顶指针⼀般⽤top表⽰
6.2 链式栈的实现
链式栈的常⽤操作：
建⽴⼀个空的链式栈
判断链式栈是否为空
取得链式栈的栈顶结点值
输出链式栈中各个结点的值
向链式栈中插⼊⼀个值为x的结点
删除链式栈的栈顶节点
6.2.1 链式栈的存储结构
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
七、链式队列
7.1 链式队列的基本概念及描述
链式队列：使⽤链式存储的队列
注：队列必须有队⾸和队尾指针，因此增加⼀个结构类型，其中的两个指针域分别为队⾸和队尾指针7.2 链式队列的实现
链式队列的常⽤操作：
建⽴⼀个空的链式队列
判断链式队列是否为空
输出链式队列中各个结点的值
取得链式队列的队⾸结点值
向链式队列中插⼊⼀个值为x的结点
删除链式队列中的队⾸结点
7.2.1 链式队列的存储结构
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
} node;
typedef struct {
node *front, *rear; // 定义队⾸和队尾指针
} queue;
⼋、算法设计题
8.1 求单链表中结点个数（算法）
设计⼀个算法，求⼀个单链表中的结点个数
typedef struct node {
int data;
struct node *next;
} linknode;
typedef linknode *linklist;
厦门自助游攻略int count(linklist head) {
int c = 0;
linklist p = head; // head为实际的第⼀个结点
while (p) // 计数
{
c++;
p = p->next;
}
return c;
}
8.2 求带头结点的单链表中的结点个数（算法）
设计⼀个算法，求⼀个带头结点单链表中的结点个数
typedef struct node {
int data;
struct node *next;
} linknode;
typedef linknode *linklist;
int count(linlist head) {
int c = 0;
linklist = head->next; // head->next 为实际的第⼀个结点
while (p) // 计数
{
c++;
p = p->next;
}
return c;
}
乔克叔叔歌词
8.3 在单链表中的某个结点前插⼀个新结点（算法）
设计⼀个算法，在⼀个单链表中值为 y 的结点前⾯插⼊⼀个值为 x 的结点。即使值为 x 的新结点成为值为 y 的结点的前驱结点typedef struct node {
int data;
struct node *next;
} linknode;
typedef linknode *linklist;
void inrt(linklist head, int y, int c) {
linklist pre, p, s; // 假设单链表带头结点
pre = head;
p = head->next;
while (p && p->data != y) {
pre = p;
p = p->next;
}
if (p) // 找到了值为 y 的结点，即 p == y
{
干度s = (linklist) malloc(sizeof(linknode));党员思想工作汇报
s->data = x;
s->next = p;
pre->next = s;
}
}
8.4 判断单链表的各个结点是否有序（算法）
设计⼀个算法，判断⼀个单链表中各个结点值是否有序
typedef struct node {
int data;
struct node *next;
} linknode;
typedef linknode *linklist;
int issorted(linklist head, char c) // c='a' 时为升序，c='d' 时为降序
{
int flag = 1;
linklist p = head->next;
switch (c) {
ca 'a': // 判断带头结点的单链表 head 是否为升序
while (p && p->next && flag) {
if (p->data <= p->next->data) p = p->next;
el flag = 0;
}
你是我的信仰
break;
ca 'd': // 判断带头结点的单链表 head 是否为降序
while (p && p->next && flag) {
if (p->data >= p->next->data) p = p->next;
el flag = 0
}
break;
