循环链表的结构和单链表结构一样,不过对于单链表,每个结点只存储了向后的指针,到了尾标志就停止了向后链的操作,这样知道某个结点却无法找到它的前驱结点。将单链表中的终端点的指针由NULL指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为循环单链表,简称循环链表。
在单链表中,最后一个节点的下一个指针(Next)指向第一个节点。
在双向链表中,最后一个节点的下一个指针(Next)指向第一个节点,第一个节点的前一个指针(Prev)指向在最后一个节点。
根据上面的说明,以下是要考虑的重点。
无论是单链列表还是双链表,最后一个链接的下一个指向(Next)列表的第一个链接。
如果是双向链接列表,则第一个链接的前一个指向(Prev)列表的最后一个。
以下是通告列表支持的重要操作。
插入 - 在列表的开头插入一个元素。
删除 - 从列表的开头删除一个元素。
显示 - 显示列表。
以下代码演示了基于单个链接列表的循环链接列表中的插入操作。
//insert link at the first location void insertFirst(int key, int data) { //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data= data; if (isEmpty()) { head = link; head->next = head; } else { //point it to old first node link->next = head; //point first to new first node head = link; } }
以下代码演示了基于单个链表的循环链表中的删除操作。
//delete first item struct node * deleteFirst() { //save reference to first link struct node *tempLink = head; if(head->next == head) { head = NULL; return tempLink; } //mark next to first link as first head = head->next; //return the deleted link return tempLink; }
下面的代码演示了循环链接列表中的显示列表操作。
//display the list void printList() { struct node *ptr = head; printf("\n[ "); //start from the beginning if(head != NULL) { while(ptr->next != ptr) { printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; } } printf(" ]"); }
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> struct node { int data; int key; struct node *next; }; struct node *head = NULL; struct node *current = NULL; bool isEmpty() { return head == NULL; } int length() { int length = 0; //if list is empty if(head == NULL) { return 0; } current = head->next; while(current != head) { length++; current = current->next; } return length; } //insert link at the first location void insertFirst(int key, int data) { //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if (isEmpty()) { head = link; head->next = head; } else { //point it to old first node link->next = head; //point first to new first node head = link; } } //delete first item struct node * deleteFirst() { //save reference to first link struct node *tempLink = head; if(head->next == head) { head = NULL; return tempLink; } //mark next to first link as first head = head->next; //return the deleted link return tempLink; } //display the list void printList() { struct node *ptr = head; printf("\n[ "); //start from the beginning if(head != NULL) { while(ptr->next != ptr) { printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; } } printf(" ]"); } void main() { insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf("Original List: "); //print list printList(); while(!isEmpty()) { struct node *temp = deleteFirst(); printf("\nDeleted value:"); printf("(%d,%d) ",temp->key,temp->data); } printf("\nList after deleting all items: "); printList(); }
Original List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ] Deleted value:(6,56) Deleted value:(5,40) Deleted value:(4,1) Deleted value:(3,30) Deleted value:(2,20) Deleted value:(1,10) List after deleting all items: [ ]
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)