数据结构与算法 循环链表

循环链表

1.初始化循环链表

结构体定义链表与单链表一样，初始化循环链表，不同之处在于循环链表就是在单链表的基础上，把最后一个节点的指针指向头节点的地址。

//结构体定义链表 typedef struct _LinkNode { int data; //数据域(存储数据) struct _LinkNode* next; //指针节点，指向(存储)下个链表节点的地址 }LinkNode, LinkList; 链表节点、链表 //初始化链表,定义头节点 bool InitLoopList(LinkList*& L) { //构造一个空的单链表 L L = new LinkNode; //创建新结点作为头结点，用头指针L指向头结点 if (!L) return false;//生成(分配内存失败)结点失败 L->next = L; //头结点的指针域指向本身,形成循环链 L->data = -1; return true; }

2.尾插法

通过循环找出最后一个节点，该节点指针域肯定会指向头节点地址，以此为条件可方便找出；后将新节点的指针指向头节点地址，最后一个节点的指针指向新节点地址。

//尾插法 bool ListInsert_back(LinkList*& L, LinkNode* node) { LinkNode* last = NULL; if (!L || !node) return false;//判断是否为空 if (L == L->next) { //判断头节点指针是否指向自己,若是,那么就是空链表 node->next = L;//新节点指针域指向头节点地址 L->next = node;//头节点指针域指向新节点地址 }else { //非空的循环链表 last = L->next;//让last指针指向第一个节点地址 //通过循环找出最后一个节点 while (last->next != L) last = last->next; node->next = L; //将新节点指针指向头节点地址 last->next = node; //将(循环找出的)最后一个节点指针指向新节点 //由此,新节点就成为了最后一个节点 } return true; }

3.打印循环链表

//打印循环链表 void LinkPrint(LinkList* L) { LinkList* p; if (!L || L == L->next) { //判断链表是否为空,空链表 cout << "链表为空!" << endl; return; } p = L->next; //将p指针指向第一个节点地址 while (p != L) { //判断该节点指针是否指向头节点,若是则结束 cout << p->data << "\t"; //输出该节点元素值 p = p->next; //使p指向下一个节点地址 } cout << endl; }

其他方法都与单链表大体相同，就不写一一入了!

完整代码

#include <iostream> #include <string> #include <stdlib.h> using namespace std; //结构体定义链表 typedef struct _LinkNode { int data; //数据域(存储数据) struct _LinkNode* next; //指针节点，指向(存储)下个链表节点的地址 }LinkNode, LinkList; 链表节点、链表 //初始化链表,定义头节点 bool InitLoopList(LinkList*& L) { //构造一个空的单链表 L L = new LinkNode; //创建新结点作为头结点，用头指针L指向头结点 if (!L) return false;//生成(分配内存失败)结点失败 L->next = L; //头结点的指针域指向本身,形成循环链 L->data = -1; return true; } //尾插法 bool ListInsert_back(LinkList*& L, LinkNode* node) { LinkNode* last = NULL; if (!L || !node) return false;//判断是否为空 if (L == L->next) { //判断头节点指针是否指向自己,若是,那么就是空链表 node->next = L;//新节点指针域指向头节点地址 L->next = node;//头节点指针域指向新节点地址 }else { //非空的循环链表 last = L->next;//让last指针指向第一个节点地址 //通过循环找出最后一个节点 while (last->next != L) last = last->next; node->next = L; //将新节点指针指向头节点地址 last->next = node; //将(循环找出的)最后一个节点指针指向新节点 //由此,新节点就成为了最后一个节点 } return true; } //打印循环链表 void LinkPrint(LinkList* L) { LinkList* p; if (!L || L == L->next) { //判断链表是否为空,空链表 cout << "链表为空!" << endl; return; } p = L->next; //将p指针指向第一个节点地址 while (p != L) { //判断该节点指针是否指向头节点,若是则结束 cout << p->data << "\t"; //输出该节点元素值 p = p->next; //使p指向下一个节点地址 } cout << endl; } int main(void) { LinkList* L; LinkList* s; //1.初始化一个空的新链表 if (InitLoopList(L)) { cout << "初始化链表成功！" << endl; } else { cout << "初始化链表失败！" << endl; exit(-1);//结束程序 } //2.尾插法 int n = 0; //要输入的元素个数 int i = 0; //元素下标 int num = 0; //输入元素存入 cout << "输入你插入的元素个数:"; cin >> n; while ((++i) <= n) { cout << "请输入第"<<i<<"个元素:"; cin >> num; //输入数据 s = new LinkList;//生成新节点 s->data = num; //将输入的数据存入新节点的数据域中 s->next = NULL; //新节点指针域设为空 if (ListInsert_back(L, s)) { cout << "插入成功!" << endl; }else { cout << "插入失败!" << endl; } } LinkPrint(L);//输出循环链表 system("pause"); return 0; }