//******************************************************************* //*【程式名稱】: 3_singlelist.cpp * //*【程式功能】: 節點資料由小至大排序之單向鏈結串列的資料增刪與列印 * //*【資料結構】: singly linked list * //******************************************************************* //*【變數名稱及用途】 * //* struct node : 定義 node 為一個節點結構 * //* data : 用來儲存節點資料值 * //* next : 為一個 node 指標,它指向下一個節點 * //* class list : 定義 list 為一個串列類別 * //* head : 為一個 dummy node 指標,它指向單向鏈結串列的前端 * //* rear : 為一個 dummy node 指標,它指向單向鏈結串列的尾端 //* dummy node 請參考 Carrano 講義 第 4-31 頁(Figure 4.27) //******************************************************************* #include <iostream.h> #define N 6 // ------------------------------ // 定義 node 為一個節點結構 // ------------------------------ struct node{ // 定義一個單向鏈結節點結構 int data; // data 用來儲存節點資料值 node *next; // 為一個 node 指標,它指向下一個節點 }; // -------------------------------------- // 定義 list 為一個單向鏈結串列類別 // -------------------------------------- class list{ private: node *head; // head 為一個 node 指標,它指向單向鏈結串列的前端 node *rear; // rear 為一個 node 指標,它指向單向鏈結串列的尾端 public: list(); ~list(); bool empty(); void insert_node(int key); void delete_node(int key); void print(); void list::reverse(void); }; // --------------------------------------------------- // 產生一個空串列,它只有 head 及 rear 兩個節點 // --------------------------------------------------- list::list(void) // Constructor { head = new node; rear = new node; head->next = NULL; rear->next = NULL; } list::~list(void) // Destructor { node *cur_node, *temp_node; if(head->next != NULL){ cur_node = head->next; while(cur_node->next != NULL){ temp_node = cur_node; cur_node = cur_node->next; delete temp_node; } delete cur_node; } else; delete head; delete rear; } // ---------------------- // 判斷是否為空串列 // ---------------------- bool list::empty(void) { if(head->next == NULL) // 空串列 return true; else return false; } // -------------------------------------------------------- // 將資料(key)插入單向鏈結串列中,並按小至大順序排列 // -------------------------------------------------------- void list::insert_node(int key) { node *new_node, *prev_node, *cur_node; new_node = new node; new_node->data = key; new_node->next = NULL; if(empty()){ // 空串列,插入第一個節點到head之後 head->next = new_node; rear->next = new_node; } else{ cur_node = head->next; if(key < cur_node->data){ // 插入到串列之前端 head->next = new_node; // 參考Carrano講義第 4-18 頁 new_node->next = cur_node; // Figure 4.13 } else{ while(cur_node->next != NULL){ // 插入到串列中間 prev_node = cur_node; // 參考Carrano講義第 4-17 頁 cur_node = cur_node->next; // Figure 4.12 if(key < cur_node->data){ prev_node->next = new_node; new_node->next = cur_node; return; } else; } cur_node->next = new_node; // 插入到串列尾端 rear->next = new_node; // 參考Carrano講義第 4-19 頁 } // Figure 4.14 } } // ----------------------------------- // 自單向鏈結串列中刪除資料(key) // ----------------------------------- void list::delete_node(int key) { node *cur_node, *prev_node, *temp_node; prev_node = head; cur_node = head->next; while(cur_node->next != NULL){ // 當不是最後一個節點時 if(key == cur_node->data){ temp_node = cur_node; prev_node->next = cur_node->next; delete temp_node; return; } prev_node = cur_node; cur_node = cur_node->next; } if(key == cur_node->data){ // 判斷最後一個節點 temp_node = cur_node; prev_node->next = NULL; // 我們將最後一個節點的next指向NULL rear->next = prev_node; delete temp_node; } else cout << "... 找不到資料 " << key << endl; } // ------------------------------------- // 從 head 開始列印資料(由小至大) // ------------------------------------- void list::print(void) { node *cur_node; if(! empty()){ // 若非空串列 cur_node = head->next; cout << " ==> 串列內容為 : "; while(cur_node->next != NULL){ cout << cur_node->data << " -> "; cur_node = cur_node->next; } cout << cur_node->data << "\n"; } else cout << " !!! 空串列" << endl; } // ------------------------ // 將單向鏈結串列反轉 // ------------------------ void list::reverse(void) { node *prev_node, *cur_node, *next_node; next_node = head->next; cur_node = NULL; while(next_node->next != NULL){ prev_node = cur_node; cur_node = next_node; next_node = next_node->next; cur_node->next = prev_node; } next_node->next = cur_node; head->next = next_node; } void main(void) { int i; int a[N] = {5, 65, 31, 83, 78, 21}; list list_1; cout << endl << "【將資料插入單向鏈結串列,並保持資料由小至大之排序】..." << endl; for(i = 0; i < N; i++){ cout << endl << " 步驟 <" << i << "> 插入 " << a[i] << endl; list_1.insert_node(a[i]); list_1.print(); } cout << endl << "【刪除 5】..." << endl; list_1.delete_node(5); list_1.print(); cout << endl << "【刪除 83】..." << endl; list_1.delete_node(83); list_1.print(); cout << endl << "【刪除 31】..." << endl; list_1.delete_node(31); list_1.print(); cout << endl << "【將串列反轉】..." << endl; list_1.reverse(); list_1.print(); cout << endl << "【將串列反轉】..." << endl; list_1.reverse(); list_1.print(); }