【C语言】顺序表（原理+实现）_顺序表长度的原理是什么

一.原理

1.线性表、顺序表

线性表（Linear list）是n个具有相同特性的数据元素的有限序列。线性表在逻辑上是线性结构，就如同一条连续的直线，但是在物理结构上不一定是连续的。

顺序表（Sequence list）是线性表的一种，但顺序表不仅在逻辑上是线性的，它在物理上同样是线性的。顺序表的底层结构是数组，数组本身就是同一类型数据的集合，顺序表在对数组的封装上实现了常用的增删改查等接口。

2.静态顺序表

静态顺序表的实现如下，在一个自定义结构体SL中定义一个定长数组和已用长度size,在对顺序表进行增删时size（也就是当前数组元素个数进行加减），但之所以叫作静态顺序表，就是因为在开始数组的大小就被给定了（就是MAX），数据最多只能存储到MAX个，因此MAX的大小设置成了问题，空间给少了不够用，给多了造成空间浪费，因此就有了动态顺序表。

3.动态顺序表

动态顺序表在静态的基础上，将定长数组改为一个指针，这样对于就能使用realloc函数合理地进行扩容，并且容量（capacity）也能随时变化，做到了动态地变化。

二.实现

1.初始化、销毁

在进行实现之前需要注意一点：结构体传参的时候，要传结构体的地址。（这点在我之前结构体的文章介绍过）不仅是由于压栈，在如下顺序表初始化的函数中，需要给结构体成员赋值，只有指针能做到，传值的话只能改变形式参数，无法达到效果。

无论是初始化还是销毁，只要传参传的地址，先使用assert对其进行断言保障安全性，初始化指针赋NULL，元素个数size和容量都为0即可。销毁时需要释放动态开辟的空间，并且将指针赋NULL。

//初始化
void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
 
//销毁
void SLDestroy(SL* ps)
{
	assert(ps);
	assert(ps->arr);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

2.打印

打印需要分不同的类型，在之前的结构体定义前对类型统一命名为SLdatatype，方便修改和阅览。如果对SLdatatype重命名的是int，那么此时的打印方式就以int的形式进行。

//打印
void SLPrint_int(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

3.头插、尾插

在正式进行插入前，首先要进行容量判定，如果容量不够怎么能成功插入呢？如果不够就进行扩容，在扩容时选择一个标准，一般是成倍数的进行扩容（2倍，3倍），这样能较好的节约空间并且也能足够使用。在此作者选择2倍扩容，不过在最开始（即ps->capacity = 0）时先扩容四个元素大小，检查容量是否足够就是检查capacity是否等于size。

//容量检查、扩容
void SLcheckcapacity(SL* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		int newspace = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLdatatpye* tmp = (SLdatatpye*)realloc(ps->arr, newspace * sizeof(SLdatatpye));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newspace;
	}
}

 头插，需要把每个元素往后移动一位，使用for循环实现，随后在第一位插入输入的值，最后不要忘了size++，只要是插入建议先写size++防止忘记。尾插则更为简单，只需要在size出赋值就行。不过需要知道，size是代表元素个数，而元素个数要是表示下标，那就是最后一个元素的后一位。

//头插
void SLPushfront(SL* ps, SLdatatpye value)
{
	assert(ps);
	SLcheckcapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]
	}
	ps->arr[0] = value;
	ps->size++;
}
 
//尾插
void SLPushback(SL* ps, SLdatatpye value)
{
	assert(ps);
	SLcheckcapacity(ps);
	ps->arr[ps->size++] = value;
}

4.头删、尾删

与头插尾插同理，头删需要将第一位后的数字都往前移动一位，随后就是size--（删掉了一个元素）。而尾删只需要size--就行，不会影响其他函数，能达到删除的功能。

//头删
void SLDeletefront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//size - 2 = size - 1
	}
	ps->size--;
}
 
//尾删
void SLDeleteback(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

5.指定位置插入、删除

将头插尾插进行广泛化，但核心原理是相同的，只不过起点可以指定而已，此处对于指定位置需要进行判断，必须大于等于0和小于（等于）size。

//指定位置插入
void SLInsert(SL* ps, int pos, SLdatatpye value)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLcheckcapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//pos+1 = pos
	}
	ps->arr[pos] = value;
	ps->size++;
}
 
//指定位置删除
void SLDelete(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//size -2 = size - 1
	}
	ps->size--;
}

6.查找

对动态数组进行遍历，查看是否有与输入值相等的值，若有则返回下标。

//查找
int SLFind(SL* ps, SLdatatpye value)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == value)
			return i;
	}
	return -1;
}

三.完整代码

头文件：SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLdatatpye;
 
 
typedef struct Seqlist
{
	SLdatatpye* arr;
	int size;
	int capacity;
}SL;
 
//初始化
void SLInit(SL*);
 
//销毁
void SLDestroy(SL* ps);
 
//打印
void SLPrint_int(SL* ps);
 
//检查容量、扩容
void SLcheckcapacity(SL* ps);
 
//头插
void SLPushfront(SL* ps, SLdatatpye value);
 
//尾插
void SLPushback(SL* ps, SLdatatpye value);
 
//头删
void SLDeletefront(SL* ps);
 
//尾删
void SLDeleteback(SL* ps);
 
//指定位置插入
void SLInsert(SL* ps, int pos, SLdatatpye value);
 
//指定位置删除
void SLDelete(SL* ps, int pos);
 
//查找
int SLFind(SL* ps, SLdatatpye value);

源文件：SeqList.c

#include"SeqList.h"
 
void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
 
void SLDestroy(SL* ps)
{
	assert(ps);
	assert(ps->arr);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
 
void SLPrint_int(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
 
void SLcheckcapacity(SL* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		int newspace = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLdatatpye* tmp = (SLdatatpye*)realloc(ps->arr, newspace * sizeof(SLdatatpye));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newspace;
	}
}
 
void SLPushfront(SL* ps, SLdatatpye value)
{
	assert(ps);
	SLcheckcapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]
	}
	ps->arr[0] = value;
	ps->size++;
}
 
void SLPushback(SL* ps, SLdatatpye value)
{
	assert(ps);
	SLcheckcapacity(ps);
	ps->arr[ps->size++] = value;
}
 
void SLDeletefront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//size - 2 = size - 1
	}
	ps->size--;
}
 
void SLDeleteback(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}
 
void SLInsert(SL* ps, int pos, SLdatatpye value)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLcheckcapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//pos+1 = pos
	}
	ps->arr[pos] = value;
	ps->size++;
}
 
void SLDelete(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//size -2 = size - 1
	}
	ps->size--;
}
 
int SLFind(SL* ps, SLdatatpye value)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == value)
			return i;
	}
	return -1;
}

源文件：test.c 

#include"Seqlist.h"
 
void testSL01(SL* ps)
{
	SLInit(ps);
	SLPushback(ps, 1);
	SLPushback(ps, 2);
	SLPushback(ps, 3);
	SLPushback(ps, 4);
	SLPrint_int(ps);
	
	SLInsert(ps, 2, 3);
	SLInsert(ps, 0, 0);
	SLPrint_int(ps);
	
	SLDelete(ps, 3);
	SLDelete(ps, 0);
	SLPrint_int(ps);
	
	int ret = SLFind(ps, 2);
	if (ret != -1)
	{
		printf("找到了，下标为：%d\n", ret);
	}
	else
	{
		printf("找不到\n");
	}
	
	SLDestroy(ps);
}
 
int main()
{
	SL s;
	testSL01(&s);
}