c语言数据结构:顺序表(增,删,查,改)

1.顺序表的概念及其结构

1.1线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是?种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的?条直线。

但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表的分类

2.1 顺序表和数组的区别

顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

所以可以这么说,顺序表的本质就是一个数组.

2.2 如何声明和构建一个顺序表

静态顺序表因为不常用,这里便不进行介绍了,感兴趣的可自行去了解

重点是动态顺序表

typedef struct seqlist
{
   sldatatype* arr; //顺序表本质是个数组,这里定义一个指针arr用于对顺序表进行操作
   int capacity; //顺序表可存储的最大元素个数
   int size; //size指的是当前顺序表(数组)存储的元素个数
}sl;//sl是此顺序表的类型

举个例子来更好的了解capacity和size,如果说capacity是一个碗,那么size就是这个碗里面盛的饭

3.顺序表的基础操作(增,删,查,改)

3.1 顺序表的初始化

void slinit(sl *ps)
{//传值的本质是形参是实参的值的拷贝
ps->arr = NULL;//此时的结构体变量还没有初始化,所以没有具体的值,所以应该传址
ps->size = ps->capacity = 0;
}

为什么这里使用的是传址的方式void slinit(sl *ps)

传址的方式更为常用,因为这样可以减少时空复杂度
特别是在需要对结构体变量进行修改操作或者结构体变量较大时，传址方式可以提高程序的效率和可读性。
或者这么说,顺序表的本质是个数组,传参是指针才方便操作嘛

3.2 在进行各项基础操作前检验内存是否足够的函数

//此函数的作用是判断内存是否足够,是否需要扩容
void slcheckcapacity(sl* ps)
{
   //若空间不够,扩容
//使用三目操作符更简洁:
   if (ps->size == ps->capacity)//当前已使用空间等于最初给的最大容量
   {
       //因为之前是有capacity的初始化为0操作,所以直接2被扩容是无效的,所以这里要对其进行最大容量初始化不为0操作
       int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
       //保证初始空间不为以后创建一个tmp指针变量用realloc函数对ps所指向的空间进行扩容操作
       sldatatype* tmp = (sldatatype*)realloc(ps->arr, newcapacity * sizeof(sldatatype));//对数组arr进行扩容,扩容后的空间大小一般是扩容前的空间二倍大小
       if (tmp == NULL)//扩容失败
       {
           perror("realloc fail");
           exit(1);
       }
       //扩容成功,realloc函数不需要手动free,因为它以经帮你做好了
       ps->arr = tmp;
       ps->capacity = newcapacity;
   }
}

3.3 顺序表的尾插操作

void slpushback(sl* ps, sldatatype x)
{
   assert(ps != NULL);

  slcheckcapacity(ps);
   //若空间足够,直接插入
   ps->arr[ps->size] = x;//向着数组arr中尾插元素x,size是数组当前的大小
   ps->size++;//有效数据个数随之++
}

3.4顺序表的头插操作

//将头后面的所有数据都向前挪动一位
void slpopfront(sl* ps)
{
   assert(ps);
   assert(ps->size);

   for (int i = 0;i<ps->size-1;i++)//最后一个有效数据是ps->arr[size-1]
   {
       ps->arr[i] =ps->arr[i + 1] ;//将ps->arr[i + 1] 的元素赋值给   ps->arr[i]
   }
   ps->size--;
}

3.4顺序表的头插操作

//将所有的数据都往后移一位,使顺序表头部空出一个位置
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[i - 1]赋值给后面的数据ps->arr[i]以达到元素后移的目的
   }
   ps->arr[0] = x;
   ps->size++;

}

3.4 顺序表的头插操作

//将所有的数据都往后移一位,使顺序表头部空出一个位置
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[i - 1]赋值给后面的数据ps->arr[i]以达到元素后移的目的
   }
   ps->arr[0] = x;
   ps->size++;
}

3.5 顺序表的尾删操作

void slpopback(sl *ps)
{
   //顺序表及其内部数据都不可为空,如果顺序表存储的数据为空,那么它就无法进行删除操作
   //就是capacity和size都不可以为空
   assert(ps);
   assert(ps->size);

   //顺序表不为空
   ps->size--;
}

3.6 顺序表的头删操作

//将头后面的所有数据都向前挪动一位
void slpopfront(sl* ps)
{
   assert(ps);
   assert(ps->size);

   for (int i = 0;i<ps->size-1;i++)//最后一个有效数据是ps->arr[size-1]
   {
       ps->arr[i] =ps->arr[i + 1] ;//将ps->arr[i + 1] 的元素赋值给   ps->arr[i]
   }
   ps->size--;
}

3.7 顺序表的指定位置之前插入操作

void slinsert(sl* ps, int pos, sldatatype x)//pos是指定位置
{
   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++;
}

3.8 顺序表的指定位置删除操作

void slerase(sl* ps, int pos)
{
   assert(ps);
   //pos之后的数据前挪一位
   assert(pos >= 0 && pos <= ps->size);
   for (int i=pos;i<ps->size;i++)
   {
       ps->arr[i] = ps->arr[i + 1];
   }
   ps->size--;
}

完整代码: 登录 - Gitee.com