/* ======================================== */
/*    程式實例: 12_4.cpp                    */
/*    鏈結串列類別實作                      */
/* ======================================== */
#include <iostream.h>

struct llink                      /* 串列結構宣告      */
{  
    int data;                     /* 串列資料          */
    llink *next;                  /* 指向下一個資料    */ 
};

class linklist                    /* Linklist類別宣告  */
{
private:
    llink *first;                 /* 串列的開始指標    */
public:
    linklist() { first = NULL; }  /* 建構函數          */
    void insertNode(int d);       /* 成員函數的宣告    */
    void deleteNode(int d); 
    void printLlist();
    int search(int d);
};

/* ---------------------------------------- */
/*  成員函數: 在串列開頭插入節點            */
/* ---------------------------------------- */
void linklist::insertNode(int d)
{
    /* 建立節點記憶體 */
    llink *newnode = new llink;

    newnode->data = d;            /* 建立節點內容      */
    newnode->next = first;        /* 連結節點          */
    first = newnode;              /* 指向新節點        */
}

/* ---------------------------------------- */
/*  成員函數: 刪除指定資料的節點            */
/* ---------------------------------------- */
void linklist::deleteNode(int d)
{
    llink *current = first;       /* 建立目前的串列指標 */
    llink *last= current;         /* 建立前一個串列指標 */

    if ( current == NULL )        /* 檢查串列是否是空的 */
       return;
    else{
       while ( current != NULL )  /* 走訪串列節點的回路 */
       {
           /* 是否找到資料且是第一個節點 */
	   if (current->data == d && current == first )
           {
	      first = current->next; /* 重設串列指標    */
              delete current;        /* 釋放串列節點    */
              return; 
           }     /* 是否找到資料且不是第一個節點 */
	   else if (current->data == d && current != first )
           {
                /* 前一個指標連接下一個指標 */
		last->next = current->next;
                delete current;      /* 釋放串列節點    */
                return;
	   }
           else
		last = current;    /* 保留前一個串列指標 */
	   current = current->next;/* 下一個節點         */
       }
    }
}

/* ---------------------------------------- */
/*  成員函數: 走訪搜尋指定的資料            */
/* ---------------------------------------- */
int linklist::search(int d){
    llink *current = first;       /* 建立目前的串列指標 */

    while ( current != NULL )     /* 搜尋主回路         */
    {
	if ( current->data == d ) /* 是否找到資料       */
           return 1;              /* 找到               */
	current = current->next;  /* 下一個節點         */
    }
    return 0;                     /* 沒有找到           */
}

/* ---------------------------------------- */
/*  成員函數: 列印串列資料                  */
/* ---------------------------------------- */
void linklist::printLlist()
{
    llink *current = first;       /* 建立目前的串列指標 */

    while ( current != NULL )     /* 列印主回路         */
    {
        /* 列印節點資料 */
	cout << "[" << current->data << "]";
	current = current->next;  /* 下一個節點         */
    }
    cout << "\n";
}

/* ---------------------------------------- */
/*  主程式: 建立串列物件和測試成員函數      */
/* ---------------------------------------- */
void main()
{
    linklist Li;                    /* 建立物件           */
    int i,temp;
    int llist[6] = { 1, 2, 3, 4, 5, 6 }; /* 陣列內容      */

    for ( i = 0; i < 6; i++ )       /* 建立串列節點的回路 */
        Li.insertNode(llist[i]);    /* 插入節點           */

    cout << "原來的鏈表: ";
    Li.printLlist();                /* 列印原來串列       */

    cout << "請輸入節點內容: ";     /* 輸出字串           */
    cin >> temp;                    /* 輸入節點資料       */
    /* 搜尋指定的節點資料 */
    if ( Li.search(temp) ) 
       cout << "鏈表包含節點[" << temp << "]!\n";
    Li.deleteNode(temp);            /* 刪除節點           */
    cout << "刪除后的鏈表: ";
    Li.printLlist();                /* 列印刪除後串列     */
}