[数据结构与算法]数据结构与算法实战：顺序表

顺序表基本理论

线性表的顺序存储又称顺序表。表中元素的逻辑顺序与其物理顺序相同，存储在一块连续的内存空间上。

我们将带大家实现以下顺序表的基本操作。

? 顺序表：?维数组

? 插?操作：在第K位置插?元素

? 删除操作：删除第K位置的元素

? 查找操作：查找某元素在表中的位置

?修改操作：修改第K位置的元素

顺序表的定义及初始化

#define MAX 10 //定义表长
struct SList
{
    int data[MAX];
    int length; //表的长度或元素个数
};

定义一个名为SList的结构体用于实现顺序表的功能，其中data数组是内存上申请的一块连续的内存空间，用来存放我们的元素数据，定义的整型元素length用来记录我们顺序表的长度或元素个数，我们宏定义的MAX是我们设定的顺序表的长度

void init(struct SList* p)  //初始化表
{
    p->length = 0;
}

初始化将该表的长度置为0即可，无需改动数组内容，我们的插入删除等操作无非都是在顺序表长度的约束下进行的，插入和删除均是对数组原有元素的一种覆盖

操作的实现

为了考虑我们操作的效率，所以我们在传参过程中都传的是顺序表的地址

顺序表的插入：在第K位置插?元素

首先我们要分析，我们插入函数的功能是什么，是对我们要操作的表进行元素的插入，若该位置有元素，则该元素及其之后的元素从最后一个元素开始，依次往后移动一位，那么3个问题就来了

1.对那个表进行操作？ 2.插入那个位置？ 3.插入的元素是什么？

由此可得到我们插入函数的参数形式：(进行插入操作的表，插入位置，插入元素)，参数我们分析好了，那么另一个重要的问题来了：我们的函数返回值是什么呢？首先我们思考，通过这个函数我们要得到什么或是实现什么功能，显然我们是要往顺序表中插入一个元素，那么我们如何知道我们是否插入成功了呢？每次插入后输出一下顺序表显然不是一个很好的方法，那么我们是否可以通过函数的返回值来了解我们的插入操作是否成功呢？这似乎是可行的，由此我们也就确定了我们函数的类型为int型，返回值我们用0表示插入失败，用1表示插入成功

int insert(struct SList* p, int k, int x) //函数的定义,参数形式：(进行插入操作的表，插入位置，插入元素)

接下来就是对这个函数的具体实现了，首要的问题就是，我们的插入操作一定会成功吗？当然不一定，如果我们插入的位置不合法，肯定是不成功的，但是难道插入的位置合法就一定成功吗？合法位置的范围是啥？先思考第二个问题，长度为length的顺序表下标是从0开始的，一直到length-1，我们的插入范围是0-length-1吗？这样显然是不太合适的，为啥？若我们规定插入的位置是0，那么表的开头是可以插入元素的，那么表的末尾呢？好像是不行的，如果我们选择插入length-1的位置，插入之后的结果也只是我们插入的元素位于表中的倒数第二个元素，并未达到我们想要的效果，所以我们选择规定了合法位置为0-length，位置合法了，但是表满了也不能插入成功，所以，当我们插入的另一个条件便是表应该是没有满的。

int insert(struct SList* p, int k, int x)
{
    if (k<0 || k>p->length || p->length == MAX) return 0; //判断条件是否合法，不合法插入失败返回0
    else
    {
        //操作合法，将插入位置及其之后的元素按照从后往前的顺序依次向后移动一位
        for (int i = p->length - 1; i >= k; i--)
        {
            p->data[i + 1] = p->data[i];
        }
        p->data[k] = x;//将我们要插入的元素插入我们要求的位置
        p->length++;//顺序表元素加1
        return 1;//插入成功，返回1
    }

}

顺序表的删除：删除第K位置的元素

删除和插入操作函数大体的思路也是一致的，首先是明确我们要进行删除操作的表，删除元素的位置，往往我们也需要知道所删除元素的值，以及明确我们的操作是否成功，所以在删除元素操作之前，我们先定义一个变量x，用于记录所删除的值，然后在函数传参时，传入我们定义变量x的地址，删除函数定义的参数int *px的作用就是接收我们为了用于记录进行删除操作所删除元素的值所定义变量x的地址，传过x的地址之后可以直接将我们所删除元素的值赋给x，提高我们的效率。

int deleteSList(struct SList* p, int k, int* px)//参数形式(进行删除操作的表，删除元素的位置，删除元素的值)

删除操作也需要注意其合法性，与插入操作不同的是仅需考虑删除位置的合法性而无需关注表是否已满，下面给出具体实现

int deleteSList(struct SList* p, int k, int* px)
{
    if (k < 0 || k >= p->length) return 0;//删除不合法，返回0
    else
    {
        *px = p->data[k];//记录我们所删除元素的值
        for (int i = k + 1; i < p->length; i++)
        {
            p->data[i - 1] = p->data[i];//从我们要删除位置的后一位开始，依次向前移动一位
        }
        p->length--;//顺序表元素个数减1
        return 1;//删除成功，返回1

    }

}

顺序表的输出

如何去直观的感受我们插入删除操作的效果呢？这里我们给出输出顺序表的代码实现

//前面加const的原因是我们对a只会进行读的操作，不会去改变a，处于严谨性考虑
void printSList(const struct SList* p)
{
    for (int i = 0; i < p->length; i++)
    {
        printf("%d,", p->data[i]);
    }
    printf("\n");//全部打印完成之后可以换个行^_^ hhh~
}

顺序表的查找:查找某元素在表中的位置

查找函数的作用就是查找该顺序表中是否有我们需要的值，所以该函数参数应该包括我们所查找的表，以及我们要查询的元素，函数返回值为我们所查找元素的下标，若出现重复元素，则返回该元素第一次出现位置的下标，若顺序表中没有该值，则返回-1(不返回0的原因是有可能我们所查找的元素位于该表中下标为0的位置)

int findx(struct SList *p,int x)
{
    //记录发现元素的位置，若没有发现，则返回-1,若有，则返回元素的下标
    int index=-1;//默认我们没有发现
    for(int i=0;i<p->length;i++)
    {
        if(p->data[i]==x)
        {
            index=i;//如果发现，则将改元素下标赋给index
            break;//若顺序表中存多个位置都为该值，返回第一个值所在位置的下标
        }
    }
    return index;
}

当然，查找也可能是查找表中某个位置元素的值，由于实现较为简单，故不在此赘述

顺序表的修改:修改第K位置元素的值

修改函数的作用为修改该顺序表中第K位置的元素的值，所以我们函数首先应该传入我们要修改的表，要修改的位置，以及要修改的值，并且该操作也是有合法范围的，即我们修改的位置应该是合法的，其次也应该返回0或1来告知我们的操作是否成功，故给出以下代码

int modifySList(struct SList *p,int k,int x)
{
    if(k<0||k>=p->length) return 0;//判断合法
    else
    {
        p->data[k]=x;//修改
        return 1;//操作成功返回1
    }
}

结果测试

#include <stdio.h>
#define MAX 10 //定义表长
struct SList
{
    int data[MAX];
    int length; //表的长度或元素个数
};

void init(struct SList* p)  //初始化表
{
    p->length = 0;
}

//前面加const的原因是我们对a只会进行读的操作，不会去改变a，处于严谨性考虑
void printSList(const struct SList* p)
{
    for (int i = 0; i < p->length; i++)
    {
        printf("%d,", p->data[i]);
    }
    printf("\n");//全部打印完成之后可以换个行^_^ hhh~
}

int insert(struct SList* p, int k, int x)
{
    //首先判断插入位置是否合法,因为我们的函数是插入第k个元素
    if (k<0 || k>p->length || p->length == MAX) return 0; //插入失败
    else
    {
        for (int i = p->length - 1; i >= k; i--)
        {
            p->data[i + 1] = p->data[i];
        }
        p->data[k] = x;
        p->length++;
        return 1;
    }

}

int deleteSList(struct SList* p, int k, int* px)
{
    if (k < 0 || k >= p->length) return 0;
    else
    {
        *px = p->data[k];
        for (int i = k + 1; i < p->length; i++)
        {
            p->data[i - 1] = p->data[i];
        }
        p->length--;
        return 1;

    }

}

int findx(struct SList *p,int x)
{
    int index=-1;//记录发现元素的位置，若没有发现，则返回-1
    for(int i=0;i<p->length;i++)
    {
        if(p->data[i]==x)
        {
            index=i;
            break;
        }
    }
    return index;
}

int modifySList(struct SList *p,int k,int x)
{
    if(k<0||k>=p->length) return 0;
    else
    {
        p->data[k]=x;
        return 1;
    }
}

int main()
{
    struct SList a; //创建顺序表的结构体
    init(&a);//调用初始化表的函数
    insert(&a, 0, 11);//参数形式：(进行插入操作的表，插入位置，插入元素)
    insert(&a, 0, 22);
    insert(&a, 0, 33);
    insert(&a, 0, 22);
    insert(&a, 0, 55);
    insert(&a, 0, 66);      
    printSList(&a);
    
    printf("该元素的位置下标是： %d\n",findx(&a,22));//查找操作

    int x = 0;
    deleteSList(&a, 1, &x);//参数形式(进行删除操作的表，删除元素的位置，删除元素的值)
    deleteSList(&a, 1, &x);
    printf("删除操作后\n");
    printSList(&a);
    modifySList(&a,2,23);
    printf("修改操作后\n");
    printSList(&a);
    //打印这个表,因为我们不需要改变这个a，其实是可以直接把a传过去的，但是仅仅把a传过去,他会把
    //整个变量的值拷贝一份传进去，效率是较低的,所以我们考虑传a的地址

    return 0;
}