單連結串列

概念：連結串列是一種物理儲存結構上非連續、非順序的儲存結構，資料元素的邏輯順序是通過連結串列中的指標連結次序實現的。

值得注意的是：

1.連結串列的在邏輯是連續的，物理上不一定是連續的；
2.現實中節點是從堆上申請的。

連結串列的實現

連結串列的單個結點的定義

就像這個圖一樣，一個空間用了存放資料（資料域），另一個空間用了存放下一個節點的地址（指標域）。

template <class DateType>
struct LinkNode
{
    //資料域
    DateType data;
    //指標域
    LinkNode<DateType>* next;
    //注意兩個事項：1.如果程式設計師提供了有參構造，那麼編譯器就不會提供預設的建構函式，但是會提供預設的拷貝構造
    //2.注意事項2：如果程式設計師提供了拷貝構造，那麼編譯器不會提供預設的建構函式和拷貝構造
    LinkNode(LinkNode<DateType> *ptr = NULL):next(ptr) {  }
    //struct的建構函式，預設引數構造, //函數參數列中的形參允許有預設值，但是帶預設值的引數需要放後面
    LinkNode(const DateType& item, LinkNode<DateType>* ptr = NULL)
    {
        next = ptr;
        data = item;
    }
};

連結串列的小框架

template <class DateType>
class LinkList
{
public:

private:
	//頭節點
    LinkNode<DateType>* head;
};

連結串列的介面

LinkList(); //建構函式,初始化為空連結串列
LinkList(const DateType &item);//有參構造，初始化頭節點
LinkList(const LinkList<DateType>& list);//拷貝構造,拷貝單連結串列
CreateLink(int n);//建立單連結串列
~LinkList();//解構函式,單連結串列的刪除
void PushBack(const DateType& data);//尾插
void PopBack();//尾刪
void PushFront(const DateType &data)；//頭插
void PopFront();//頭刪
int Length()const;//求單連結串列的長度
bool GetElem(int pos, DateType& data);//獲得pos位置的元素
LinkNode<DateType>* Locate(int pos);//返回連結串列中第pos個元素的地址，如果pos<0或pos超出連結串列最大個數返回NULL
bool Insert(int pos, const DateType &data);//在序號pos位置插入元素值為data的結點
bool Delete(int pos, DateType& data);//刪除pos位置的結點，並且返回結點
LinkNode<DateType>* Locate(int pos);//返回連結串列中第pos個元素的地址，如果pos<0或pos超出連結串列最大個數返回NULL
void Clear();//清空連結串列
void PrintList()const;//輸出單連結串列所有結點的元素值
void Exchangedata(int pos1, int pos2);//進行兩結點元素值的交換

構造和解構

1.無參建構函式：沒什麼好說的，用new從堆分配一個結點的空間給我們都頭結點指標，注意檢查堆是否滿是一個很好的習慣

2.含參建構函式：初始化頭節點指向第一個結點

3.解構函式（單連結串列的刪除）：單連結串列的刪除很簡單用兩個指標，從頭結點開始，一前一後依次釋放申請的記憶體即可

4.拷貝構造：操作都很簡單，依次分配記憶體拷貝連結即可，類似於連結串列的構建。區別在於拷貝構造還沒有LinkList物件，需要建立，而賦值已經有了LinkList物件，需要將其連結串列刪除再重新構造

    //建構函式,初始化為空連結串列
    LinkList()
    {
        head = new LinkNode<DateType>;
        if (head == NULL)
        {
            cout << "記憶體分配失敗" << endl;
            exit(-1);
        }
    }
    //有參構造，初始化頭節點
    LinkList(const DateType &item)
    {
        //LinkNode會呼叫建構函式，初始化結點內的內容
        head = new LinkNode<DateType>();
        LinkNode<DateType> *p = new LinkNode<DateType>(item);
        head->next = p;
        if (head == NULL)
        {
            cout << "記憶體分配失敗" << endl;
            exit(-1);
        }
    }
    //拷貝構造,拷貝單連結串列
    LinkList(const LinkList<DateType>& list)
    {
        LinkNode<DateType>* p = list.head->next;
        if (p == NULL)
        {
            cout << "記憶體分配失敗" << endl;
            exit(-1);
        }
        head = new LinkNode<DateType>;
        LinkNode<DateType>* h = head;
        while (p != NULL)
        {
            LinkNode<DateType>* t = new LinkNode<DateType>;
            h->next = t;
            t->data = p->data;
            p = p->next;
            h = h->next;
        }
    }
    //解構函式,單連結串列的刪除
    ~LinkList()
    {
        //申請一個指標指向頭節點
        LinkNode<DateType>* cur = head;
        LinkNode<DateType>* next;
        while (cur)
        {
            next = cur->next;
            delete cur;
            cur = next;
        } 
    }

尾插

首先，我們先來實現一個尾插的介面，尾插就是在連結串列的尾部插入一個節點。
在進行尾插的時候我們要考慮的幾點：

此時連結串列是否為空，如果為空我們應該怎麼做，不為空又應該怎麼做，這兩種情況我們要分開討論；
如何申請節點，是在堆上還是棧上？

為了更好的理解尾插，我們先看一個動圖展示：

void PushBack(const DateType& data)
   {
      LinkNode<DateType>* p = new LinkNode<DateType>(data);
      if (head->next == NULL)
      {
          head->next = p;
      }
      else
      {
          LinkNode<DateType>* cur = head;
          while (cur->next != NULL)
          {
              cur = cur->next;
          }
          cur->next = p;
      }
   }

建立單連結串列

首先定義一個指向Head的指標q；
然後不斷重複以下三個步驟完成單連結串列的構造：
①用new申請一個LinkNode的空間返回指標p，並輸入資料元素；
②q->next=p，將q指標對應結點的後繼修改為p；
③q=q->next,將指標指向其直接後繼，這樣一個結點就被連結進了連結串列之中

//建立單連結串列
    void CreateLink(int n)
    {
        LinkNode<DateType>* q = head;
        int* nodetemp = new int[n];
        for (size_t i = 0; i < n; i++)
        {
            cout << "Enter the element:  " << endl;
            cin >> nodetemp[i];
        }
        //尾插法
        for (size_t i = 0; i < n; i++)
        {
            LinkNode<DateType>* p = new LinkNode<DateType>;
            p->data = nodetemp[i];
            p->next = q->next;
            q->next = p;
            q = q->next;
        }
        delete[] nodetemp;
    }

尾刪

尾刪無非就是在連結串列的尾部刪除一個節點，聽起來很簡單，但是有很多細節是我們要注意的，我們要分三種情況來進行討論：

沒有節點
只有一個節點
兩個及兩個以上的節點

先看動圖演示：

//尾刪
void PopBack()
{
    //分三種情況
    //1.沒有結點
    if (head->next == NULL)
    {
        return;
    }
     //2.只有一個結點
    else if (head->next->next == NULL) {
        delete head->next;
        head->next= NULL;
     }
     //3.兩個以及兩個以上的結點
     else
     {
         LinkNode<DateType>* prev = NULL;
         LinkNode<DateType>* cur = head;
         while (cur->next != NULL)
         {
             prev = cur;
             cur = cur->next;
         }
         delete cur;
         cur = NULL;
         prev->next = NULL;
     }
}

頭插

先看動圖演示：

//頭插
void PushFront(const DateType &data)
{
    LinkNode<DateType>* p = new LinkNode<DateType>(data);
    p->next = head->next;
    head->next = p;
}

頭刪

頭刪就要分情況討論：

連結串列為空
連結串列不為空

先看動圖演示：

//頭刪
void PopFront()
{
     //分兩種情況
     if (head->next == NULL)
     {
         return;
     }
     else
     {
         LinkNode<DateType>* p = head->next;
         head->next = p->next;
         delete p;
         p = NULL;
    }
}

定位位置

封裝一個函數，返回第pos位置的地址，在下面用得到

//返回連結串列中第pos個元素的地址，如果pos<0或pos超出連結串列最大個數返回NULL
    LinkNode<DateType>* Locate(int pos)
    {
        int i = 0;
        LinkNode<DateType>* p = head;
        if (pos < 0)
            return NULL;
        while (NULL != p && i < pos)
        {
            p = p->next;
            i++;
        }
        return p;
    }