1. 介绍
链表是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
链表相比于顺序表，在插入和删除元素时，效率要高很多。
每个数据单元叫做结点。由两部分组成：
①、数据域，存储数据值；
②、指针域，指向下一个数据单元。
链表
当多个结点通过指针指向，关联起来，就形成了一个链，即链表。
链式存储结构的特点：
①、比顺序存储结构的存储密度小（链式存储结构中每个结点都由数据域与指针域两部分组成，相比顺序存储结构增加了存储空间）。
②、逻辑上相邻的节点物理上不必相邻。
③、插入、删除灵活（不必移动节点，只要改变节点中的指针）。
④、查找节点时链式存储要比顺序存储慢。
⑤、每个节点是由数据域和指针域组成。
⑥、由于簇是随机分配的，这也使数据删除后覆盖几率降低，恢复可能提高。
2. 单链表
单链表就是沿着单方向的链表。
A -> B -> C -> D -> ... 按照顺序连下去，可以由 A 向后找其他元素，反之则不能。
单链表操作
/* 单链表结构。元素存放在动态分配的堆空间（非连续内存）
头结点索引为 -1。新增、删除的索引从 0 开始
*/
typedef struct Node {
int data;
struct Node * next;
int length; // 链表长度
} Node, Link;
/// 初始化单链表
void initLink(Link * link)
{
link->next = NULL;
link->length = 0;
}
/// 空单链表
bool isEmptyLink(Link * link)
{
return link->length == 0;
}
/// 插入
void inputLink(Link * link, int data, int index)
{
if (index < 0 || index > link->length)
return;
// 新增结点
Node * node = (Node *)malloc(sizeof(Node));
node->data = data;
// 上一个结点
Node * preNode = searchLink(link, index - 1);
// 下一个结点
Node * nextNode = preNode->next;
node->next = nextNode;
preNode->next = node;
link->length++;
}
/// 移除
bool outputLink(Link * link, int * data, int index)
{
if (isEmptyLink(link) || index < 0 || index >= link->length)
return NO;
// 上一个结点
Node * preNode = searchLink(link, index - 1);
// 当前结点
Node * curNode = preNode->next;
if (data != NULL)
*data = curNode->data;
// 下一个结点
Node * nextNode = curNode->next;
preNode->next = nextNode;
link->length--;
return YES;
}
/// 查找指定索引位置的结点
Node * searchLink(Link * link, int index)
{
if (index < 0)
return link; // 返回头结点
Node * node = link->next;
int i = 0;
while (node && node->next && i < index) {
node = node->next;
i++;
}
return node;
}
/// 打印单链表的内容
void printLink(Link * link)
{
if (isEmptyLink(link))
return;
Node * node = searchLink(link, 0);
while (node) {
printf("%d\t", node->data);
node = node->next;
}
printf("\r\n");
}
/// 调用
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int data = 0;
Link link = { 0 };
for (int i = 0; i < 9; i++) {
inputLink(&link, array[i], i);
}
printLink(&link);
inputLink(&link, 0, 5);
inputLink(&link, 0, 7);
printLink(&link);
outputLink(&link, &data, 4);
outputLink(&link, &data, 10); // 索引为 10 移除的是第 11 个内容
printLink(&link);
}
1 2 3 4 5 6 7 8 9
1 2 3 4 5 0 6 0 7 8 9
1 2 3 4 0 6 0 7 8 9
3. 双链表
双链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
双向链表操作
双链表结构：
typedef struct Node {
int data;
int length; // 链表长度
struct Node * parent;
struct Node * children;
} Node, Link;
4. 循环链表
它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
循环链表
5. 约瑟夫环
设编号为 1、2、… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
/// 约瑟夫环。k ∈[1, n] m >= 1
void josephusCircle(Link * link, int k, int m)
{
int index = k - 1;
while (!isEmptyLink(link)) {
int data = 0;
index = (index + m - 1) % link->length;
outputLink(link, &data, index);
printf("%d\t", data);
}
}
/// 调用
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
Link link = { 0 };
initLink(&link);
for (int i = 0; i < 9; i++) {
inputLink(&link, array[i], i);
}
josephusCircle(&link, 2, 1);
}
2 3 4 5 6 7 8 9 1
josephusCircle(&link, 2, 2);
3 5 7 9 2 6 1 8 4
josephusCircle(&link, 2, 3);
4 7 1 5 9 6 3 8 2
josephusCircle(&link, 9, 3);
2 5 8 3 7 4 1 6 9
josephusCircle(&link, 9, 9);
8 9 2 5 3 4 1 6 7
网友评论