数据结构-顺序表的实现-阿里云开发者社区

线性表和顺序表

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列，是一种很常见的数据结构

线性表在逻辑上是线性结构，但是在物理结构上并不一定是连续的

常见的线性表有：顺序表、链表、栈、队列、字符串等

顺序表

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

可以认为，顺序表的本质就是数组

顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。    
复制代码

静态顺序表

使用定长数组存储元素。

例子：静态通讯录

#define BOOK_MAX 100
typedef int DataType //这样可以随时改变内容的类型
typedef struct address_book //通讯录内容
{
  struct perinfmt p[BOOK_MAX];//每个人信息,数组一共100个人
  DataType ID;//统计每个人编号
}SeqlistContact;//顺序表
复制代码

动态顺序表

动态顺序表：使用动态开辟的数组存储。

例子：动态通讯录

typedef struct PeopleInfo
{
    struct People* a;//指向动态开辟的结构体成员数组
    int size;//标记成员个数(有效成员个数)
    int capacity;//容量，如果不够可以增容
}PeopleInfo;
复制代码

2.1.基本架构

使用typedef，类型可以不固定，后序想要更改存储的数据类型更方便

typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;
  size_t size;
  size_t capacity; // unsigned int
}SeqList;
复制代码

size是有效数字个数，同时也是最后一个数据的下一个位置的下标

2.2初始化

指针置空，一开始可以不给容量，也可以给一定的容量

void SeqListInit(SeqList* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = 0;
  ps->size = 0;
}
复制代码

2.3扩容

realloc ：如果传空指针，相当于malloc

realloc原理
    1.原地扩容：如果后面空间足够则在后面扩
    2.异地扩容：如果后面空间不够，则重新找一块空间开辟，把原来的数组拷贝过去，然后释放原来空间
复制代码

最初就是空指针，所以最开始使用realloc时相当于是malloc

扩容每次扩两倍，要判断realloc是否成功

最后还要把新容量赋给ps->capacity，把新开辟空间的地址赋给ps->a

void CheckCapacity(SeqList* ps)
{
  if (ps->size == ps->capacity)
  {
    //扩容
    //如果最初容量为0，就把容量设置为4
    //如果最初容量不为0，那就两倍扩容
    int newcapacity = ps->capacity == 0 ? 4 : ps -> capacity * 2;
    SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (newcapacity));
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);//直接结束进程
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
}
复制代码

2.4打印

遍历数组打印即可,ps->size标志的就是有效数字的个数

void SeqListPrint(SeqList* ps)
{
  assert(ps);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
复制代码

2.5尾插

尾插：即插入到size位置

size：标志元素个数，size下标是数组最后一个元素的下一个位置

注意：插入要判断容量是否满了 插入元素后：size++

void SeqListPushBack(SeqList* ps, SLDateType x)
{
  CheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}
复制代码

2.6头插

把元素往后移动，然后在0位置插入元素

注意：防止元素覆盖，要从数组最后一个元素往后移动，0位置的元素也要后移

注意：插入要判断容量是否满了 插入元素后：size++

void SeqListPushFront(SeqList* ps, SLDateType x)
{
  int i = 0;
  for (i = ps->size; i > 0; i--)
  {
    ps->a[i] = ps->a[i - 1];
  }
  //写法2
  /*
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  */
  ps->a[0] = x;
  ps->size++;
}
复制代码

2.7尾删

注意:要考虑数组中是否还有元素可以被删除

只需让ps->size--即可，因为size标志的就是元素个数。最后一个元素虽然空间还在，但是我们已经没有权限访问了

void SeqListPopBack(SeqList* ps)
{
  //温柔处理
  if (ps->size == 0)
  {
    printf("已经没有元素\n");
    return ;
  }
  //暴力处理：assert(ps->size >0)
  ps->size--;
}
复制代码

2.8头删

注意:要考虑数组中是否还有元素可以被删除

头删：即把第二个元素往前覆盖

注意：要从前面开始往前覆盖！ 删除元素：size--

void SeqListPopFront(SeqList* ps)
{
  if (ps->size == 0)
  {
    printf("已经没有元素\n");
    return ;
  }
  int i = 0;
  for (i = 0; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i+1];
  }
  //写法2：
  //int begin = 1;
  //while (begin < ps->size)
  //{
  //  ps->a[begin - 1] = ps->a[begin];
  //  ++begin;
  //}
  //写法3：
  //int begin = 0;
  //while (begin < ps->size-1)
  //{
  //  ps->a[begin] = ps->a[begin+1];
  //  ++begin;
  //}
  ps->size--; 
}
复制代码

2.9查找

遍历数组进行查找即可，如果数组是有序的，可以使用二分查找。如果找到了，返回对应下标，找不到返回-1

int SeqListFind(SeqList* ps, SLDateType x)
{
  //遍历查找
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
  }
  //找不到
  return -1;
}
复制代码

2.10 pos位置插入

注意：插入要考虑容量是否足够的问题，还要考虑pos位置是否合法。pos位置可以在0位置插入，也可以在size位置插入(因为size标志的是成员个数，同时也是最后一个元素的下一个位置的下标) 插入后：size++

在pos位置插入：即把pos位置的数据往后移动

注意：要从后往前移动

void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
  //断言：如果括号内为真就无视，如果为假就报错
  //所以写成：assert(pos < 0 || pos >ps->size)是错误的
  //插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
  assert(pos >= 0 && pos<=ps->size);
  CheckCapacity(ps);
  //写法1
  //int i = 0;
  ////往后移动
  //for (i = ps->size-1 ; i > pos; i--)
  //{
  //  ps->a[i+1] = ps->a[i];
  //}
  //ps->a[pos] = x;
  //ps->size++;
  //写法2：
  int i =ps->size ;
  while (i > pos)
  {
    ps->a[i] = ps->a[i-1];
    i--;
  }
  ps->size++;
  ps->a[pos] = x;
}
复制代码

头插尾插的写法：

头插：即在0位置插入

尾插：即在size-1位置插入

头插：SeqListInsert(ps, 0, x);
尾插：SeqListInsert(ps,ps->size - 1,x)
复制代码

2.11pos位置删除

注意：删除也要保证位置的合法性 删除后，size--

在pos位置删除，即把pos后面的数据向前覆盖。

从前往后移动(先移动pos+1位置的数据往前覆盖)

void SeqListErase(SeqList* ps, size_t pos)
{
  //此时pos不可以为size，
  //因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置，这个位置没有存元素，不可以删除
  assert(pos >= 0 && pos < ps->size);
  int i = 0;
  for (i = pos; i < ps->size -1; i++)
  {
    ps->a[i] = ps->a[i+1];
  }
    /*
  //写法2：
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin-1] = ps->a[begin];
    begin++;
  }
  */
  ps->size--;
}
复制代码

头删尾删的写法

头删：SeqListErase(ps,0)
尾删：SeqListErase(ps, ps->size - 1);
复制代码

2.12销毁

因为数组指向的空间是动态开辟的，所以结束时要把空间销毁，防止内存泄漏。

销毁之后要把指针置空！！防止造成野指针

void SeqListDestory(SeqList* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
复制代码

注意事项

插入元素考虑因素：

整个顺序表空间是否满了，满了则扩容，插入之后size要++

头插：从后往前移动(先移动最后的数据)

尾插：直接插入到size位置

删除元素考虑因素

是否还有元素可以被删除，删除元素之后size--

头删：从前往后移动(先移动前面的数据进行覆盖)

尾删：直接size--即可

test.c

#include"Seqlist.h"
void Test1()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 3);
  SeqListPushFront(&s, 5);
  SeqListPushFront(&s, 6);
  SeqListPushFront(&s, 7);
  // 7 6 5 1 3
  SeqListInsert(&s, 0,1);
  SeqListPrint(&s);
}
int main()
{
  Test1();
  return 0;
}
复制代码

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include"Seqlist.h"
void SeqListInit(SeqList* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = 0;
  ps->size = 0;
}
void SeqListDestory(SeqList* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
void SeqListPrint(SeqList* ps)
{
  assert(ps);
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
void CheckCapacity(SeqList* ps)
{
  if (ps->size == ps->capacity)
  {
    //扩容
    //如果最初容量为0，就把容量设置为4
    //如果最初容量不为0，那就两倍扩容
    int newcapacity = ps->capacity == 0 ? 4 : ps -> capacity * 2;
    SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (newcapacity));
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);//直接结束进程
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
}
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x)
{
  CheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}
//头插
void SeqListPushFront(SeqList* ps, SLDateType x)
{
  int i = 0;
  for (i = ps->size; i > 0; i--)
  {
    ps->a[i] = ps->a[i - 1];
  }
  int end = ps->size - 1;
  //写法2
  /*
    while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  */
  ps->a[0] = x;
  ps->size++;
}
//头删
void SeqListPopFront(SeqList* ps)
{
  if (ps->size == 0)
  {
    printf("已经没有元素\n");
    return ;
  }
  int i = 0;
  for (i = 0; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i+1];
  }
  //写法2：
  //int begin = 1;
  //while (begin < ps->size)
  //{
  //  ps->a[begin - 1] = ps->a[begin];
  //  ++begin;
  //}
  //写法3：
  //int begin = 0;
  //while (begin < ps->size-1)
  //{
  //  ps->a[begin] = ps->a[begin+1];
  //  ++begin;
  //}
  ps->size--; 
}
//尾删
void SeqListPopBack(SeqList* ps)
{
  //温柔处理
  if (ps->size == 0)
  {
    printf("已经没有元素\n");
    return ;
  }
  //暴力处理：assert(ps->size >0)
  ps->size--;
}
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
  //遍历查找
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
  }
  //找不到
  return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
  //断言：如果括号内为真就无视，如果为假就报错
  //所以写成：assert(pos < 0 || pos >ps->size)是错误的
  //插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
  assert(pos >= 0 && pos<=ps->size);
  CheckCapacity(ps);
  //写法1
  //int i = 0;
  ////往后移动
  //for (i = ps->size-1 ; i > pos; i--)
  //{
  //  ps->a[i+1] = ps->a[i];
  //}
  //ps->a[pos] = x;
  //ps->size++;
  //写法2：
  int i =ps->size ;
  while (i > pos)
  {
    ps->a[i] = ps->a[i-1];
    i--;
  }
  ps->size++;
  ps->a[pos] = x;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{
  //此时pos不可以为size，
  //因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置，这个位置没有存元素，不可以删除
  assert(pos >= 0 && pos < ps->size);
  int i = 0;
  for (i = pos; i < ps->size -1; i++)
  {
    ps->a[i] = ps->a[i+1];
  }
  //写法2：
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin-1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}
//头删：SeqListErase(ps,0)
//尾删：SeqListErase(ps, ps->size - 1);
//
//头插：SeqListInsert(ps, 0, x);
//尾插：SeqListInsert(ps,ps->size - 1,x)
复制代码

Seqlist.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
// SeqList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;
  size_t size;
  size_t capacity; // unsigned int
}SeqList;
// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestory(SeqList* ps);
void CheckCapacity(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos);
复制代码

写的时候遇到的坑点：

//在pos位置插入
//错误写法：
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
  assert(pos >= 0 && pos<=ps->size);
  CheckCapacity(ps);
  //写法1
  //int i = 0;
  ////往后移动
  //for (i = ps->size-1 ; i >= pos; i--)
  //{
  //  ps->a[i+1] = ps->a[i];
  //}
  //ps->a[pos] = x;
  //ps->size++;
  //写法2：
  int i =ps->size -1 ;
  while (i >= pos)
  {
    ps->a[i+1] = ps->a[i];
    i--;
  }
  ps->size++;
  ps->a[pos] = x;
}
复制代码

错误原因：pos是size_t类型，无符号整形。i为整形

pos和i进行比较时，i会提升为无符号整形，即i的范围为：[0,2147483 648]，i恒大于0.所以若在pos = 0位置插入，则 i>=pos恒成立，会造成死循环。

pos为其他正数值的时候不会发生，因为i的返回时[0,2^31]，i终究会变到小于pos的值跳出循环！！，但是若pos为0，则i>=pos恒满足，死循环。所以这是个很隐藏的错误，

即使i也定义为无符号整形也是如此

i和pos进行比较不能取相等！！！防止出现pos位置取0的情况！

//正确写法：
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
  //断言：如果括号内为真就无视，如果为假就报错
  //所以写成：assert(pos < 0 || pos >ps->size)是错误的
  //插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
  assert(pos >= 0 && pos<=ps->size);
  CheckCapacity(ps);
  //写法1
  //int i = 0;
  ////往后移动
  //for (i = ps->size-1 ; i > pos; i--)
  //{
  //  ps->a[i+1] = ps->a[i];
  //}
  //ps->a[pos] = x;
  //ps->size++;
  //写法2：
  int i =ps->size ;
  while (i > pos)
  {
    ps->a[i] = ps->a[i-1];
    i--;
  }
  ps->size++;
  ps->a[pos] = x;
}
复制代码

同理在pos位置删除时，i和pos比较也不能取等号

数据结构-顺序表的实现

线性表和顺序表

线性表

顺序表

静态顺序表

动态顺序表

2.1.基本架构

2.2初始化

2.3扩容

realloc ：如果传空指针，相当于malloc

2.4打印

2.5尾插

2.6头插

2.7尾删

2.8头删

2.9查找

2.10 pos位置插入

头插尾插的写法：

2.11pos位置删除

头删尾删的写法

2.12销毁

注意事项

test.c

Seqlist.c

Seqlist.h

写的时候遇到的坑点：

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构-顺序表的实现

线性表和顺序表

线性表

顺序表

静态顺序表

动态顺序表

2.1.基本架构

2.2初始化

2.3扩容

realloc ：如果传空指针，相当于malloc

2.4打印

2.5尾插

2.6头插

2.7尾删

2.8头删

2.9查找

2.10 pos位置插入

头插尾插的写法：

2.11pos位置删除

头删尾删的写法

2.12销毁

注意事项

test.c

Seqlist.c

Seqlist.h

写的时候遇到的坑点：

热门文章

最新文章

相关课程

相关电子书