C语言实现顺序表(增删查改等数据管理)

Bertha 。 2022-12-27 07:41 179阅读 0赞

# 顺序表seqlist #

小伙伴们，提到顺序表会想到什么呢？

数组？还是链表？

其实，数组和链表都是属于线性表，而链表在逻辑上是线性的，并非物理存储上也为线性；而数组无论在逻辑上还是物理存储上均为线性

所以说，顺序表就是用一段连续的物理地址存储单元上依次存储数据元素的线性结构

常见最为典型的就是数组了，在数组里完成增删查改

**顺序表主要分为两类**

*  静态顺序表：使用定长数组存储数据
 *  动态顺序表：动态开辟存储空间存储

## 顺序表结构定义： ##

顺序表结构采用C语言结构体定义，为实现动态顺序表，将定义整型（SLDateType\*）类型指针，其次设置size表示当前顺序表中有效元素个数，capacity表示当前顺序表可存放数据的容量大小

typedef int SLDateType;
    typedef struct SeqList
    {
    	SLDateType* a;
    	size_t size;
    	size_t capacity; // unsigned int
    }SeqList;

## 顺序表接口声明： ##

顺序表主要接口为数据的管理，主要就是增删查改

具体包括头插，头删，尾插，尾删 ，查找，初始化，顺序表销毁，指定位置删除，插入

// 对数据的管理:增删查改 
    void SeqListInit(SeqList* ps);
    void SeqListDestory(SeqList* ps);
    void SeqListPrint(SeqList* ps);
    void SeqListPushBack(SeqList* ps, SLDateType x);
    void SeqListPushFront(SeqList* ps, SLDateType x);
    void SeqListPopFront(SeqList* ps);
    void SeqListPopBack(SeqList* ps);
    
    // 顺序表查找
    int SeqListFind(SeqList* ps, SLDateType x);
    // 顺序表在pos位置插入x
    void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
    // 顺序表删除pos位置的值
    void SeqListErase(SeqList* ps, size_t pos);
    //返回pos位置的值
    SLDateType SeqListAt(SeqList* ps, size_t pos);
    //返回有效元素个数
    size_t SeqListSize(SeqList* ps);
    //顺序表是否为空
    int SeqListisEmpty(SeqList* ps);

## 顺序表的实现 ##

在顺序表实现增删查改之前，我们注意到，由于是动态存储数据，就存在动态开辟的问题，我们在进行数据插入操作的过程中需要进行容量判断

如果容量不足，需要进行增容

但是此处要注意，避免函数栈帧出现，是否增容在函数外部进行判断，外部判断需要增容，调用增容函数

同时在增容函数中注意到，容量如果为0，刚进行初始化后，新的顺序表中还没有数据，首次插入时，如果容量不赋初值将无法扩容进行插入，对此需要判断为0 ，赋初值为1

void add_capacity(SeqList* ps)
    {
    	//容量开辟选择 初始化容量为0
    	int newcapacity = ps->capacity == 0 ? 1 : 2 * ps->capacity;
    	//为顺序表数据存放开辟空间
    	SLDateType* tmp = (SLDateType*)malloc(newcapacity * sizeof(SLDateType));
    	//新空间新地址，将原有数据拷贝过来
    	if (tmp != NULL)
    	{
    		memcpy(tmp, ps->a, sizeof(SLDateType)*ps->size);
    		free(ps->a);
    		ps->a = tmp;
    		ps->capacity = newcapacity;
    	}
    }

*  ### 顺序表初始化和销毁 ###

void SeqListInit(SeqList* ps)
    {
    	if (ps == NULL)
    	{
    		return;
    	}
    	ps->a = NULL;
    	ps->size = 0;
    	ps->capacity = 0;
    }
    //顺序表销毁
    void SeqListDestory(SeqList* ps)
    {
    	if (ps != NULL && ps->a!= NULL)
    	{
    		free(ps->a);
    		ps->a = NULL;
    		ps->size = 0;
    		ps->capacity = 0;
    	}
    }

动态开辟空间，销毁顺序表的时候也需要free进行释放，此操作不可忽略，否则会造成空间浪费，如果被释放空间首地址不置NULL，将会造成内存泄漏

*  ### 顺序表尾插，尾删 ###

顺序表的尾插和尾删十分简单，

尾插就是判断容量，容量足够情况下，进行尾部插入，即size处放入一个数据

尾删就是更新维护数组有效数据大小的size，size--即可删除，即使数据并没有真正意义上删除，但不属于顺序表维护的数据，即认为删除掉了

//顺序表尾插
    void SeqListPushBack(SeqList* ps, SLDateType x)
    {
    	assert(ps);
    	if (ps->size == ps->capacity)
    	{
    		add_capacity(ps);
    	}
    	ps->a[ps->size] = x;
    	ps->size++;
    }

//顺序表尾删
    void SeqListPopBack(SeqList* ps)
    {
    	assert(ps);
    	if (ps->size > 0)
    	{
    		ps->size--;
    	}
    }

*  ### 顺序表查找 ###

顺序表查找即为遍历整个顺序表，从头开始到size结束

// 顺序表查找
    int SeqListFind(SeqList* ps, SLDateType x)
    {
    	assert(ps);
    	unsigned int pos;
    	for (unsigned int i = 0; i < ps->size; i++)
    	{
    		if (ps->a[i] == x)
    		{
    			pos = i;
    			return pos;
    		}
    	}
    	return -1;
    }

*  ### 顺序表的头插，头删 ###

头插：从尾部开始后撤一位，为头部给一个空位，为什么要从尾部移动，就为了保证原有的数据不会被覆盖

头删：从投的后一位往前覆盖，覆盖头部数据，即完成删除

//顺序表头插
    void SeqListPushFront(SeqList* ps, SLDateType x)
    {
    	assert(ps);
    	//检查容量是否增容
    	if (ps->size == ps->capacity)
    	{
    		add_capacity(ps);
    	}
    	从尾部开始后撤
    	//int end = ps->size;
    	//while(end>0)
    	//{
    	//	ps->a[end] = ps->a[end - 1];
    	//	end--;
    	//}
    	//ps->a[0] = x;
    	更新大小
    	//ps->size++;
    	SeqListInsert(ps,0,x);
    }
    
    //顺序表头删
    void SeqListPopFront(SeqList* ps)
    {
    	assert(ps);
    	//unsigned int start = 0;
    	从头部前移 覆盖前一个
    	//while (start < ps->size-1)
    	//{
    	//	ps->a[start] = ps->a[start+1];
    	//	start++;
    	//}
    	更新大小
    	//ps->size--;
    	SeqListErase(ps, 0);
    }

我们发现，这个插入和删除过程中都涉及到数组元素的移动，关键就是注意移动顺序，保证原有的数据不允许被覆盖即可，后面在指定位置处删除和插入操作与此步骤类似，所以，头插和头删可以调用指定位置插入和删除函数完成

*  ### 顺序表指定位置删除插入 ###

// 顺序表在pos位置插入值
    void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
    {
    	assert(ps);
    	//检查容量是否增容
    	if (pos >= 0 && pos < ps->size)
    	{
    		if (ps->size == ps->capacity)
    		{
    			add_capacity(ps);
    		}
    		unsigned int end = ps->size;
    		while (end > pos)
    		{
    			ps->a[end] = ps->a[end - 1];
    			end--;
    		}
    		//pos位置放入新值
    		ps->a[pos] = x;
    		//更新大小
    		ps->size++;
    	}
    }
    
    // 顺序表删除pos位置的值
    void SeqListErase(SeqList* ps, size_t pos)
    {
    	assert(ps);
    	if (pos >= 0 && pos < ps->size)
    	{
    		unsigned int start = pos;
    		//从头部前移 覆盖前一个
    		while (start < ps->size - 1)
    		{
    			ps->a[start] = ps->a[start + 1];
    			start++;
    		}
    		//更新大小
    		ps->size--;
    	}
    }

*  ### 顺序表获取大小，对应位置元素，以及判断表是否为空等操作 ###

//返回pos位置的值
    SLDateType SeqListAt(SeqList* ps, size_t pos)
    {
    	assert(ps);
    	if (pos >= 0 && pos <= ps->size)
    	{
    		return ps->a[pos];
    	}
    	return -1;
    }
    
    //返回有效元素个数
    size_t SeqListSize(SeqList* ps)
    {
    	assert(ps);
    	return ps->size;
    }
    
    //顺序表是否为空
    int SeqListisEmpty(SeqList* ps)
    {
    	if (ps == NULL || ps->size == 0)
    	{
    		return 1;
    	}
    	else
    		return 0;
    }