单链表分析
对于单链表，由于每个结点只存储了向后的指针，到了尾部标识就停止了向后链的操作。按照这样的方式，只能索引后继结点不能索引前驱结点。
带来的问题
列如不从头结点出发，就无法访问到全部结点。
解决办法
将单链表终端结点的指针端由空指针改为指向头结点。
循环链表
定义
将单链表中终端结点的指针端有空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称单链表(circle linked list)
循环链表带有头结点的空链表：
循环链表带有头结点的空链表
循环链表带有头结点的非空链表:
循环链表带有头结点的非空链表
注意：并不是说循环链表一定要有头结点！
循环单链表和单链表的主要差异就在于循环的判断条件上：
- 原来是判断
p->next是否为null - 现在是
p->next是否等于头结点
但是循环链表进过改造，不用头指针，而是用指向终端结点的尾指针来表示循环链表，这样查找开始结点和终端结点都很方便。
终端结点用尾指针
rear表示，则查找终端结点是O(1),开始结点就是rear->next->next，时间复杂度也为O(1);
合并两个循环链表
-
图示
- 代码
LinkList Connect(LinkList A, LinkList B){
LinkList p = A->next; // 保存A表的头结点
A->next = B->next->next; // 将B表的开始结点链接到A表尾部
free(B); // 释放B表的头结点
B->next = p;
return B; // 返回新循环链表的尾指针
}
循环链表操作
循环链表创建和初始化
#include <stdio.h>
#include <stdlib.h>
/*链式存储结构的定义*/
typedef struct CLinkList{
int data;
struct CLinkList * next;
}node;
/**
* 1.初始化循环链表
*/
void ds_init(node **pNode){
int item;
node * temp;
node * target;
printf("输入结点的值，输入0完成初始化\n");
while (1) {
scanf("%d", &item);
fflush(stdin); // 清空输入缓存区
if (item == 0) return;
if ((*pNode) == NULL) {
// 链表中只有一个结点
*pNode = (node *)malloc(sizeof(struct CLinkList));
if (!(*pNode)) exit(0);
(*pNode)->data = item;
(*pNode)->next = *pNode;
}else{
//找到next指向第一个结点的结点
for (target = (*pNode); target->next != (*pNode); target = target->next);
// 生成一个新的结点
temp = (node *)malloc(sizeof(struct CLinkList));
if (!temp) exit(0);
temp->data = item;
temp->next = *pNode;
target->next = temp;
}
}
}
插入结点操作
/**
* 2.插入结点
* @param pNode 链表的第一个结点
* @param i 插入的位置
*/
void ds_insert(node **pNode, int i){
node * temp;
node * target;
node * p;
int item;
int j = 1;
printf("输入要插入加点的值:");
scanf("%d", &item);
if (i == 1) { // 插入到第一个位置
// 新插入的结点作为第一个结点
temp = (node *)malloc(sizeof(struct CLinkList));
if (!temp) exit(0);
temp->data = item;
//找到最后一个结点
for (target = (*pNode); target->next != (*pNode); target = target->next);
temp->next = (*pNode);
target->next = temp;
*pNode = temp;
}else{ // 插入到其他位置
target = *pNode;
for (; j<(i-1); j++) {
target = target->next;
}
temp = (node *)malloc(sizeof(struct CLinkList));
if (!temp) exit(0);
temp->data = item;
p = target->next;
target->next = temp;
temp->next = p;
}
}
删除结点操作
/**
* 3.删除结点
* @param pNode 链表的第一个结点
* @param i 删除的位置
*/
void ds_delete(node **pNode, int i){
node * target;
node * temp;
int j = 1;
if (i ==1) { // 删除的是第一个结点
// 找到最后一个结点
for (target = *pNode; target->next != *pNode; target = target->next);
temp = *pNode;
*pNode = (*pNode)->next;
target->next = *pNode;
free(temp);
}else{ // 删除其他结点
target = *pNode;
for (; j<i-1 ; j++) {
target = target->next;
}
temp = target->next;
target->next = temp->next;
free(temp);
}
}
返回结点所在位置
/**
* 4.返回结点所在位置
* @param pNode 链表的第一个结点
* @param elem 结点所在位置
*/
int ds_search(node *pNode, int elem){
node * target;
int i = 1;
for (target = pNode; target->data != elem && target->next != pNode; i++) {
target = target->next;
}
if (target->next == pNode) return 0; // 表中不存在该元素
else
return i;
}
遍历
/**
* 5.遍历
*/
void ds_traverse(node *pNode){
node * temp;
temp = pNode;
printf("*************链表中的元素**********\n");
do {
printf("%4d ", temp->data);
} while ((temp = temp->next) != pNode);
printf("\n");
}
在main()函数里面执行：
int main(int argc, const char * argv[]) {
node * pHead = NULL;
char opp = '\0';
int find;
printf("1.初始化链表\n \n2.插入结点 \n\n3.删除结点 \n\n4.返回结点位置 \n\n5.遍历链表 \n\n0.退出 \n\n选择你的操作：");
while (opp != '0') {
scanf("%c", &opp);
switch (opp) {
case '1':
ds_init(&pHead);
printf("\n");
ds_traverse(pHead);
break;
case '2':
printf("输入要插入结点的位置？");
scanf("%d", &find);
ds_insert(&pHead, find);
printf("在位置%d插入值后：\n",find);
ds_traverse(pHead);
printf("\n");
break;
case '3':
printf("输入需要删除的结点的位置？");
scanf("%d", &find);
ds_delete(&pHead, find);
printf("删除第%d个结点后:\n",find);
ds_traverse(pHead);
printf("\n");
break;
case '4':
printf("输入你要查找的结点的值？");
scanf("%d", &find);
printf("元素%d所在位置：%d\n",find, ds_search(pHead, find));
printf("\n");
break;
case '5':
ds_traverse(pHead);
printf("\n");
break;
case '0':
exit(0);
}
}
return 0;
}
运行效果
用循环链表解决约瑟夫问题
约瑟夫问题：
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
代码：
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node * next;
}node;
node * create(int n);
int main(int argc, const char * argv[]) {
int n = 41;
int m = 3;
int i;
node *p = create(n);
node * temp;
while (p != p->next) {
for (i = 1; i < m-1; i++) {
p = p->next;
}
printf("%d->",p->next->data);
temp = p->next; // 删除第m个结点
p->next = temp->next;
free(temp);
p = p->next;
}
printf("%d\n", p->data);
return 0;
}
/**
* 根据参数创建链表
*/
node * create(int n){
node * p = NULL;
node * head;
head = (node *)malloc(sizeof(node));
p = head; // p为指向当前结点的指针
node *s = NULL;
int i = 1;
if (n != 0) {
while (i <= n) {
s = (node *)malloc(sizeof(node));
s->data = i++; // 为循环链表初始化，第一个结点为1，第二个结点为2
p->next = s;
p = s;
}
s->next = head->next; // 最后一个结点指向第一个结点
}
free(head); // 删除头结点
return s->next;
}
打印结果
网友评论