你真的了解线性表中的顺序表了吗？（静态与动态顺序）

今天开启我们数据结构中的第二篇文章了，过了几天我们今天就来了解了解我们常说的顺序表。

在这之前我们也先了解一下线性表。

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

那么我们今天就来学习一下顺序表！！！

顺序表的概念

静态顺序表功能的简单实现

动态顺序表的功能简单实现

顺序表的概念

顺序表是一种常见的数据结构，它是将数据元素按照一定的顺序依次存储在连续的存储空间中。

顺序表的基本思想是使用一块连续的内存空间来存储数据元素，每个元素按照特定的顺序依次排列。通常，元素在顺序表中的位置可以通过索引来访问，索引从 0 开始递增。

顺序表的优点包括：

1. 实现简单：顺序表的实现相对简单，易于理解和操作。
2. 随机访问：可以通过索引快速地访问任意位置的元素，具有较高的访问效率。
3. 内存效率：由于元素连续存储，所以可以有效地利用内存空间。

然而，顺序表也有一些限制和缺点：

1. 插入和删除操作：在顺序表中进行插入和删除操作可能需要移动其他元素，导致较高的时间复杂度。
2. 固定大小：顺序表的大小通常是固定的，在需要扩展时可能需要重新分配内存并复制元素。
3. 内存需求：顺序表需要连续的内存空间，如果数据量较大，可能会受到内存限制。

为了克服顺序表的一些限制，可以使用链式结构（如链表）或其他更复杂的数据结构来实现。具体选择取决于具体的应用场景和对数据操作的需求。

顺序表在许多编程语言中都有直接的实现，例如数组。它们在需要快速随机访问和顺序处理数据的情况下非常有用，例如在排序、查找、遍历等操作中。

静态顺序表功能的简单实现

根据上方的描述其实在像C语言中的数组也是一个顺序表。那么下面我们就用数组和代码实现一个顺序表的增，删，查，改函数接口。

顺序表的静态储存

struct SEQlist
{
	int arr[MAXSIZE];
	int size;


};

这里因为数据不同，我们需要创建一个结构体，我们现在使用整形数组来举例。这里的size是指顺序表里有的有效数据，MAXSIZE为宏定义的最大元素数。

注：这里把结构体命名为SL ，详情如头尾文件定义如下:

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXSIZE 10

typedef struct SEQlist SL;
void Init(SL* s);
void Print(SL* s);
void pushFront(SL* s, int x);

静态顺序表的格式化接口函数

void Init(SL* s)
{
	memset(s->arr, 0, sizeof(int) * MAXSIZE);
	s->size = 0;

}

这里格式化我们就把数组中的数据都格式化为0，size也格式化为0，格式化我们可以用循环来进行赋值，但是这里我们就用了一个函数进行赋值。函数为memset.

关于memset的介绍各位可以看一下这里：

这里显示了他的头文件和用法，已经被我给圈起来了。

void * memset ( void * ptr, int value, size_t num );其中num是内容字节大小。

静态顺序表的头插接口函数

void pushFront(SL* s, int x)
{
	int end = s->size - 1;
	for (int i = end; i >= 0; --i)
	{
		s->arr[i + 1] = s->arr[i];

	}
	s->arr[0] = x;
	s->size++;

}

头插功能即在顺序表开头插上数据。

静态顺序表打印接口

void Print(SL* s)
{
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->arr[i]);
	}

就将数据打印完出来。

总结：静态顺序表的缺点还是很明显的，不能够灵活运用数据的大小是固定的，即MAXSIZE，给少了不够用，给多了就用不完。那么接下来我们就弄一个静态的顺序表。

动态顺序表的功能简单实现

这里我们在创建一个结构体，不同的是，因为我们要实现一个动态的顺序表，所以我们不再创建数组，而设置一个指针来实现动态。

struct SQ
{
	int* a;
	int size;
	int capacity

};

后面我把此结构SEQ。

动态顺序表的格式化插口

void Init(SEQ* s)
{
	  
	s->a = NULL;
    s->size = 0;         // 表示数组中存储了多少个数据
	s->capacity = 0;   数组实际能存数据的空间容量是多大 

	
}

这里我们将a 指向一个空指针。

动态顺序表的检查与扩容插口函数

void CheckCapacity(SEQ* s)
{
	// 如果没有空间或者空间不足，那么我们就扩容
	if (s->size == s->capacity)
	{
		int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
		int* tmp = (int*)realloc(s->a, newcapacity*sizeof(int));
		if (tmp == NULL)
		{
			printf("realloc 失败\n");
			exit(-1);
		}

		s->a = tmp;
		s->capacity = newcapacity;
	}
}

这里我们首先检查有没有空间和空间是否足够，如不够则进行扩容，这里扩容我们用到realloc 函数，函数具体使用方法和头文件详情请看下图。

动态顺序表的尾插和尾删插口函数

void SeqListPushBack(SEQ* s, int x)
{
	CheckCapacity(s);

	s->a[s->size] = x;
	s->size++;
}

void SeqListPopBack(SEQ* s)
{
	
	// 暴力处理方式
	assert(s->size > 0);
	s->size--;
}

这里就是简单的增加删减，需要注意在尾插时先进行检查容量是否充足。即先调用CheckCapacity函数。

删的时候只要将数据size减1，在打印数据时也只打印前size位数据，所以减减后也可以当作删除了尾部数据。

动态顺序表的头插和头删函数

void SeqListPushFront(SEQ* s, int x)
{
	CheckCapacity(ps);

	// 挪动数据
	int end = s->size - 1;
	while (end >= 0)
	{
		s->a[end + 1] = s->a[end];
		--end;
	}
	s->a[0] = x;
	s->size++;
}

void SeqListPopFront(SEQ* s)
{
	assert(s->size > 0);

	// 挪动数据
	int begin = 1;
	while (begin < s->size)
	{
		s->a[begin - 1] = s->a[begin];
		++ begin;
	}

	s->size--;
}

也是像上面一样简单增删就不过多解释了。

动态顺序表的销毁插口

所为销毁也就是令指针销毁，然后让数据和容量位0.

void SeqListDestory(SEQ* s)
{
	free(s->a);
	s->a = NULL;
	s->capacity = s->size = 0;
}

下面给大家看一下插口函数效果。

头插几个数据

int main()
{
	Init(&s);
	SeqListPushFront(&s, 1);
	SeqListPushFront(&s, 2);
	SeqListPushFront(&s, 3);
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 11);
	Print(&s);
	return 0;
}

再头删几个数据

int main()
{
	Init(&s);
	SeqListPushFront(&s, 1);
	SeqListPushFront(&s, 2);
	SeqListPushFront(&s, 3);
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 11);
	Print(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	Print(&s);


	return 0;
}

下面就是尾插和尾删了

我们尾插55，95，22，然后又尾删掉三个数据

int main()
{
	Init(&s);
	SeqListPushFront(&s, 1);
	SeqListPushFront(&s, 2);
	SeqListPushFront(&s, 3);
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 11);
	Print(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	Print(&s);


	SeqListPushBack(&s,55);
	SeqListPushBack(&s,95);
	SeqListPushBack(&s,22);
	Print(&s);

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	Print(&s);


	return 0;
}