(Circular Linked Lists) 環狀鏈結串列 (Circular Linked Lists)
定義 一個鏈結串列之最後一個節點指向鏈結串 列之最前端，則形成一個環狀鏈結串列， 如下圖所示：
基本運算與圖解
加入動作 加入節點於前端 當head = = NULL時 head = x; tail = x; x → next = x;
當head != NULL時 x → next = head; tail → next = x;
head= x;
加入節點於尾端 tail → next = x;
x → next = head; tail = x;
刪除動作 刪除節點於前端 tail → next = head → next; p = head; head =head → next ; free(p); head= x; 加入節點於尾端 tail → next = x; x → next = head; tail = x;
基本運算之演算法及程式
加入動作 void insert_node (struct node *ptr, struct node *head, struct node *tail) { struct node *prev; *this if (head = = NULL) { /*加入資料為第一筆 ptr -> next = ptr; head = ptr; tail = ptr; } this = head;
if (ptr ->key < this ->key) { /*加入前端 ptr -> next = this; head = ptr; tail -> next = head; } else { while (this -> next != head) ptr = this; this = this ->next;
if (ptr->key < this->key) { /*加入於特定節點*/ ptr ->next = this; prev ->next = ptr; break; } if (ptr->key >= tail->key) { /*加入尾端*/ ptr->next = head; this->next = ptr; tail = ptr;
刪除動作 計算環狀鏈結串列之長度 int Clength (NODE *CL ) /*此函數計算環狀鏈結串列之長度*/ { int num=0; NODE *p; if (p != CL) { p=CL; do { num ++; p = p->next; } while (p != CL); } return(num);