C语言实现顺序表

/在写之前，我们先来讲解一下思路：当我们向头部插入元素的时候，不仅要让元素成功的插入到数组中，还要保证数组中原来的元素不会丢失，因此，我们要将原数组的元素统一向后面移动一位再将要插入的元素插入到头部位置就可以了(这里有一个点需要我们大家注意一下，就是我们在进行向后移动的时候，要从后面开始，往前进行循环移动元素操作)。//在进行尾插操作之前还要先看一下数组中的空间够不够，如果不够，则需要再重新扩充空

轩源源

1335人浏览 · 2024-05-21 23:52:21

轩源源 · 2024-05-21 23:52:21 发布

一.介绍：

二.与顺序表有关的相关操作：

1.顺序表的定义（其实就是定义一个结构体）：

这里建议大家使用电脑观看：

各位未来的高级程序员们，大家好，这一期的博客呢，我来为大家讲解一下顺序表相关的内容，精彩如下。

一.介绍：

顺序表是线性表的一种，它也不是多么神奇的东西，他的本质上就是一个数组。

顺序表{ 物理结构：一定是线性的

{ 逻辑结构：一定是线性的

二.与顺序表有关的相关操作：

1.顺序表的定义（其实就是定义一个结构体）：

typedef int SLDataType;//顺序表中的元素不一定是int类型，还有可能是别的一些类型，这样写方便以后修改类型。

typedef struct Seqlist

{
       SLDataType *arr;//定义一个动态的数组

       int size;//顺序表中的有效数据的大小

       int capacity;顺序表中的空间大小

}

2.顺序表的初始化：

void SLInit(SL*ps)

{

       ps->arr=NULL;//指针一般初始化为NULL

       ps->size=0;//整形一般初始化为0

       ps->capacity=0;//整形一般初始化为0

}

3.顺序表的销毁：

void SLDestroy(SL*ps)

{

       assert(ps);

       free(ps->arr);

       ps->size=0;

       ps->capacity=0;

}

4.创建数组空间：

我们在执行完前两步之后，接下来就要开始起到顺序表中执行操作了，在此之前，我们必须要创建一个数组，因为顺序表它就是通过数组来实现的，我们在使用顺序表的时候，必须要先判断一下顺序表中是否含有空间，又或者是有没有为顺序表开创一块动态数组，说到这里，我们再插一句，我来给大家说一说这里为什么要建立一个动态数组，动态数组它相较于静态数组来说有一个极大的优点，就是它可以在数组的内存面临不够的情况下，动态数组可以在原有数组的基础之上，再开创出新的空间出来，也就是我们常说的扩容，而静态数组是不可以进行扩容操作的，也就是它所开创的空间个数是固定的，任谁都是无法改变的，但是我不知道大家有没有想过就是假如你在工作中要创建一个顺序表来存放一些数据，你知不知道有多少个数据呢？你就这么确定在以后不会再向这个顺序表中去存放数据吗？鉴于种种原因，我们这里决定使用动态数组，而非静态数组。

void SLCheckCapacity(SL*ps)

{

       if(ps->size==ps->capacity)

       {

              int newcapacity=ps->capacity==0?4:2*capacity;//这里我们使用了一个三目操作符，具体就是要判断数组中有没有空间，如果capacity==0的话，那说明数组中是没有空间的，我们在这里就必须先创建空间，创建4个int类型的空间在数组中，如果capacity！=0，说明数组中原来是创建有空间的，只不过是空间被占满了，需要重新开创新的空间，我们在开创新的空间个数时，一般将空间扩充为原来空间的2倍大小（这里是基于种种原因考虑到的，我们只需知道并且会使用就可以了，不需要去研究为什么），因此2*capacity。

              int *tmp=(int*)realloc(sizeof(int)*newcapacity);//在这里我们使用realloc函数来实现动态数组的扩容操作，如果数组中的空间为0的话，就开创一个空间为4的数组空间，否则，就可以直接对原数组进行扩容操作（扩容之后的空间为原数组空间的2倍）realloc函数这里建议大家了解一下，他有一种情况可以创建空间，函数链接在后面，大家感兴趣的话可以看一下 。

              if(tmp==0)

              {
                     perror("realloc fail");

                     return;

               }//这一步操作是要判断一下空间是否开创成功（预防一下没有开创成功的情况）。

       }

       ps->a=tmp;//让指针a指向开创或扩容后的数组的地址

       ps->capacity=newcapacity;//数组空间中的容量变为newcapacity

}

https://cplusplus.com/https://cplusplus.com/

5.尾插元素：

具体操作如下图所示：

实现：

void SLPushBack(SL*ps,SLDataType x)

{

       assert(ps);//判断一下是否接受到了地址

       SLCheckCapacity(ps);//在进行尾插操作之前还要先看一下数组中的空间够不够，如果不够，则需要再重新扩充空间或开创空间，否则，无法进行尾插操作

       ps->arr[ps->size]=x;//将要尾插进数组中的元素插入到数组中的下一个位置

       ++ps->size;//插入一个元素，size++

}

6.头插元素：

具体操作如下图所示：

实现：

void SLPushFront(SL*ps,SLDataType x)

{

       assert(ps);//判断一下是否接受到了地址

       SLCheckCapacity(ps);//在进行头插操作之前还要先看一下数组中的空间够不够，如果不够，则需要再重新扩充空间或开创空间，否则，无法进行头插操作

       //在写之前，我们先来讲解一下思路：当我们向头部插入元素的时候，不仅要让元素成功的插入到数组中，还要保证数组中原来的元素不会丢失，因此，我们要将原数组的元素统一向后面移动一位再将要插入的元素插入到头部位置就可以了(这里有一个点需要我们大家注意一下，就是我们在进行向后移动的时候，要从后面开始，往前进行循环移动元素操作)。

       for(int i=ps->size;i>0;i--)

       {
              ps->arr[i]=ps->arr[i-1];

       }//完成这一步后，原数组中的所有元素均向后移动了一位

       ps->arr[0]=x;//将要插入的元素插入在头部就可以了

       ps->size++;

}

7.打印顺序表：

void SLPrint(SL s)//这里只是打印，并不需要修改一些数值，因此，这里没有传值的必要

{

       for(int i=0;i<size;i++)

       {

              printf("%d ",ps->arr[i]);

       }

       printf("\n");

}

8.删除尾端的一个元素：

删除尾端的一个元素，换句话说就是不将最后这个元素打印出来就可以了，也就是size--就可以了。

void SLPopBack(SL*ps)

{

       assert(ps);

       assert(ps->size);//要想删除元素，首先得保证数组中得有元素

       ps->size--;

}

9.删除首端的一个元素：

删除首端的一个元素，通过尾删操作，我们可知删除一个元素，只要在最后不将他打印出来就可以了，因此，我们在这里也使用一次循环，将除了第一个元素以外的所有元素全部统一向前面移动一位，最后size--就可以了。

void SLPopFront(SL*ps)

{
       for(int i=0;i<size-1;i++)

       {

              ps->arr[i]=ps->arr[i+1];

       }

       ps->size--;

}

10.在固定位置之前插入数据：

void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--)
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ps->size++;
}

11.删除某个数据：

void SLDelete(SL* ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    for (int i = pos; i < ps->size - 1; i++)
    {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}

12.查找某个数据：

int SLFind(SL* ps, SLDataType x)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->arr[i] == x)
        {
            return i;
        }
    }
    return -1;
}