順序表的基本操作及實作（三）

這篇中，線性表的長度是可變的，且最大存儲空間随問題的不同而不同，在C語言中可用動态配置設定的一維數組。

（由于引用傳參數，是以源檔案需要

.cpp

字尾，即c++檔案存儲。）

即使是動态配置設定記憶體，配置設定的記憶體也必然是一段連續的位址空間，因為這是順序表，這是由其性質即可知道的。

注意此時的

ElemType *data;

,指針變量data指向的是線性表連續存儲空間的首位址，即通過此指針可以順序的找到所有存儲空間。

結構如下：

#define InitSize 100  //線性表存儲空間的初始配置設定量
#define Increment 10  //線性表存儲空間的配置設定增量
typedef int ElemType;

typedef struct {
    ElemType *data;  //存儲空間的基址
    int MaxSize, length;  //分别表示目前配置設定的存儲容量(以sizeof(ElemType)為機關)，和目前長度
}SeqListp;
           

一些基本操作方法如下（具體實作在後附完整源代碼裡）：

void InitList(SeqListp &L); //初始化順序表
bool InsertList(SeqListp &L, int i, ElemType e); //在順序表的第i個位置插入元素
bool DeletList(SeqListp &L, int i, ElemType &e); //删除順序表的第i個位置的元素，并用e傳回
int LocateElem(SeqListp L, ElemType e); //按值順序查找元素，并傳回其位序
ElemType GetElem(SeqListp L, int i, ElemType &e); //查找順序表中指定位置的元素，并用e傳回
           

寫一個測試類，如下：

int main()
{
    int i=1, s, j, e;
    SeqListp seqListp;
    InitList(seqListp);

    scanf("%d", &s);
    while(s != 9999)
    {
        InsertList(seqListp, i++, s);  ///注意i位置要從1開始，否則0位置不插入
        scanf("%d", &s);
    }

    printf("順序表的元素值為：");
    for(j = 0; j < seqListp.length; j++)
    {
        printf("%d ", *(seqListp.data+j));
    }

    DeletList(seqListp, 2, e);
    printf("\n删除順序表中第2個位置的元素，元素值為：%d", e);

    printf("\n順序表的元素值為：");
    for(j = 0; j < seqListp.length; j++)
    {
        printf("%d ", *(seqListp.data+j));
    }

    printf("\n順序表中值為4的元素的位序為：%d", LocateElem(seqListp, 4));

    GetElem(seqListp, 3, e);
    printf("\n順序表中第3個的元素值為：%d", e);

    return 0;
}
           

運作結果如下：

完整的源代碼如下：

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

#define InitSize 100  //線性表存儲空間的初始配置設定量
#define Increment 10  //線性表存儲空間的配置設定增量
typedef int ElemType;

typedef struct {
    ElemType *data;  //存儲空間的基址
    int MaxSize, length;  //分别表示目前配置設定的存儲容量(以sizeof(ElemType)為機關)，和目前長度
}SeqListp;

void InitList(SeqListp &L); //初始化順序表
bool InsertList(SeqListp &L, int i, ElemType e); //在順序表的第i個位置插入元素
bool DeletList(SeqListp &L, int i, ElemType &e); //删除順序表的第i個位置的元素，并用e傳回
int LocateElem(SeqListp L, ElemType e); //按值順序查找元素，并傳回其位序
ElemType GetElem(SeqListp L, int i, ElemType &e); //查找順序表中指定位置的元素，并用e傳回

int main()
{
    int i=1, s, j, e;
    SeqListp seqListp;
    InitList(seqListp);

    scanf("%d", &s);
    while(s != 9999)
    {
        InsertList(seqListp, i++, s);  ///注意i位置要從1開始，否則0位置不插入
        scanf("%d", &s);
    }

    printf("順序表的元素值為：");
    for(j = 0; j < seqListp.length; j++)
    {
        printf("%d ", *(seqListp.data+j));
    }

    DeletList(seqListp, 2, e);
    printf("\n删除順序表中第2個位置的元素，元素值為：%d", e);

    printf("\n順序表的元素值為：");
    for(j = 0; j < seqListp.length; j++)
    {
        printf("%d ", *(seqListp.data+j));
    }

    printf("\n順序表中值為4的元素的位序為：%d", LocateElem(seqListp, 4));

    GetElem(seqListp, 3, e);
    printf("\n順序表中第3個的元素值為：%d", e);

    return 0;
}

void InitList(SeqListp &L)
{
    L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
    if(!L.data)
    {
        exit(1);
    }
    L.length = 0;
    L.MaxSize = InitSize;
}

bool InsertList(SeqListp &L, int i, ElemType e)
{
    ElemType *newbase, *q, *p;
    if(i < 1 || i > L.length + 1)
    {
        return false;
    }
    if(L.length >= L.MaxSize) //重新配置設定大小：realloc()
    {
        newbase = (ElemType*)realloc(L.data, (L.MaxSize + Increment) * sizeof(ElemType));
        if(!newbase)
        {
            exit(1);
        }
        L.data = newbase;
        L.MaxSize += Increment;
    }
    q = L.data + i - 1;  //q為插入位置
    for(p = L.data + L.length -1; p >= q; --p) //依次移動元素
    {
        *(p + 1) = *p;
    }
    *q = e;
    L.length++;

    return true;
}

bool DeletList(SeqListp &L, int i, ElemType &e)
{
    ElemType *p, *q;
    if(i < 1 || i > L.length + 1)
    {
        return false;
    }
    p = L.data + i -1; //p為被删除元素的位置
    e = *p;
    q = L.data + L.length -1;
    for(++p; p <= q; p++) //依次将元素往前挪一個位置，覆寫原位置
    {
        *(p -1) = *p;
    }
    L.length--;

    return true;
}

int LocateElem(SeqListp L, ElemType e)
{
    ElemType *p = L.data;
    int i = 1;
    while(i < L.length)
    {
        if(*(p++) == e)
            return i;   //如果找到，傳回元素的位序i
        i++;
    }
    return 0;
}

ElemType GetElem(SeqListp L, int i, ElemType &e)
{
    if(i < 1 || i > L.length + 1)
    {
        return 0;
    }
    e = *(L.data + i -1);
    return 1;
}