顺序表

概念及结构

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

静态顺序表：使用定长数组存储
动态顺序表：使用动态开辟的数组存储

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组会导致空间开多了浪费，开少了不够用。
所以动态顺序表会用的比较多，根据需要动态的分配空间大小。

相关操作代码示例

seqList.h

#pragma once
//顺序表：数组，数组相关信息：有效元素个数，数组的容量

//静态顺序表  404byte
#define N 100
typedef int SLDataType;
struct seqList
{
	SLDataType _data[N];
	int _size;
};

//动态顺序表  12byte
typedef struct seqList1
{
	SLDataType* _data; //数组指针
	int _size; //有效元素个数
	int _capacity; //数组的空间
}seqList1;

void initseqList(seqList1* s1);

void seqListCheckCapacity(seqList1* s1); //扩容

//操作：增删查改
//尾插：给顺序表最后一个有效数据的末尾插入新的数据
void seqList_pushBack(seqList1* s1, SLDataType val);
//尾删：删除最后一个数据
void seqList_popBack(seqList1* s1);
//打印
void seqList_print(seqList1* s1);
//访问某一个位置的元素
SLDataType seqList(seqList1* s1, int pos);
//判断顺序表是否为空
int seqList_isEmpty(seqList1* s1);
//头插：给顺序表头部插入一个新的数据
void seqList_pushFront(seqList1* s1, SLDataType val);
//头删：删除第一个数据
void seqList_popFront(seqList1* s1);
//任意位置插入
void seqList_insPos(seqList1* s1, int pos, SLDataType val);
//任意位置删除
void seqList_delPos(seqList1* s1, int pos);

//销毁
void seqList_Destroy(seqList1* s1);

Tes1204.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"seqList.h"


//初始化一个空的顺序表
void initseqList(seqList1* s1)
{
	if (s1 == NULL)
	{
		return;
	}
	s1->_data = NULL;
	s1->_size = 0;
	s1->_capacity = 0;
}

//判断是否为空 //1->空
int seqList_isEmpty(seqList1* s1)
{
	if (s1 == NULL)
	{
		return;
	}

	if (s1->_size == 0)
		return 1;
	else
		return 0;
}

//扩容
void seqListCheckCapacity(seqList1* s1)
{
	if (s1->_size == s1->_capacity)
	{
		//空间已满，扩容
		//1.开辟新空间
		int newCapacity = s1->_capacity == 0 ? 1 : 2 * s1->_capacity;
		SLDataType* tmp = (SLDataType*)malloc(newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			return;
		}
		//2.拷贝
		memcpy(tmp, s1->_data, sizeof(SLDataType) * s1->_size);

		//3.释放原有空间
		free(s1->_data);

		s1->_data = tmp;

		//用realloc等价于2.3两步
		//s1->_data = (SLDataType*)realloc(s1->_data, newCapacity * sizeof(SLDataType));

		//4.更新容量
		s1->_capacity = newCapacity;
	}
}

//尾插操作
void seqList_pushBack(seqList1* s1, SLDataType val)
{
	if (s1 == NULL)
	{
		return;
	}
	//容量检查
	seqListCheckCapacity(s1);
	//尾插
	s1->_data[s1->_size] = val;
	s1->_size++;
}

//尾删操作
void seqList_popBack(seqList1* s1)
{
	if (s1 == NULL)
	{
		return;
	}

	//假删除，只是看不到了
	if (s1->_size > 0)
		s1->_size--;
}

//打印
void seqList_print(seqList1* s1)
{
	if (s1 == NULL)
	{
		return;
	}

	for (int i = 0; i < s1->_size; ++i)
	{
		printf("%d ", s1->_data[i]);
	}
	printf("\n");
}

//访问某一个位置的元素
SLDataType seqList(seqList1* s1, int pos)
{
	if (s1 == NULL)
	{
		return;
	}
	if (seqList_isEmpty(s1))
		return -1;

	if (pos <= s1->_size)
		return s1->_data[pos];
	else
	{
		printf("位置错误！\n");
		return -1;
	}
}

//头插：给顺序表头部插入一个新的数据
void seqList_pushFront(seqList1* s1, SLDataType val)
{
	if (s1 == NULL)
	{
		return;
	}
	//容量检查
	seqListCheckCapacity(s1);
	//头插
	for (int i = s1->_size; i > 0; --i)
	{
		s1->_data[i] = s1->_data[i - 1];
	}
	s1->_data[0] = val;
	s1->_size++;
}

//头删
void seqList_popFront(seqList1* s1)
{
	if (s1 == NULL)
	{
		return;
	}
	for (int i = 0; i < s1->_size - 1; ++i)
	{
		s1->_data[i] = s1->_data[i + 1];
	}
	s1->_size--;
}

//任意位置插入
void seqList_insPos(seqList1* s1, int pos, SLDataType val)
{
	if (s1 == NULL)
	{
		return;
	}
	if (pos <= s1->_size && pos >= 0)
	{
		seqListCheckCapacity(s1);
		for (int i = s1->_size; i > pos; --i)
		{
			s1->_data[i] = s1->_data[i - 1];
		}
		s1->_data[pos] = val;
		s1->_size++;
	}
	else
	{
		printf("位置错误！\n");
		return;
	}
}

//任意位置删除
void seqList_delPos(seqList1* s1, int pos)
{
	if (s1 == NULL)
	{
		return;
	}
	if (seqList_isEmpty(s1))
		return;

	if (pos < s1->_size && pos >= 0)
	{
		for (int i = pos; i < s1->_size - 1; ++i)
		{
			s1->_data[i] = s1->_data[i + 1];
		}
		s1->_size--;
	}
	else
	{
		printf("位置错误！\n");
		return;
	}

}

//销毁
void seqList_Destroy(seqList1* s1)
{
	if (s1 == NULL || s1->_data == NULL)
	{
		return;
	}
	free(s1->_data);
	s1->_data == NULL;
}

void test()
{
	//栈上开辟的系统会自动销毁
	seqList1 s1;
	initseqList(&s1);
	seqList_pushBack(&s1, 1);
	seqList_pushBack(&s1, 2);
	seqList_pushBack(&s1, 3);
	seqList_pushBack(&s1, 4);
	seqList_pushBack(&s1, 5);
	seqList_pushFront(&s1, 0);
	seqList_print(&s1);
	seqList_popFront(&s1);
	seqList_print(&s1);
	seqList_pushFront(&s1, 0);
	seqList_print(&s1);
	seqList_delPos(&s1, 3);
	seqList_print(&s1);
	seqList_insPos(&s1, 5, 9);
	seqList_print(&s1);
	printf("\n=============\n");

	//堆上开辟的空间，需要销毁
	seqList1* s2 = (seqList1*)malloc(sizeof(seqList1));
	initseqList(s2);
	seqList_Destroy(s2);
	free(s2);
}

int main()
{
	test();
	system("pause");
	return 0;
}