数据结构&算法 循环链表

  • 循环链表

    循环链表是链表的一种变体,其中第一个元素指向最后一个元素,最后一个元素指向第一个元素。单链表和双链表都可以制成循环链表。
  • 单链表作为循环

    在单链表中,最后一个节点的下一个指针指向第一个节点。
  • 双向链表作为循环

    在双链表中,最后一个节点的下一个指针指向第一个节点,第一个节点的前一个指针指向最后一个节点,在两个方向上循环。
    根据上面的说明,以下是要考虑的重点。
    • 无论是单链列表还是双链表,最后一个链接的下一个都指向列表的第一个链接。
    • 如果是双向链接列表,则第一个链接的前一个指向列表的最后一个节点。
  • 基本操作

    以下是循环链表支持的基本操作。
    • 插入 -在列表的开头添加一个元素。
    • 删除 -删除列表开头的元素。
    • 显示 -显示列表。
  • 插入操作

    以下代码演示了基于单个链接列表的循环链接列表中的插入操作。
    
    insertFirst(data):
    Begin
       create a new node
       node -> data := data
       if the list is empty, then
          head := node
          next of node = head
       else
          temp := head
          while next of temp is not head, do
          temp := next of temp
          done
          next of node := head
          next of temp := node
          head := node
       end if
    End
    
  • 删除操作

    以下代码演示了基于单个链表的循环链表中的删除操作。-
    
    deleteFirst():
    Begin
       if head is null, then
          it is Underflow and return
       else if next of head = head, then
          head := null
          deallocate head
       else
          ptr := head
          while next of ptr is not head, do
             ptr := next of ptr
          next of ptr = next of head
          deallocate head
          head := next of ptr
       end if
    End
    
  • 显示列表操作

    下面的代码演示了循环链接列表中的显示列表操作。
    
    display():
    Begin
       if head is null, then
          Nothing to print and return
       else
          ptr := head
          while next of ptr is not head, do
             display data of ptr
             ptr := next of ptr
          display data of ptr
       end if
    End
    
  • 循环链表的C语言实现

    循环链表是链表的一种变体,其中第一个元素指向最后一个元素,最后一个元素指向第一个元素。单链表和双链表都可以制成循环链表。
     
    #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: 
    [ ]