【数据结构】顺序表—纯C实现顺序表

定义

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素
2. 动态顺序表：使用动态开辟的数组存储。

特点

顺序表的特点：
①随机访问，即可以在 O(1) 时间内找到第 i 个元素。
②存储密度高，每个节点只存储数据元素
③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
④插入、删除操作不方便，需要移动大量元素

缺陷

1. 空间不够，需要扩容。扩容是有代价的，并且会存在空间浪费。
2. 头部或者中部的插入删除，需要挪动数据，效率低。
   

静态顺序表

#define N 7
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType arr[N];//定长数组
    size_t size;//有效数据的个数
}SeqList;
1
2
3
4
5
6
7

动态顺序表

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* array;//指向动态开辟的数组
	size_t size;	 //有效数据个数	
	size_t capicity;//容量空间的大小
}SeqList;
1
2
3
4
5
6
7

接口实现

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟的数组
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;
1
2
3
4
5
6
7
8

以下接口都以该类型实现。

顺序表初始化

void SeqListInit(SeqList* psl)
{
	assert(psl);//断言防止其为空指针
	psl->array=NULL;//讲该指针置空
	psl->size = 0;//设置有效数据个数为0
	psl->capacity = 0;//设置空间容量为0
}
1
2
3
4
5
6
7

介绍一下assert这个函数。

assert的作用就是：求表达式的值，当结果为假时，打印诊断消息并中止程序。

顺序表销毁

void SeqListDestory(SeqList* psl)
{
	assert(psl);
	//释放动态开辟的空间
	if (psl->array)
	{
		free(psl->array);
		psl->array = NULL;
		psl->capacity = 0;
		psl->size = 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

顺序表增容

想给一个表增容，最先做的就是先检查顺序表内元素个数是否已达顺序表容量上限。
若已达上限，那么我们就需要先对顺序表进行扩容，然后才能增加数据。

void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);

	if (psl->size == psl->capacity)
	{
		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SeqListDataType* tmp = (SeqListDataType*)realloc(psl->array, newCapacity * sizeof(SeqListDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		psl->array = tmp;
		psl->capacity = newCapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

头部的插入删除

头插

void SeqListPushFront(SeqList* psl, SeqListDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->array[end + 1] = psl->array[end];
		end--;
	}
    //或者用for循环
    //	for (int i = psl->size - 1; i >= 0; i--)  
    //顺序表中[0,size-1]的元素依次向后挪动一位
	//{
	//	psl->array[i + 1] = psl->array[i];
	//}
	psl->array[0] = x;
	psl->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void SeqListPushFront(SeqList* psl, SeqListDataType x)
{
   SeqListInsert(psl, 0, x);
}

1
2
3
4
5

头删

void SeqListPopFront(SeqList* psl)
{
	assert(psl);  //断言
    assert(psl->size>0);//防止数据为0时还删数据
	assert(psl->size > 0);  //顺序表不能为空
	int begin = 1;
    while(begin<ps->size)
    {
        psl->array[begin-1]=psl->array[begin];
        begin++;
    }
//	int i = 0;
//	for (i = 1; i < psl->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位
//	{
//		psl->array[i - 1] = psl->array[i];
//	}
	psl->size--;  //有效数据个数-1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void SeqListPopFront(SeqList* psl)
{
    SeqListErase(psl, 0);
}
1
2
3
4

尾部的插入删除

尾插

void SeqListPushBack(SeqList* psl, SeqListDataType x)
{
	assert(psl);
	SLCheckCapacity(psl);
	psl->array[psl->size] = x;
	psl->size++;
}
1
2
3
4
5
6
7

void SeqListPushBack(SeqList*psl,SeqListDataType X)
{
    SLInsert(psl, ps->size, x);
}
1
2
3
4

尾删

void SeqListPopBack(SeqList* psl)
{
	assert(ps);
	assert(ps->size > 0);
	psl->array[ps->size - 1] = 0;
	psl->size--;
}
1
2
3
4
5
6
7

void SeqListPopBack(SeqList*psl)
{
    SeqListErase(psl, psl->size-1);
}
1
2
3
4

中间的插入删除

中间插入

void SeqListInsert(SeqList* psl, int pos, SeqListDataType x)
{
	assert(psl);
	assert(pos >= 0);
	assert(pos <= psl ->size);

	SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->array[end + 1] = psl->array[end];
		end--;
	}

	psl->array[pos] = x;
	psl ->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

中间删除

void SeqListErase(SeqList* psl, int pos)
{ss
	assert(psl);
	assert(pos >= 0);
	assert(pos < psl->size);
	int begin = pos + 1;
	while (begin < psl->size)
	{
		psl->array[begin - 1] = psl->array[begin];
		begin++;
	}
	psl->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

顺序表查找

int SeqListFind(SeqList* psl, SeqListDataType x, int begin)
{
	assert(psl);
	for (int i = begin; i < psl->size; i++)
	{
		if (ps->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

顺序表打印

void SeqListPrint(SeqList* psl)
{
	assert(psl);
	if (psl->size == 0)
	{
		printf("空表");
		return;
	}
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14