//*******************************************************************
//*【程式名稱】: 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(); 
}