循环链表设计与API实现
基本概念
循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素

循环链表拥有单链表的所有操作
新增功能:游标的定义
在循环链表中可以定义一个“当前”指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素。

循环链表新操作
将游标重置指向链表中的第一个数据元素
CircleListNode* CircleList_Reset(CircleList* list);
获取当前游标指向的数据元素
CircleListNode* CircleList_Current(CircleList* list);
将游标移动指向到链表中的下一个数据元素
CircleListNode* CircleList_Next(CircleList* list);
直接指定删除链表中的某个数据元素
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); // 根据元素的值 删除 元素 pk根据元素的位置 删除 元素
最后加了一个循环链表的应用:求解约瑟夫问题
约瑟夫问题-循环链表典型应用
n 个人围成一个圆圈,首先第 1 个人从 1 开始一个人一个人顺时针报数,报到第 m 个人,令其出列。然后再从下一 个人开始从 1 顺时针报数,报到第 m 个人,再令其出列,…,如此下去,求出列顺序。

代码:
// circlelist.h
// 循环链表API声明
#ifndef _CIRCLELIST_H_
#define _CIRCLELIST_H_
typedef void CircleList;
typedef struct _tag_CircleListNode
{
struct _tag_CircleListNode *next;
}CircleListNode;
// 创建链表
CircleList* CircleList_Create();
// 销毁链表
void CircleList_Destroy(CircleList* list);
// 清空链表
void CircleList_Clear(CircleList* list);
// 获取链表的长度
int CircleList_Length(CircleList* list);
// 在pos位置插入结点node
int CircleList_Insert(CircleList* list,CircleListNode* node, int pos);
// 获取pos位置的结点
CircleListNode* CircleList_Get(CircleList* list, int pos);
// 删除pos位置的结点
CircleListNode* CircleList_Delete(CircleList* list, int pos);
// 根据结点的值进行数据删除
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
// 重置游标
CircleListNode* CircleList_Reset(CircleList* list);
// 获取当前游标所指结点
CircleListNode* CircleList_Current(CircleList* list);
// 将原始游标所指结点返回给上层,然后让游标移到下一个结点
CircleListNode* CircleList_Next(CircleList* list);
#endif
// circlelist.cpp
// 循环链表API实现
#include <iostream>
#include <cstdio>
#include "circlelist.h"
typedef struct _tag_CircleList
{
CircleListNode header;
CircleListNode *silder;
int length;
}TCircleList;
// 创建链表
CircleList* CircleList_Create()
{
TCircleList *ret = (TCircleList *)malloc(sizeof(TCircleList));
if (ret == NULL) {
return NULL;
}
// 初始化
ret->header.next = NULL;
ret->silder = NULL;
ret->length = 0;
return ret;
}
// 销毁链表
void CircleList_Destroy(CircleList* list)
{
if (list == NULL) {
return;
}
free(list);
return;
}
// 清空链表
void CircleList_Clear(CircleList* list)
{
if (list == NULL) {
return;
}
TCircleList *tList = (TCircleList *)list;
tList->header.next = NULL;
tList->silder = NULL;
tList->length = 0;
return;
}
// 获取链表的长度
int CircleList_Length(CircleList* list)
{
if (list == NULL) {
return -1;
}
TCircleList *tList = (TCircleList *)list;
return tList->length;
}
// 在pos位置插入结点node
int CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
{
if (list == NULL || node == NULL || pos < 0) {
return -1;
}
TCircleList *tList = (TCircleList *)list;
CircleListNode *cur = (CircleListNode *)tList;
for (int i = 0; i < pos; ++i) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
// 如果是第一次插入
if (tList->length == 0) {
tList->silder = node;
}
++tList->length; // 记得长度加1
// 如果是头插法
if (cur == (CircleListNode *)tList) {
// 获取最后一个元素
CircleListNode *last = CircleList_Get(tList, tList->length - 1);
last->next = cur->next;
}
return 0;
}
// 获取pos位置的结点
CircleListNode* CircleList_Get(CircleList* list, int pos)
{
// 因为是循环链表,所以这里不需要排除pos>length的情况
if (list == NULL || pos < 0) {
return NULL;
}
TCircleList *tList = (TCircleList *)list;
CircleListNode *cur = (CircleListNode *)tList;
for (int i = 0; i < pos; ++i) {
cur = cur->next;
}
return cur->next;
}
// 删除pos位置的结点
CircleListNode* CircleList_Delete(CircleList* list, int pos)
{
TCircleList *tList = (TCircleList *)list;
CircleListNode *ret = NULL;
if (tList != NULL && pos >= 0 && tList->length > 0) {
CircleListNode *cur = (CircleListNode *)tList;
for (int i = 0; i < pos; ++i) {
cur = cur->next;
}
// 若删除头结点,需要求出尾结点
CircleListNode *last = NULL;
if (cur == (CircleListNode *)tList) {
last = CircleList_Get(tList, tList->length - 1);
}
ret = cur->next;
cur->next = ret->next;
--tList->length;
// 若删除头结点
if (last != NULL) {
tList->header.next = ret->next;
last->next = ret->next;
}
// 若删除的元素为游标所指的元素
if (tList->silder == ret) {
tList->silder = ret->next;
}
// 若删除元素后链表长度为0
if (tList->length == 0) {
tList->header.next = NULL;
tList->silder = NULL;
}
}
return ret;
}
// 根据结点的值进行数据删除
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
{
TCircleList *tList = (TCircleList *)list;
CircleListNode *ret = NULL;
if (list != NULL && node != NULL) {
CircleListNode *cur = (CircleListNode *)tList;
int i = 0;
for (i = 0; i < tList->length; ++i) {
if (cur->next == node) {
ret = cur->next;
break;
}
cur = cur->next;
}
// 如果找到
if (ret != NULL) {
CircleList_Delete(tList, i);
}
}
return ret;
}
// 重置游标
CircleListNode* CircleList_Reset(CircleList* list)
{
TCircleList *tList = (TCircleList *)list;
CircleListNode* ret = NULL;
if (list != NULL) {
tList->silder = tList->header.next;
ret = tList->silder;
}
return NULL;
}
// 获取当前游标所指结点
CircleListNode* CircleList_Current(CircleList* list)
{
TCircleList *tList = (TCircleList *)list;
CircleListNode* ret = NULL;
if (list != NULL) {
ret = tList->silder;
}
return ret;
}
// 将原始游标所指结点返回给上层,然后让游标移到下一个结点
CircleListNode* CircleList_Next(CircleList* list)
{
TCircleList *tList = (TCircleList *)list;
CircleListNode* ret = NULL;
if (list != NULL && tList->silder != NULL) {
ret = tList->silder;
tList->silder = ret->next;
}
return ret;
}
joseph.h
// 用循环链表API求解约瑟夫问题
#include <cstdio>
#include "circlelist.h"
const int maxp = 8;
struct Person
{
CircleListNode circlenode;
int id;
};
void joseph()
{
Person s[maxp];
for (int i = 0; i < maxp; ++i) {
s[i].id = i + 1;
}
CircleList *list = NULL;
list = CircleList_Create();
// 插入元素
for (int i = 0; i < maxp; ++i) {
// 尾插法
int ret = CircleList_Insert(list, (CircleListNode *)&s[i], CircleList_Length(list));
if (ret < 0) {
printf("function CircleList_Insert err: %d\n", ret);
}
}
// 遍历链表
for (int i = 0; i < CircleList_Length(list); ++i) {
Person *tmp = (Person *)CircleList_Get(list, i);
if (tmp == NULL) {
printf("function CircleList_Get err.\n");
}
printf("age: %d\n", tmp->id);
}
// 求解约瑟夫问题
while (CircleList_Length(list) > 0)
{
Person* pv = NULL;
for (int i = 1; i < 3; i++)
{
CircleList_Next(list);
}
pv = (Person*)CircleList_Current(list);
printf("%d ", pv->id);
CircleList_DeleteNode(list, (CircleListNode *)pv); //根据结点的值,进行结点元素的删除
}
printf("\n");
CircleList_Destroy(list);
}
main.cpp
// 循环链表测试程序
#include <iostream>
#include <cstdio>
#include "circlelist.h"
#include "joseph.h"
const int maxn = 5;
struct Student
{
CircleListNode circlenode;
char name[32];
int age;
};
void play01()
{
Student s[maxn];
for (int i = 0; i < maxn; ++i) {
s[i].age = i + 1;
}
CircleList *list = NULL;
list = CircleList_Create(); // 创建链表
// 插入元素
for (int i = 0; i < maxn; ++i) {
// 尾插法
int ret = CircleList_Insert(list, (CircleListNode *)&s[i], CircleList_Length(list));
if (ret < 0) {
printf("function CircleList_Insert err: %d\n", ret);
}
}
// 遍历链表
// 这里遍历打印两边,可以证明这是一个循环链表
for (int i = 0; i < 2 * CircleList_Length(list); ++i) {
Student *tmp = (Student *)CircleList_Get(list, i);
if (tmp == NULL) {
printf("function CircleList_Get err.\n");
}
printf("age: %d\n", tmp->age);
}
// 删除结点,通过结点位置
while (CircleList_Length(list)) {
Student *tmp = (Student *)CircleList_Delete(list, CircleList_Length(list) - 1);
if (tmp == NULL) {
printf("function CircleList_Delete err.\n");
}
printf("age: %d\n", tmp->age);
}
// 销毁链表
CircleList_Destroy(list);
}
int main()
{
play01(); // 为了测试数据的生命周期,所以另写一个函数调用运行
joseph();
return 0;
}
双向链表设计与API实现
为什么需要双向链表?
双向链表的定义
在单链表的结点中增加一个指向其前驱的pre指针

双向链表拥有单链表的所有操作
插入操作

插入操作异常处理
插入第一个元素异常处理
在0号位置处插入元素;
删除操作

双向链表的新操作
双向链表重要技术场景

循环链表插入结点技术场景

循环链表删除结点技术场景

优点:双向链表在单链表的基础上增加了指向前驱的指针
功能上双向链表可以完全取代单链表的使用
双向链表的Next,Pre和Current操作可以高效的遍历链表中的所有元素
缺点:代码复杂
代码示例:
dlinklist.h
// 双向链表API声明
#ifndef _DLINKLIST_H_
#define _DLINKLIST_H_
typedef void DLinkList;
typedef struct _tag_DLinkListNode
{
_tag_DLinkListNode *next;
_tag_DLinkListNode *pre;
}DLinkListNode;
// 创建链表
DLinkList* DLinkList_Create();
// 销毁链表
void DLinkList_Destroy(DLinkList *list);
// 清空链表
void DLinkList_Clear(DLinkList *list);
// 获取链表长度
int DLinkList_Length(DLinkList *list);
// 在pos位置,插入结点node
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos);
// 获取pos位置的结点,返回给上层
DLinkListNode* DLinkList_Get(DLinkList *list, int pos);
// 删除pos位置的结点
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos);
// 删除值为node的结点
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
// 重置游标
DLinkListNode* DLinkList_Reset(DLinkList* list);
// 获取当前游标所指的结点
DLinkListNode* DLinkList_Current(DLinkList* list);
// 获取游标当前所指结点,然后让游标指向下一个结点
DLinkListNode* DLinkList_Next(DLinkList* list);
// 获取游标当前所指结点,然后让游标指向前一个结点
DLinkListNode* DLinkList_Pre(DLinkList* list);
#endif
dlinklist.cpp
// 循环链表API实现
#include <cstdio>
#include <malloc.h>
#include "dlinklist.h"
typedef struct _tag_DLinkList
{
DLinkListNode header;
DLinkListNode *slider;
int length;
}TDLinkList;
// 创建链表
DLinkList* DLinkList_Create()
{
TDLinkList *ret = (TDLinkList *)malloc(sizeof(TDLinkList));
if (ret != NULL) {
ret->header.next = NULL;
ret->header.pre = NULL;
ret->slider = NULL;
ret->length = 0;
}
return ret;
}
// 销毁链表
void DLinkList_Destroy(DLinkList *list)
{
if (list != NULL) {
free(list);
}
return;
}
// 清空链表
void DLinkList_Clear(DLinkList *list)
{
TDLinkList *tList = (TDLinkList *)list;
if (tList != NULL) {
tList->header.next = NULL;
tList->header.pre = NULL;
tList->slider = NULL;
tList->length = 0;
}
return;
}
// 获取链表长度
int DLinkList_Length(DLinkList *list)
{
TDLinkList *tList = (TDLinkList *)list;
int ret = -1;
if (tList != NULL) {
ret = tList->length;
}
return ret;
}
// 在pos位置,插入结点node
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos)
{
TDLinkList *tList = (TDLinkList *)list;
int ret = -1, i = 0;
if (list != NULL && node != NULL && pos >= 0)
{
ret = 0;
DLinkListNode *cur = (DLinkListNode *)tList;
DLinkListNode *next = NULL;
for (i = 0; i < pos && cur->next != NULL; ++i) {
cur = cur->next;
}
next = cur->next;
cur->next = node;
node->next = next;
// 当链表插入第一个结点时需要进行特殊处理
if (next != NULL) {
next->pre = node;
}
node->pre = cur;
if (tList->length == 0) {
tList->slider = node; // 当链表插入第一个元素处理游标
}
// 若在0位置插入,需要特殊处理,新来的结点next前pre指向NULL
if (cur == (DLinkListNode *)tList) {
node->pre = NULL;
}
++tList->length;
}
return ret;
}
// 获取pos位置的结点,返回给上层
DLinkListNode* DLinkList_Get(DLinkList *list, int pos)
{
TDLinkList *tList = (TDLinkList *)list;
DLinkListNode* ret = NULL;
int i = 0;
if (list != NULL && pos >= 0 && pos < tList->length) {
DLinkListNode *cur = (DLinkListNode *)tList;
for (i = 0; i < pos; ++i) {
cur = cur->next;
}
ret = cur->next;
}
return ret;
}
// 删除pos位置的结点
DLinkListNode* DLinkList_Delete(DLinkList *list, int pos)
{
TDLinkList *tList = (TDLinkList *)list;
DLinkListNode* ret = NULL;
int i = 0;
if (tList != NULL && pos >= 0) {
DLinkListNode *cur = (DLinkListNode *)tList;
DLinkListNode *next = NULL;
for (i = 0; i < pos && cur->next != NULL; ++i) {
cur = cur->next;
}
ret = cur->next;
next = ret->next;
cur->next = next;
if (next != NULL) {
next->pre = cur;
if (cur == (DLinkListNode *)tList) { // 第0个位置,需要特殊处理
next->pre = NULL;
}
}
if (tList->slider == ret) {
tList->slider = next;
}
--tList->length;
}
return ret;
}
// 删除值为node的结点
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
{
TDLinkList *tList = (TDLinkList *)list;
DLinkListNode* ret = NULL;
int i = 0;
if (tList != NULL) {
DLinkListNode *cur = (DLinkListNode *)tList;
for (i = 0; i < DLinkList_Length(tList); ++i) {
if (cur->next == node) {
ret = cur->next;
break;
}
cur = cur->next;
}
if (!ret) {
DLinkList_Delete(tList, i);
}
}
return ret;
}
// 重置游标
DLinkListNode* DLinkList_Reset(DLinkList* list)
{
TDLinkList *tList = (TDLinkList *)list;
DLinkListNode* ret = NULL;
if (tList != NULL) {
tList->slider = tList->header.next;
ret = tList->slider;
}
return ret;
}
// 获取当前游标所指的结点
DLinkListNode* DLinkList_Current(DLinkList* list)
{
TDLinkList *tList = (TDLinkList *)list;
DLinkListNode* ret = NULL;
if (tList != NULL) {
ret = tList->slider;
}
return ret;
}
// 获取游标当前所指结点,然后让游标指向下一个结点
DLinkListNode* DLinkList_Next(DLinkList* list)
{
TDLinkList *tList = (TDLinkList *)list;
DLinkListNode* ret = NULL;
if (tList != NULL && tList->slider != NULL) {
ret = tList->slider;
tList->slider = ret->next;
}
return ret;
}
// 获取游标当前所指结点,然后让游标指向前一个结点
DLinkListNode* DLinkList_Pre(DLinkList* list)
{
TDLinkList *tList = (TDLinkList *)list;
DLinkListNode* ret = NULL;
if (tList != NULL && tList->slider != NULL) {
ret = tList->slider;
tList->slider = ret->pre;
}
return ret;
}
main.cpp
// 循环线表测试程序
#include <cstdio>
#include "dlinklist.h"
const int maxn = 5;
struct Student
{
DLinkListNode node;
int age;
};
void play()
{
Student s[maxn];
for (int i = 0; i < maxn; ++i) {
s[i].age = i + 21;
}
DLinkList *list = NULL;
list = DLinkList_Create(); // 创建链表
// 插入结点
for (int i = 0; i < maxn; ++i) {
int ret = DLinkList_Insert(list, (DLinkListNode *)&s[i], DLinkList_Length(list));
if (ret < 0) {
return;
printf("function DLinkList_Insert err.\n");
}
}
// 遍历链表
for (int i = 0; i < DLinkList_Length(list); ++i) {
Student *tmp = (Student *)DLinkList_Get(list, i);
if (tmp == NULL) {
printf("function DLinkList_Get err.\n");
return;
}
printf("age: %d\n", tmp->age);
}
DLinkList_Delete(list, DLinkList_Length(list) - 1); // 删除尾结点
DLinkList_Delete(list, 0); // 删除头结点
// 用游标遍历链表
for (int i = 0; i < DLinkList_Length(list); ++i) {
Student *tmp = (Student *)DLinkList_Next(list);
if (tmp == NULL) {
printf("function DLinkList_Next err.\n");
return;
}
printf("age: %d\n", tmp->age);
}
printf("\n");
DLinkList_Reset(list);
DLinkList_Next(list);
Student *tmp = (Student *)DLinkList_Current(list);
if (tmp == NULL) {
printf("function DLinkList_Current err.\n");
return;
}
printf("age: %d\n", tmp->age);
DLinkList_DeleteNode(list, (DLinkListNode*)tmp);
tmp = (Student *)DLinkList_Current(list);
if (tmp == NULL) {
printf("function DLinkList_Current err.\n");
return;
}
printf("age: %d\n", tmp->age);
printf("length: %d\n", DLinkList_Length(list));
DLinkList_Pre(list);
tmp = (Student *)DLinkList_Current(list);
if (tmp == NULL) {
printf("function DLinkList_Current err.\n");
return;
}
printf("age: %d\n", tmp->age);
printf("length: %d\n", DLinkList_Length(list));
DLinkList_Destroy(list);
return;
}
int main()
{
play();
return 0;
}