【数据结构】顺序表详解-阿里云开发者社区

当我们写完通讯录后，顺序表肯定难不倒你，跟着小张一起来学习顺序表吧！

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

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

顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

静态顺序表：使用定长数组存储元素。
动态顺序表：使用动态开辟的数组存储。

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef struct pro
{
  int* p;// 指向动态开辟的数组
  int size;// 有效数据个数
  int capcity;// 容量空间的大小
}pro;
void  SeqListInit(pro* ps );//初始化顺序表
void CheckCapacity(pro* ps);//判断是否空间不够，进行扩容
void  SeqListPushBack(pro* ps,int x);//尾插
void  SeqListPushFront(pro* ps, int x);//头插
void SeqListPopBack(pro* ps);//尾删
void  SeqListPopFront(pro* ps);//头删
void  SeqListPrint(pro* ps);//打印顺序表
void SeqListInsert(pro* ps, int pos, int x);//随意插
void SeqListErase(pro* ps, int pos);//随意删
void SeqListFind(pro* ps, int pos);//查找
void SeqListmodify(pro* ps, int x,int y);//修改
void SeqListDestory(pro* ps);//销毁

结构体定义和创建一个结构体变量

typedef struct pro
{
  int* p;// 指向动态开辟的数组
  int size;// 有效数据个数
  int capcity;// 容量空间的大小
}pro;
int main()
{
  pro info;//定义一个结构体变量
}

初始化顺序表

void  SeqListInit(pro* ps )//初始化顺序表
{
  ps->p = NULL;
  ps->size = 0;
  ps->capcity = 0;
}

初始化顺序表，有效数据个数为0，容量空间大小为0，还未给数据动态开辟空间，指向动态开辟空间的指针指向空地址

扩容顺序表

void CheckCapacity(pro* ps)//判断是否空间不够，进行扩容
{
  if (ps->size == ps->capcity)
  {
    int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;
    int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);
    if (tmp == NULL)
    {
      perror("realloc fail!!");
        }
    ps->p = tmp;
    ps->capcity = newcapcity;
   }
}

什么时候需要扩容顺序表呢？？当顺序表刚被初始化，你要进行插入数据时，发现容量空间已经满了，此时必须要扩容空间，当你要插入第一个数据时，在此之前，顺序表没有任何数据，容量空间为0，然后要插入数据的话，也必须扩容。

条件判断如果有效数据个数等于容量大小时，分两种情况，第一种，刚开始的时候，有效数据个数和容量大小都为0的时候，第二种，当要插入数据时，发现此时的有效数据个数和容量大小相等时，且不等于0.对空间进行扩容， newcapcity变量是新的容量大小，当需要扩容的时候，直接新容量为原来的2倍，刚开始，他的容量是0，采用三目运算符，如果容量是0的话，就给四个空间大小，如果不是就开原来容量的2倍。将realloc来的空间的地址存放在tmp指针里面，如果realloc失败就返回空指针，打印错误信息，realloc成功的话就将tmp中存放扩容的地址交给指针p,然后容量大小更新为newcapcity。

尾插

void  SeqListPushBack(pro* ps,int x)//尾插
{
  CheckCapacity(ps);
    ps->p[ps->size] = x;
  ps->size++;}

每次插入都要判断是否需要扩容

然后有效数据+1.

头插

void  SeqListPushFront(pro* ps, int x)//头插
{
  CheckCapacity(ps);
  int end = ps->size - 1;
  while (end>=0)
  {
    ps->p[end + 1] = ps->p[end];
    end--;
    }
  ps->p[0] = x;
  ps->size++;
}

头插一个数据，必须将后面的数据向后面移动，移动的过程中可能超过容量大小，所以在插入时都需要进行扩容判断

如果按这个顺序移动数据当1挪到2的位置的时候，2这个数据就会被覆盖，所以我们必须从后往前面挪

当数据挪到后面之后，然后在第一个位置填入x,第一个位置也就是下标为0的位置。

在下标为0的地方填入插入的数据x,然后ps->size+1;

尾删

void SeqListPopBack(pro* ps)//尾删
{
  assert(ps);
  assert(ps->size > 0);
  ps->size--;
}

尾巴要删除一个数据的话，我们需要将删除的数据改为0吗？如果要删除的数据本来就是0呢？所以我们只需要将ps->size–;因为打印的时候只打印到下标为ps->size-1的位置，打印出来看起来就像我们删除了这个数据，注意这里用断言是因为在删除的时候ps->size–,当ps->size<0的时候，在添加数据时

ps->p[-1]=x;这个是不合理的，在ps->size<0时，直接报错，第一个断言是为了防止空指针。

头删

void  SeqListPopFront(pro* ps)//头删
{
  assert(ps->size > 0);
  int begin = 1;
  while (begin<ps->size)
  {
    ps->p[begin - 1] = ps->p[begin];
    begin++;
     }
  ps->size--;
}

这里的断言和上面是一个道理，然后相比尾删向后挪动数据，头删是往前挪数据，吸取尾删的教训，我们可以直到移动的顺序是

定义一个变量begin=1,首先是要将数据2移动到数据1的位置，对应的操作是

ps->p[begin - 1] = ps->p[begin];然后begin++,依次将数据3挪到数据2的位置，数据4挪到数据3的位置。循环最后一次是将数据5挪到数据4的位置，也就是begin=4,ps->size=5.则循环判断条件为beginsize,循环结束后将

ps->size–;

顺序表的打印

void  SeqListPrint(pro* ps)//打印顺序表
{
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->p[i]);
  }
}

循环遍历顺序表，将每个数据打印出来

随意插

void SeqListInsert(pro* ps, int pos, int x)//随意插
{
  CheckCapacity(ps);
  assert(pos>=0&&pos<=ps->size);
  int end = ps->size - 1;
  while (end>=pos)
  {
    ps->p[end + 1] = ps->p[end];
    end--;
    }
  ps->p[pos] = x;
  ps->size++;
}

断言是为了检查插入的位置是否合理

当有5个数据时，pos的可能取值如图所示，推广到一般

就是pos>=0&&pos<=ps->size,如果我们想在pos=2的位置插入一个x,我们应该怎么做呢？

1.插入一个x,我们需要将3，4，5向后移动，必须先移动5，定义一个变量end,

end变量的初值给ps->size-1，也就是4，要想将数据5向后挪动，对应的操作是ps->p[end + 1] = ps->p[end];然后end–;循环分别将4，3向后挪动，循环结束后，将数据x插入到pos=2的位置，对应操作为ps->p[pos] = x;然后有效数据大小ps->size++；

随意删

void SeqListErase(pro* ps, int pos)//随意删
{
  int begin = pos;
  assert(pos >= 0 && pos <= ps->size);
  while (begin<ps->size-1)
  {
    ps->p[begin] = ps->p[begin+1];
    begin++;
    }
  ps->size--;
}

断言判断删除的数据的位置是否合理，和随意插的那里一样

如果我们要删除数3，然后数据3后面的数据向前挪动，第一步就是将数据4移动到数据3的位置，定义一个变量begin=pos=2;对应的操作为

ps->p[begin] = ps->p[begin+1];，然后begin++;将数据5移动到最开始数据4的地方。最后一次循环是将数据5移动到数据4的地方，也就是begin最后等于3，ps->size=5，则循环判断条件是begin< ps->size-1,循环结束将ps->size–;

顺序表的查找

void SeqListFind(pro* ps, int pos)//查找
{
  assert(pos >= 0 && pos < ps->size);
  printf("你查找的下标是%d,对应的数据是%d", pos, ps->p[pos]);
}

断言保证查找位置的合理性，因为函数传参pos 刚好是要查找数据的下标，直接打印出来

顺序表的修改

void SeqListmodify(pro* ps, int x,int y)//修改
{
  for (int i = 0; i < ps->size; i++)
  {
    if (x == ps->p[i])
    {
      ps->p[i] = y;
    }
  }
}

x为修改前的值，y是修改之后的值，循环遍历顺序表，将顺序表中所有的x都修改成y

顺序表的销毁

void SeqListDestory(pro* ps)//销毁
{
  ps->capcity = 0;
  ps->size = 0;
  free(ps->p);
  ps->p = NULL;
}

销毁一个顺序表，将顺序表的容量置为0，顺序表的有效数据个数置为0，将p指针所指向的动态开辟的内存空间释放了，由于释放了动态开辟的内存空间，所有p指向的空间未初始化，p成为野指针，为了防止野指针，将p置为空指针。

整体代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct pro
{
  int* p;// 指向动态开辟的数组
  int size;// 有效数据个数
  int capcity;// 容量空间的大小
}pro;
void  SeqListInit(pro* ps )//初始化顺序表
{
  ps->p = NULL;
  ps->size = 0;
  ps->capcity = 0;
}
void CheckCapacity(pro* ps)//判断是否空间不够，进行扩容
{
  if (ps->size == ps->capcity)
  {
    int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;
    int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);
    if (tmp == NULL)
    {
      perror("realloc fail!!");
    }
    ps->p = tmp;
    ps->capcity = newcapcity;
  }
}
void  SeqListPushBack(pro* ps,int x)//尾插
{
  CheckCapacity(ps);
    ps->p[ps->size] = x;
  ps->size++;
}
void  SeqListPushFront(pro* ps, int x)//头插
{
  CheckCapacity(ps);
  int end = ps->size - 1;
  while (end>=0)
  {
    ps->p[end + 1] = ps->p[end];
    end--;
    }
  ps->p[0] = x;
  ps->size++;
}
void SeqListPopBack(pro* ps)//尾删
{
  assert(ps);
  assert(ps->size > 0);
  ps->size--;
}
void  SeqListPopFront(pro* ps)//头删
{
  assert(ps->size > 0);
  int begin = 1;
  while (begin<ps->size)
  {
    ps->p[begin - 1] = ps->p[begin];
    begin++;
     }
  ps->size--;
}
void  SeqListPrint(pro* ps)//打印顺序表
{
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->p[i]);
  }
}
void SeqListInsert(pro* ps, int pos, int x)//随意插
{
  CheckCapacity(ps);
  assert(pos>=0&&pos<=ps->size);
  int end = ps->size - 1;
  while (end>=pos)
  {
    ps->p[end + 1] = ps->p[end];
    end--;
    }
  ps->p[pos] = x;
  ps->size++;
}
void SeqListErase(pro* ps, int pos)//随意删
{
  int begin = pos;
  assert(pos >= 0 && pos <= ps->size);
  while (begin<ps->size-1)
  {
    ps->p[begin] = ps->p[begin+1];
    begin++;
    }
  ps->size--;
}
void SeqListFind(pro* ps, int pos)//查找
{
  assert(pos >= 0 && pos < ps->size);
  printf("你查找的下标是%d,对应的数据是%d", pos, ps->p[pos]);
}
void SeqListmodify(pro* ps, int x,int y)//修改
{
  for (int i = 0; i < ps->size; i++)
  {
    if (x == ps->p[i])
    {
      ps->p[i] = y;
    }
  }
}
void SeqListDestory(pro* ps)//销毁
{
  ps->capcity = 0;
  ps->size = 0;
  free(ps->p);
  ps->p = NULL;
}
int main()
{
  pro info;
  SeqListInit(&info);
  printf("尾插:");
  SeqListPushBack(&info, 1);
  SeqListPushBack(&info, 2);
  SeqListPushBack(&info, 3);
  SeqListPushBack(&info, 4);
  SeqListPrint(&info);
  printf("\n");
  printf("头插:");
  SeqListPushFront(&info, 7);
  SeqListPushFront(&info, 6);
  SeqListPushFront(&info, 5);
  SeqListPushFront(&info, 5);
  SeqListPrint(&info);
  printf("\n");
  printf("尾删:");
  SeqListPopBack(&info);
  SeqListPrint(&info);
  printf("\n");
  printf("头删:");
  SeqListPopFront(&info);
  SeqListPrint(&info);
  printf("\n");
  printf("随意插:");
  SeqListInsert(&info, 1, 1);
  SeqListPrint(&info);
  printf("\n");
  printf("随意删:");
  SeqListErase(&info,1,1);
  SeqListPrint(&info);
  printf("\n");
  printf("查找:");
  SeqListFind(&info, 3);
  printf("\n");
  printf("修改:");
  SeqListmodify(&info, 1, 2);
  SeqListPrint(&info);
  printf("\n");
  printf("销毁:");
  SeqListDestory(&info);
    SeqListPrint(&info);
}

【数据结构】顺序表详解

线性表

顺序表