C++ 程序实现循环单链表
c++programmingserver side programming
循环单链表是一种数据结构，由使用自引用结构创建的节点组成。每个节点包含两部分，即数据和对下一个列表节点的引用。
只需引用第一个列表节点即可访问整个链接列表。这称为头部。列表中的最后一个节点指向列表的头部或第一个节点。这就是它被称为循环链接表的原因。
下面给出了一个实现循环单链表的程序。
示例
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
struct Node *ptr = head;
newnode->data = newdata;
newnode->next = head;
if (head!= NULL) {
while (ptr->next != head)
ptr = ptr->next;
ptr->next = newnode;
} else
newnode->next = newnode;
head = newnode;
}
void display() {
struct Node* ptr;
ptr = head;
do {
cout<<ptr->data <<" ";
ptr = ptr->next;
} while(ptr != head);
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"循环链表为:";
display();
return 0;
}
输出
循环链表为:9 2 7 1 3
在上面的程序中，结构 Node 构成链表节点。它包含数据和指向下一个链表节点的指针。如下所示。
struct Node {
int data;
struct Node *next;
};
函数 insert() 将数据插入链表的开头。它创建一个新节点，并将数字插入新节点的数据字段中。如果 head 为 NULL，则 newnode 指向自身，否则循环链表中的最后一个节点指向 newnode。然后 head 指向列表的开头，即 newnode。如下所示。
void insert(int newdata) {
struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
struct Node *ptr = head;
newnode->data = newdata;
newnode->next = head;
if (head!= NULL) {
while (ptr->next != head)
ptr = ptr->next;
ptr->next = newnode;
} else
newnode->next = newnode;
head = newnode;
}
函数display()显示整个链表。首先ptr指向head。然后它不断转发到下一个节点，直到打印出所有节点的数据值。如下所示。
void display() {
struct Node* ptr;
ptr = head;
do {
cout<< ptr->data <<" ";
ptr = ptr->next;
} while(ptr != head);
}
在函数main()中，首先通过调用insert()将各种值插入到循环链表中。然后显示链接列表。如下所示。
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"循环链接列表为:";
display();
return 0;
}
