单循环链表：将单链表中终端结点的next域由空指针改为指向头结点，就使得整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。
如下图所示
单循环链表
1.循环链表和单链表的主要差异在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next是否为头结点
2.选择不用头指针，而是用指向终端结点的尾指针rear来表示循环链表，则查找开始结点和终端结点都很方便快捷
LinkList_cycle.h
#pragma once
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
//数据类型
typedef int ElemType;
typedef struct LNode
{
ElemType data;
LNode* next;
}LNode, * LinkList_cycle;
//初始化链表
Status InitList_cycle(LinkList_cycle& L);
//判空
bool ListEmpty_cycle(LinkList_cycle L);
//销毁单链表（包括头结点在内的所有结点）
Status DestroyList_cycle(LinkList_cycle& L);
//遍历单循环链表
void ListTraverse_cycle(LinkList_cycle L);
//头插法建立单循环链表（返回尾指针）
LinkList_cycle CreateList_cycle_H(LinkList_cycle& L_H, int n);
//尾插法建立单循环链表（返回尾指针）
LinkList_cycle CreateList_cycle_T(LinkList_cycle& L_T, int n);
//合并两个用尾指针表示的单循环链表,合并后将另一个销毁
void Connect(LinkList_cycle& rear_H, LinkList_cycle& rear_T);
LinkList_cycle.cpp
#include "LinkList_cycle.h"
#include <iostream>
using namespace std;
//初始化链表
Status InitList_cycle(LinkList_cycle& L)
{
L = new LNode;
L->next = L; //与单链表不同的是其头结点的next域指向头结点，而单链表的情况是指向NULL
cout << "初始化循环链表成功" << endl;
return OK;
}
//判空
bool ListEmpty_cycle(LinkList_cycle L)
{
if (L) //头结点存在
{
if (L->next == L) //第一个结点不存在
{
cout << "循环链表为空" << endl;
return true;
}
else
{
cout << "循环链表不为空" << endl;
return false;
}
}
else
{
cout << "循环链表不存在" << endl;
return true;
}
}
//销毁单循环链表（包括头结点在内的所有结点）
//需要根据头结点判断循环结束条件，先删除除头结点之外的所有结点，再删除头结点
Status DestroyList_cycle(LinkList_cycle& L)
{
LNode* p = L->next; //第一个结点
LNode* q;
while (p != L) //结束条件为p=头结点
{
q = p->next;
delete p;
p = q;
}
delete L;
cout << "销毁成功" << endl;
return OK;
}
//遍历单循环链表
void ListTraverse_cycle(LinkList_cycle L)
{
LNode* p = L->next;
while (p != L)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//头插法建立单循环链表,并返回此链表的尾指针
LinkList_cycle CreateList_cycle_H(LinkList_cycle& L_H, int n)
{
L_H = new LNode;
L_H->next = L_H; //单循环链表空表
LNode* rear = L_H; //开始时尾指针指向头结点
for (int i = n; i > 0; i--)
{
LNode* p = new LNode; //建立新结点
p->data = i;
p->next = L_H->next; //新结点的next域指向原来头结点的next域指向的结点
L_H->next = p; //头结点的next域指向新结点
if (p->next == L_H) //如果p的next域指向的结点为头结点
{
rear = p; //更新尾指针
}
}
return rear;
}
//尾插法建立单循环链表（返回尾指针）
LinkList_cycle CreateList_cycle_T(LinkList_cycle& L_T, int n)
{
L_T = new LNode;
L_T->next = L_T; //单循环链表的空表
LNode* rear = L_T; //记录尾指针，开始就为头结点
for (int i = 1; i <= n; i++)
{
LNode* p = new LNode; //建立新结点
p->data = i + 5;
p->next = rear->next; //新结点指向头结点，即尾指针的next域指向的结点
rear->next = p; //原来尾指针指向的next域为新结点
rear = p; //尾指针更新为指向新结点
}
return rear;
}
两个单循环链表合并：
合并
1.保存第一个链表的头结点
2.第一个链表尾指针的next域指向第二个链表的第一个结点
3.第二个链表的尾指针的next域指向第一个链表的头结点
//合并两个用尾指针表示的单循环链表到第一个链表中
void Connect(LinkList_cycle& rear_H, LinkList_cycle& rear_T)
{
LinkList_cycle L_H = rear_H->next; //第一个链表的头结点
rear_H->next = rear_T->next->next; //第一个链表的尾指针的next域指向第二个链表的第一个结点
rear_T->next = L_H; //第二个链表的尾指针指向第一个链表的头结点
cout << "合并成功" << endl;
}
main.cpp
测试：
#include "LinkList_cycle.h"
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
LinkList_cycle L;
InitList_cycle(L); //初始化单循环链表
ListEmpty_cycle(L); //判空
DestroyList_cycle(L); //销毁
LinkList_cycle L_H;
LNode* rear_H = CreateList_cycle_H(L_H, 5); //头插法创建
ListTraverse_cycle(L_H); //遍历
cout << "单循环链表第一个结点:" << rear_H->next->next->data << endl;
LinkList_cycle L_T;
LNode* rear_T = CreateList_cycle_T(L_T, 5); //尾插法创建
ListTraverse_cycle(L_T); //遍历
cout << "单循环链表第一个结点:" << rear_T->next->next->data << endl;
Connect(rear_H, rear_T); //合并两个链表到rear_H中
ListTraverse_cycle(rear_T->next); //遍历合并后的链表
ListTraverse_cycle(L_H); //遍历合并后的链表
DestroyList_cycle(L_T); //销毁第二个链表
return 0;
}
网友评论