算法 【数据结构】顺序表

目录

线性表

 顺序表

一、顺序表的存储

1.顺序表的静态存储

2.顺序表的动态存储

二、顺序表的初始化

三、顺序表的检查(动态增容)

四、顺序表的销毁释放 

五、顺序表的头尾操作

1.表尾插入元素

2.表尾删除元素

3.表头插入元素 

4.表头删除元素

5.顺序表查找某个元素

六、顺序表打印

 七、顺序表插入指定位置元素

八、 顺序表删除指定位置元素

前言：

线性表

先说一下线性表

线性表是一种数据结构，它由一组元素组成，这些元素按照一定的顺序排列。线性表中的元素可以是任意类型的，比如数字、字符、字符串、结构体等，在线性表中，每个元素都有一个编号，这个编号称作元素的下标或索引，从0开始递增。线性表中的元素之间存在一种线性关系，即元素只能按照一定的顺序依次排列，每个元素最多只有两个相邻的元素。常见的线性表包括数组、链表、栈、队列等。线性表通常用于实现各种算法和数据结构，如查找、排序、图论等。

 首先这里涉及 的一些 知识点 ：结构体  和  malloc 等动态内存函数

如果感到理解有些难度可以先去学习上述 知识点。

 顺序表

一、顺序表的存储

存储定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

1.顺序表的静态存储

 即 使用固定长度的数组来存储元素

#define N 25

//顺序表的静态存储

typedef int SLDDataType;

typedef struct SeqList

{

SLDDataType arr[N]; //定长数组

size_t size; //有效数据的个数

}SeqList;

该种定义的方法适用于已知数据元素的个数的情况下，提供的大小是固定的，定义N大了，就会浪费空间，定义N小了，就不够用。所以根据情况比较推荐适用动态顺序表。

2.顺序表的动态存储

typedef struct SeqList

{

SLDataType* a; //定义的动态数组

int size; //当前数据元素的个数

int capacity; //数组的容量

}SeqList;

先定义一个指针，使用malloc函数进行开辟

 下面采用动态扩容的方式

二、顺序表的初始化

//初始化顺序表

void SeqListInit(SeqList* ps)

{

assert(ps); //断言一下避免出现空指针

ps->a = NULL;

ps->size = 0;

ps->capacity = 0;

}

接下我们会顺序表的元素进行增、删、改、查，这样就需要对顺序表先进行检查

三、顺序表的检查(动态增容)

//顺序表的检查

void SLCheckCapacity(SeqList* ps)

{

//顺序表满了，使用realloc增容

if (ps->size == ps->capacity)//有效数据个数 等于 当前容量

{

//先判断一下顺序表是否第一次使用空间

int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

SLDataType* tmp = (SLDataType*)realloc(ps->a,sizeof(SLDataType)*newcapacity);

if (tmp != NULL)

{

ps->a = tmp;

ps->capacity = newcapacity;

}

else

{

perror("SLCheckCapacity -> realloc");

return;

}

}

}

四、顺序表的销毁释放 

 顺序表的销毁

//顺序表的销毁

void SeqListDestory(SeqList* ps)

{

assert(ps);

if (ps->a != NULL)

{

free(ps->a);//释放动态数组

ps->a = NULL;

ps->size = 0;

ps->size = 0;

}

}

五、顺序表的头尾操作

1.表尾插入元素

从顺序表的表尾插入元素

// 顺序表的尾插元素

void SeqListPushBack(SeqList* ps,SLDataType x)

{

assert(ps); //避免指针为空

//先进行顺序表的检查，动态增容

SLCheckCapacity(ps);

ps->a[ps->size] = x;//将元素x放到表尾

ps->size++; //表示有效个数据个数增加了1个

}

 注意 表尾插入元素的时间复杂度是O(1)

2.表尾删除元素

//表尾删除元素

void SeqListPopBack(SeqList* ps)

{

assert(ps);

assert(ps->size > 0);

ps->size--;

}

 测试效果图：

3.表头插入元素 

思想：先从表尾开始，从前往后移动元素，再把要插入的元素放到表头。当表为空的时候直接插入

//表头插入元素

void SeqListPushFront(SeqList* ps, SLDataType x)

{

assert(ps);

//检查容量，动态扩容

SLCheckCapacity(ps);

int end = ps->size - 1; //指向表尾

while (end >= 0)

{

ps->a[end + 1] = ps->a[end]; //依次后移

end--;

}

ps->a[0] = x;

ps->size++;

}

 注意：这里的时间复杂度尾O(N^2)

4.表头删除元素

 主要思想：从表的头部开始前移元素

//表头删除元素

void SeqListPopFront(SeqList* ps)

{

assert(ps);

assert(ps->size > 0); //首先的保证有元素

int begin = 1;

while (begin size)

{

ps->a[begin-1] = ps->a[begin]; //从头部开始前移

begin++;

}

ps->size--;

}

测试效果图： 

5.顺序表查找某个元素

//顺序表的查找

int SeqListFind(SeqList* ps, SLDataType x)

{

assert(ps);

int i = 0;

for (i = 0; i < ps->size;i++)

{

if (x == ps->a[i])

{

return i; //查找成功返回下标

}

}

//查找失败

return -1;

}

测试效果图：

六、顺序表打印

//顺序表的打印

void SeqListPrint(SeqList* ps)

{

assert(ps);

int i = 0;

for (i = 0; i < ps->size;i++)

{

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

}

}

 七、顺序表插入指定位置元素

void SeqListInsert(SeqList* ps, int pos, SLDataType x)

{

assert(ps);

//判断给出的位置是否合法

assert(pos >= 0 && pos <= ps->size );

SLCheckCapacity(ps);

int end = ps->size - 1;

while (end >= pos)

{

ps->a[end + 1] = ps->a[end];

end--;

}

ps->a[pos] = x;

ps->size++;

}

测试效果图：

八、 顺序表删除指定位置元素

//顺序表删除pos位置的值

void SeqListErase(SeqList* ps, int pos)

{

assert(ps);

//判断位置是否合法，注意这里是 小于 ps->size.

//也就是要在数组范围内

assert(pos >= 0 && pos < ps->size);

SLCheckCapacity(ps);

int begin = pos; //记录指定位置

while (begin < ps->size-1)

{

ps->a[begin] = ps->a[begin + 1];

begin++;

}

ps->size--;

}

测试效果图：

【总结】 

线性表的顺序存储方式，顺序表。主要介绍对顺序表的增、删、改、查。

另外

说到线性表 ，可能会想到 数组，因为数组的空间是连续的，数组下标从0 到 n ,显然是有序的。

这里多说一下，数组的下标为什么从0开始呢？原因是 数组的下标表示元素在内存中的偏移量，也就是它相对于数组首地址的距离。而第一个元素相对于首地址的偏移量是0，因此第一个元素的下标为0，还有就是 方便 指针 与 数组 之间转换的自洽，p[0] == *(p+0)。 

 在测试效果中，可能会遇到越界的问题（越界一定会报错吗？）越界不一定报错，系统对越界的检查是一种抽查

进行读操作时，越界是检查不出来的进行写操作时，如果是修改到标志位才会检查出来。(比如数组，系统会在数组末尾后设有标志位，越界写时，修改到标志位时，就会被检查出来，进行报错)

原文链接：