C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(shí)例

更新時(shí)間：2017年06月26日 16:33:46 投稿：lqh

這篇文章主要介紹了C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(shí)例的相關(guān)資料,需要的朋友可以參考下

C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(shí)例

用數(shù)組描述的鏈表，即稱(chēng)為靜態(tài)鏈表。

在C語(yǔ)言中，靜態(tài)鏈表的表現(xiàn)形式即為結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體變量包括數(shù)據(jù)域data和游標(biāo)cur。

這種存儲(chǔ)結(jié)構(gòu)，仍需要預(yù)先分配一個(gè)較大的空間，但在作為線性表的插入和刪除操作時(shí)不需移動(dòng)元素，僅需修改指針，故仍具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)。

下圖表示了靜態(tài)鏈表的一中存儲(chǔ)結(jié)構(gòu)：

圖中用彩色途上的是兩個(gè)頭結(jié)點(diǎn)，不存放數(shù)據(jù)，分別用來(lái)記錄第一個(gè)備用節(jié)點(diǎn)和第一個(gè)數(shù)據(jù)節(jié)點(diǎn)的下標(biāo)。
下面給出靜態(tài)鏈表的C++實(shí)現(xiàn)代碼：

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

#include<iostream>
#include<assert.h>
using namespace std;

#define MAXSIZE 20    // 靜態(tài)鏈表（數(shù)組）默認(rèn)長(zhǎng)度
#define ElemType int   // 值類(lèi)型

class StaticList;

//節(jié)點(diǎn)類(lèi)
typedef class StaticListNode  // 靜態(tài)鏈表的節(jié)點(diǎn)類(lèi)型（數(shù)組元素類(lèi)型）
{
  friend class StaticList;
private:
  ElemType data;       // 值域
  int   cur;        // 游標(biāo) （指示當(dāng)前節(jié)點(diǎn)的下一個(gè)元素下標(biāo)）
}StaticListNode;


// 靜態(tài)鏈表類(lèi)</strong></span>
class StaticList
{
public:
  StaticList()
  {
    for(int i = 2; i<MAXSIZE-1; ++i)
      space[i].cur = i+1;
    space[i].cur = 0;    //整個(gè)鏈表結(jié)束
    space[0].cur = 2;
    space[1].cur = 0;    //數(shù)據(jù)節(jié)點(diǎn)頭的游標(biāo)為空，沒(méi)有數(shù)據(jù)
  }

  ~StaticList()
  {}

// 尾部插入法
  void push_back(const ElemType &x)
  {
    int i = Malloc_SL();
    if(0 == i)       // 空間申請(qǐng)失敗
    {
      cout<<"已滿(mǎn)！"<<x<<"不能插入"<<endl;  
      return ;
    }
    space[i].data = x;
    space[i].cur = 0;

    int k = 1;
    while(0!=k && 0!=space[k].cur) // 找到最后一個(gè)節(jié)點(diǎn)
      k = space[k].cur;

    space[k].cur = i;       // 把剛申請(qǐng)的下標(biāo)為i的節(jié)點(diǎn)鏈到最后一個(gè)節(jié)點(diǎn)后面       
  }

// 頭部插入法
  void push_front(const ElemType &x)
  {
    int i = Malloc_SL();
    if(0 == i)      // 同上，空間申請(qǐng)失敗
    {
      cout<<"已滿(mǎn)！"<<x<<"不能插入"<<endl;
      return ;
    }
    space[i].data = x;  // 把x放入剛申請(qǐng)的節(jié)點(diǎn)中

    space[i].cur = space[1].cur;  // 此時(shí)剛申請(qǐng)的節(jié)點(diǎn)i的游標(biāo)指向第一個(gè)數(shù)據(jù)節(jié)點(diǎn)，稱(chēng)為第一個(gè)結(jié)點(diǎn)
    space[1].cur = i;       // 使頭結(jié)點(diǎn)指向第一個(gè)數(shù)據(jù)節(jié)點(diǎn)
  }

// 尾部刪除
  void pop_back()
  {
    int i = space[1].cur;
    int j = 0;
    for(; 0!=space[i].cur; j = i, i = space[i].cur)
    {}  // 找到最后一個(gè)節(jié)點(diǎn)以及倒數(shù)第二個(gè)節(jié)點(diǎn)

    space[j].cur = 0;   // 倒數(shù)第二個(gè)節(jié)點(diǎn)的游標(biāo)賦空
    Free_SL(i);      // 最后一個(gè)節(jié)點(diǎn)被釋放
  }

// 頭部刪除
  void pop_front()
  {
    int i = space[1].cur;  // i是第一個(gè)數(shù)據(jù)節(jié)點(diǎn)的下標(biāo)
    space[1].cur = space[i].cur; // 頭結(jié)點(diǎn)指向第二個(gè)數(shù)據(jù)節(jié)點(diǎn)的下標(biāo)
    Free_SL(i);       // i 節(jié)點(diǎn)被釋放
  }

  void show_list()
  {
    for(int i = space[1].cur; i!=0; i = space[i].cur)
      cout<<space[i].data<<" ";
    cout<<"Over"<<endl;
  }

  /* 靜態(tài)鏈表從小到大排序的前提下，插入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;    //在下標(biāo)k之后插入

    if(0 == space[k].cur)  // 如果k指向最后一個(gè)節(jié)點(diǎn)，執(zhí)行尾插
      push_back(x);
    else if(k == 1)     // 如果k指向第一個(gè)節(jié)點(diǎn)，執(zhí)行頭插
      push_front(x);
    else           // 在中間任意位置插入x
    {  
      int i = Malloc_SL();
      assert(0 != i);
      space[i].data = x;
      space[i].cur = space[k].cur;  // i節(jié)點(diǎn)的游標(biāo)指向k節(jié)點(diǎn)后面的一個(gè)節(jié)點(diǎn)
      space[k].cur = i;       // k節(jié)點(diǎn)的游標(biāo)指向新開(kāi)辟的i節(jié)點(diǎn)
    }
  }

  /* 返回key的前一個(gè)節(jié)點(diǎn)下標(biāo)*/
  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<<"沒(méi)找到 "<<key<<endl;
      return -1;
    }
    return i;
  }

  /* 刪除給定的值key所在節(jié)點(diǎn)，若沒(méi)找到則返回 */
  void delete_val(const ElemType &key)
  {
    int i = find(key);
    if(-1 == i)   // 說(shuō)明靜態(tài)鏈表中沒(méi)有元素key
      return ;
    else if(1 == i) // key 處于下標(biāo)為2的節(jié)點(diǎn)(第一個(gè)數(shù)據(jù)節(jié)點(diǎn))
      pop_front();
    else if(0 == space[i].cur) // key處于最后一個(gè)節(jié)點(diǎn)
      pop_back();
    else       // key 處于中間任意位置
    {
      int k = space[i].cur;  // 記錄要?jiǎng)h除位置的下標(biāo)
      space[i].cur = space[k].cur; // 脫離出要?jiǎng)h除節(jié)點(diǎn)
      Free_SL(k); // 刪除key所在節(jié)點(diǎn)
    }
  }

  /* sl1 和 sl2已存在，把它們糅合到另一個(gè)鏈表，使之按非遞減排列 */
  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)
    {    
      // 哪個(gè)數(shù)據(jù)較小，就把該數(shù)據(jù)尾插到新鏈表中，并使游標(biāo)指向下一個(gè)
      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)
    {    // 因?yàn)閟l1已經(jīng)有序，如果sl1還沒(méi)有全部插入新鏈表，就把剩下的全部插入
      push_back(sl1.space[p].data);
      p = sl1.space[p].cur;
    }
    while(0!=q)
    {    // 因?yàn)閟l2已經(jīng)有序，如果sl2還沒(méi)有全部插入新鏈表，就把剩下的全部插入
      push_back(sl2.space[q].data);
      q = sl2.space[q].cur;
    }
  }

  /* 如果靜態(tài)鏈表無(wú)序，使其按非遞減順序排列 */
  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;   // 找到一個(gè)位置k, 在k后插入s所指節(jié)點(diǎn)的數(shù)據(jù)
      while(0!=k && space[space[k].cur].data < space[s].data)
      {
        k1 = k;         //如果k==0,用k1記錄最后一個(gè)數(shù)據(jù)節(jié)點(diǎn)
        k = space[k].cur;    //在下標(biāo)k之后插入
      }
      if(0 == k)  //尾插
      {
        space[k1].cur = s;
        space[s].cur = 0;
      }
      else     //頭插和中間插
      {
        space[s].cur = space[k].cur;
        space[k].cur = s;
      }
    }
  }

  /* 逆置靜態(tài)鏈表 */
  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所指節(jié)點(diǎn) 頭插進(jìn)原有鏈表
      space[1].cur = s;       // s成為第一個(gè)數(shù)據(jù)節(jié)點(diǎn)
    }
  }

  /* 清空靜態(tài)鏈表 */
  void clear()
  {
    for(int i = 2; i<MAXSIZE-1; ++i)
      space[i].cur = i+1;
    space[i].cur = 0;

    space[0].cur = 2;   // 下標(biāo)2成為第一個(gè)備用節(jié)點(diǎn)
    space[1].cur = 0;   // 第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為空
  }

  /* 返回表長(zhǎng) */
  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;
  }

  /* 返回下標(biāo)為k的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)下標(biāo) 在靜態(tài)鏈表中用處不大*/
  int next(const int k)
  {
    if(0==k || 1==k)
      return -1;
    return space[k].cur;
  }
  /* 返回下標(biāo)為k的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)下標(biāo) */
  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:
  /* 用來(lái)申請(qǐng)一個(gè)空間，返回該節(jié)點(diǎn)的下標(biāo) */
  int Malloc_SL()  
  {
    int i = space[0].cur;  // 0下標(biāo)的游標(biāo)指向第一個(gè)備用節(jié)點(diǎn)
    if(space[0].cur) space[0].cur = space[i].cur; // 修改頭結(jié)點(diǎn)保存的第一個(gè)備用節(jié)點(diǎn)下標(biāo) 
    return i;
  }
  /* 釋放下標(biāo)為k的節(jié)點(diǎn) */
  void Free_SL(int k)  
  {
    space[k].cur = space[0].cur;  // 該節(jié)點(diǎn)的游標(biāo)指向第一個(gè)備用節(jié)點(diǎn)
    space[0].cur = k;        // 該節(jié)點(diǎn)稱(chēng)為第一個(gè)備用節(jié)點(diǎn)
  }

private:
  StaticListNode space[MAXSIZE];
};

下面是測(cè)試代碼：Main.cpp

#include"StaticList.h"

void main()
{
  StaticList SL;

  StaticList SL1;  //測(cè)試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<<"請(qǐng)選擇：》";
    cin>>select;
    switch(select)
    {
    case 1:
      cout<<"輸入要尾插的數(shù)據(jù):(-1結(jié)束)>";
      while(cin>>Item && -1 != Item)
        SL.push_back(Item);
      break;

    case 2:
      cout<<"輸入要頭插的數(shù)據(jù):(-1結(jié)束)>";
      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<<"輸入要插入的數(shù)據(jù):>";
      cin>>Item;
      SL.insert_val(Item);
      break;

    case 7:
      cout<<"鏈表長(zhǎng)度為："<<SL.length()<<endl;
      break;

    case 8:
      cout<<"輸入要查找的數(shù)據(jù):>";
      cin>>Item;
      SL.find(Item);
      break;

    case 9:
      SL.merge(SL1, SL2);
      break;

    case 10:
      cout<<"輸入要?jiǎng)h除的數(shù)據(jù):>";
      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;
    }
  }
}

下面是測(cè)試截圖：