数据结构1-顺序表的基础实现_数据结构顺序表上基本操作的实现

目录

1. 定义顺序表类型

2. 初始化顺序表

3. 在顺序表中插入元素

4. 在顺序表中删除元素

5. 按位查找元素

6. 按值查找元素

7. 初始化顺序表并向其中插入元素

8. 动态分配顺序表

---

本篇博客主要介绍了顺序表的基本操作，顺序表是一种线性表，其在物理地址上连续存储。本文所介绍的代码使用的是静态数组。

        首先，我们需要定义一个顺序表的结构体类型Sqlist，其中包含两个成员变量：data和length，分别表示存储数据元素的数组和当前顺序表中元素的个数。MaxSize表示顺序表的最大长度。

        然后，我们需要对该顺序表进行初始化。在InitList函数中，将顺序表的元素个数设置为0，即表示该顺序表为空表。

        接着，我们可以实现在顺序表中插入元素或删除元素的操作。具体而言，ListInsert函数用于在顺序表的第i个位置插入新元素e，ListDelete函数用于删除顺序表中第i个元素。需要注意的是，在进行插入或删除操作前，需要判断该操作是否合法。如果待插入位置不在顺序表的范围内，或者顺序表已经达到最大长度，那么该操作就是非法的。

        此外，我们还可以通过顺序表的位序或值查找元素。具体而言，GetElem函数用于按位查找元素，返回顺序表中第i个元素的值；LocateElem函数用于按值查找元素，返回顺序表中第一个值等于e的元素的位序。需要注意的是，在进行按值查找操作时，需要遍历整个顺序表，直到找到匹配的元素或达到表尾。

        最后，我们在主函数中对顺序表进行初始化，并向其中插入一个元素，然后输出顺序表中每个元素的值。除了静态数组，我们还可以使用动态分配数组来实现顺序表。需要注意的是，在使用动态分配数组时，需要进行动态内存分配和释放，以便更好地利用计算机资源。

1. 定义顺序表类型

//静态数组
#define MaxSize 10 //定义最大长度
typedef struct {
    int data[MaxSize];
    int length;
}Sqlist;

可以看到，我们使用了#define关键字定义了顺序表的最大长度MaxSize，这样可以方便地在代码中引用。然后，我们定义了一个结构体类型Sqlist来表示顺序表，其中包含两个成员变量：data和length，分别表示存储数据元素的数组和当前顺序表中元素的个数。

2. 初始化顺序表

void InitList(Sqlist& L) {
    L.length = 0;
}

该函数的作用是将顺序表初始化为空表，即将顺序表中元素个数置为0。

3. 在顺序表中插入元素

bool ListInsert(Sqlist& L, int i, int e) {
    if (i<1 || i>L.length + 1)
        return false;
    if (L.length >= MaxSize)
        return false;
    for (int j = L.length; j >= i; j--)//将第i个元素及之后的元素往后移动
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;
    L.length++;
    return true;
}

ListInsert函数用于在顺序表中的第i个位置插入新元素e。首先，需要判断该操作是否合法，如果待插入位置在顺序表的范围之外，或者顺序表已经达到最大长度，则该操作非法，直接返回false。否则，需要将第i个元素及其后面的元素往后移动一位，为插入元素e腾出空间。然后，将元素e插入到第i个位置，同时将顺序表中元素个数加1。最后，返回true表示插入成功。

4. 在顺序表中删除元素

bool ListDelete(Sqlist& L, int i, int &e) {
    if (i<1 || i>L.length + 1)
        return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

ListDelete函数用于删除顺序表中第i个元素。同样地，需要判断该操作是否合法。如果待删除位置在顺序表的范围之外，则该操作非法，直接返回false。否则，将元素e赋值为第i个元素的值，并将第i个元素及其后面的元素往前移动一位，以删除元素e。最后，将顺序表中元素个数减1，返回true表示删除成功。

5. 按位查找元素

int GetElem(Sqlist L, int i) {
    return L.data[i - 1];
}

GetElem函数用于按位查找元素，即返回顺序表中第i个元素的值。需要注意的是，由于该函数不涉及修改顺序表中的元素，因此可以将参数声明为值传递而不是引用传递。

6. 按值查找元素

int LocateElem(Sqlist L, int e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e)//匹配
            return i + 1;
    return 0;
}

LocateElem函数用于按值查找元素，即返回顺序表中第一个值等于e的元素的位序。需要注意的是，在进行按值查找操作时，需要遍历整个顺序表，直到找到匹配的元素或达到表尾。如果没有找到匹配的元素，则返回0。

7. 初始化顺序表并向其中插入元素

int main() {
    Sqlist L;
    InitList(L);
    ListInsert(L, 3, 3);
    for (int i = 0; i < MaxSize; i++) {
        printf("data[%d]=%d\n", i, L.data[i]);
    }
    return 0;
}

在main函数中，我们首先调用InitList函数将顺序表初始化为空表。然后，使用ListInsert函数向顺序表中的第3个位置插入元素3。最后，遍历整个顺序表，并输出每个元素的值。

8. 动态分配顺序表

除了静态数组，我们还可以使用动态分配数组来实现顺序表。需要注意的是，在使用动态分配数组时，需要进行动态内存分配和释放，以便更好地利用计算机资源。以下是一个简单的动态分配顺序表的代码示例：

#define ElemType int
#define Initsize 10
typedef struct {
    ElemType* data; //表示动态分配数组的指针
    int Maxsize;
    int length;
}SeqList;
 
void InitList(SeqList& L) {
    //用malloc函数申请一片连续的存储空间
    L.data = (int*)malloc(Initsize * sizeof(int));
    L.length = 0;
    L.Maxsize = Initsize;
}
 
//增加动态数组的长度
void IncreaseSize(SeqList& L, int len) {
    int* p = L.data;
    L.data = (int*)malloc((L.Maxsize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];
    }
    L.Maxsize = L.Maxsize + len;
    free(p);
}
 
int main() {
    SeqList L;
    InitList(L);
    IncreaseSize(L, 5);
    return 0;
}

在该代码中，我们首先定义了一个动态分配顺序表的结构体类型SeqList，其中包含三个成员变量，分别表示存储数据元素的数组、当前顺序表中元素的个数以及数组的最大长度。

在InitList函数中，使用malloc函数申请一片连续的存储空间来存储顺序表中的元素，同时将顺序表的元素个数和最大长度初始化为0和预设值Initsize。

如果顺序表中的元素个数已经达到最大长度，我们可以使用IncreaseSize函数来增加顺序表的长度，以容纳更多的元素。该函数首先将原来的存储空间指针p保存起来，然后重新申请一片更大的存储空间，并将之前的元素逐个复制到新的存储空间中，最后释放原来的存储空间。

在main函数中，我们首先调用InitList函数初始化顺序表，然后调用IncreaseSize函数增加顺序表的长度，以容纳更多的元素。