C++ 實現靜態鏈表的簡單實例

2020-01-26 14:03:07

字體：大中小

來源：轉載

供稿：網友

C++ 實現靜態鏈表的簡單實例

用數組描述的鏈表，即稱為靜態鏈表。

在C語言中，靜態鏈表的表現形式即為結構體數組，結構體變量包括數據域data和游標cur。

這種存儲結構，仍需要預先分配一個較大的空間，但在作為線性表的插入和刪除操作時不需移動元素，僅需修改指針，故仍具有鏈式存儲結構的主要優點。

下圖表示了靜態鏈表的一中存儲結構：

圖中用彩色途上的是兩個頭結點，不存放數據，分別用來記錄第一個備用節點和第一個數據節點的下標。
下面給出靜態鏈表的C++實現代碼：

首先給出頭文件：StaticList.h:

#include<iostream>#include<assert.h>using namespace std;#define MAXSIZE 20    // 靜態鏈表（數組）默認長度#define ElemType int   // 值類型class StaticList;//節點類typedef class StaticListNode  // 靜態鏈表的節點類型（數組元素類型）{  friend class StaticList;private:  ElemType data;       // 值域  int   cur;        // 游標 （指示當前節點的下一個元素下標）}StaticListNode;// 靜態鏈表類</strong></span>class StaticList{public:  StaticList()  {    for(int i = 2; i<MAXSIZE-1; ++i)      space[i].cur = i+1;    space[i].cur = 0;    //整個鏈表結束    space[0].cur = 2;    space[1].cur = 0;    //數據節點頭的游標為空，沒有數據  }  ~StaticList()  {}// 尾部插入法  void push_back(const ElemType &x)  {    int i = Malloc_SL();    if(0 == i)       // 空間申請失敗    {      cout<<"已滿！"<<x<<"不能插入"<<endl;        return ;    }    space[i].data = x;    space[i].cur = 0;    int k = 1;    while(0!=k && 0!=space[k].cur) // 找到最后一個節點      k = space[k].cur;    space[k].cur = i;       // 把剛申請的下標為i的節點鏈到最后一個節點后面         }// 頭部插入法  void push_front(const ElemType &x)  {    int i = Malloc_SL();    if(0 == i)      // 同上，空間申請失敗    {      cout<<"已滿！"<<x<<"不能插入"<<endl;      return ;    }    space[i].data = x;  // 把x放入剛申請的節點中    space[i].cur = space[1].cur;  // 此時剛申請的節點i的游標指向第一個數據節點，稱為第一個結點    space[1].cur = i;       // 使頭結點指向第一個數據節點  }// 尾部刪除  void pop_back()  {    int i = space[1].cur;    int j = 0;    for(; 0!=space[i].cur; j = i, i = space[i].cur)    {}  // 找到最后一個節點以及倒數第二個節點    space[j].cur = 0;   // 倒數第二個節點的游標賦空    Free_SL(i);      // 最后一個節點被釋放  }// 頭部刪除  void pop_front()  {    int i = space[1].cur;  // i是第一個數據節點的下標    space[1].cur = space[i].cur; // 頭結點指向第二個數據節點的下標    Free_SL(i);       // i 節點被釋放  }  void show_list()  {    for(int i = space[1].cur; i!=0; i = space[i].cur)      cout<<space[i].data<<" ";    cout<<"Over"<<endl;  }  /* 靜態鏈表從小到大排序的前提下，插入x */  void insert_val(const ElemType &x)  {    int k = 1;    while(0!=k && 0!=space[k].cur && space[space[k].cur].data<x)      k = space[k].cur;    //在下標k之后插入    if(0 == space[k].cur)  // 如果k指向最后一個節點，執行尾插      push_back(x);    else if(k == 1)     // 如果k指向第一個節點，執行頭插      push_front(x);    else           // 在中間任意位置插入x    {        int i = Malloc_SL();      assert(0 != i);      space[i].data = x;      space[i].cur = space[k].cur;  // i節點的游標指向k節點后面的一個節點      space[k].cur = i;       // k節點的游標指向新開辟的i節點    }  }  /* 返回key的前一個節點下標*/  int find(const ElemType &key)      {    int i = 1;    while(0!=i && space[space[i].cur].data!=key)      i = space[i].cur;    if(0 == i)    {      cout<<"沒找到 "<<key<<endl;      return -1;    }    return i;  }  /* 刪除給定的值key所在節點，若沒找到則返回 */  void delete_val(const ElemType &key)  {    int i = find(key);    if(-1 == i)   // 說明靜態鏈表中沒有元素key      return ;    else if(1 == i) // key 處于下標為2的節點(第一個數據節點)      pop_front();    else if(0 == space[i].cur) // key處于最后一個節點      pop_back();    else       // key 處于中間任意位置    {      int k = space[i].cur;  // 記錄要刪除位置的下標      space[i].cur = space[k].cur; // 脫離出要刪除節點      Free_SL(k); // 刪除key所在節點    }  }  /* sl1 和 sl2已存在，把它們糅合到另一個鏈表，使之按非遞減排列 */  void merge(StaticList &sl1, StaticList &sl2)  {    sl1.sort();      sl2.sort();    if(0==sl1.length() || 0==sl2.length())      return ;    int p = sl1.space[1].cur;    int q = sl2.space[1].cur;    while(0!=p && 0!=q)    {          // 哪個數據較小，就把該數據尾插到新鏈表中，并使游標指向下一個      if(sl1.space[p].data < sl2.space[q].data)      {              push_back(sl1.space[p].data);        p = sl1.space[p].cur;      }      else      {        push_back(sl2.space[q].data);        q = sl2.space[q].cur;      }    }    while(0!=p)    {    // 因為sl1已經有序，如果sl1還沒有全部插入新鏈表，就把剩下的全部插入      push_back(sl1.space[p].data);      p = sl1.space[p].cur;    }    while(0!=q)    {    // 因為sl2已經有序，如果sl2還沒有全部插入新鏈表，就把剩下的全部插入      push_back(sl2.space[q].data);      q = sl2.space[q].cur;    }  }  /* 如果靜態鏈表無序，使其按非遞減順序排列 */  void sort()  {    int s = space[1].cur;    int p = space[s].cur;    if(0 == p)      return ;    space[s].cur = 0;    int k = 1;    int k1 = 0;    while(0 != p)    {      s = p;      p = space[p].cur;      k = 1;   // 找到一個位置k, 在k后插入s所指節點的數據      while(0!=k && space[space[k].cur].data < space[s].data)      {        k1 = k;         //如果k==0,用k1記錄最后一個數據節點        k = space[k].cur;    //在下標k之后插入      }      if(0 == k)  //尾插      {        space[k1].cur = s;        space[s].cur = 0;      }      else     //頭插和中間插      {        space[s].cur = space[k].cur;        space[k].cur = s;      }    }  }  /* 逆置靜態鏈表 */  void reserve()  {    int s = space[1].cur;    int p = space[s].cur;    if( 0==p )      return ;    space[s].cur = 0;    while(0 != p)    {      s = p;      p = space[p].cur;      space[s].cur = space[1].cur;  // 把s所指節點 頭插進原有鏈表      space[1].cur = s;       // s成為第一個數據節點    }  }  /* 清空靜態鏈表 */  void clear()  {    for(int i = 2; i<MAXSIZE-1; ++i)      space[i].cur = i+1;    space[i].cur = 0;    space[0].cur = 2;   // 下標2成為第一個備用節點    space[1].cur = 0;   // 第一個數據節點為空  }  /* 返回表長 */  int length()  {    if(0 == space[1].cur)      return 0;    int i = 1;    int count = -1;    do    {      ++count;      i = space[i].cur;    }while(0 != i);    return count;  }  /* 返回下標為k的節點的下一個節點下標 在靜態鏈表中用處不大*/  int next(const int k)  {    if(0==k || 1==k)      return -1;    return space[k].cur;  }  /* 返回下標為k的節點的上一個節點下標 */  int prio(const int k)  {    if(0==k || 1==k)      return -1;    int p = 1;    while(0!=p && space[p].cur!=k)      p = space[p].cur;    return p;  }protected:  /* 用來申請一個空間，返回該節點的下標 */  int Malloc_SL()    {    int i = space[0].cur;  // 0下標的游標指向第一個備用節點    if(space[0].cur) space[0].cur = space[i].cur; // 修改頭結點保存的第一個備用節點下標     return i;  }  /* 釋放下標為k的節點 */  void Free_SL(int k)    {    space[k].cur = space[0].cur;  // 該節點的游標指向第一個備用節點    space[0].cur = k;        // 該節點稱為第一個備用節點  }private:  StaticListNode space[MAXSIZE];};

下面是測試代碼：Main.cpp

#include"StaticList.h"void main(){  StaticList SL;  StaticList SL1;  //測試merge()  StaticList SL2;  SL1.push_back(1);  SL1.push_back(9);  SL1.push_back(0);  SL1.push_back(6);  SL1.push_back(999);  SL2.push_back(5);  SL2.push_back(8);  SL2.push_back(100);  ElemType Item = 0;  int select = 1;  while(select)  {    cout<<"********************************************"<<endl;    cout<<"*[1] push_back      [2] push_front  *"<<endl;    cout<<"*[3] show_list      [4] pop_back   *"<<endl;    cout<<"*[5] pop_front      [6] insert_val  *"<<endl;    cout<<"*[7] length       [8] find     *"<<endl;    cout<<"*[9] merge        [10] delete_val  *"<<endl;    cout<<"*[11] sort        [12] reserve   *"<<endl;    cout<<"*[13] next        [14] prio     *"<<endl;    cout<<"*[15] clear       [16] destroy   *"<<endl;    cout<<"*[0] quit_sys               *"<<endl;    cout<<"********************************************"<<endl;    cout<<"請選擇：》";    cin>>select;    switch(select)    {    case 1:      cout<<"輸入要尾插的數據:(-1結束)>";      while(cin>>Item && -1 != Item)        SL.push_back(Item);      break;    case 2:      cout<<"輸入要頭插的數據:(-1結束)>";      while(cin>>Item && -1 != Item)        SL.push_front(Item);      break;    case 3:      SL.show_list();      break;    case 4:      SL.pop_back();      break;    case 5:      SL.pop_front();      break;    case 6:      cout<<"輸入要插入的數據:>";      cin>>Item;      SL.insert_val(Item);      break;    case 7:      cout<<"鏈表長度為："<<SL.length()<<endl;      break;    case 8:      cout<<"輸入要查找的數據:>";      cin>>Item;      SL.find(Item);      break;    case 9:      SL.merge(SL1, SL2);      break;    case 10:      cout<<"輸入要刪除的數據:>";      cin>>Item;      SL.delete_val(Item);      break;    case 11:      SL.sort();      break;    case 12:      SL.reserve();      break;    case 13:      SL.next(0);      break;    case 14:      SL.prio(0);      break;    case 15:      SL.clear();      break;    case 16:      SL.~StaticList();      break;    default:      break;    }  }}

下面是測試截圖：