線性表的順序表示和實(shí)現(xiàn)

前文我們提到過(guò)線性表是邏輯結(jié)構(gòu)，只說(shuō)明了數(shù)據(jù)元素之間的相互關(guān)系，想要使用線性表，我們還需要在計(jì)算機(jī)上表示出這些數(shù)據(jù)元素以及元素之間的關(guān)系。而對(duì)于同一種邏輯結(jié)構(gòu)，可以有多種存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)它。線性表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，可以用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種不同方式來(lái)實(shí)現(xiàn)，本節(jié)主要說(shuō)明線性表的順序表示。

---

1 線性表的順序表示

1.1 順序表的定義

線性表的順序存儲(chǔ)又稱為順序表， 它是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素，從而使得邏輯上相鄰的兩個(gè)元素在物理地址上也相鄰。順序表的特點(diǎn)是表中元素的邏輯順序與其物理順序相同。順序表是一種存儲(chǔ)結(jié)構(gòu)，關(guān)注的是如何在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)元素及其關(guān)系。

1.2 順序表的特點(diǎn)

假設(shè)線性表的每個(gè)元素需占用 $l$ 個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第 $i+1$ 個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 $LOC(a_i+1)$ 和第 $i$ 個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 $LOC(a_i)$ 之間滿足下列關(guān)系：
$$LOC(a_i+1)=LOC(a_i)+l$$
一般來(lái)說(shuō)，線性表的第 $i$ 個(gè)數(shù)據(jù)元素 $a_i$ 的存儲(chǔ)位置為：
$$LOC(a_i)=LOC(a_1)+(i?1)?l$$
其中 $LOC(a_1)$ 是線性表的第一個(gè)數(shù)據(jù)元素 $a_1$ 的存儲(chǔ)位置，也被稱為線性表的起始位置或基地址。

觀察上圖我們可以發(fā)現(xiàn)，順序表的每一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置都和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比的常數(shù)。由此，只要確定了存儲(chǔ)線性表的起始位置，表中任一數(shù)據(jù)元素都可以隨機(jī)存取（也稱為直接訪問(wèn)），所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。更廣泛地說(shuō)，順序存儲(chǔ)一般對(duì)應(yīng)隨機(jī)存取。

總結(jié)
順序表有以下主要特點(diǎn)：

• 隨機(jī)存取，讀取（或查找）操作時(shí)間復(fù)雜度為 $O(1)$ 。
• 存儲(chǔ)密度高，每個(gè)節(jié)點(diǎn)只存儲(chǔ)數(shù)據(jù)元素。
• 邏輯上相鄰的元素物理上也相鄰，因此插入和刪除操作需要移動(dòng)大量元素。

---

2 順序表的實(shí)現(xiàn)

由于高級(jí)程序語(yǔ)言中的數(shù)組類型也有隨機(jī)存取的特性，因此通常用數(shù)組來(lái)描述數(shù)據(jù)結(jié)構(gòu)中的順序存儲(chǔ)結(jié)構(gòu)。

下文的默認(rèn)實(shí)現(xiàn)語(yǔ)言為C++，因此一切未注明的語(yǔ)法都以C++為準(zhǔn)。

2.1 定義

C++中的一維數(shù)組可以是靜態(tài)分配的，也可以是動(dòng)態(tài)分配的。詳情見(jiàn)C++動(dòng)態(tài)數(shù)組。

• 靜態(tài)分配時(shí)，由于數(shù)組的大小和空間已經(jīng)事先決定了，一但空間占滿，再加入新的數(shù)據(jù)就會(huì)產(chǎn)生溢出，導(dǎo)致程序崩潰。

  /*** 靜態(tài)數(shù)組實(shí)現(xiàn)順序表的類型定義 ***/ #define MaxSize 10typedef int elemType; // 定義新的類型elemType typedef struct{elemType data[MaxSize]; // ElemType為指定元素類型int length; } SqList;

• 動(dòng)態(tài)分配就不存在這樣的問(wèn)題，一旦空間占滿，就另外開(kāi)辟一塊更大的存儲(chǔ)空間，用以替換原來(lái)的空間。但要注意的是，動(dòng)態(tài)分配并不是鏈?zhǔn)酱鎯?chǔ)，它同樣屬于順序存儲(chǔ)結(jié)構(gòu)，依然是隨機(jī)存取的方式。但是動(dòng)態(tài)數(shù)組需要用戶顯式地釋放內(nèi)存。

  /*** 動(dòng)態(tài)數(shù)組實(shí)現(xiàn)順序表的類型定義 ***/ #define InitSize 50 // 線性表存儲(chǔ)空間的初始分配量 #define Increment 10 // 線性表存儲(chǔ)空間的分配增量typedef int elemType; // 定義新的類型elemType typedef struct{ elemType *data; // 存儲(chǔ)空間基地址int capacity, length // 當(dāng)前分配的最大容量和數(shù)組長(zhǎng)度 } SqList

2.2 主要操作的實(shí)現(xiàn)

在順序存儲(chǔ)下，容易實(shí)現(xiàn)線性表的某些操作，如隨機(jī)存取第 $i$ 個(gè)元素等，因此這里只討論順序表較復(fù)雜的插入、刪除和按值查找操作。

因?yàn)殪o態(tài)數(shù)組的局限性較大，后文正文內(nèi)皆以動(dòng)態(tài)數(shù)組實(shí)現(xiàn)為例展示代碼，靜態(tài)數(shù)組實(shí)現(xiàn)將放于文末附錄。

2.2.1 插入操作

在順序表 $L$ 的第 $i(1\le i\le L.\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}+1)$ 個(gè)位置插入新元素 $e$。若 $i$ 的輸入不合法，則返回 false，表示插入失敗；否則，將第 $i$ 個(gè)元素及其后的所有元素依次往后移動(dòng)一個(gè)位置，順序表長(zhǎng)度增加1，返回 true 。

/*** 動(dòng)態(tài)數(shù)組順序表實(shí)現(xiàn)插入操作 ***/ // 擴(kuò)容操作 void increment(SqList &L){elemType *data = new elemType[L.capacity+Increment]; // 重新申請(qǐng)內(nèi)存for (int i=0;i<L.capacity;i++){ // 將原來(lái)的元素移動(dòng)到新的順序表中data[i] = L.data[i];}delete[] L.data; // 釋放內(nèi)存L.data = data;L.capacity += Increment;printf("Finish Increment.\n"); }// 插入操作 bool listInsert(SqList &L, int i, elemType e){if (i<1 || i>L.length+1){ // 判斷i的范圍是否有效printf("Index is illegal!\n");return false;} if (L.length >= L.capacity){ // 判斷存儲(chǔ)空間是否還有剩余,printf("Need Increment.\n");increment(L); // 不夠則擴(kuò)容}for (int j=L.length;j>=i;j--){ // 將位置i及之后的元素向后移動(dòng)一位L.data[j] = L.data[j-1];}L.data[i-1] = e;L.length++;return true; }

時(shí)間復(fù)雜度分析

對(duì)插入操作來(lái)說(shuō)，插入元素只需要一步，而移動(dòng)元素可能重復(fù)很多次，所以基本操作為移動(dòng)元素。我們只需要關(guān)心每一次插入操作發(fā)生時(shí)，總共移動(dòng)了多少個(gè)元素，而移動(dòng)元素的個(gè)數(shù)取決于插入新元素的位置。

• 最優(yōu)情況：在表尾插入（即 $i=n+1$），元素不用后移，時(shí)間復(fù)雜度為 $O(1)$。
• 最差情況：
  • 靜態(tài)數(shù)組：在表頭插入（即 $i=1$），現(xiàn)存所有元素（共 $n$ 個(gè)）都需后移，時(shí)間復(fù)雜度為 $O(n)$。
  • 動(dòng)態(tài)數(shù)組：在表頭插入且空間不夠，需先執(zhí)行擴(kuò)容操作，移動(dòng)表內(nèi)現(xiàn)存的所有元素，共 $n$ 次。然后再插入新的元素，將表內(nèi)的舊元素全部后移一位，共 $n$ 次。總共需要 $2n$ 次移動(dòng)，時(shí)間復(fù)雜度為 $O(n)$。
• 平均情況：令 $p_i$ 為在第 $i$ 個(gè)位置上插入一個(gè)元素的概率，假設(shè)任意一個(gè)位置上發(fā)生插入元素的概率是相等的，那么 $p_i=\frac{1}{(n+1)}$。在長(zhǎng)度為 $n$ 的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)元素的平均次數(shù)為
  $$\sum _{i=1}^{n+1}{p}_i(n?i+1)=\frac{n}{2}$$
  因此，平均情況的時(shí)間復(fù)雜度為 $O(n)$。

2.2.2 刪除操作

刪除順序表 $L$ 中第 $i(1\le i\le L.\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}+1)$ 個(gè)位置的元素，用引用變量 $e$ 返回。若 $i$ 的值不合法，則返回 false ；否則，將被刪除元素賦給引用變量 $e$ ，并將第 $i=1$ 個(gè)元素及其后的所有元素依次往前移動(dòng)一個(gè)位置，返回 true 。

/*** 動(dòng)態(tài)數(shù)組順序表實(shí)現(xiàn)刪除操作 ***/ // 刪除操作 bool listDelete(SqList &L, int i, elemType &e){if (i<1 || i>L.length){ // 判斷i的范圍是否有效printf("Index is illegal!\n");return false;}e = L.data[i-1]; // 將被刪除的元素的值賦給efor (int j=i;j<L.length;j++){ // 將位置i以后的元素向前移動(dòng)一位L.data[j-1] = L.data[j];}L.length--;return true; }

時(shí)間復(fù)雜度分析

分析和插入操作類似，刪除操作的基本操作也是對(duì)元素的移動(dòng)。

• 最優(yōu)情況：在表尾刪除（即 $i=n$），元素不用后移，時(shí)間復(fù)雜度為 $O(1)$。
• 最差情況：在表頭刪除（即 $i=1$），現(xiàn)存所有元素（共 $n$ 個(gè)）都需前移，時(shí)間復(fù)雜度為 $O(n)$。
• 平均情況：令 $p_i$ 為在第 $i$ 個(gè)位置上刪除一個(gè)元素的概率，假設(shè)任意一個(gè)位置上發(fā)生插入元素的概率是相等的，那么 $p_i=\frac{1}{n}$。在長(zhǎng)度為 $n$ 的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)元素的平均次數(shù)為
  $$\sum _{i=1}^n{p}_i(n?i)=\frac{n?1}{2}$$
  因此，平均情況的時(shí)間復(fù)雜度為 $O(n)$。

2.2.3 按值查找操作

在順序表 $L$ 中查找第一個(gè)元素值等于 $e$ 的元素，并返回其位序。

/*** 動(dòng)態(tài)數(shù)組順序表實(shí)現(xiàn)按位查找操作 ***/ // 按值查找操作 int locateElem(SqList L, elemType e){for (int i=0;i<L.length;i++){if (L.data[i] == e){return i+1;}}return 0; }

時(shí)間復(fù)雜度分析
查找操作的基本操作是比較元素，因此我們只關(guān)注元素的比較次數(shù)。

• 最優(yōu)情況：查找元素就在表頭（即 $i=1$），只用比較一次，時(shí)間復(fù)雜度為 $O(1)$。
• 最差情況：查找元素在表尾（即 $i=n$）或不存在時(shí)，需要比較表內(nèi)的所有元素，共 $n$ 次，時(shí)間復(fù)雜度為 $O(n)$。
• 平均情況：令 $p_i$ 為查找元素出現(xiàn)在第 $i$ 個(gè)位置上的概率，假設(shè)任意一個(gè)位置上發(fā)生插入元素的概率是相等的，那么 $p_i=\frac{1}{n}$。在長(zhǎng)度為 $n$ 的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)元素的平均次數(shù)為
  $$\sum _{i=1}^n{p}_i\times i=\sum _{i=1}^n\frac{1}{n}\times i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}$$
  因此，平均情況的時(shí)間復(fù)雜度為 $O(n)$。

---

參考資料：
【C++】細(xì)說(shuō)C++中的數(shù)組之“靜態(tài)”數(shù)組
【C++】細(xì)說(shuō)C++中的數(shù)組之動(dòng)態(tài)數(shù)組

相關(guān)章節(jié)

第一節(jié) 【緒論】數(shù)據(jù)結(jié)構(gòu)的基本概念
第二節(jié) 【緒論】算法和算法評(píng)價(jià)
第三節(jié) 【線性表】線性表概述
第四節(jié) 【線性表】線性表的順序表示和實(shí)現(xiàn)
第五節(jié) 【線性表】線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
第六節(jié) 【線性表】雙向鏈表、循環(huán)鏈表和靜態(tài)鏈表
第七節(jié) 【棧和隊(duì)列】棧
第八節(jié) 【棧和隊(duì)列】棧的應(yīng)用
第九節(jié) 【棧和隊(duì)列】棧和遞歸
第十節(jié) 【棧和隊(duì)列】隊(duì)列

---

附錄

靜態(tài)數(shù)組實(shí)現(xiàn)順序表的完整代碼

/** File: SqList.h* -------------------------* Using struct to implement SqList*//********** 使用靜態(tài)數(shù)組實(shí)現(xiàn)順序表 **********/ #ifndef _STATIC_SEQUENTIAL_LIST_h_ #define _STATIC_SEQUENTIAL_LIST_h_#include <stdio.h> #include <iostream> using namespace std;/*** 靜態(tài)數(shù)組順序表的定義 ***/ #define MaxSize 10 // 默認(rèn)靜態(tài)數(shù)組最大容量為10typedef int elemType; // 定義新的類型elemType typedef struct {elemType data[MaxSize];int length; // 記錄靜態(tài)數(shù)組的有效長(zhǎng)度 } SqList;/*** 基本操作的實(shí)現(xiàn) ***/ // 初始化操作 void initList(SqList &L){L.length = 0; // 將有效長(zhǎng)度歸零 }// 銷毀操作 void destroyList(SqList &L){}// 判空操作 bool listEmpty(SqList L){return not L.length; }// 求表長(zhǎng)操作 int listLength(SqList L){return L.length; }// 按位查找操作，如果存在返回1，否則返回0 int getElem(SqList L, int i, elemType &e){if (i<1 || i>L.length) {printf("Index is illegal!\n");return 0;} else {e = L.data[i-1];return 1;} }// 按值查找操作，返回第一個(gè)符合查找要求的元素的位置，如果不存在則返回0 int locateElem(SqList L, elemType e){for (int i=0;i<L.length;i++){if (L.data[i] == e){return i+1;}}return 0; }// 插入操作，在位值i處插入元素e bool listInsert(SqList &L, int i, elemType e){if (i<1 || i>L.length+1){ // 判斷i的范圍是否有效printf("Index is illegal!\n");return false;} if (L.length >= MaxSize){ // 判斷存儲(chǔ)空間是否還有剩余printf("Out of space!\n");return false;}for (int j=L.length;j>=i;j--){ // 將位置i及之后的元素向后移動(dòng)一位L.data[j] = L.data[j-1];}L.data[i-1] = e;L.length++;return true; }// 刪除操作，刪除第i個(gè)位置的元素，并用e返回刪除元素的值 bool listDelete(SqList &L, int i, elemType &e){if (i<1 || i>L.length){ // 判斷i的范圍是否有效printf("Index is illegal!\n");return false;}e = L.data[i-1]; // 將被刪除的元素的值賦給efor (int j=i;j<L.length;j++){ // 將位置i以后的元素向前移動(dòng)一位L.data[j-1] = L.data[j];}L.length--;return true; }// 輸出操作 void listPrint(SqList L){for (int i=0;i<L.length;i++){printf("%d ", L.data[i]);}printf("\n"); }#endif // _STATIC_SEQUENTIAL_LIST_h_

動(dòng)態(tài)數(shù)組實(shí)現(xiàn)順序表的完整代碼

/** File: SqList.h* -------------------------* Using struct to implement SqList*//********** 使用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)順序表 **********/ #ifndef _DYNAMIC_SEQUENTIAL_LIST_h_ #define _DYNAMIC_SEQUENTIAL_LIST_h_#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std;/***** 動(dòng)態(tài)數(shù)組順序表的定義 *****/ #define InitSize 10 // 動(dòng)態(tài)數(shù)組初始容量為10 #define Increment 10 // 線性表存儲(chǔ)空間的分配增量typedef int elemType; // 定義新的類型elemType typedef struct {elemType *data;int capacity, length; // 動(dòng)態(tài)數(shù)組當(dāng)前最大容量和有效長(zhǎng)度 } SqList;/***** 基本操作的實(shí)現(xiàn) *****/ // 初始化操作 void initList(SqList &L){L.data = new elemType[InitSize]; // 申請(qǐng)內(nèi)存L.length = 0;L.capacity = InitSize; }// 銷毀操作 void destroyList(SqList &L){if (L.data != NULL){delete[] L.data;L.length = 0;L.capacity = 0;} }// 判空操作 bool listEmpty(SqList L){return not L.length; }// 求表長(zhǎng)操作 int listLength(SqList L){return L.length; }// 按位查找操作 int getElem(SqList L, int i, elemType &e){if (i<1 || i>L.length) {printf("Index is illegal!\n");return 0;} else {e = L.data[i-1];return 1;} }// 按值查找操作 int locateElem(SqList L, elemType e){for (int i=0;i<L.length;i++){if (L.data[i] == e){return i+1;}}return 0; }// 擴(kuò)容操作 void increment(SqList &L){elemType *data = new elemType[L.capacity+Increment]; // 重新申請(qǐng)內(nèi)存for (int i=0;i<L.capacity;i++){ // 將原來(lái)的元素移動(dòng)到新的順序表中data[i] = L.data[i];}delete[] L.data; // 釋放內(nèi)存L.data = data;L.capacity += Increment;printf("Finish Increment.\n"); }// 插入操作 bool listInsert(SqList &L, int i, elemType e){if (i<1 || i>L.length+1){ // 判斷i的范圍是否有效printf("Index is illegal!\n");return false;} if (L.length >= L.capacity){ // 判斷存儲(chǔ)空間是否還有剩余,printf("Need Increment.\n");increment(L); // 不夠則擴(kuò)容}for (int j=L.length;j>=i;j--){ // 將位置i及之后的元素向后移動(dòng)一位L.data[j] = L.data[j-1];}L.data[i-1] = e;L.length++;return true; }// 刪除操作 bool listDelete(SqList &L, int i, elemType &e){if (i<1 || i>L.length){ // 判斷i的范圍是否有效printf("Index is illegal!\n");return false;}e = L.data[i-1]; // 將被刪除的元素的值賦給efor (int j=i;j<L.length;j++){ // 將位置i以后的元素向前移動(dòng)一位L.data[j-1] = L.data[j];}L.length--;return true; }// 輸出操作 void listPrint(SqList L){for (int i=0;i<L.length;i++){printf("%d ", L.data[i]);}printf("\n"); }#endif // _DYNAMIC_SEQUENTIAL_LIST_h_

順序表檢測(cè)程序

/** File name: SqList.cpp* -----------------------* Using struct to implement SqList*/#include "SqList.h"int main(){SqList L;initList(L);int n, i, res;elemType e;char helpInfo[] = "*****************************\n" \"Sequential list check: \n" "\t1-Insert element\n" \"\t2-Delete element\n" \"\t3-Print\n" \"\t4-Empty check\n" \"\t5-Get Length\n" \"\t6-Search by value\n" \"\t7-Search by location\n" \"\t8-Initialization\n" \"\t9-Quit\n" \"*****************************\n"; while (n!= 9){printf(helpInfo);scanf("%d", &n);switch(n){case 1:printf("Please enter the location: ");scanf("%d", &i);printf("Please enter the element: ");scanf("%d", &e);listInsert(L, i, e);break;case 2:printf("Please enter the location: ");scanf("%d", &i);listDelete(L, i, e);printf("Element in location %d with value %d has been deleted.\n", i, e);break;case 3:printf("List: ");listPrint(L);break;case 4:if (listEmpty(L)) {printf("This list is empty!\n");}else {printf("This list is not empty!\n");}break;case 5:printf("Length of list is: %d\n", listLength(L));break;case 6:printf("Please enter the target value: ");scanf("%d", &e);res = locateElem(L, e);if (res) {printf("The index of target is %d\n", res);} else {printf("We didn't find the value.\n");}break;case 7:printf("Please enter the target index: ");scanf("%d", &i);res = getElem(L, i, e);if (res) {printf("The value of target is %d\n", e);}break;case 8:initList(L);printf("List has been initialized.\n");break;}}destroyList(L);return 0; }

總結(jié)

以上是生活随笔為你收集整理的四、【线性表】线性表的顺序表示和实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。