數據結構【第一篇】線性表之順序表的實現與講解

• 2019 年 10 月 7 日
• 筆記

線性表

引言

新生安排體檢，為了 便管理與統一數據，學校特地規定了排隊的方式，即按照學號排隊，誰在前誰在後，這都是規定好的，所以誰在誰不在，都是非常方便統計的，同學們就像被一條線（學號）聯繫起來了，這種組織數據（同學）的方式我們可以稱作線性表結構

定義

線性表：具有零個或多個（具有相同性質，屬於同一元素的）數據元素的有限序列

若將線性表記為 ( a0 , a1 ,ai -1 ai ,ai +1 , … , an - 1 , an )

• 注意：i 是任意數字，只為了說明相對位置，下標即其在線性表中的位置)
• 前繼和後繼：由於前後元素之間存在的是順序關係，所以除了首尾元素外，每個元素均含有前驅和後繼，簡單的理解就是前一個 元素和後一個元素
• 空表：如果線性表中元素的個數 n 為線性表長度，那麼 n = 0 的時候，線性表為空
• 首節點、尾節點：上面表示中的 ：a0 稱作首節點，an 稱作尾節點

抽象數據類型

• 數據類型：一組性質相同的值的集合及定義在此集合上的一些操作的總稱
• 抽象數據類型：是指一個數學模型及定義在該模型上的一組操作

關於數據類型我們可以舉這樣一個例子

• 例如：我們常常用到的 整數型 浮點型 數據 這些都是數據的總稱，所有符合其性質特徵的都可以用其對應數據類型來定義，例如 520是一個滿足整數特徵的數據，所以可以賦值給 一個int型的變數 int love = 520;

像這些一般的數據類型通常在程式語言的內部定義封裝，直接提供給用戶，供其調用進行運算，而抽象數據類型一般由用戶自己根據已有的數據類型進行定義

抽象數據類型和高級程式語言中的數據類型實際上是一個概念，但其含義要比普通的數據類型更加廣泛、抽象

為什麼說抽象呢？是因為它是我們用戶為了解決實際的問題，與描述顯示生活且現實生活中的實體所對應的一種數據類型，我可以定義其存儲的結構，也可以定義它所能夠，或者說需要進行的一些操作，例如在員工表中，添加或刪除員工資訊，這兩部分就組成了 「員工」 這個抽象的數據類型

大致流程就是：

• A：一般用戶會編寫一個自定義數據類型作為基礎類型
• B：其中一些抽象操作就可以定義為該類型的成員函數，然後實現這些函數
• C：如果對外的介面在公有域中，就可以通過對象來調用這些操作了
• 當然，我們在使用抽象數據類型的時候，我們更加註意數據本身的API描述，而不會關心數據的表示，這些都是實現該抽象數據類型的開發者應該考慮的事情

線性表分為兩種——順序存儲結構和鏈式存儲結構，我們先來學習第一種

順序存儲結構

什麼是順序存儲結構呢？

順序存儲結構：用一段地址連續的存儲單元依次存儲線性表的數據元素

怎麼理解這這種存儲方式呢？

例如在一個菜園子中，有一片空地，我們在其中找一小塊種蔬菜，因為土地不夠平整疏鬆所以我們需要耕地，同時將種子按照一定的順序種下去，這就是對錶的初始化

菜園子可以理解為記憶體空間，空地可以理解為可以使用的記憶體空間，我們通過種蔬菜種子的方式，將一定的記憶體空間所佔據，當然，這片空間中你所放置的數據元素都必須是相同類型的 也就是說都得是蔬菜種子，有時候有些種子被蟲子咬壞了，我們就需要移除一些種子，買來以後再在空出來的位置中選地方種好，這也就是增加和刪除數元素

地址計算方式

從定義中我們可以知道 這種存儲方式，存儲的數據是連續的，而且相同類型，所以每一個數據元素佔據的存儲空間是一致的，假設每個數據 佔據 L個存儲單元那麼我們可以的出這樣的結論公式

Loc(a_i) = Loc(a_1) + (i -1)*L

注意：_ 代表代表下標符號

• i 代表所求元素的下標
• 也就是單位長度乘以對應的個數

線性表的抽象數據類型

#ifndef _LIST_H_  #define _LIST_H_  #include<iostream>  using namespace std;    class outOfRange{};  class badSize{};  template<class T>  class List {  public:      // 清空線性表      virtual void clear()=0;      // 判空，表空返回true，非空返回false      virtual bool empty()const=0;      // 求線性表的長度      virtual int size()const=0;      // 在線性表中，位序為i[0..n]的位置插入元素value      virtual void insert(int i,const T &value)=0;      // 在線性表中，位序為i[0..n-1]的位置刪除元素      virtual void remove(int i)=0;      // 在線性表中，查找值為value的元素第一次出現的位序      virtual int search(const T&value)const=0;      // 在線性表中，查找位序為i的元素並返回其值      virtual T visit(int i)const=0;      // 遍歷線性表      virtual void traverse()const=0;      // 逆置線性表      virtual void inverse()=0;      virtual ~List(){};  };    /*自定義異常處理類*/      class outOfRange :public exception {  //用於檢查範圍的有效性  public:      const char* what() const throw() {          return "ERROR! OUT OF RANGE.n";      }  };    class badSize :public exception {   //用於檢查長度的有效性  public:      const char* what() const throw() {          return "ERROR! BAD SIZE.n";      }  };    #endif  

在上麵線性表的抽象數據類型中，定義了一些常用的方法，我們可以在其中根據需要，增刪函數

有了這樣的抽象數據類型List 我們就可以寫出線性表其下的順序結構和鏈式結構表的定義寫出來

異常語句說明：如果new在調用分配器分配存儲空間的時候出現了錯誤（錯誤資訊被保存了一下），就會catch到一個bad_alloc類型的異常，其中的what函數，就是提取這個錯誤的基本資訊的，就是一串文字，應該是const char*或者string

順序表——順序存儲結構的定義

#ifndef _SEQLIST_H_  #define _SEQLIST_H_  #include "List.h"  #include<iostream>  using namespace std;    //celemType為順序表存儲的元素類型  template <class elemType>  class seqList: public List<elemType> {  private:      // 利用數組存儲數據元素      elemType *data;      // 當前順序表中存儲的元素個數      int curLength;      // 順序表的最大長度      int maxSize;      // 表滿時擴大表空間      void resize();  public:      // 構造函數      seqList(int initSize = 10);       // 拷貝構造函數      seqList(seqList & sl);      // 析構函數      ~seqList()  {delete [] data;}      // 清空表，只需修改curLength      void clear()  {curLength = 0;}      // 判空      bool empty()const{return curLength == 0;}      // 返回順序表的當前存儲元素的個數      int size() const  {return curLength;}      // 在位置i上插入一個元素value，表的長度增1      void insert(int i,const elemType &value);      // 刪除位置i上的元素value，若刪除位置合法，表的長度減1      void remove(int i);      // 查找值為value的元素第一次出現的位序      int search(const elemType &value) const ;      // 訪問位序為i的元素值，「位序」0表示第一個元素，類似於數組下標      elemType visit(int i) const;      // 遍歷順序表      void traverse() const;      // 逆置順序表      void inverse();      bool Union(seqList<elemType> &B);  };  

順序表基本運算的實現

(一) 構造函數

在構造函數中，我們需要完成這個空順序表的初始化，即創建出一張空的順序表

template <class elemType>  seqList<elemType>::seqList(int initSize) {        if(initSize <= 0) throw badSize();      maxSize = initSize;      data = new elemType[maxSize];      curLength = 0;    }  

在這裡我們注意區分 initSize 和 curLenght 這兩個變數

• initSize ：初始化 (指定) 數組長度
• 數組長度是存放線性表的存儲空間的長度，一般來說這個值是固定的，但是為了滿足需要很多情況下，我們會選擇動態的分配數組，即定義擴容機制，雖然很方便，但是確帶來了效率的損失，我們在擴容的函數中會再提到這一問題
• curLenght：線性表長度，即數據元素的個數

(二) 拷貝構造函數

template <class elemType>  seqList<elemType>::seqList(seqList & sl) {        maxSize = sl.maxSize;      curLength = sl.curLength;      data = new elemType[maxSize];      for(int i = 0; i < curLength; ++i)          data[i] = sl.data[i];    }  

(三) 插入

我們下面來談一個非常常用的操作——插入操作，接著用我們一開始的例子，學校安排體檢，大家自覺的按照學號順訊排好了隊伍，但是遲到的某個學生Z和認識前面隊伍中的C同學，過去想套近乎，插個隊，如果該同學同意了，這意味著原來C同學前面的人變成了Z，B同學後面的人也從C變成了Z同學，同時從所插入位置後面的所有同學都需要向後移動一個位置，後面的同學莫名其妙的就退後了一個位置

我們來想一下如何用程式碼實現它呢，並且有些什麼需要特別考慮到的事情呢？

• 1、插入元素位置的合法以及有效性
• 插入的有效範圍：[0,curLength] 說明：curLength：當前有效位置
• 2、檢查是否表滿，表滿不能繼續添加，否則發生溢出錯誤
• A：不執行操作，報錯退出 (為避免可以將數組初始大小設置大一些)
• B：動態擴容，擴大數組容量 (下例採用)
• 3、首尾節點的特殊插入情況考慮
• 4、移動方向
• 利用循環，從表尾開始逐次移動，如果從插入位置開始，會將後面的未移動元素覆蓋掉

template <class elemType>  void seqList<elemType>::insert(int i, const elemType &value) {        //合法的插入範圍為【0..curlength】      if (i < 0 || i > curLength) throw outOfRange();      //表滿，擴大數組容量      if (curLength == maxSize) resize();      for (int j = curLength; j > i; j--)          //下標在【curlength-1..i】範圍內的元素往後移動一步          data[j] = data[j - 1];      //將值為value的元素放入位序為i的位置      data[i] = value;      //表長增加      ++curLength;    }  

(四) 刪除

既然理解了插入操作，趁熱打鐵，先認識一下對應的刪除操作，這個操作是什麼流程呢？還是上面的例子，插隊後的同學被管理人員發現，不得不離開隊伍，這樣剛才被迫集體後移的那些同學就都又向前移動了一步，當然刪除位置的前後繼關係也發生了改變

與插入相同，它又有什麼注意之處呢?

• 1、刪除元素位置的合法以及有效性
• 刪除的有效範圍：[0,curLength - 1]
• i < 0 || i > curLength- 1隱性的解決了判斷空表的問題
• 2、移動方向
• 利用循環，從刪除元素的位置後開始逐次前移

template <class elemType>  void seqList<elemType>::remove(int i) {        //合法的刪除範圍      if(i < 0 || i > curLength- 1) throw outOfRange();      for(int j = i; j < curLength - 1; j++)          data[j] = data[j+1];      --curLength;  }  

(五) 擴容操作

還記得嗎，我們在構造函數中，定義了數組的長度 seqList<elemType>::seqList(int initSize) { 程式碼內容}

同時我們將這個初始化的指定參數值做為了 數組的長度

maxSize = initSize;

為什麼我們不直接指定構造函數中的參數為 maxSize呢？

從變數名可以看出這是為了說明初始值和最大值不是同一個數據，也可以說是為了擴容做準備，

為什麼要擴容呢？

數組中存放著線性表，但是如果線性表的長度（數據元素的個數）達到了數組長度會怎麼樣？很顯然我們已經沒有多餘的空間進行例如插入這種操作，也稱作表滿了，所以我們定義一個擴容的操作，當涉及到可能表滿的情況，就執行擴容操作

擴容是不是最好的方式？

雖然數組看起來有一絲不太靈光，但是數組確實也是存儲對象或者數據的有效方式，我們也推薦這種方式，但是由於其長度固定，導致它在很多時候會受到一些限制，就例如我們上面的表滿問題，那麼如何解決呢？方法之一就是我們設置初始值比實際值多一些，但是由於實際值往往會有一些波動，就會導致佔用過多的記憶體空間造成浪費，或者仍發生表滿問題，為了解決實際問題，很顯然還是擴容更加符合需要，但是代價就是一定的效率損失

數組就是一個簡單的線性序列，這使得元素訪問非常快速。但是為這種速度所付出的代價是數組對象的大小被固定，並且在其生命周期中不可改變

我們看一下擴容的基本原理你就知道原因了！

擴容思想：

由於數組空間在記憶體中是必須連續的，因此，擴大數組空間的操作需要重新申請一個規模更大的新數組，將原有數組的內容複製到新數組中，釋放原有數組空間，將新數組作為線性表的存儲區

所以為了實現空間的自動分配，儘管我們還是會首選動態擴容的方式，但是這種彈性顯然需要一定的開銷

template <class elemType>  void seqList<elemType>::resize() {        elemType *p = data;      maxSize *= 2;      data = new elemType[maxSize];      for(int i = 0; i < curLength; ++i)          data[i] = p[i];      delete[] p;    }  

(六) 按值查找元素

順序查找值為value的元素第一次出現的位置，只需要遍歷線性表中的每一個元素數據，依次與指定value值比較

• 相同：返回值的位序
• 注意查詢的有效範圍
• 找不到或錯誤：返回 -1

template<class elemType>  int seqList<elemType>::search(const elemType & value) const  {        for(int i = 0; i < curLength; i++)          if(value == data[i])return i;      return - 1;    }  

(七) 按位置(下標)查找元素

這個就真的很簡單了，直接返回結果即可

template<class elemType>  elemType seqList<elemType>::visit(int i) const {        return data[i];    }  

(八) 遍曆元素

遍歷是什麼意思呢？遍歷其實就是每一個元素都訪問一次，從頭到尾過一遍，所以我們就可以利用遍歷實現查詢，或者輸出等功能，如果表是空表，就輸出資訊提示，並且注意遍歷的有效範圍是[0，最後一個元素 - 1]

template<class elemType>  void seqList<elemType>::traverse()const {        if (empty())          cout << "is empty" << endl;      else {          cout << "output element:n";          //依次訪問順序表中的所有元素          for (int i = 0; i < curLength; i++)              cout << data[i] << " ";          cout << endl;      }    }  

(九) 逆置運算

逆置運算顧名思義 ，就是將線性表中的數據顛倒一下，也就是說首元素和尾元素調換位置，然後就是第二個元素和倒數第二個元素調換，接著向中間以對為單位繼續調換，也可以稱作收尾對稱交換，需要注意的就是循環的次數僅僅是線性表長度的一半而已

template<class elemType>  void seqList<elemType>::inverse() {        elemType tem;      for(int i = 0; i < curLength/2; i++) {          //調換的具體方式，可以設置一個中間值          tem = data[i];          //對稱的兩個數據          data[i] = data[curLength - i -1];          data[curLength - i -1] = tem;      }    }  

(十) 合併順序表

現在給出兩個線性表，表A和表B，其中的元素均為正序存儲，如何可以合併兩個表，放於A表中，但是表中的元素仍然保證正序存儲

演算法思想：我們分別設置三個指針，分別代表了A B C，C 代表新表，我們分別讓三個指針指向三個表的末尾，將A表和B表的尾元素進行比較，然後將大的移入新A表中，然後將大的元素所在線性表的指針和新表的指針，前移一位 ，這樣A和B表繼續比較元素大小，重複操作，直到一方表空，將還有剩餘的那個表的剩餘元素移入新A表中

template<class elemType>  bool seqList<elemType>::Union(seqList<elemType> &B) {        int m, n, k, i, j;      //當前對象為線性表A      //m,n分別為線性表A和B的長度      m = this->curLength;      n = B.curLength;      //k為結果線性表的工作指針（下標）新A表中      k = n + m - 1;      //i,j分別為線性表A和B的工作指針（下標）      i = m - 1, j = n - 1;      //判斷表A空間是否足夠大，不夠則擴容      if (m + n > this->maxSize)          resize();      //合併順序表，直到一個表為空      while (i >= 0 && j >= 0)          if (data[i] >= B.data[j])              data[k--] = data[i--];          //默認當前對象，this指針可省略          else data[k--] = B.data[j--];      //將表B中的剩餘元素複製到表A中      while (j >= 0)          data[k--] = B.data[j--];      //修改表A長度      curLength = m + n;      return true;    }  

順序表的優缺點

優點：

1. 邏輯與物理順序一致，順序表能夠按照下標直接快速的存取元素
2. 無須為了表示表中元素之間的邏輯關係而增加額外的存儲空間

缺點：

1. 線性表長度需要初始定義，常常難以確定存儲空間的容量，所以只能以降低效率的代價使用擴容機制
2. 插入和刪除操作需要移動大量的元素，效率較低

時間複雜度證明

讀取：

還記的這個公式嗎？

Loc(a_i) = Loc(a_1) + (i -1)*L

通過這個公式我們可以在任何時候計算出線性表中任意位置的地址，並且對於電腦所使用的時間都是相同的，即一個常數，這也就意味著，它的時間複雜度為 O(1)

插入和刪除：

我們以插入為例子

• 首先最好的情況是這樣的，元素在末尾的位置插入，這樣無論該元素進行什麼操作，均不會對其他元素產生什麼影響，所以它的時間複雜度為 O(1)
• 那麼最壞的情況又是這樣的，元素正好插入到第一個位置上，這就意味著後面的所有元素全部需要移動一個位置，所以時間複雜度為 O(n)
• 平均的情況呢，由於在每一個位置插入的概率都是相同的，而插入越靠前移動的元素越多，所以平均情況就與中間那個值的一定次數相等，為 (n - 1) / 2 ，平均時間複雜度還是 O(n)

總結：

讀取數據的時候，它的時間複雜度為 O(1)，插入和刪除數據的時候，它的時間複雜度為 O(n)，所以線性表中的順序表更加適合處理一些元素個數比較穩定，查詢讀取多的問題

結尾：

如果文章中有什麼不足，或者錯誤的地方，歡迎大家留言分享想法，感謝朋友們的支援！

郵箱：[email protected]

如果能幫到你的話，那就來關注我吧！

如果您更喜歡微信文章的閱讀方式，可以關注我的公眾號

如果您更加喜歡PC端的閱讀方式，可以訪問我的個人部落格

域名：www.ideal-20.cn

在這裡的我們素不相識，卻都在為了自己的夢而努力 ❤ 一個堅持推送原創Java技術的公眾號：理想二旬不止