線性表（順序存儲結(jié)構(gòu)）

線性表：包含零個或多個數(shù)據(jù)元素的有限序列。

線性表的順序存儲結(jié)構(gòu)，指的是用一段連續(xù)的存儲單元存儲線性表的數(shù)據(jù)元素。

線性表特性：

  • 是一個序列，元素直接是有順序的。
  • 表中元素個數(shù)叫表長，元素個數(shù)可以有多個，也可以為0。
  • 某個元素的上一個元素叫直接前驅(qū)元素，下一個元素叫直接后繼元素。

順序存儲結(jié)構(gòu)特點
使用數(shù)組對元素進行存儲。
優(yōu)點：

  • 可以快速存儲表中任意位置的元素的值。
  • 無需為表中的邏輯關(guān)系增加額外的存儲空間。

缺點：

  • 插入和刪除元素需移動大量的元素。
  • 容易生成存儲空間"碎片"。

時間復雜度

  • 讀取時的時間復雜度為O(1)。
  • 插入、刪除時的時間復雜度為O(n)。
線性表示意圖
線性表插入元素示意圖.png
線性表刪除元素示意圖.png

實現(xiàn)代碼如下：

// 線性表（順序存儲結(jié)構(gòu)）
#include <stdio.h>

#define OK 1      // 執(zhí)行成功
#define ERROR 0   // 執(zhí)行失敗
#define TRUE 1    // 返回值為真
#define FALSE 0   // 返回值為假

#define MAXSIZE 20 // 初始分配存儲空間

typedef int Status; // 函數(shù)返回結(jié)果類型
typedef int ElemType; // 元素類型

// 線性表結(jié)構(gòu)
typedef struct {
    ElemType data[MAXSIZE]; // 存放線性表元素的數(shù)組
    int length; // 線性表長度
} SqList;

/**
 * 初始化線性表
 * @param L 線性表
 * @return 執(zhí)行狀態(tài)
 */
Status InitList(SqList *L) {
    L->length = 0;
    return OK;
}

/**
 * 判斷線性表是否為空
 * @param L 線性表
 * @return 執(zhí)行狀態(tài)
 */
Status ListEmpty(SqList L) {
    if (L.length == 0) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 清空線性表
 * @param L 線性表
 * @return 執(zhí)行狀態(tài)
 */
Status ClearList(SqList *L) {
    // 設置線性表長度為0
    L->length = 0;
    return OK;
}

/**
 * 獲取線性表長度
 * @param L 線性表
 * @return 線性表長度
 */
int ListLength(SqList L) {
    return L.length;
}

/**
 * 獲取線性表中指定位置的元素值
 * @param L 線性表
 * @param i 獲取元素位置下標
 * @param e 獲取元素值
 * @return 執(zhí)行狀態(tài)
 */
Status GetElem(SqList L, int i, ElemType *e) {
    // 數(shù)組長度為空，或下標不在數(shù)組范圍內(nèi)
    if (L.length == 0 || i < 1 || i > L.length) {
        return ERROR;
    }
    // 獲取對應下標元素的值，賦值給e
    *e = L.data[i - 1];
    return OK;
}

/**
 * 定位元素e在線性表中的位置
 * 找到的該元素返回元素下標，未找到該元素返回0
 * @param L 線性表
 * @param e 元素
 * @return 元素在線性表中的下標
 */
int LocateElem(SqList L, ElemType e) {
    int i; // 元素下標
    // 線性表長度為空
    if (L.length == 0) {
        return 0;
    }

    // 遍歷線性表，尋找元素e
    for (i = 0; i < L.length; i++) {
        // 找到元素e，退出循環(huán)
        if (L.data[i] == e) {
            break;
        }
    }

    // 下標大于線性表長度，未找到該元素
    if (i >= L.length) {
        return 0;
    }

    // 返回元素在線性表中的下標
    return i + 1;
}

/**
 * 在線性表中指定位置插入新元素
 * @param L 線性表
 * @param i 插入位置
 * @param e 插入的值
 * @return 執(zhí)行狀態(tài)
 */
Status ListInsert(SqList *L, int i, ElemType e) {
    int k; // 用于遍歷元素的下標

    // 線性表已滿，插入失敗
    if (L->length == MAXSIZE) {
        return ERROR;
    }

    // 插入位置不在線性表范圍內(nèi)，插入失敗
    if (i < 1 || i > L->length + 1) {
        return ERROR;
    }

    // 插入的位置在線性表范圍內(nèi)
    if (i <= L->length) {
        // 從倒數(shù)第二個元素開始到插入位置的元素，全都向后移動一個位置
        for (k = L->length - 1; k >= i - 1; k--) {
            L->data[k + 1] = L->data[k];
        }
    }

    L->data[i - 1] = e; // 將新元素插入
    L->length++; // 線性表長度加1
    return OK;
}

/**
 * 刪除線性表中指定位置的元素
 * 刪除位置的值，將存到元素e中
 * @param L 線性表
 * @param i 刪除位置的下標
 * @param e 刪除位置的值
 * @return 執(zhí)行狀態(tài)
 */
Status ListDelete(SqList *L, int i, ElemType *e) {
    int k; // 用于遍歷元素的下標

    // 線性表長度為空，刪除失敗
    if (L->length == 0) {
        return ERROR;
    }

    // 刪除位置不在線性表范圍內(nèi)，刪除失敗
    if (i < 1 || i > L->length) {
        return ERROR;
    }

    // 將刪除位置元素的值賦值給e
    *e = L->data[i - 1];

    // 刪除位置在線性表范圍內(nèi)
    if (i < L->length) {
        // 從刪除位置的下一個元素到線性表最后一個元素，全都向前移動一個位置
        for (k = i; k < L->length; k++) {
            L->data[k - 1] = L->data[k];
        }
    }
    // 線性表長度減1
    L->length--;
    return OK;
}

/**
 * 打印單個元素
 * @param c 元素值
 * @return 執(zhí)行狀態(tài)
 */
Status visit(ElemType c) {
    printf("%d ", c);
    return OK;
}

/**
 * 遍歷輸出線性表中所有元素
 * @param L 線性表
 * @return 執(zhí)行狀態(tài)
 */
Status ListTravel(SqList L) {
    int i; // 用于遍歷元素的下標

    printf("[ ");
    // 遍歷線性表所有元素
    for (i = 0; i < L.length; i++) {
        visit(L.data[i]); // 打印單個元素
    }
    printf("]\n");
    return OK;
}

/**
 * 合并兩個線性表的值到La中
 * @param La 線性表1
 * @param Lb 線性表2
 */
void unionL(SqList *La, SqList Lb) {
    int i; // 用于遍歷元素的下標
    int La_len, Lb_len; // 線性表La、Lb的長度
    ElemType e; // 用于存放Lb中元素的值

    // 獲取線性表La和Lb的長度
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);

    // 遍歷線性表Lb中的元素
    for (i = 1; i <= Lb_len; i++) {
        // 獲取Lb中i位置元素的值到元素e中
        GetElem(Lb, i, &e);
        // 元素e中的值在La中不存在
        if (!LocateElem(*La, e)) {
            // 將元素e插入La的最后
            ListInsert(La, ++La_len, e);
        }
    }
}

int main() {
    SqList L; // 線性表
    SqList Lb;
    Status status; // 執(zhí)行狀態(tài)
    ElemType e; // 線性表元素
    int result; // 運行結(jié)果
    int j, k; // 用于遍歷元素的下標

    InitList(&L); // 初始化線性表
    printf("初始化線性表L后，L的長度為：%d\n", L.length);

    result = ListEmpty(L); // 獲取線性表是否為空
    printf("L是否為空：%s\n", result == TRUE ? "是" : "否");

    /*** 給L的表頭插入5個元素 ***/
    for (j = 1; j <= 5; j++) {
        status = ListInsert(&L, 1, j); // 向線性表表頭插入值
    }
    printf("在L表頭依次插入1~5后，L中的值為：");
    ListTravel(L); // 遍歷線性表

    printf("插入5個元素后，L的長度為：%d\n", L.length);

    result = ListEmpty(L); // 獲取線性表是否為空
    printf("L是否為空：%s\n", result == TRUE ? "是" : "否");

    /*** 清空L中的元素 ***/
    status = ClearList(&L); // 清空線性表
    printf("清空線性表L后，L的長度為：%d\n", L.length);

    result = ListEmpty(L); // 獲取線性表是否為空
    printf("L是否為空：%s\n", result == TRUE ? "是" : "否");

    /*** 給L的表尾插入10個元素 ***/
    for (j = 1; j <= 10; j++) {
        ListInsert(&L, j, j); // 向線性表表尾插入值
    }
    printf("在L表尾依次插入1~10后，L中的值為：");
    ListTravel(L); // 遍歷線性表

    printf("插入10個元素后，L的長度為：%d\n", L.length);

    /*** 給L的表頭插入一個元素 ***/
    ListInsert(&L, 1, 33); // 向線性表表頭插入元素33

    printf("在L表頭插入元素33后，L中的值為：");
    ListTravel(L); // 遍歷線性表

    printf("插入元素33后，L的長度為：%d\n", L.length);

    /*** 獲取第5個元素的值 ***/
    GetElem(L, 5, &e); // 獲取L中下標為5的元素到e中
    printf("L中第5個元素的值為：%d\n", e);

    /*** 獲取下標為3、4元素的值 ***/
    for (j = 3; j <= 4; j++) {
        k = LocateElem(L, j); // 獲取L中下標為j的元素的值
        if (k) {
            printf("第%d個元素的值為：%d\n", k, j);
        } else {
            printf("沒有值為%d的元素\n", j);
        }
    }

    /*** 刪除表中多個元素 ***/
    k = ListLength(L); // k為表長
    for (j = k + 1; j >= k; j--) {
        status = ListDelete(&L, j, &e); // 刪除L中第j個元素，并把刪除元素的值賦值給e
        if (status == ERROR) {
            printf("刪除第%d個元素失敗\n", j);
        } else {
            printf("刪除第%d個元素的值為：%d\n", j, e);
        }
    }
    printf("刪除表中元素后，L中的值為：");
    ListTravel(L); // 遍歷線性表

    /*** 刪除L中第5個元素 ***/
    j = 5;
    ListDelete(&L, j, &e); // 刪除L中第j個元素，并把刪除元素的值賦值給e
    printf("刪除第%d個元素的值為：%d\n", j, e);

    printf("刪除第%d個元素后，L中的值為：",j);
    ListTravel(L); // 遍歷線性表

    /*** 初始化線性表Lb，給Lb的表頭插入10個元素 ***/
    status = InitList(&Lb); // 初始化線性表Lb
    for (j = 6; j <= 15; j++) {
        status = ListInsert(&Lb, 1, j); // 向Lb表頭插入10個元素
    }
    printf("插入10個元素后，Lb中的值為：");
    ListTravel(Lb);

    /*** 合并L和Lb的值到L中 ***/
    unionL(&L, Lb); // 合并兩個線性表的值到L中

    printf("合并L和Lb到L后，L中的值為：");
    ListTravel(L); // 遍歷線性表

    return 0;
}
運行結(jié)果.png
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

  • 一、線性表的順序存儲結(jié)構(gòu) 線性表有兩種物理存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 順序存儲結(jié)構(gòu) ①定義：用一段地址...
    我可能是個假開發(fā)閱讀 1,443評論 0贊 7
  • 數(shù)據(jù)結(jié)構(gòu)與算法-目錄 1、線性表的定義：有零個或多個數(shù)據(jù)元素組成的有序數(shù)列。 線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)。在實際應...
    香沙小熊閱讀 2,805評論 0贊 6
  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應的運算，而且確保經(jīng)過這...
    Winterfell_Z閱讀 6,584評論 0贊 13
  • 你們倆個人的價值連城，強哥的約定俗成強哥強的7去了嗎樣好也過得和我好好的我爸棒棒噠和八點半不對勁下班攝像機上個世紀...
    王志博1閱讀 356評論 0贊 0
  • 鴻雁倦了，隨著落葉飛舞，去尋找他北方的歸宿，一次旅行，也悄然拉開了帷幕。背井離鄉(xiāng)，拖著行李，我來到了這個陌生的...
    鴻葉閱讀 285評論 3贊 1

友情鏈接更多精彩內(nèi)容