文章目录

• ❤️前言
• ❤️准备任务
• 一、🌳初始化
• 二、🌳尾插

• 1.❤️扩容
• 2.尾插

• 三、🌳打印
• 五、🌳头插
• 六、🌳指定下标位置插入
• 七、🌳尾删
• 八、🌳头删
• 九、🌳指定下标位置删除
• 十、🌳查找某个元素
• 最后，🌳销毁
• ❤️总结
• test0310.c
• SeqList.h
• SeqList.c

🔊个人介绍

🌳数据结构系列点击跳转

🌳戳我跳到本人个人主页

🇨🇳大家好，我是_奇奇，一名C/C++博主。河牧院大一在读。

🔔欢迎大家交流学习

❤️编程的前途是光明的，道路是曲折的。

🌳笑到最后才是赢家🍺

❤️前言

严老师的书来镇楼，压迫感有没有上升

数据结构的书看着无聊，没有欲望看词下去？看着感觉头大？那这一篇绝对是小白的福音。数据结构第二版严蔚敏的书看不懂？顺序表链表学不会，学不懂？或者学会了听会了。不知道怎么敲代码，感觉心里不踏实？

究其原因是因为学校的课程快，偏理论，而大多数人并不是天才的水平，达不到听几遍就会写代码了。所以需要多多画图，多多敲代码。但是，严蔚敏老师书上的代码是伪代码，不适合我们初学者使用，初学者不能说无法把伪代码变成C语言写出来。但我肯定应该会很难，甚至将你劝退，让你没有去把顺序表用代码写出来的欲望。

• 只有把顺序表用代码写出来，让你自然而然的真正做到理解顺序表。

此篇用C语言在带你从零基础开始复现顺序表的代码。带你从简单到复杂。从基础延伸到深度理解顺序表。实现数据结构从入门到精通。后期数据结构的全部内容都会设置在这个专栏里——>点我进入专栏。

• 对于计算机专业的学生，无论考研还是就业，数据结构都是重中之重。所以数据结构需要学好。
  
• 对于学好数据结构，有以下几个关键点。
  

1.注重细节，注重细节，注重细节。数据结构是对C语言的提升。能够锻炼我们的细节问题。考虑问题要全面。比如要考虑当顺序表只有1个元素或者为空时的临界点。保证程序的健壮性。一般bug的出现都在这里。

2.注重实践，就是多敲代码，学校教的课程偏理论，大部分是老师课堂没时间让我们实践。光教理论课程时间都紧缺。所以我们需要在课余时间学会上机实践。

实践是检验真理的唯一标准

3.多画图，多思考。数据结构在你想不出来的时候一定要多画图。可以用windows自带的画图工具

也可以在本本上用笔画图。都可以。适合自己的才是最好的。画完图之后你就思路开阔了

提示：以下是本篇的正文，环境是vs2022编译器，用devc++也可以实现，再次提醒，要做到心中有图，你就会觉得如此简单

❤️准备任务

首先，在头文件中创建顺序表结构体。这个结构体里面包含一个指向这个结构体的指针a。和数据的个数size。因为我们实现的动态的顺序表，所以还有一个容量变量capacity。

学过C语言的应该都能看懂下面的代码。看不懂的就要好好补补C语言了。或者在评论区可以询问，第一时间回复喔。

一、🌳初始化

这里在源文件里定义了SeqList结构体类型的变量s。`需要注意的是实参部分要传地址。第一是因为这样代码效率会高，假如传值的话形参会在栈区给实参再拷贝一份，这会导致压栈占用内存，

第二是因为在链表章节的时候要改变实参现有的值的话，你把s里的值传过去。形参psl只是一份拷贝而已。你改变psl里面的值是不会影响实参s的值的，这一点要格外注意。

关于为什么要初始化，原因是因为才开始需要给变量赋值，否则变量里面的值都是随机值，后面用的时候可能会出错。

1.testSeqList0310.c

2.Seqlist.h

3.SeqList.c

二、🌳尾插

• 因为尾插简单所以先写尾插的代码。
• 但在尾插之前，因为顺序表是空的，所以需要先扩容（SeqListCheckCapacity），也就是判断顺序表是否满了。来增加顺序表元素的数量。

1. testSeqList0310.c
   2.Seqlist.h

1.❤️扩容

3.SeqList.c

当if (psl->size == psl->capacity)判断完顺序表满的的时候。一般扩容都有个规则，就是扩容到原来的二倍。但是才开始初始化的capacity是0。所以乘2就是0了。这就是一个bug，所以就先暂时赋值给临时变量newCapaity。然后再托付给他值得一辈子人——也就是这个操作psl->capacity =newCapacity;

要考虑到扩容失败这个情况，顺序表提高就是我们的细节能力。假如扩容失败也就是tmp指向的空间为空，就exit结束程序。

2.尾插

• 尾插很简单啊，因为元素下标比元素个数少一。元素个数是psl->size.直接数组访问这个位置，然后赋值就可以了。顺便元素个数自增
• size分别为时0,1,2,3,4.可以带进去思考一下。

三、🌳打印

3.SeqList.c

• 尾插后我们要展示出道界面上查看。所以我们需要打印，用for循环遍历顺序表就可以打印了。
  如图为结果。
  

五、🌳头插

分别头插0和负一，然后打印

testSeqList0310.c

2.Seqlist.h

和上面几个操作一样。头文件内需要先声明函数。一般良好的编程习惯是函数的声明和定义分离。

3.SeqList.c

头插就是把顺序表中的数依次往后挪一个位置，给第一个位置空出来。进而实现名义上的头插。

还是需要注意要先判断顺序表满了没有

六、🌳指定下标位置插入

testSeqList0310.c

注意。这里是在指定下标的位置插入数据。所以说只要下标所对应的值合法，就可以进行插入。

2.Seqlist.h

插入的算法时间复杂度为大O(n)

3.SeqList.c

注意细节。在这里需要先判断指针是否为空。然后再判断指定的下标是否越界。如果越界return返回。return的结果是跳出这个函数，然后执行此函数的下一条语句。这两步的判断可以使程序更加健壮

注意边界问题。当指定的下标pos为0就相当于是头插了。当pos为size时，这时就相当于尾插了。

七、🌳尾删

当我们学会了尾插。那尾删也易如反掌。但尾删也不是真正意义上的删除只需要让size–就达到尾删了。

当然这样就错了，你还需要判断顺序表是否为空。为空的话就return就好了。

2.Seqlist.h

3.SeqList.c

八、🌳头删

1. testSeqList0310.c
   头删也不是真正的把首元素地址上的值删掉。而是后面的往前依次覆盖，把首元素的值覆盖了就完成头删了。
   

2.Seqlist.h

3.SeqList.c

九、🌳指定下标位置删除

同指定位置插入，不赘述

1. testSeqList0310.c
   

2.Seqlist.h

3.SeqList.c

十、🌳查找某个元素

遍历一遍顺序表，然后判断每个元素是否等于所查找的值，若查到则返回其下标。

3.SeqList.c

最后，🌳销毁

• 销毁时需要注意要free掉原来的空间后，一定要将原来的地址置为空，否则a就是一个野指针了。
• free的时候编译器才会检查指针是否越界。这时候报的错一般都是越界的问题。

❤️总结

• 顺序表还是特别需要画图。画完图代码就是顺水成章就写出来了，也不是很难。
• 最重要的还是多练习。多思考。
• 顺序表直接访问某个元素的时间复杂度为O(1)头插，头删或者中间插入的时间复杂度为O(n)

喜欢数据结构系列的就点击订阅吧，下期更新最常用的无头单向不循环链表。

test0310.c

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
int main()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushFront(&s, 0);
  SeqListPushFront(&s, -1);
  SeqListPrint(&s);
  SeqListInsert(&s, 2, 5);
  SeqListPrint(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
  SeqListErease(&s, 2);
  SeqListPrint(&s);
  SeqListDestroy(&s);
  return 0;
}

SeqList.h

#define _CRT_SECURE_NO_WARNINGS
//防止被重复包含
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//要求存储的数据必须从0开始，依次连续存储
typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a;
  int size;//数据个数
  int capacity;//数据空间大小
}SL, SeqList;
//初始化
void SeqListInit(SeqList* psl);
//扩容
void SeqListCheckCapacity(SeqList* psl);
//尾插O(1)
void SeqListPushBack(SeqList* psl, SLDataType x);
//打印
void SeqListPrint(SeqList* psl);
//头插O(n)
void SeqListPushFront(SeqList* psl, SLDataType x);
//指定位置插入O(n)
void SeqListInsert(SeqList* psl, SLDataType pos, SLDataType x);
//尾删O(1)
void SeqListPopBack(SeqList* psl);
//头删O(n)
void SeqListPopFront(SeqList* psl);
//指定位置删除
void SeqListErease(SeqList* psl, SLDataType pos);
//销毁动态开辟的空间
void SeqListDestroy(SeqList* psl);
//查找
void SeqListFind(SeqList* psl, SLDataType x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
//销毁
void SeqListDestroy(SeqList* psl)
{
  assert(psl);
  free(psl->a);
  psl ->a = NULL;
  psl->capacity = psl->size = 0;
}
//初始化
void SeqListInit(SeqList* psl)
{
  assert(psl);
  psl->a = NULL;
  psl->size = 0;
  psl->capacity = 0;
}
//打印
void SeqListPrint(SeqList* psl)
{
  assert(psl);
  for (int i = 0; i < psl->size; i++)
  {
    printf("%d ", psl->a[i]);
  }
  printf("\n");
}
//检查是否需要扩容
void SeqListCheckCapacity(SeqList* psl)
{
  if (psl->size == psl->capacity)
  {
    int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail");
      exit(-1);
    }
    else
    {
      psl->a = tmp;
      psl->capacity =newCapacity;
    }
  }
}
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
  assert(psl);
  SeqListCheckCapacity(psl);
  psl->a[psl->size] = x;
  psl->size++;
}
//尾删
void SeqListPopBack(SeqList* psl)
{
  assert(psl);
  if (psl->size > 0)
  {
    psl->size--;
  }
}
//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
  assert(psl);
  SeqListCheckCapacity(psl);
  int end = psl->size - 1;
  while (end >= 0)
  {
    psl->a[end + 1] = psl->a[end];
    end--;
  }
  psl->a[0] = x;
  psl->size++;
}
//头删
void SeqListPopFront(SeqList* psl)
{
  assert(psl);
  //挪出数据，腾出头部空间
  if (psl->size > 0)
  {
    int begin = 1;
    while (begin < psl->size)
    {
      psl->a[begin - 1] = psl->a[begin];
      ++begin;
    }
    --psl->size;
  }
}
//指定位置插入
void SeqListInsert(SeqList* psl, SLDataType pos, SLDataType x)
{
  assert(psl);
  if (pos > psl->size)
  {
    printf("pos越界");
    return;
  }
  else
  {
    int end = psl->size;
    SeqListCheckCapacity(psl);
    while (end > pos)
    {
      psl->a[end] = psl->a[end - 1];
      --end;
    }
    psl->a[pos] = x;
    ++psl->size;
  }
}
//指定位置删除O(n)
void SeqListErease(SeqList* psl, SLDataType pos)
{
  assert(psl);
  if (pos > 0 && pos < psl->size)
  {
    int begin = pos;
    while (begin < psl->size)
    {
      psl->a[begin - 1] = psl->a[begin];
      ++begin;
    }
    --psl->size;
  }
}
//查找
void SeqListFind(SeqList* psl, SLDataType x)
{
  assert(psl);
  for (int i = 0; i < psl->size; i++)
  {
    if (psl->a[i] == x)
    {
      return i;
    }
    else
    {
      return -1;
    }
  }
}