(Circular Linked Lists)

Presentation on theme: "(Circular Linked Lists)"— Presentation transcript:

1 (Circular Linked Lists)
環狀鏈結串列 (Circular Linked Lists)

2 定義 一個鏈結串列之最後一個節點指向鏈結串 列之最前端，則形成一個環狀鏈結串列， 如下圖所示：

3 基本運算與圖解

4 加入動作 加入節點於前端 當head = = NULL時 head = x; tail = x; x → next = x;

5 當head != NULL時 x → next = head; tail → next = x;

6 head= x;

7 加入節點於尾端 tail → next = x;

8 x → next = head; tail = x;

9 刪除動作 刪除節點於前端 tail → next = head → next; p = head; head =head → next ;
free(p); head= x; 加入節點於尾端 tail → next = x; x → next = head; tail = x;

10 基本運算之演算法及程式

11 加入動作 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;

12 if (ptr ->key < this ->key)
{ /*加入前端 ptr -> next = this; head = ptr; tail -> next = head; } else { while (this -> next != head) ptr = this; this = this ->next;

13 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;

14 刪除動作 計算環狀鏈結串列之長度 int Clength (NODE *CL ) /*此函數計算環狀鏈結串列之長度*/ {
int num=0; NODE *p; if (p != CL) { p=CL; do { num ++; p = p->next; } while (p != CL); } return(num);