一十艾、線性表

線性表是一種抽象的數(shù)據(jù)類型抵代，下面介紹幾種具體的線性表存儲結(jié)構(gòu)（即物理結(jié)構(gòu)）：順序、鏈式和靜態(tài)鏈式忘嫉。無論線性表采用哪種數(shù)據(jù)結(jié)構(gòu)主守，她們的邏輯結(jié)構(gòu)是一樣的，都有以下性質(zhì)：除第一個元素外榄融，線性表中每個元素都有一個前驅(qū)元素参淫；除最后一個元素外，線性表中每一個元素都有一個后繼元素愧杯。

實現(xiàn)：

//線性表抽象類的定義
template<typename T>class AList
{
public:
  void ClearList();  //重置線性表為空表
  bool ListEmpty()const;  //若線性表為空表涎才，則返回 true；否則返回 false
  int LocateElem(T e, bool(*eq) (T, T))const;
  //返回第一個與 e 滿足關(guān)系 eq() 的數(shù)據(jù)元素的位序力九，若這樣的元素不存在枉氮，則返回值為 0
  bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const;
  //若 e 與表的某數(shù)據(jù)元素滿足定義的 eq() 相等關(guān)系邀杏，且該數(shù)據(jù)不是表中第一個，
  //則用 pre_e 返回它的前驅(qū)，否則操作失敗得封，pre_e 無定義
  bool NextElem(T e, bool(*eq) (T, T), T &next_e)const;
  //若 e 與表中的某數(shù)據(jù)元素滿足定義的 eq() 相等關(guān)系纵潦，且該數(shù)據(jù)不是表中最后一個店归，
  //則用 next_e 返回它的后繼仇哆，否則操作失敗，next_e 無定義
  bool ListDelete(int i, T &e);
  //刪除線性表第 i 個數(shù)據(jù)元素（1 <= i <= ListLength()）灾炭，并用 e 返回其值
  void ListTraverse(void(*visit) (T*))const;
  //依次對每個數(shù)據(jù)元素調(diào)用函數(shù) visit()
  virtual bool GetElem(int i, T &e)const=0;  //純虛函數(shù)
  //用 e 返回線性表第 i 個元素的值（1 <= i <= ListLength()）
  virtual bool ListInsert(int i, T e)=0;
  //在線性表第 i 個位置（1 <= i <= ListLength()）之前插入新的數(shù)據(jù)元素
  virtual int ListLength()const=0;  //返回線性表的長度茎芋，常成員函數(shù)，不改變對象的值
};

1. 順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)容易實現(xiàn)隨機查找線性表的第 i 個元素的操作蜈出，但在實現(xiàn)插入和刪除操作時要移動大量的數(shù)據(jù)元素田弥。所以，它適用于數(shù)據(jù)相對穩(wěn)定的線性表铡原。

實現(xiàn)：

//繼承 AList 的順序表類
template<typename T>class SqList: public AList<T>
{
  friend void MergeList(const SqList<T>&, const SqList<T>&, SqList<T>&);
  //聲明普通函數(shù) MerfeList() 為 SqList 類的友元
private:
  T *elem;  //線性表存儲空間的基址
  int length;  //線性表的當前表長
  int listsize;  //線性表當前的存儲容量
public:
  SqList(int k=1)
  {//構(gòu)造函數(shù)偷厦，動態(tài)生成具有 k 個初始存儲空間的空線性表
    elem = new T[k];
    assert(elem != NULL);  //存儲分配失敗商叹，退出
    length = 0;  //空表長度為 0
    listsize = k;  //初始存儲容量
  }
  ~SqList()
  {//析構(gòu)函數(shù)
    delete[] elem;  //釋放 elem 所指的存儲空間數(shù)組
  }
  void ClearList()
  {//重置線性表為空表
    length = 0;
  }
  bool ListEmpty()const  //常成員函數(shù)，不會改變對象的值
  {//若線性表為空表只泼，則返回 true沈自；否則返回 false
    return length == 0;
  }
  int ListLength()const
  {//返回線性表的長度
    return length;
  }
  bool GetElem(int i, T &e)const
  {//用 e 返回線性表第 i 個元素的值（1 <= i <= ListLength()）
    if (i < 1 || i > length)  //i 不再表的范圍之內(nèi)
      return false;
    e = *(elem + i - 1);  //將第 i 個元素的值賦給 e
    return true;
  }
  int LocateElem(T e, bool(*eq) (T, T))const
  {//返回第一個與 e 滿足關(guān)系 eq() 的數(shù)據(jù)元素的位序，若這樣的元素不存在辜妓，則返回值為 0
    int i = 1;  //i 的初值指第一個元素
    while(i <= length && !eq(*(elem + i - 1), e))
    //i 沒超出表的范圍且 i 指向的數(shù)據(jù)元素與 e 不滿足關(guān)系
      i++;  //計數(shù)加 1 ，繼續(xù)往后找
    if (i <= length)  //找到滿足關(guān)系的數(shù)據(jù)元素
      return i;  //返回其位序
    else  //沒找到滿足關(guān)系的數(shù)據(jù)元素
      return 0;
  }
  int PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
  {//若 e 與表的某數(shù)據(jù)元素滿足 eq() 關(guān)系忌怎，且該數(shù)據(jù)元素不是表中第一個籍滴，
   //則用 pre_e 返回它的前驅(qū)，否則操作失敗榴啸，pre_e 無定義
    int i = LocateElem(e, eq);  //將第一個滿足關(guān)系的數(shù)據(jù)元素的位序賦給 i
    if (i <= 1)  //沒找到孽惰，或是第一個元素
      return false;  //操作失敗
    else  //找到了值為 e 的元素，其位序為 i
    {
      pre_e = *(elem + i - 2);  //將前一個元素的值賦給 pre_e
      return true;  //操作成功
    }
  }
  bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
  {//若 e 與表的某數(shù)據(jù)元素滿足 eq() 關(guān)系鸥印，且該數(shù)據(jù)元素不是表中最后一個勋功，
   //則用 next_e 返回它的后繼，否則操作失敗库说，next_e 無定義
    int i = LocateElem(e, eq);
    if (i == 0 || i == length)  //沒找到狂鞋，或是最后一個元素
      return false;  
    else
    {
      next_e = *(elem + i);
      return true;
    }
  }
  bool ListInsert(int i, T e)
  {//在線性表第 i 個位置（1 <= i <= ListLength()）之前插入新的數(shù)據(jù)元素 e
    T *newbase, *q, *p;
    if (i < 1 || i > length)  //i 值不合法
      return false;
    if (length == listsize)  //當前存儲空間已滿
    {
      newbase = new T[listsize * 2];
      assert(newbase != NULL);  //存儲空間分配失敗，退出
      for (int j = 0; j < length; j++)
        *(newbase + j) = *(elem + j);  //將原表空間中的數(shù)據(jù)復制到新的表空間
      delete[] elem;  //釋放原表空間
      elem = newbase;  //新基址賦給 elem
      listsize *= 2;  //更新存儲容量
    }
    q = elem + i - 1;  // q 為插入位置
    for (p = elem + length - 1; p >= q; p--)  //插入位置之后的元素后移
      *(p + 1) = *p;
    *q = e;
    length++;
    return true;
  }
  bool ListDelete(int i, T &e)
  {//刪除線性表第 i 個元素（1 <= i <= ListLength()）潜的，并用 e 返回其值
    T *p, *q;
    if (i < 1 || i > length)  //i 值不合法
      return false;
    p = elem + i - 1;  //p 為被刪除元素的位置
    e = *p;
    q = elem + length -1;  //q 為表尾元素的位置
    for (++p; p <= q; ++p)  //被刪除元素之后的元素前移
      *(p - 1) = *p;
    length--;
    return true;
  }
  void ListTraverse(void(*visit) (T*))const;  
  {//依次對每個數(shù)據(jù)元素調(diào)用函數(shù) visit()
    for (int i = 0; i < length; i++)
      visit(elem + i);  //對每個數(shù)據(jù)元素調(diào)用 visit()
    cout << endl;
  }
};

2. 鏈式存儲

與順序存儲相比骚揍，鏈式存儲結(jié)構(gòu)在實現(xiàn)插入、刪除的操作時不需要移動大量數(shù)據(jù)元素啰挪，但是不容易實現(xiàn)隨機存取線性表的第 i 個數(shù)據(jù)元素的操作信不。所以，鏈式存儲結(jié)構(gòu)適用于經(jīng)常需要進行插入和刪除操作的線性表亡呵。

2.1 單鏈表

實現(xiàn)：

//單鏈表結(jié)點類型結(jié)構(gòu)體
template<typename T>struct LNode
{
  T data;  //結(jié)點數(shù)據(jù)類型
  LNode<T> *next;  //后繼指針
}抽活；

//單鏈表的類
template<typename T>class LinkList: public AList
{//帶模板并繼承 AList 的單鏈表類
  friend void MergeList(LinkList<T>&, LinkList<T>&);
protected:
  LNode<T> *Head;  //頭指針
public:
  LinkList()
  {//構(gòu)造函數(shù)，構(gòu)造一個空的線性表
    Head = new LNode<T>;  //產(chǎn)生頭結(jié)點
    assert(Head != NULL);  //存儲空間分配失敗锰什，退出
    Head->next = NULL;  //頭結(jié)點的指針為空
  }
  ~LinkList()
  {//析構(gòu)函數(shù)下硕，銷毀線性表
    ClearList();  //置為空表
    delete Head;  //釋放頭結(jié)點
  }
  void ClearList()const
  {//重置線性表為空
    LNode<T> *q, *p = Head->next;  //p 指向第一個結(jié)點
    Head->next = NULL;  //頭結(jié)點指針域為空
    while(!p = NULL)  //釋放其他結(jié)點
    {
      q = p->next;
      delete p;
      p = q;
    }
  }
  bool ListEmpty()const
  {//若線性表為空表，則返回 true汁胆，否則返回 false
    return Head->next == NULL;
  }
  int ListLength()const
  {//返回線性表的長度
    int i = 0;  //計數(shù)器初值為 0
    LNode<T> *p = Head->next;  //p 指向第一個結(jié)點
    while(p != NULL)  //沒到表尾
    {
      i++;
      p->next;
    }
    return i;
  }
  bool GetElem(int i, T &e)const
  {//當?shù)?i 個元素存在（1 <= i <= ListLength()）時卵牍，其值賦給 e 并返回 true ，
   //否則返回 false
    int j = 1;
    LNode<T> *p = Head->next;  //p 指向第一個結(jié)點
    while(p != NULL && j < i)  //順序查找
    {
      j++;
      p = p->next;
    }
    if (p == NULL || j > i)
      return false;
    e = p->data;
    return true;
  }
  int LocateElem(T e, bool(*eq) (T, T))const
  {//返回第一個與 e 滿足 eq() 關(guān)系的數(shù)據(jù)元素的位序沦泌，若這樣的元素不存在糊昙，則返回 0
    int i = 0;
    LNode<T> *p = Head->next;
    while(p != NULL)
    {
      i++;
      if (eq(p->data, e))
        return i;
      p = p->next;
    }
    return 0;
  }
  bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
  {//若 e 與表中的某數(shù)據(jù)元素滿足 eq() 關(guān)系，且該元素不是表中第一個谢谦，
   //則用 pre_e 返回它的前驅(qū)释牺，否則操作失敗萝衩，pre_e 無定義
    LNode<T> *p = Head->next;
    while(p != NULL && p->next != NULL)  //p 所指結(jié)點有后繼
    {
      q = p->next;
      if (eq(q->data, e))
      {
        pre_e = p->data;
        return true;
      }
      p = q;  //p 的后繼 q 不等于 e ，p 向后移
    }
    return false;
  }
  bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
  {//若 e 與表中某數(shù)據(jù)元素滿足 eq() 關(guān)系没咙，且該元素不是表中最后一個猩谊，
   //則用 next_e 返回它的后繼，否則操作失敗祭刚，next_e 無定義
    LNode<T> *p = Head->next;
    while(p != NULL && p->next != NULL)
    {
      if (eq(p->data, e))
      {
        next_e = p->next->data;
        return true;
      }
      p = p->next;
    }
    return false;
  }
  bool ListInsert(int i, T e)
  {//在帶頭結(jié)點的單鏈表中第 i 個位置（1 <= i <= ListLength()）之前插入新的數(shù)據(jù)元素 e
    int j = 0;
    LNode<T> *s, *p = Head;
    while(p != NULL && j < i-1)  //尋找第 i-1 個結(jié)點
    {
      j++;
      p = p->next;
    }
    if (p == NULL || j > i-1)  //i 小于 1 或者大于表長+1
      return false;
    s = new LNode<T>;  //生成新結(jié)點
    if (s == NULL)  //生成新結(jié)點失敗
      return false;  //插入失敗
    s->data = e;
    s->next = p->next;  //新結(jié)點指向原第 i 個結(jié)點
    p-next = s;  //原第 i-1 個結(jié)點指向新結(jié)點
    return true;  //插入成功
  }
  bool ListDelete(int i, T &e)const
  {//在帶頭結(jié)點的單鏈線性表中刪除第 i 個數(shù)據(jù)元素（1 <= i <= ListLength()）牌捷，
   //并用 e 返回其值
    int j = 0;
    LNode<T> *q, *p = Head;
    while(p->next != NULL && j < i-1)  //尋找第 i 個結(jié)點，并令 p 指向其前驅(qū)
    {
      j++;
      p = p->next;
    }
    if (p->next == NULL || j > i-1)  
      return false;
    q = p->next;  //q 指向刪除結(jié)點
    p->next = q->next;  //待刪結(jié)點的前驅(qū)指向待刪結(jié)點的后繼
    e = q->data;
    delete q;
    return true;
  }
  void ListTraverse(void(*visit) (T*))const
  {//依次對每個數(shù)據(jù)元素調(diào)用函數(shù) visit()
    LNode<T> *p = Head->next;
    while(p != NULL)
    {
      visit(&p->data);
      p = p->next;
    }
    cout << endl;
  }
};

2.2 單循環(huán)鏈表

單循環(huán)鏈表結(jié)點的存儲結(jié)構(gòu)和單鏈表結(jié)點的一樣涡驮，不同的是：單循環(huán)鏈表最后一個結(jié)點的指針域指向頭結(jié)點暗甥，而不是 NULL 。這樣捉捅，由表尾很容易找到表頭撤防。但若鏈表較長，則由表頭找到表尾仍較費時棒口。因而寄月，單循環(huán)鏈表往往設立尾指針而不是頭指針。這樣无牵，查找最后一個結(jié)點和頭結(jié)點都很方便漾肮。這在兩個鏈表首尾相連合并成一個鏈表時尤為方便。

實現(xiàn)：

//設立尾指針的單循環(huán)鏈表的類
template<typename T>class LinkListCy: public AList
{//帶模板并繼承 AList 的單循環(huán)鏈表類
  friend void MergeList(LinkListCy<T>&, LinkListCy<T>&);
private:
  LNode<T> *Tail;  //尾指針
public:
  LinkListCy()
  {//構(gòu)造函數(shù)茎毁，構(gòu)造一個空的線性表
    Tail = new LNode<T>;  //產(chǎn)生頭結(jié)點初橘，并使 Tail 指向此頭結(jié)點（尾指針指向頭結(jié)點）
    assert(Tail != NULL);  //存儲分配失敗，退出
    Tail->next = Tail;  //頭結(jié)點的指針域指向頭結(jié)點
  }
  ~LinkListCy()
  {//析構(gòu)函數(shù)充岛，銷毀線性表
    ClearList();  //將線性表重置為空表
    delete Tail;  //釋放頭結(jié)點
  }
  void ClearList()
  {//將線性表重置為空表
    LNode<T> *p, *q;
    Tail = Tail->next;  //Tail 指向頭結(jié)點
    p = Tail->next;  //p 指向第一個結(jié)點
    while(p != Tail)  //沒到表尾
    {
      q = p->next;
      delete p;
      p = q;
    }
    Tail->next = Tail;  //頭結(jié)點指針域指向自身
  }
  bool ListEmpty()const
  {//若線性表為空表保檐，則返回 true ；否則返回 false
    return Tail->next==Tail;  
  }
  int ListLength()const
  {//返回線性表中數(shù)據(jù)元素個數(shù)
    int i = 0;
    LNode<T> *p = Tail->next;  //p指向頭結(jié)點
    while(p != Tail)
    {
      i++;
      p = p->next;
    }
    return i;
  }
  bool GetElem(int i, T &e)const
  {//在第 i 個元素存在時崔梗，其值賦給 e 并返回 true 夜只；否則返回 false
    int j = 1;
    LNode<T> *p = Tail->next->next;  //p 指向第一個結(jié)點
    if (i <= 0 || i > ListLength())
      return false;
    while(j < i)
    {
      j++;
      p = p->next;
    }
    e = p->data;
    return true;
  }
  int LocateElem(T e, bool(*eq) (T, T))const
  {//返回第一個與 e 滿足 eq() 關(guān)系的數(shù)據(jù)元素的位序，若這樣的元素不存在蒜魄，則返回 0
    int i = 0;
    LNode<T> *p = Tail->next->next;  //p 指向第一個結(jié)點
    while(p != Tail->next)
    {
      i++;
      if (eq(p->data, e))
        return i;
      p = p->next;
    }
    return 0;
  }
  bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
  {//若 e 與表中的某數(shù)據(jù)元素滿足 eq() 關(guān)系扔亥，且該元素不是表中第一個，
   //則用 pre_e 返回它的前驅(qū)谈为，否則操作失敗旅挤，pre_e 無定義
    LNode<T> *q, *p = Tail->next->next;  //p 指向第一個結(jié)點
    q = p->next;
    while(q != Tail->next)  
    {
      if (eq(q->data, e))
      {
        pre_e = p->data;
        return true;
      }
      p = q;  //p 的后繼 q 不等于 e ，p 向后移
      q = q->next;
    }
    return false;
  }
  bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
  {//若 e 與表中某數(shù)據(jù)元素滿足 eq() 關(guān)系伞鲫，且該元素不是表中最后一個粘茄，
   //則用 next_e 返回它的后繼，否則操作失敗，next_e 無定義
    LNode<T> *p = Tail->next->next;
    while(p != Tail)
    {
      if (eq(p->data, e))
      {
        next_e = p->next->data;
        return true;
      }
      p = p->next;
    }
    return false;
  }
  bool ListInsert(int i, T e)
  {//在帶頭結(jié)點的單鏈表中第 i 個位置（1 <= i <= ListLength()）之前插入新的數(shù)據(jù)元素 e
    int j = 0;
    LNode<T> *p = Head;
    if (i <= 0 || i > ListLength()+1)
      return false;
    while(j < i-1)  //尋找第 i-1 個結(jié)點
    {
      j++;
      p = p->next;
    }
    s = new LNode<T>;  //生成新結(jié)點
    if (s == NULL)  //生成新結(jié)點失敗
      return false;  //插入失敗
    s->data = e;
    s->next = p->next;  //新結(jié)點指向原第 i 個結(jié)點
    p-next = s;  //原第 i-1 個結(jié)點指向新結(jié)點
    if (p == Tail)  //插在表尾
      Tail = s;
    return true;  //插入成功
  }
  bool ListDelete(int i, T &e)
  {//在帶頭結(jié)點的單鏈線性表中刪除第 i 個數(shù)據(jù)元素（1 <= i <= ListLength()）柒瓣，
   //并用 e 返回其值
    int j = 0;
    LNode<T> *q, *p = Tail->next;
    if (i <= 0 || i > ListLength())
      return false;
    while(j < i-1)  //尋找第 i 個結(jié)點儒搭，并令 p 指向其前驅(qū)
    {
      j++;
      p = p->next;
    }
    q = p->next;  //q 指向刪除結(jié)點
    p->next = q->next;  //待刪結(jié)點的前驅(qū)指向待刪結(jié)點的后繼
    e = q->data;
    if (Tail == q)
      Tail=p;
    delete q;
    return true;
  }
  void ListTraverse(void(*visit) (T*))const
  {//依次對每個數(shù)據(jù)元素調(diào)用函數(shù) visit()
    LNode<T> *p = Tail->next->next;
    while(p != Tail->next)  //p 不指向頭結(jié)點
    {
      visit(&p->data);
      p = p->next;
    }
    cout << endl;
  }
};

2.3 雙向循環(huán)鏈表

實現(xiàn)：

//雙向結(jié)點類型結(jié)構(gòu)體
template<typename T>struct DLNode
{
  T data;
  DLNode<T> *prior, *next;
}

//雙向鏈表類
template<typename T> class DLinkList: public AList<T>
{//帶模板并繼承 AList 的雙向鏈表類
private:
  DLNode<T> *Head;  //頭指針
  DLNode<T>* GetElemP(int i)const
  {//在雙向鏈表中返回第 i 個結(jié)點的地址，i 為 0 芙贫，則返回頭結(jié)點的地址
   //若第 i 個結(jié)點不存在搂鲫，則返回 NULL
    int j = 0;
    DLNode<T> *p = Head;
    if (i < 0)
      return NULL;
    if (i == 0)
      return p;
    do
    {
      p = p->next;
      j++;
    }while(p != Head && j < i);  //p 沒返回到頭結(jié)點并且還沒到第 i 個結(jié)點
    if (p == Head)  //查找失敗
      return NULL;
    else
      return p;
  }
  DLNode<T>* GetElemE(T e, bool(*eq) (T, T))const
  {//在雙向鏈表中返回第一個與 e 滿足定義的 eq() 相等關(guān)系的數(shù)據(jù)元素地址
   //若這樣的數(shù)據(jù)元素不存在，返回 NULL
    DLNode<T> *P = Head->next;
    while(p != Head && !eq(p->data, e))
      p = p->next;
      if (p == Head)  //這樣的元素不存在
        return NULL;
      else
      return p;
  }
public:
  DLinkList()
  {//構(gòu)造一個空的雙向循環(huán)鏈表
    Head = new DLNode<T>;  //產(chǎn)生頭結(jié)點
    assert(Head != NULL)
    Head->next = Head->prior = Head;  //頭結(jié)點的指針域指向自身
  }  
  ~DLinkList()
  {//析構(gòu)函數(shù)磺平，銷毀雙向鏈表
    ClearList();  //置為空表
    delete Head;  //釋放頭結(jié)點
  }
  void ClearList()const
  {//重置雙向循環(huán)線性表為空表
    DLNode<T> *P = Head->next;
    while(p != Head)
    {
      p = p->next;
      delete p->prior;
    }
    Head->next = Head->prior = Head;
  }
  bool ListEmpty()const
  {//若線性表為空表魂仍，則返回 true ；否則返回 false
    return Head->next == Head;
  }
  int ListLength()const
  {//返回線性表的長度
    int i = 0;
    DLNode<T> *p = Head->next;
    while(p != Head)
    {
      i++;
      p = p->next;
    }
    return i;
  }
  bool GetElem(int i, T &e)const
  {//在第 i 個元素存在時拣挪，其值賦給 e 并返回 true 擦酌；否則返回 false
    DLNode<T> *p = GetElemP(i);  //p 指向第 i 個結(jié)點
    if (p != NULL)  //第 i 個結(jié)點存在
    {
      e = p->data;
      return true;
    }
    else
      return false;
  }
  int LocateElem(T e, bool(*eq) (T, T))const
  {//返回第一個與 e 滿足 eq() 關(guān)系的數(shù)據(jù)元素的位序，若這樣的元素不存在媒吗，則返回 0
    int i = 0;
    LNode<T> *p = Head->next;  //p 指向第一個結(jié)點
    while(p != Head)
    {
      i++;
      if (eq(p->data, e))
        return i;
      p = p->next;
    }
    return 0;
  }
  bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
  {//若 e 與表中的某數(shù)據(jù)元素滿足 eq() 關(guān)系，且該元素不是表中第一個乙埃，
   //則用 pre_e 返回它的前驅(qū)闸英，否則操作失敗，pre_e 無定義
    LNode<T> *p = GetElemE(e, eq);  //p 指向結(jié)點 e
    if (p != NULL && p->prior != Head)  //p 指向值為 e 的結(jié)點且該結(jié)點不是第一個結(jié)點
    {
      pre_e = p->prior->data;
      return true;
    }
    return false;
  }
  bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
  {//若 e 與表中某數(shù)據(jù)元素滿足 eq() 關(guān)系介袜，且該元素不是表中最后一個甫何，
   //則用 next_e 返回它的后繼，否則操作失敗遇伞，next_e 無定義
    DLNode<T> *p = GetElemE(e, eq);  //p 指向結(jié)點 e
    if (p != NULL && p->next != Head)  //p 指向值為e的結(jié)點且該結(jié)點不是最后一個結(jié)點
    {
      pre_e = p->next->data;
      return true;
    }
    return false;
  }
  bool ListInsert(int i, T e)
  {//在帶頭結(jié)點的單鏈表中第 i 個位置（1 <= i <= ListLength()）之前插入新的數(shù)據(jù)元素 e
    DLNode<T> *s, *p = GetElemP(i-1);  //確定第 i 個結(jié)點前驅(qū)的位置指針 p
    if (p = NULL) //第 i 個結(jié)點的前驅(qū)不存在（設頭結(jié)點為第 0 個結(jié)點）
      return false;
    s = new DLNode<T>;  //生成新結(jié)點
    if (s == NULL)
      return false;  //生成失敗
    s->data = e;
    s->prior = p;
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    return true;
  }
  bool ListDelete(int i, T &e)
  {//在帶頭結(jié)點的單鏈線性表中刪除第 i 個數(shù)據(jù)元素（1 <= i <= ListLength()）辙喂，
   //并用 e 返回其值
    DLNode<T> *p =GetElemP(i);
    if (p == NULL)
      return false;
      e = p->data;
      p->prior->next = p->next;
      p->next->prior = p->prior;
      delete p;
      return true;
  }
  void ListTraverse(void(*visit) (T*))const
  {//依次對每個數(shù)據(jù)元素調(diào)用函數(shù) visit()
    DLNode<T> *p = Head->next;
    while(p != Head)  //p 不指向頭結(jié)點
    {
      visit(&p->data);
      p = p->next;
    }
    cout << endl;
  }
  void ListBackTraverse(void(*visit) (T*))const
  {//由雙向循環(huán)線性表的頭結(jié)點出發(fā)，逆序?qū)γ總€元素調(diào)用函數(shù) visit()
    DLNode<T> *p = Head->prior;  //p 指向尾結(jié)點
    while(p != Head)
    {
      visit(&p->data);
      p = p->prior;
    }
    cout << endl;
  }
};

2.4 不設頭結(jié)點的鏈表

鏈表也可以不設頭結(jié)點鸠珠，這樣看起來更自然一些巍耗。但不設頭結(jié)點會使得對第 1 個元素做插入或刪除的操作與其他元素不同，這會帶來編程上的麻煩渐排。不設頭結(jié)點的雙向循環(huán)鏈表在動態(tài)存儲管理中有應用炬太。下面對它們做簡單介紹，因為是簡單介紹驯耻，沒有完全實現(xiàn)線性表抽象類 AList 的 3 個純虛函數(shù)亲族，故他們不能繼承 AList 。

實現(xiàn)：

//不設頭結(jié)點的單鏈表類
template<typename T>class LinkListNH
{//帶模板的不設頭結(jié)點的單鏈表類
private:
  LNode<T> *Head;  //頭指針
public:
  LinkListNH()
  {//構(gòu)造函數(shù)可缚，構(gòu)造一個空的線性表
    Head = NULL;  //指針為空
  }
  ~LinkListNH()
  {//析構(gòu)函數(shù)霎迫，銷毀線性表
    ClearList();  //將線性表重置為空表
  }
  void ClearList()
  {//將線性表重置為空表
    LNode<T> *p;
    while(Head != NULL)  //表不為空
    {
      p = Head;  //p 指向第一個結(jié)點
      Head = Head->next;  //Head 指向下一個結(jié)點
      delete p;
    }
  }
  int ListLength()const
  {//返回線性表的長度
    int i = 0;
    LNode<T> *p = Head;  //p指向頭結(jié)點
    while(p != NULL)
    {
      i++;
      p = p->next;
    }
    return i;
  }
  int LocateElem(T e, bool(*eq) (T, T))const
  {//返回第一個與 e 滿足 eq() 關(guān)系的數(shù)據(jù)元素的位序，若這樣的元素不存在帘靡，則返回 0
    int i = 0;
    LNode<T> *p = Head;  //p 指向第一個結(jié)點
    while(p != NULL)
    {
      i++;
      if (eq(p->data, e))
        return i;
      p = p->next;
    }
    return 0;
  }
  LNode<T>* Point(T e, bool(*eq) (T, T), LNode<T>* &p)const
  {//查找表中第一個與 e 滿足 eq() 關(guān)系的結(jié)點知给，如找到，返回指向該結(jié)點的指針描姚，
   //p 指向該結(jié)點的前驅(qū)（若該結(jié)點是第一個結(jié)點炼鞠，則 p=NULL）,沒找到則返回NULL缘滥，p無定義
    if (Head)  //表不空
      if (eq(Head->data, e))
      {
        p = NULL;
        return Head;
      }
      else
      {
        p = Head;  
        while(p->next->data, e)
          if (eq(p->next->data, e))
            return p->next;
          else
            p = p->next;
      }
    return NULL;
  }
  bool ListInsert(int i, T e)
  {//在不設頭結(jié)點的單鏈線性表第 i 個位置之前插入元素 e
    int j = 1;
    LNode<T> *s, *p = Head;
    if (i < 1)
      return false;
    s = new LNode<T>;
    if (s == NULL)
      return false;
    s->data = e;
    if (i == 1)  //插在表頭
    {
      s->next = Head;  //新結(jié)點指向原第一結(jié)點
      Head = s;  //Head 指向新結(jié)點
    }
    else
    {//插在表的其余處
      while(p != NULL && j < i-1)  //尋找第 i-1 個結(jié)點
      {
        j++;
        p = p->next;
      }
      if (p == NULL)  //i 大于表長+1
        return false;
      else  //p 指向第 i-1 個結(jié)點
      {
        s->next = p->next;
        p-next = s;
      }
    }
    return true;
  }
  bool ListDelete(T e, bool(*eq) (T, T))
  {//在不設頭結(jié)點的單鏈線性表中，刪除與 e 滿足 eq() 關(guān)系的結(jié)點
    LNode<T> *p, *q;
    q = Point(e, eq, p);  //p 指向待刪結(jié)點的前驅(qū)
    if (q == NULL)  //沒找到待刪結(jié)點
      return false;
    else  //找到待刪結(jié)點
    {
      if (p == NULL)  //待刪結(jié)點是第一個結(jié)點
        Head = q->next;
      else
        p->next = q->next;
      delete q;
      return true;
    }
  }
  void ListTraverse(void(*visit) (T*))const
  {//依次對每個數(shù)據(jù)元素調(diào)用函數(shù) visit()
    LNode<T> *p = Head;  //p 指向第一個結(jié)點
    while(p != NULL)  //p 所指結(jié)點存在
    {
      visit(&p->data);
      p = p->next;
    }
    cout << endl;
  }
};

//不設頭結(jié)點的雙向鏈表的類
template<typename T>class DLinkListNH
{//帶模板的不設頭結(jié)點的雙向鏈表類
  friend void Joseph(int, int);
  friend class BoundaryLogo;  //聲明邊界標識法類為友類
  friend class BuddySystem;  //聲明伙伴系統(tǒng)為友類
private：
  DLNode<T> *Head;  //頭指針
  DLNode<T>* GetElemP(int i)const
  {//在雙向鏈表中返回第 i 個結(jié)點的地址谒主，若第 i 個結(jié)點不存在朝扼，返回 NULL
    int j = 1;
    DLNode<T> *p = Head;  //p 指向第一個結(jié)點
    if (i <= 0 || Head == NULL)
      return NULL;
    if (i == 1)  //第一個結(jié)點
      return p;
    do
    {
      p = p->next;
      j++;
    }while(p != Head && j < i);
    if (p == Head)  //第 i 個結(jié)點不存在
      return NULL;
    else
      return p;
  }
public:
  DLinkListNH()
  {//構(gòu)造一個空的雙向循環(huán)鏈表
    Head = NULL;  //頭指針為空
  }
  ~DLinkListNH()
  {//析構(gòu)函數(shù)，銷毀雙向循環(huán)鏈表
    ClearList();
  }
  void ClearList()
  {//重置雙向循環(huán)鏈表為空表
   //不帶頭結(jié)點的循環(huán)鏈表可以解開先循環(huán)再依次刪除霎肯，
   //也可以不解開循環(huán)進行依次刪除擎颖，不過最后還得單獨把頭指針所指向的結(jié)點刪除
    DLNode<T> *p = Head;  //p 指向第一個結(jié)點
    if (Head != NULL)
    {
      Head->prior->next = NULL;  //打開循環(huán)鏈表為單鏈表，很關(guān)鍵
      while(p != NULL)
      {
        p = p->next;
        delete Head;
        Head = p;
      }
    }
  }
  int ListLength()const
  {//返回線性表的長度
    int i = 0;
    DLNode<T> *p = Head;
    if (Head != NULL)
      do
      {
        i++;
        p = p->next;
      }while(p != Head);
    return i;
  }
  bool ListInsert(int i, T e)
  {//在不設頭結(jié)點的雙向循環(huán)鏈表中第 i 個位置之前插入新的數(shù)據(jù)元素 e
    DLNode<T> *s, *p = GetElemP(i-1);  //p 指向第 i-1 個結(jié)點
    s = new DLNode<T>;
    if (s == NULL)
      return false;
    s->data = e;
    if (i == 1)  //在第一個結(jié)點前插入
    {
      if (Head == NULL)
        s->prior = s->next =s;
      else
      {
        s->prior = Head->prior;
        s->next = Head;
        s->prior->next = s;
        s->next->prior =s;
      }
      Head = s;
      return true;
    }
    else  //i > 1
    {
      if (p == NULL)  //第 i-1 個結(jié)點不存在
        return false;
      else
      {
        s->next = p->next;
        s->prior = p;
        s->next->prior = s;
        p->next = s;
        return true;
      }
    }
  }
  bool ListDelete(int i, T &e)
  {//刪除不帶頭結(jié)點的雙向循環(huán)鏈表的第 i 個元素观游，并用 e 返回其值
    DLNode<T> *p = GetElemP(i);  //p 指向第 i 個結(jié)點
    if (p == NULL)
      return false;
    e = p->data;
    if (p->next == p)  //表中只有一個元素搂捧，且將被刪除
      Head == NULL;
    else  //表中有多個元素
    {
      P->next->prior = p->prior;
      p->prior->next = p->next;
      if (p == Head)  //刪除的是第一個結(jié)點
        Head = p->next;
    }
    delete p;
    return true;
  }
  void ListTraverse(void(*visit) (T*))const
  {//依次對雙向循環(huán)鏈表的每個數(shù)據(jù)元素調(diào)用函數(shù) visit()
    DLNode<T> *p = Head;
    if (Head != NULL)
      do
      {
        visit(p->data);
        p = p->next;
      }while(p != Head)
    cout << endl;
  }
};

用不設頭結(jié)點的循環(huán)鏈表解決某些問題比較方便，如約瑟夫環(huán)問題：n 個小孩圍坐一圈懂缕，由第一個小孩開始允跑，依次循環(huán)報數(shù)，報到 m 的小孩出列搪柑。從下一個小孩重新開始循環(huán)報數(shù)聋丝，直到所有小孩都出列，求小孩出列順序工碾。

C++ 的標準模板庫（STL）也提供了鏈表類的操作弱睦，稱為 list （表），使用雙向鏈表實現(xiàn)的渊额】瞿荆可以訪問cplusplus查詢相關(guān)操作函數(shù)。

3. 靜態(tài)鏈表存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)也可以實現(xiàn)鏈式存儲功能旬迹。首先火惊，開辟一個充分大的結(jié)構(gòu)體數(shù)組。結(jié)構(gòu)體數(shù)組的一個成員（data）存放數(shù)據(jù)奔垦，另一個成員（link）存放鏈表中的下一個數(shù)據(jù)元素在數(shù)組中的位置（下標）矗晃，這稱為靜態(tài)鏈表。

靜態(tài)鏈表存于數(shù)組中宴倍，單聊標的輸出卻不是按數(shù)組的順序輸出的张症，是由一個指定的位置開始根據(jù) link 的值依次輸出的。靜態(tài)鏈表存儲結(jié)構(gòu)在赫夫曼樹和內(nèi)部排序中都有應用鸵贬。

實現(xiàn)：

const int MAX_SIZE = 10;  //靜態(tài)鏈表的最大長度
//靜態(tài)鏈表類
template<typename T>class StLinkList
{//帶模板的靜態(tài)鏈表類
  struct component  //類內(nèi)定義的結(jié)構(gòu)體俗他，只用于本類內(nèi)
  {
    T data;
    int link;
  };
private:
  component SL[MAX_SIZE];  //靜態(tài)數(shù)組
  int NEW()
  {//若備用鏈表非空，則返回分配的結(jié)點下標（備用鏈表的第一個結(jié)點）阔逼；否則返回 0
    int i = SL[MAX_SIZE - 1].link;  //備用鏈表第一個結(jié)點的位置
    if (i)  //備用鏈表非空
      SL[MAX_SIZE - 1].link = SL[i].link;  
      //備用鏈表的頭結(jié)點指向原備用鏈表的第二個結(jié)點
    return i;  //返回新開辟結(jié)點的下標
  }
  void DELETE(int k)
  {//將下標為 k 的空閑結(jié)點回收到備用鏈表中兆衅，成為備用鏈表的第一個結(jié)點
    SL[k].link = SL[MAX_SIZE - 1].link;  //回收結(jié)點的下標指向備用鏈表的第一個結(jié)點
    SL[MAX_SIZE - 1].link = k;  //備用鏈表的頭結(jié)點指向新回收的結(jié)點
  }
public:
  StLinkList()
  {//構(gòu)造一個空的鏈表，表頭為單元 [0]，其余單元鏈成一個備用鏈表
   //備用鏈表表頭為最后一個單元 [MAX_SIZE - 1]羡亩，link 域 0 表示空指針
    int i;
    SL[0].link = 0;  //[0] 為空鏈表的表頭
    SL[MAX_SIZE - 1].link = 1;  //[1] 為備用鏈表的第一個單元
    for(i = 1; i < MAX_SIZE - 2; i++)
    //將其余單元鏈成以 [MAX_SIZE - 1] 為表頭的備用鏈表
      SL[i].link = i + 1;
    SL[MAX_SIZE - 2].link = 0;
  }
  void ClearList()
  {//將靜態(tài)鏈表重置為空表
    int j, i = SL[MAX_SIZE - 1].link;  //i 指示備用鏈表第一個結(jié)點的位序
    while(i)  //未到備用鏈表表尾
    {
      j = i;
      i = SL[i].link;
    }
    SL[j].link = SL[0].link;  //鏈表的第一個結(jié)點接到備用鏈表的尾部
    Sl[0].link = 0;  //鏈表空
  }
  bool ListEmpty()const
  {//若是空表摩疑，返回 true；否則返回 false
    return SL[0].link == 0;
  }
  int ListLength()const
  {//返回表中數(shù)據(jù)元素個數(shù)
    int j = 0, i = SL[0].link;  //i 指向鏈表的第一個結(jié)點的位序
    while(i)
    {
      i = SL[i].link;
      j++;
    }
    return j;
  }
  bool PriorElem(T e, bool(*eq) (T, T), T &pre_e)const
  {//若 e 與表中某數(shù)據(jù)元素滿足定義的 eq() 關(guān)系畏铆，且該數(shù)據(jù)不是表中第一個雷袋，
   //則用 pre_e 返回它的前驅(qū)，否則操作失敗辞居，pre_e 無定義
    int j, i = SL[0].link;
    do
    {
      j = i;
      i = SL[i].link;
    }while(i && !eq(Sl[i].data, e));  //i 所指元素存在且其值不是 e 楷怒，繼續(xù)循環(huán)
    if (i)  //找到該元素
    {
      pre_e = SL[i].data;
      return true;
    }
    return false;  //沒找到該元素，或其無前驅(qū)
  }
  bool NextElem(T e, bool(*eq) (T, T), T &next_e)const
  {//若 e 與表中某數(shù)據(jù)元素滿足定義的 eq() 關(guān)系瓦灶，且該元素不是表中最后一個鸠删，
   //則用 next_e 返回它的后繼，否則操作失敗贼陶，next_e 無定義
    int i = SL[0].link;
    while(i)
    {
      if (eq(SL[i].data, e) && SL[i].link)  //找到該元素且其有后繼
      {
        next_e = SL[SL[i].link].data;
        return true;
      }
      i = SL[i].link;
    }
    return false;  //不存在該元素刃泡，或者其無后繼
  }
  bool ListInsert(int i, T e)
  {//在靜態(tài)鏈表的第 i 個元素
    int m, k = 0;  //k 指示頭結(jié)點的位序
    for (m = 1; m < i; m++)
    {
      k = SL[k].link;  //k 指向下一結(jié)點
      if (k == 0)  //已到表尾
        break;
    }
    if (m < i)  //表中沒有第 i-1 個結(jié)點
      return false;
    else  //表中有第 i-1 個結(jié)點，并由 k 指向
    {
      m = NEW();  //申請新單元
      if (m)  //申請成功
      {
        SL[m].data = e;
        SL[m].link = SL[k].link;
        SL[k].link = m;
        return true;
      }
      return false;
    }
  }
  bool ListDelete(int i, T &e)
  {//刪除第 i 個數(shù)據(jù)元素碉怔，并用 e 返回其值
    int m, k = 0;  //k 指示頭結(jié)點的位序
    for(m = 1; m < i; m++)
    {
      k = SL[k].link;
      if (k == 0)  //已到表尾
        break;
    }
    if (m < i || SL[k].link == 0)  //表中沒有第 i-1 個結(jié)點或者沒有第 i 個結(jié)點
      return false;
    else
    {
      m = SL[k].link;
      SL[k].link = SL[m].link;
      e = SL[m].data;
      DELETE(m);
      return true;
    }
  }
  void ListTraverse(void(*visit) (T*))
  {//依次對每個元素調(diào)用函數(shù) visit()
    int i = SL[0].link;
    while(i)
    {
      visit(&SL[i].data);
      i = SL[i].link;
    }
    cout << endl;
  }
};

靜態(tài)鏈表存儲于數(shù)組中烘贴，但其順序卻不是按數(shù)組下標的順序，而是像鏈表一樣眨层，由當前結(jié)點 link 域的值決定下一結(jié)點的位置庙楚，這是鏈表的特性上荡；又由于用數(shù)組存儲趴樱，故稱為靜態(tài)鏈表。我們只要知道第一個結(jié)點（頭結(jié)點）的位置就可以依次找到靜態(tài)鏈表中的其他結(jié)點酪捡。我們將不再鏈表中的空閑結(jié)點也鏈接成一個靜態(tài)鏈表叁征，成為 “備用鏈表” 。靜態(tài)鏈表數(shù)組 SL 中有一個鏈表頭結(jié)點在位置 [0]逛薇，有一個備用鏈表頭結(jié)點在位置 [MAX_SIZE - 1] 捺疼，其余結(jié)點不再鏈表中就在備用鏈表中。

當靜態(tài)鏈表需要新結(jié)點時永罚，我們把備用鏈表中的第一個結(jié)點從備用鏈表中刪除啤呼，作為新結(jié)點插入靜態(tài)鏈表。當刪除靜態(tài)鏈表中的結(jié)點時呢袱，被刪除的結(jié)點插入備用鏈表中官扣，成為備用鏈表的第一個結(jié)點。之所以從備用鏈表刪除結(jié)點或是插入結(jié)點的操作都在表頭進行羞福，是因為這樣的效率最高惕蹄。

備注：如果不理解備用鏈表，可以參考下面這篇博客：
靜態(tài)鏈表 C實現(xiàn)。

靜態(tài)鏈表和單鏈表的主要區(qū)別：

• 單鏈表的結(jié)點通過 new 關(guān)鍵字產(chǎn)生卖陵，結(jié)點被限制在動態(tài)存儲區(qū)這個大范圍內(nèi)遭顶。因此，指示結(jié)點位置的指針類型實際上是常整型泪蔫。而靜態(tài)鏈表的結(jié)點被限制在靜態(tài)數(shù)組這個小范圍內(nèi)棒旗。因此，指示結(jié)點位置的指針類型（link）一般是整型鸥滨；
• 單鏈表不用的結(jié)點通過 delete 關(guān)鍵字釋放嗦哆，釋放后的結(jié)點由編譯軟件管理。而靜態(tài)鏈表中不用的結(jié)點要自己管理（插入到備用鏈表中）婿滓。