循环链表
对于单链表, 由于每个结点只存储了向后的指针, 到了尾部标识就停止了向后链的操作也就是说, 按照这样的方式, 只能索引后继结点不能索引前驱结点
这会带来什么问题呢?
例如不从头结点出发, 就无法访问到全部结点
事实上要解决这个问题也并不麻烦, 只需要将单链表中终端结点的指针端由空指针改为指向头结点, 问题就结了
一定义
将单链表中终端结点的指针端由空指针改为指向头结点, 就使整个单链表形成一个环, 这种头尾相接的单链表成为单循环链表, 简称循环链表
循环链表. png
注: 这里并不是说循环链表一定要有头结点
循环链表和单链表的主要差异就在于循环的判断空链表的条件上:
原来判断 head->next 是否为 null,
现在则是 head->next 是否等于 head
由于终端结点用尾指针 rear 指示, 则查找终端结点是 O(1),
而开始结点是 rear->next->next, 当然也是 O(1)
二代码实现
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. 插入部分:
- /* 链表存储结构的定义 */
- typedef struct CLinkList
- {
- int data;
- struct CLinkList *next;
- }node;
- /* 插入结点 *$* 参数: 链表的第一个结点, 插入的位置 */
- 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;
- }
- // target 指向第三个元素的
- temp = (node *)malloc(sizeof(struct CLinkList));
- if(!temp)
- exit(0);
- temp->data = item;
- p = target->next;
- target->next = temp;
- temp->next = p;
- }
- }
3. 删除部分:
- /* 删除结点 */
- 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. 返回结点所在位置:
- /* 返回结点所在位置 */
- 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;
- }
完整程序:
- #include <stdio.h>
- #include <stdlib.h>
- /* 链表存储结构的定义 */
- typedef struct CLinkList
- {
- int data;
- struct CLinkList *next;
- }node;
- /************************************************************************$* 操作 *$************************************************************************$* 初始化循环链表 */
- 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;
- }
- }
- }
- /* 插入结点 *$* 参数: 链表的第一个结点, 插入的位置 */
- 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;
- }
- }
- /* 删除结点 */
- 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);
- }
- }
- /* 返回结点所在位置 */
- 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;
- }
- /* 遍历 */
- void ds_traverse(node *pNode)
- {
- node *temp;
- temp = pNode;
- printf("*********** 链表中的元素 ******************\n");
- do
- {
- printf("M", temp->data);
- }while((temp = temp->next) != pNode);
- printf("\n");
- }
- int main()
- {
- node *pHead = NULL;
- char opp;
- 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));
- //ListTraverse(L);
- printf("\n");
- break;
- case '5':
- ds_traverse(pHead);
- printf("\n");
- break;
- case '0':
- exit(0);
- }
- }
- return 0;
- }
三约瑟夫问题:
用循环链表模拟约瑟夫问题, 把 41 个人自杀的顺序编号输出
代码实现:
- //n 个人围圈报数, 报 m 出列, 最后剩下的是几号?
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct node
- {
- int data;
- struct node *next;
- }node;
- node *create(int n)
- {
- node *p = NULL, *head;
- head = (node*)malloc(sizeof (node ));
- p = head;
- node *s;
- int i = 1;
- if( 0 != n )
- {
- 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 ;
- }
- int main()
- {
- int n = 41;
- int m = 3;
- int i;
- node *p = create(n);
- node *temp;
- m %= n; // m 在这里是等于 2
- 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;
- }
编号为 1~N 的 N 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数, 可以自由输入), 开始人选一个正整数作为报数上限值 M, 从第一个人按顺时针方向自 1 开始顺序报数, 报道 M 时停止报数报 M 的人出列, 将他的密码作为新的 M 值, 从他顺时针方向上的下一个人开始从 1 报数, 如此下去, 直至所有人全部出列为止
代码实现:
- #include <stdio.h>
- #include <stdlib.h>
- #define MAX_NODE_NUM 100
- #define TRUE 1U
- #define FALSE 0U
- typedef struct NodeType
- {
- int id;
- int cipher;
- struct NodeType *next;
- } NodeType;
- /* 创建单向循环链表 */
- static void CreaList(NodeType **, const int);
- /* 运行 "约瑟夫环" 问题 */
- static void StatGame(NodeType **, int);
- /* 打印循环链表 */
- static void PrntList(const NodeType *);
- /* 得到一个结点 */
- static NodeType *GetNode(const int, const int);
- /* 测试链表是否为空, 空为 TRUE, 非空为 FALSE */
- static unsigned EmptyList(const NodeType *);
- int main(void)
- {
- int n, m;
- NodeType *pHead = NULL;
- while (1)
- {
- printf("请输入人数 n(最多 %d 个):", MAX_NODE_NUM);
- scanf("%d", &n);
- printf("和初始密码 m:");
- scanf("%d", &m);
- if (n> MAX_NODE_NUM)
- {
- printf("人数太多, 请重新输入!\n");
- continue;
- }
- else
- break;
- }
- CreaList(&pHead, n);
- printf("\n------------ 循环链表原始打印 -------------\n");
- PrntList(pHead);
- printf("\n------------- 删除出队情况打印 -------------\n");
- StatGame(&pHead, m);
- }
- static void CreaList(NodeType **ppHead, const int n)
- {
- int i, iCipher;
- NodeType *pNew, *pCur;
- for (i = 1; i <= n; i++)
- {
- printf("输入第 %d 个人的密码:", i);
- scanf("%d", &iCipher);
- pNew = GetNode(i, iCipher);
- if (*ppHead == NULL)
- {
- *ppHead = pCur = pNew;
- pCur->next = *ppHead;
- }
- else
- {
- pNew->next = pCur->next;
- pCur->next = pNew;
- pCur = pNew;
- }
- }
- printf("完成单向循环链表的创建!\n");
- }
- static void StatGame(NodeType **ppHead, int iCipher)
- {
- int iCounter, iFlag = 1;
- NodeType *pPrv, *pCur, *pDel;
- pPrv = pCur = *ppHead;
- /* 将 pPrv 初始为指向尾结点, 为删除作好准备 */
- while (pPrv->next != *ppHead)
- pPrv = pPrv->next;
- while (iFlag)
- {
- for (iCounter = 1; iCounter <iCipher; iCounter++)
- {
- pPrv = pCur;
- pCur = pCur->next;
- }
- if (pPrv == pCur)
- iFlag = 0;
- pDel = pCur; /* 删除 pCur 指向的结点, 即有人出列 */
- pPrv->next = pCur->next;
- pCur = pCur->next;
- iCipher = pDel->cipher;
- printf("第 %d 个人出列, 密码: %d\n", pDel->id, pDel->cipher);
- free(pDel);
- }
- *ppHead = NULL;
- getchar();
- }
- static void PrntList(const NodeType *pHead)
- {
- const NodeType *pCur = pHead;
- if (EmptyList(pHead))
- return;
- do
- {
- printf("第 %d 个人, 密码: %d\n", pCur->id, pCur->cipher);
- pCur = pCur->next;
- }
- while (pCur != pHead);
- getchar();
- }
- static NodeType *GetNode(const int iId, const int iCipher)
- {
- NodeType *pNew;
- pNew = (NodeType *)malloc(sizeof(NodeType));
- if(!pNew)
- {
- printf("Error, the memory is not enough!\n");
- exit(-1);
- }
- pNew->id = iId;
- pNew->cipher = iCipher;
- pNew->next = NULL;
- return pNew;
- }
- static unsigned EmptyList(const NodeType *pHead)
- {
- if(!pHead)
- {
- printf("The list is empty!\n");
- return TRUE;
- }
- return FALSE;
- }
四循环链表的特点
在单链表中, 我们有了头结点时, 我们可以用 O(1)的时间访问第一个结点, 但对于要访问最后一个结点, 我们必须要挨个向下索引, 所以需要 O(n)的时间
通过循环链表的特点, 用 O(1)的时间就可以由链表指针访问到最后一个结点
我们不用头指针, 而是用指向终端结点的尾指针来表示循环链表, 此时查找开始结点和终端结点都很方便了, 如图:
用尾指针表示循环链表. png
按照这个逻辑的话, 判断是否为空链表的条件则变为了:
判断 rear 是否等于 rear->next
循环链表的特点是无须增加存储量, 仅对链接方式稍作改变, 即可使得表处理更加方便灵活
题目: 实现将两个线性表 (a1,a2,,an) 和(b1,b2,,bm)连接成一个线性表 (a1,,an,b1,bm) 的运算
分析:
若在单链表或头指针表示的单循环表上做这种链接操作, 都需要遍历第一个链表, 找到结点 an, 然后将结点 b1 链到 an 的后面, 其执行时间是 O(n)
若在尾指针表示的单循环链表上实现, 则只需修改指针, 无须遍历, 其执行时间是 O(1)
操作示意图. png
第一步: 改变单链表 a 中的 rear(a), 使其不再指向其本身的头结点, 而是指向 b1;
第二步: 把 b 链表的头结点释放, 把 bn(尾结点)指向 a 链表的头;
代码实现:
- // 假设 A,B 为非空循环链表的尾指针
- LinkList Connect(LinkList A,LinkList B)
- {
- LinkList p = A->next; // 保存 A 表的头结点位置
- A->next = B->next->next; //B 表的开始结点链接到 A 表尾
- free(B->next); // 释放 B 表的头结点
- B->next = p;
- return B; // 返回新循环链表的尾指针
- }
五判断单链表中是否有环
有环的定义是, 链表的尾节点指向了链表中的某个节点
单链表中有环. png
要判断单链表中是否有环, 主要有以下两种方法
方法一:
使用 pq 两个指针, p 总是向前走, 但 q 每次都从头开始走, 对于每个节点, 看 p 走的步数是否和 q 一样如图, 当 p 从 6 走到 3 时, 用了 6 步, 此时若 q 从 head 出发, 则只需两步就到 3, 因而步数不等, 出现矛盾, 存在环
方法二:
使用 pq 两个指针, p 每次向前走一步, q 每次向前走两步, 若在某个时候 p == q, 则存在环
代码实现:
- #include "stdio.h"
- #define OK 1
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- typedef int Status;/* Status 是函数的类型, 其值是函数结果状态代码, 如 OK 等 */
- typedef int ElemType;/* ElemType 类型根据实际情况而定, 这里假设为 int */
- typedef struct Node
- {
- ElemType data;
- struct Node *next;
- }Node, *LinkList;
- /* 初始化带头结点的空链表 */
- Status InitList(LinkList *L)
- {
- *L = (LinkList)malloc(sizeof(Node)); /* 产生头结点, 并使 L 指向此头结点 */
- if(!(*L)) /* 存储分配失败 */
- return ERROR;
- (*L)->next=NULL; /* 指针域为空 */
- return OK;
- }
- /* 初始条件: 顺序线性表 L 已存在操作结果: 返回 L 中数据元素个数 */
- int ListLength(LinkList L)
- {
- int i=0;
- LinkList p=L->next; /* p 指向第一个结点 */
- while(p)
- {
- i++;
- p=p->next;
- }
- return i;
- }
- /* 随机产生 n 个元素的值, 建立带表头结点的单链线性表 L(头插法) */
- void CreateListHead(LinkList *L, int n)
- {
- LinkList p;
- int i;
- srand(time(0)); /* 初始化随机数种子 */*L = (LinkList)malloc(sizeof(Node));
- (*L)->next = NULL; /* 建立一个带头结点的单链表 */
- for (i=0; i <n; i++)
- {
- p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */
- p->data = rand()%100+1; /* 随机生成 100 以内的数字 */
- p->next = (*L)->next;
- (*L)->next = p; /* 插入到表头 */
- }
- }
- /* 随机产生 n 个元素的值, 建立带表头结点的单链线性表 L(尾插法) */
- void CreateListTail(LinkList *L, int n)
- {
- LinkList p,r;
- int i;
- srand(time(0)); /* 初始化随机数种子 */*L = (LinkList)malloc(sizeof(Node)); /* L 为整个线性表 */
- r = *L; /* r 为指向尾部的结点 */
- for (i=0; i <n; i++)
- {
- p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */
- p->data = rand()%100+1; /* 随机生成 100 以内的数字 */
- r->next=p; /* 将表尾终端结点的指针指向新结点 */
- r = p; /* 将当前的新结点定义为表尾终端结点 */
- }
- r->next = (*L)->next->next;
- }
- // 比较步数的方法
- int HasLoop1(LinkList L)
- {
- LinkList cur1 = L; // 定义结点 cur1
- int pos1 = 0; // cur1 的步数
- while(cur1)
- { // cur1 结点存在
- LinkList cur2 = L; // 定义结点 cur2
- int pos2 = 0; // cur2 的步数
- while(cur2)
- { // cur2 结点不为空
- if(cur2 == cur1)
- { // 当 cur1 与 cur2 到达相同结点时
- if(pos1 == pos2) // 走过的步数一样
- break; // 说明没有环
- else // 否则
- {
- printf("环的位置在第 %d 个结点处 \ n\n", pos2);
- return 1; // 有环并返回 1
- }
- }
- cur2 = cur2->next; // 如果没发现环, 继续下一个结点
- pos2++; // cur2 步数自增
- }
- cur1 = cur1->next; // cur1 继续向后一个结点
- pos1++; // cur1 步数自增
- }
- return 0;
- }
- // 利用快慢指针的方法
- int HasLoop2(LinkList L)
- {
- int step1 = 1;
- int step2 = 2;
- LinkList p = L;
- LinkList q = L;
- while (p != NULL && q != NULL && q->next != NULL)
- {
- p = p->next;
- if (q->next != NULL)
- q = q->next->next;
- printf("p:%d, q:%d \n", p->data, q->data);
- if (p == q)
- return 1;
- }
- return 0;
- }
- int main()
- {
- LinkList L;
- Status i;
- char opp;
- ElemType e;
- int find;
- int tmp;
- i = InitList(&L);
- printf("初始化 L 后: ListLength(L)=%d\n",ListLength(L));
printf("\n1. 创建有环链表(尾插法) \n2. 创建无环链表(头插法) \n3. 判断链表是否有环 \n0. 退出 \n\n 请选择你的操作:\n");
- while(opp != '0')
- {
- scanf("%c",&opp);
- switch(opp)
- {
- case '1':
- CreateListTail(&L, 10);
- printf("成功创建有环 L(尾插法)\n");
- printf("\n");
- break;
- case '2':
- CreateListHead(&L, 10);
- printf("成功创建无环 L(头插法)\n");
- printf("\n");
- break;
- case '3':
- printf("方法一: \n\n");
- if( HasLoop1(L) )
- {
- printf("结论: 链表有环 \ n\n\n");
- }
- else
- {
- printf("结论: 链表无环 \ n\n\n");
- }
- printf("方法二:\n\n");
- if( HasLoop2(L) )
- {
- printf("结论: 链表有环 \ n\n\n");
- }
- else
- {
- printf("结论: 链表无环 \ n\n\n");
- }
- printf("\n");
- break;
- case '0':
- exit(0);
- }
- }
- }
六魔术师发牌问题
问题描述: 魔术师利用一副牌中的 13 张黑牌, 预先将他们排好后叠放在一起, 牌面朝下对观众说: 我不看牌, 只数数就可以猜到每张牌是什么, 我大声数数, 你们听, 不信? 现场演示魔术师将最上面的那张牌数为 1, 把他翻过来正好是黑桃 A, 将黑桃 A 放在桌子上, 第二次数 1,2, 将第一张牌放在这些牌的下面, 将第二张牌翻过来, 正好是黑桃 2, 也将它放在桌子上这样依次进行将 13 张牌全部翻出, 准确无误
问题: 牌的开始顺序是如何安排的?
利用循环链表来解决: Magician.c
- #include <stdio.h>
- #include <stdlib.h>
- #define CardNumber 13
- typedef struct node
- {
- int data;
- struct node *next;
- }sqlist, *linklist;
- linklist CreateLinkList()
- {
- linklist head = NULL;
- linklist s, r;
- int i;
- r = head;
- for(i=1; i <= CardNumber; i++)
- {
- s = (linklist)malloc(sizeof(sqlist));
- s->data = 0;
- if(head == NULL)
- head = s;
- else
- r->next = s;
- r = s;
- }
- r->next = head;
- return head;
- }
- // 发牌顺序计算
- void Magician(linklist head)
- {
- linklist p;
- int j;
- int Countnumber = 2;
- p = head;
- p->data = 1; // 第一张牌放 1
- while(1)
- {
- for(j=0; j <Countnumber; j++)
- {
- p = p->next;
- if(p->data != 0) // 该位置有牌的话, 则下一个位置
- {
- p->next;
- j--;
- }
- }
- if(p->data == 0)
- {
- p->data = Countnumber;
- Countnumber ++;
- if(Countnumber == 14)
- break;
- }
- }
- }
- // 销毁工作
- void DestoryList(linklist* list)
- j
- }
- int main()
- {
- linklist p;
- int i;
- p = CreateLinkList();
- Magician(p);
- printf("按如下顺序排列:\n");
- for (i=0; i <CardNumber; i++)
- {
- printf("黑桃 %d", p->data);
- p = p->next;
- }
- DestoryList(&p);
- return 0;
- }
七拉丁方阵问题
拉丁方阵是一种 n×n 的方阵, 方阵中恰有 n 种不同的元素, 每种元素恰有 n 个, 并且每种元素在一行和一列中 恰好出现一次著名数学家和物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的符号, 拉丁方阵因此而得名
例如下图是一个 3×3 的拉丁方阵:
拉丁方阵. jpg
来源: http://www.jianshu.com/p/82049395149c