資料結構之線性表的順序存儲

一 概述

線性表的順序存儲又稱作順序表，它是一組位址連續的存儲單元依次存儲線性表中的資料元素，進而使得邏輯上相鄰的兩個元素在實體位置上也相鄰。第1個元素存儲線上性表的起始位置，第i個元素的存儲位置後面緊接者存儲的是第i+1個元素，稱i為元素ai線上性表中的位序。是以，順序表的特點是表中元素的邏輯順序與其實體順序相同。

二 順序表與數組之間的關系

假設線性表L存儲的起始位置為LOC(A)，sizeof(ElemType)是每個元素所占用的記憶體空間的大小；

線性表所對應的順序存儲

注意：線性表中元素的位序是從1開始的，而數組中元素的下标是從0開始的。一維數組可以是靜态配置設定的，也可以是動态配置設定的。

靜态配置設定：在靜态配置設定時，由于數組的大小和空間實作已經固定，一旦空間占滿，再加入新的資料将會産生溢出，進而導緻程式崩潰。

動态配置設定：在動态配置設定時，由于存儲數組的空間是在程式執行過程中通過動态存儲配置設定語句配置設定的，一旦資料空間占滿，就另外開辟一塊更大的存儲空間，用以替換原來的存儲空間，進而達到擴充存儲數組空間的目的，而不需要為線性表一次性地劃分所有空間。

注意：動态配置設定并不是鍊式存儲，它同樣屬于順序存儲結構，實體結構沒有變化，依然是随機存取方式，隻是配置設定的空間大小可以在運作時決定。

三 順序表的特點

順序表最主要的特點是随機通路，即通過首位址和元素序号可在時間O(1)内找到指定的元素。

順序表的存儲密度高，每個結點隻存儲資料元素。

順序表邏輯上相鄰的元素實體上也相鄰，是以插入和删除操作需要移動大量元素。

順序表在存儲二叉樹的時候，适合存儲完全二叉樹，按層序周遊。對于非完全二叉樹，會存在空值元素。

四 順序表的代碼實作

代碼頭部分與宏定義：

#include<iostream>
using namespace std;

//宏定義
#define OK 1 
#define ERROR 0
#define OVERFLOW 2
#define MAXSIZE 100 //順序表可能達到的最大長度
           

資料類型重命名部分：

typedef int Status;    //Status 是函數傳回值類型，其值是函數結果狀态碼
typedef int ElemType;  //ElemType 為可定義的資料類型，此處設定為int類型

typedef struct 
{
    ElemType *elem;    //存儲空間的基位址
    int length;        //順序表的目前長度
}SqList;               //可以作為類型聲明新的結構體變量
           

初始化順序表：

//初始化順序表
Status InitList_Squeue(SqList &L) {
    
    L.elem = new ElemType[MAXSIZE];

    //C語言中，exit(1)表示異常退出，exit(0)表示正常退出。

    /*exit是系統級别的調用，是一個函數，
     *表示一個程序的結束。
     *exit在調用處強行退出程式，運作依次就結束。
     */
    if(!L.elem) exit(OVERFLOW); //存儲配置設定失敗
    L.length = 0;               //空表長度為0

    /*return是語言級别的，是關鍵字，他表示調用堆棧的傳回，
     *return用于一個結束一個函數的執行，在一般函數中将函數
     *的執行資訊傳給其他調用函數使用，如果是main函數則結束
     *并退出程式。
     */

    return OK;
}
           

順序表的查找：

//順序表的查找
int LocateElem_Squeue(SqList L, ElemType e){
    
    for(int i; i < L.length; i++){
        if(L.elem[i] == e)
        return i+1;    //順序表中i+1表示是數組中第i個位置的資料在順序表中的序列
        return 0;
    }
}
           

順序表的插入：

//在順序表L中第i個位置插入新的元素e,i的合法範圍為1<= i <= L.length+1(插入)
//插入的過程中，增加一個資料位，需要移動資料時，先移動資料，然後将資料插入
Status ListInsert_Squeue(Sqlist &L, ElemType e){
    
    if(i<1 || i>L.length + 1) return ERROR;  //i值不合法
    if(L.length == MAXSIZE) return ERROR;    //目前存儲空間已滿，達到了資料表的最大值
    
    for(int j = L.length - 1; j >= i-1; j--) {
        
        L.elem[j+1] = L.elem[j];    //插入位置及之後的元素後移
        L.elem[i-1] = e;            //将新元素e放入第i個位置
        ++L.length;                 //表長增1
        return OK;                  
    }
}
           

順序表的删除：

/*順序表在删除資料的時候，先删除某個資料然後将删除後的資料前移
 *順序表的删除
 *在順序表中L中删除第i個元素，并用e傳回其值
 *i值的合法範圍是1<=i<=L.length
 */
Status ListDelete_Squeue(SqList &L, int i, ElemType &e) {
    
    if(i<1 || i>L.length) return ERROR;    //i值不合法
    e = L.elem[i-1];                       //将欲删除的元素保留在e中
    for(int j=i;j <= L.length;j++) {        
        L.elem[j-1] = L.elem[j];           //被删除元素之後的元素前移
        --L.length;                        //表長減1
        return OK;
    }   
}