【C語言 資料結構】順序表的使用

文章目錄

• ​​順序表​​

• ​​什麼是順序表​​
• ​​順序表的初始化​​
• ​​順序表插入元素​​
• ​​順序表删除元素​​

順序表

什麼是順序表

順序表又稱順序存儲結構，是線性表的一種，專門存儲邏輯關系為“一對一”的資料。

順序表存儲資料的具體實作方案是：将資料全部存儲到一整塊記憶體空間中，資料元素之間按照次序挨個存放。

舉個簡單的例子，将 {1,2,3,4,5} 這些資料使用順序表存儲，資料最終的存儲狀态如下圖所示：

順序表的初始化

使用順序表存儲資料，除了存儲資料本身的值以外，通常還會記錄以下兩樣資料：

• 順序表的最大存儲容量：順序表最多可以存儲的資料個數；
• 順序表的長度：目前順序表中存儲的資料個數。

C 語言中，可以定義一個結構體來表示順序表：

// TODO 定義結構體
typedef struct {
    ElemType *elem;
    int length;
    int listSize;
} SeqList;      

嘗試建立一個順序表，例如：

//TODO 構造空的線性表L
void initList(SeqList *L) {
    L->elem = (ElemType *) malloc(LISTSIZE * sizeof(char));
    L->length = 0;
    L->listSize = LISTSIZE;
}      

如上所示，整個建立順序表的過程都封裝在一個函數中，建好的順序表可以存儲 5 個邏輯關系為“一對一”的整數。

通常情況下，malloc() 函數都可以成功申請記憶體空間，當申請失敗時，示例程式中進行了“輸出失敗資訊和強制程式退出”的操作，您可以根據實際需要修改代碼。

順序表插入元素

向已有順序表中插入資料元素，根據插入位置的不同，可分為以下 3 種情況：

• 插入到順序表的表頭；
• 在表的中間位置插入元素；
• 尾随順序表中已有元素，作為順序表中的最後一個元素；

雖然資料元素插入順序表中的位置有所不同，但是都使用的是同一種方式去解決，即：通過周遊，找到資料元素要插入的位置，然後做如下兩步工作：

• 将要插入位置元素以及後續的元素整體向後移動一個位置；
• 将元素放到騰出來的位置上；

例如，在 ​

​{1,2,3,4,5}​

​ 的第 3 個位置上插入元素 6，實作過程如下：

• 周遊至順序表存儲第 3 個資料元素的位置，如圖1 所示：

• 将元素 3、4 和 5 整體向後移動一個位置，如圖 2 所示：

• 将新元素 6 放入騰出的位置，如圖 3 所示：

是以，順序表插入資料元素的 C 語言實作代碼如下：

// TODO 插入
void insertList(SeqList *L, int loc, char c) {
    //存儲空間已滿
    if (L->length >= L->listSize) {
        L->elem = (ElemType *) realloc(L->elem, (L->listSize + LISTINCREMENT) * sizeof(char));
        L->listSize += LISTINCREMENT;
    }
    for (int k = L->length; k > loc; k--) {
        L->elem[k] = L->elem[k - 1];
    }
    L->length++;
    L->elem[loc] = c;
}      

順序表删除元素

從順序表中删除指定元素，實作起來非常簡單，隻需找到目标元素，并将其後續所有元素整體前移 1 個位置即可。

後續元素整體前移一個位置，會直接将目标元素删除，可間接實作删除元素的目的。

例如，從 ​

​{1,2,3,4,5}​

​ 中删除元素 3 的過程如圖 4 所示：

是以，順序表删除元素的 C 語言實作代碼為：

// TODO 删除
void delList(SeqList *L, int loc) {
    for (int j = loc; j < L->length; j++) {
        L->elem[j - 1] = L->elem[j];
    }
    L->length--;
}      

完整的代碼如下所示

#include "stdio.h"
#include "windows.h"
#include "stdlib.h"

// TODO 定義常量
#define LISTSIZE 10
#define LISTINCREMENT 2

typedef char ElemType;

// TODO 定義結構體
typedef struct {
    ElemType *elem;
    int length;
    int listSize;
} SeqList;

//TODO 構造空的線性表L
void initList(SeqList *L) {
    L->elem = (ElemType *) malloc(LISTSIZE * sizeof(char));
    L->length = 0;
    L->listSize = LISTSIZE;
}

// TODO 增加
void appendList(SeqList *L, char c) {
    L->elem[L->length++] = c;
}

// TODO 插入
void insertList(SeqList *L, int loc, char c) {
    //存儲空間已滿
    if (L->length >= L->listSize) {
        L->elem = (ElemType *) realloc(L->elem, (L->listSize + LISTINCREMENT) * sizeof(char));
        L->listSize += LISTINCREMENT;
    }
    for (int k = L->length; k > loc; k--) {
        L->elem[k] = L->elem[k - 1];
    }
    L->length++;
    L->elem[loc] = c;
}

// TODO 删除
void delList(SeqList *L, int loc) {
    for (int j = loc; j < L->length; j++) {
        L->elem[j - 1] = L->elem[j];
    }
    L->length--;
}
// TODO 列印
void printList(SeqList *L){
    for (int i = 0; i < L->length; ++i) {
        printf("%c",L->elem[i]);
    }
    printf("\n");
}
void combine(SeqList *a, SeqList *b, SeqList *c)
{
    int i=0, j=0, k=0;
    //同時掃描兩個表
    while(i<a->length && j<b->length)
    {
        if(a->elem[i]<=b->elem[j])
        {
            c->elem[k] = a->elem[i];
            i++;
            k++;
        }
        else
        {
            c->elem[k] = b->elem[j];
            j++;
            k++;
        }
    }
    //A表掃完，B組未掃完
    if(i==a->length)
    {
        for(; j<b->length; j++)
        {
            c->elem[k] = b->elem[j];
            k++;
        }
    }
    if(j==b->length)
    {
        for(; i<a->length; i++)
        {
            c->elem[k] = a->elem[i];
            k++;
        }
    }
    c->length=k;
}

int main() {
    char a[] = "ajcniydu";
    SeqList list;
    // TODO 初始化順序表
    initList(&list);
    printf("%d\n", list.length);
    for (int i = 0; i < strlen("ajcniydu"); i++) {
        appendList(&list, a[i]);
    }
    printList(&list);
    printf("%d\n", list.length);
    insertList(&list, 3, 'p');
    printList(&list);
    printf("%d\n", list.length);
    delList(&list, 3);
    printList(&list);
    printf("%d\n", list.length);
    SeqList aList;
    SeqList bList;
    SeqList cList;
    initList(&aList);
    initList(&bList);
    initList(&cList);

    char a1[] = {'1','3','5','7'};
    char a2[] = {'2','4','6'};
    for (int i = 0; i < 4; i++) {
        appendList(&aList, a1[i]);
    }
    for (int i = 0; i < 3; i++) {
        appendList(&bList, a2[i]);
    }
    combine(&aList,&bList,&cList);
    printList(&cList);
    return 0;
}