文章目录

• 循环单链表的一些基本概念
• • 头结点
  • • 头结点的定义
    • 头结点目的
  • 尾指针
  • • 尾指针的定义
    • 尾指针的作用
• 循环单链表的相关声明
• • 二级指针
• 循环单链表的定义
• 循环单链表的基本通用操作
• • 1、初始化循环单链表
  • 2、循环单链表是否为空
  • 3、创建新结点
  • 4、查找指定位置上的元素
  • 5、在指定位置上插入结点
  • 6、在首部插入新结点
  • 7、在尾部插入新结点
  • 8、删除指定位置上的结点
  • 9、从头部删除元素
  • 10、从尾部删除结点
  • 11、修改特定位置上的元素
  • 12、得到表长
  • 13、清空链表

循环单链表的一些基本概念

头结点

头结点的定义

头结点是链表中的第一个结点，其数据域一般无意义（有时可存放链表长度等）。

头结点目的

统一链表的操作。使得空表时的操作不用特殊处理，简化了链表的操作。

尾指针

尾指针的定义

尾指针是指向链表尾结点的指针。

尾指针的作用

用来找到整个链表。
减少时间复杂度。链表的插入删除操作一般在表尾进行操作，头指针因为一开始指向头结点，要找到尾结点的时间复杂度为O(n)，而尾指针指向的就是尾结点，所以找到尾结点的时间复杂度为O(1)。

循环单链表的相关声明

#pragma once#include#include#include#includestruct Node;typedef struct Node* PtrToNode;typedef PtrToNode CircList;// 表示指向链表的指针typedef PtrToNode Position;// 表示指向结点的指针typedef int ElemType;// 数据类型// 结点的定义typedef struct Node {ElemType element;Position next;}Node;void InitList(CircList* pprear);bool IsEmptyList(CircList rear);Position CreateNode(ElemType elem);Position GetElem(CircList rear, int pos);void InsertElem(CircList* pprear, int pos, ElemType elem);void PushFront(CircList* ppRear, ElemType elem);void PushBack(CircList* ppRear, ElemType elem);ElemType DeleteElem(CircList* ppRear, int pos);ElemType PopFront(CircList* ppRear);ElemType PopBack(CircList* ppRear);void ModifyElem(CircList rear, int pos, ElemType elem);int GetLength(CircList rear);void ClearList(CircList* ppRear);// 非通用型Position FirstSameElem(CircList rear, int elem);int FirstSameElemPos(CircList rear, int elem);int RemoveFirstSameElem(CircList* ppRear, ElemType elem);void HeadInsert(CircList* ppRear);bool InputInteger(int* elem);void Print(CircList L);

二级指针

二级指针是指向指针的指针**，用来在函数中改变指针的位置。
在带有尾指针的循环单链表中尾指针始终是指向尾结点的，所以当尾结点发生改变时，如插入，删除等操作改变了尾结点，那么就要传入二级指针移动尾指针。

循环单链表的定义

struct Node;// 先定义结点的结构体，不创建模板typedef struct Node* PtrToNode;typedef PtrToNode CircList;// 表示指向链表的指针typedef PtrToNode Position;// 表示指向结点的指针typedef int ElemType;// 链表的数据类型// 结点结构体的定义typedef struct Node {ElemType element;Position next;}Node;

循环单链表的基本通用操作

1、初始化循环单链表

因为是循环链表，初始化时只有一个头结点，所以尾指针指向的是头结点，头结点指向的还是头结点。

void InitList(CircList* ppRear){(*ppRear) = (CircList)malloc(sizeof(Node));// 创建头结点并使尾指针指向头结点assert((*ppRear) != NULL);// 如果头结点创建失败则终止程序(*ppRear)->next = (*ppRear);// 使头结点的下一个还是头结点，形成循环}

2、循环单链表是否为空

单独写个函数，为了方便后面做特殊情况判断。

bool IsEmptyList(CircList rear){return rear->next == rear;// 如果头结点的下一个结点还是头结点那么就是空表}

3、创建新结点

单独写个创建新结点的函数方便以后插入相关的操作使用。

Position CreateNode(ElemType elem){Position node = (Position)malloc(sizeof(Node));// 创建新结点if (node == NULL)// 创建失败则提示并终止程序{puts("Creation failed.");exit(EXIT_FAILURE);}node->element = elem;// 为新节点赋值node->next = NULL;// 不知道新节点的下一个位置，所以暂时指向NULLreturn node;// 返回新结点地址}

4、查找指定位置上的元素

查找元素时会有两个错误
1、表为空表
2、查找的位置超出范围
所以要有这两个错误的处理
查找元素时有些特殊情况
1、查找位置为0时，因为pos为0，pos<0与count<pos都不成立，所以会直接返回头结点的位置
2、查找位置为表尾时count=pos，cur为尾结点，然后会跳出while循环，这时就会返回尾结点
（rear为尾结点，尾结点下一个是头结点）

Position GetElem(CircList rear, int pos){if (pos < 0)// 左越界判断{puts("Wrong position.");exit(EXIT_FAILURE);}Position cur = rear->next;// 从头结点开始找int count = 0;// 用来计数// 右越界判断：如果循环了一遍链表还没找到那就代表位置越界，则终止程序while (count < pos){cur = cur->next;count++;// 当找到头结点时，说明已经循环完一遍链表但还没找到，代表越界了if (cur == rear->next){puts("Wrong position.");exit(EXIT_FAILURE);}}return cur;// 返回位置结点}

5、在指定位置上插入结点

插入结点需要知道插入位置的前驱结点，这样才能将新结点连接上链表，而上面写的查找指定位置的元素函数就能帮我们做到。

void InsertElem(CircList* ppRear, int pos, ElemType elem){Position prec = GetElem((*ppRear), pos - 1);// 查找前驱结点目的是为了将新结点连接上链表Position newnode = CreateNode(elem);// 创建新结点newnode->next = prec->next;// 将新节点连接上链表prec->next = newnode;if (prec == *ppRear)// 如果新节点的位置是在最后一位那么要移动尾指针指向新节点(*ppRear) = newnode;}

6、在首部插入新结点

要注意：如果是空表的情况要移动一次尾指针

void PushFront(CircList* ppRear, ElemType elem){Position newNode = CreateNode(elem);// 创建一个新节点newNode->next = (*ppRear)->next->next;// 使新节点指向首元结点(*ppRear)->next->next = newNode;// 使首结点指向新节点，新节点变为新的首元结点// 对空表插入后只有头结点和第一个结点，此时尾指针指向头结点，这时候需要将尾指针移动到第一个结点上if ((*ppRear)->next->next == *ppRear)*ppRear = (*ppRear)->next;}

7、在尾部插入新结点

每次在尾部插入新结点时都要移动尾指针

void PushBack(CircList* ppRear, ElemType elem){Position newNode = CreateNode(elem);// 创建一个新节点newNode->next = (*ppRear)->next;// 使新节点指向首元结点(*ppRear)->next = newNode;// 使尾结点指向新结点(*ppRear) = newNode;// 移动尾指针}

8、删除指定位置上的结点

要检查该链表是否为空表和越界问题
注意：当要删除的结点是尾结点的下一个时，GetElem函数不会报错，而是会返回尾结点，所以要做特殊越界处理

ElemType DeleteElem(CircList* ppRear, int pos){if (IsEmptyList(*ppRear))// 空表则中断程序{puts("The list is empty.");exit(EXIT_FAILURE);}Position prec = GetElem(*ppRear, pos - 1);// 找到将被删除的结点的前驱节点// 如果前驱结点为最后一个时GetElem函数不会报错，所以要做特殊处理if (prec == (*ppRear)){puts("Wrong position.");exit(EXIT_FAILURE);}Position cur = prec->next;// 标记要被删除的结点ElemType elem = cur->element;// 标记要被删除的元素if (cur == (*ppRear))// 如果被删除的结点是最后一个时就要移动尾指针指向他*ppRear = prec;prec->next = cur->next;// 将前驱结点与被删除结点的后继结点连接在一起free(cur);// 删除（释放）结点return elem;// 返回被删除的元素}

9、从头部删除元素

ElemType PopFront(CircList* ppRear){if (IsEmptyList(*ppRear))// 空表则中断程序{puts("The list is empty.");exit(EXIT_FAILURE);}Position cur = (*ppRear)->next->next;// 标记将被删除的首元结点ElemType elem = cur->element;// 标记将被删除的元素(*ppRear)->next->next = cur->next;// 将首元结点改为将被删除的结点的后一个if (cur == (*ppRear))// 如果链表中只有一个结点，那么要将指针重新指向头结点*ppRear = (*ppRear)->next;free(cur);// 删除（释放）结点return elem;// 返回被删除的元素}

10、从尾部删除结点

每次删除结点时都要找到尾结点的前驱结点，并且移动尾指针指向它

ElemType PopBack(CircList* ppRear){if (IsEmptyList(*ppRear))// 空表则中断程序{puts("The list is empty.");exit(EXIT_FAILURE);}Position prec = (*ppRear)->next;Position cur = (*ppRear);// 标记将被删除的尾结点ElemType elem = (*ppRear)->element;while (prec->next != (*ppRear))// 找到尾结点的前驱节点prec = prec->next;prec->next = (*ppRear)->next;// 将尾结点的前驱结点与头结点连接变为新的尾结点*ppRear = prec;// 使尾指针指向新的尾结点free(cur);// 删除（释放）结点return elem;}

11、修改特定位置上的元素

要做空表判断
pos为0时的结点为头结点，GetElem函数不会报错，所以要特殊处理

void ModifyElem(CircList rear, int pos, ElemType elem){if (IsEmptyList(rear))// 空表则中断程序{puts("The list is empty.");exit(EXIT_FAILURE);}if (pos == 0)// 左越界判断{puts("Wrong position.");exit(EXIT_FAILURE);}Position cur = GetElem(rear, pos);// 找到该结点cur->element = elem;// 修改值}

12、得到表长

要做空表判断
结点从首元结点开始找，如果找到头结点就代表找完一遍了

int GetLength(CircList rear){if (IsEmptyList(rear))// 空表则中断程序{puts("The list is empty.");exit(EXIT_FAILURE);}Position cur = rear->next->next;// 标记首元结点int length = 0;// 用来计数while (cur != rear->next)// 找到头结点时代表找完一遍，结束循环{cur = cur->next;length++;}return length;}

13、清空链表

要做空表判断
借用尾指针找到一个元素，用cur记录这个元素，尾指针指向下一个元素，再释放cur，直到尾指针重新指向头结点
最后使头结点指向头结点形成空表

void ClearList(CircList* ppRear){if (IsEmptyList(*ppRear))// 空表则中断程序{puts("The list is empty.");exit(EXIT_FAILURE);}Position head = (*ppRear)->next;// 记录头结点位置*ppRear = head->next;// 将指针移动到首元结点// 记录指针指向的结点，让指针指向下一个结点，释放被记录的结点，直到指针指向头结点while ((*ppRear) != head){Position cur = (*ppRear);*ppRear = cur->next;free(cur);}(*ppRear)->next = (*ppRear);// 变回只有头结点的循环单链表}