数据结构之顺序表——动态顺序表(C语言版)

静态顺序表我们已经实现完毕了，下来我们实现一下动态顺序表

静态链接：数据结构之顺序表——动态顺序表(C语言版)
首先来了解一下两个顺序表的差别
一、内存管理的灵活性
动态分配与释放：动态顺序表能够在运行时根据需要动态地分配和释放内存空间。这意味着，当数据量增加时，它可以自动扩容以容纳更多的数据；而当数据量减少时，理论上也可以相应地释放不再需要的内存空间（尽管这通常需要程序员手动操作或依赖垃圾回收机制，具体取决于编程语言）。这种灵活性使得动态顺序表能够更高效地管理内存资源。
避免内存浪费：与静态顺序表相比，动态顺序表能够更准确地根据实际需求分配内存空间，从而避免了因预先分配过多内存而导致的内存浪费问题。同时，它也能够在数据量减少时释放部分内存空间，进一步提高了内存资源的利用率。
二、操作的便捷性
插入与删除操作的灵活性：在动态顺序表中，插入和删除操作可以更加灵活地进行。由于内存空间是动态分配的，因此可以在不移动大量元素的情况下完成插入和删除操作（尽管在某些情况下仍然需要移动部分元素以保持数据的连续性）。相比之下，静态顺序表在进行插入和删除操作时通常需要移动大量的元素，这降低了操作的效率。
适应数据变化的能力：动态顺序表能够更好地适应数据量的变化。当数据量增加时，它可以自动扩容以容纳更多的数据；而当数据量减少时，它也可以相应地调整内存空间的大小。这种能力使得动态顺序表在处理不确定大小的数据集时更加高效和便捷
。
总而言之，就是为了使我们的顺序表更加灵活，长度不够去动态开辟。
下来我们通过代码来实现一下动态顺序表。
首先还是一样，我们从头文件开始写起

#pragma once
//包含头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 定义顺序表存储的数据类型 
typedef int SQDataType;
// 定义顺序表的结构体  
typedef struct {SQDataType* arr;// 指向动态分配数组的指针（数组的首地址）  int size; // 顺序表当前存储的元素个数（有效长度）int capacity; // 顺序表的容量（即数组的总大小）  
}SL;
void SListInIt(SL* ps);//初始化函数

为了方便测试，我们完成打印函数

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

下来我们完成初始化函数：

//包含我们自己写的头文件
#include"SList_02.h"
// 初始化顺序表  
// 为顺序表分配初始内存，并设置size为0，capacity为指定的初始容量  
void SListInIt(SL* ps)
{ps->arr = NULL;//将数组的首地址赋值为空ps->size = 0;//数组的有效长度ps->capacity = 0;//容量
}

OK，经过调试我们知道我们的初始化已经完成了

下来我们写尾插函数

void SListPushback(SL* ps,SQDataType x)
{//首先进行动态内存分配mallocint newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;if (ps->capacity == ps->size){SQDataType* temp = malloc(newcapacity * sizeof(SQDataType));if (temp == NULL){printf("erro\n");exit(-1);}else{ps->arr = temp;ps->capacity = newcapacity;}}ps->arr[ps->size] = x;ps->size++;
}

运行一下

尾插成功
由于我们每次都需要检查一下剩余的空间是否足够所以我们这里写一个检查函数，就会方便很多

void SqListCheck(SL* ps)
{int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//创建一个变量newcapacity,如果原来的容量为0则修改为4，如果不为0，则为原来的二倍if (ps->capacity == ps->size)//说明容量满了，需要扩容了{SQDataType *tmp=realloc(ps->arr, newcapacity * sizeof(SQDataType));//扩容二倍//如果扩容失败if (tmp == NULL){printf("error\n");exit(-1);//非正常退出程序}//正常执行else{ps->arr = tmp;//扩容的新地址给原来的变量ps->capacity = newcapacity;//新容量赋值给原来的容量}}
}

头插函数

void SListPushFront(SL* ps, SQDataType x)
{//程序开始先检查一下需不需要扩容SqListCheck(ps);//ps已经是指针变量了指向SL类型//头插就是把所有的数据往后挪动一位，空出来索引为0的位置，将新数据插入进去int end = ps->size - 1;//由于我们每次插入数据之后，size都会++所以这里end表示的是索引值while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;
}

测试一下没有问题

头删函数：

void SqListDeleteFront(SL* ps)
{//和静态一样，只需要覆盖就好了int start = 0;while (start < ps->size){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;
}

调用了两次，成功删除
尾删函数：

void SqListDeleteback(SL* ps)
{//直接把有效长度减一就可以了，很简单ps->size--;
}

删除成功
随机插入函数：

void SqListInter(SL* ps, int pos, SQDataType x)
{	assert(pos < ps->size);//断言一下看是否插入合法SqListCheck(ps);//检查一下，长度不够的话就扩容int end = ps->size - 1;//跟头插差不多，循环条件改到pos 就可以了while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;//赋值要插入的值给索引pos的位置ps->size++;}

成功插入
随机删除函数：

void SqListDelete(SL* ps, int pos)
{assert(pos < ps->size);//断言一下看是否删除合法int start = pos;while (start < ps->size){ps->arr[start - 1] = ps->arr[start];start++;}ps->size--;}

删除成功，这里不是按照索引删除的，是按照数字的真实位置删除，如果需要按照索引删除，只需要改一下代码：

void SqListDelete(SL* ps, int pos)
{assert(pos < ps->size);//断言一下看是否删除合法int start = pos+1;while (start < ps->size){ps->arr[start - 1] = ps->arr[start];start++;}ps->size--;}

现在就是根据索引删除啦

改函数：

void SqListModity(SL* ps, int pos, SQDataType x)
{assert(pos < ps->size);//断言一下看是否改变合法//改直接改就行了，看是根据索引改，还是根据真实序号改//这里我们以索引为例ps->arr[pos] = x;}

成功修改了
查函数：是按照索引来显示的，如果要按照真实位置则需要在打印的时候换成 i + 1

void SqListFound(SL* ps, SQDataType x)
{int count = 0;for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("此元素是第%d个元素\n", i);count++;break;}}if (count == 0){printf("顺序表中没有这个元素\n");}}

而且我们也可以用排序的方式来查，这里提供接口函数

//快速排序
void SqListSort(SL* ps)
{qsort(ps->arr, ps->size, sizeof(SQDataType), cmp);
}
//排序方法
int cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
//二分查找
int Binary_Search(struct Sq* ps, int x)
{int min = 0;int max = ps->size - 1;int mid = 0;while (min <= max){mid = (min + max) / 2;if (ps->arr[mid] < x){min = mid + 1;}else if (ps->arr[mid] > x){max = mid - 1;}else{return mid;}}return -1;
}

大家可以试一下
关于qsort函数，大家可以看qsort快速排序以及冒泡模拟实现
最后我们还得释放多余的空间，释放函数：

void SqListDestory(SL* ps)
{free(ps->arr);ps->arr = NULL;ps->capacity = ps->size = 0;
}

以下是完整代码：

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
typedef struct {SQDataType* arr;int size;int capacity;
}SL;
void SListInit(SL* ps);//初始化函数
void SListPushback(SL* ps,SQDataType x);//尾插函数
void SListPushFront(SL* ps, SQDataType x);//头插函数
void PrintSList(SL* ps);//打印函数
void SqListDeleteFront(SL* ps);//头删
void SqListDeleteback(SL* ps);//尾删
void SqListInter(SL* ps, int pos, SQDataType x);//随即插入
void SqListDelete(SL* ps, int pos);//随机删除
void SqListModity(SL* ps, int pos, SQDataType x);//改函数
void SqListFound(SL* ps, SQDataType x);//查函数
void SqListCheck(SL* ps);//检查函数
void SqListDestory(SL* ps);//释放函数

函数

#include"SList_02.h"
void SListInit(SL* ps)
{ps->arr = NULL;//将数组的首地址赋值为空ps->size = 0;//数组的有效长度ps->capacity = 0;//容量
}
void PrintSList(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d  ", ps->arr[i]);}printf("\n");
}
void SqListCheck(SL* ps)
{int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//创建一个变量newcapacity,如果原来的容量为0则修改为4，如果不为0，则为原来的二倍if (ps->capacity == ps->size)//说明容量满了，需要扩容了{SQDataType *tmp=realloc(ps->arr, newcapacity * sizeof(SQDataType));//扩容二倍//如果扩容失败if (tmp == NULL){printf("error\n");exit(-1);//非正常退出程序}//正常执行else{ps->arr = tmp;//扩容的新地址给原来的变量ps->capacity = newcapacity;//新容量赋值给原来的容量}}
}
//void SqListCheck(SL* ps)
//{
//	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//	//如果满了就要扩容
//	if (ps->size == ps->capacity)
//	{
//		/*ps->capacity=realloc(ps->arr,ps->capacity=ps->capacity*2)*/
//		SQDataType* temp = realloc(ps->arr, newcapacity * sizeof(SQDataType));
//		if (temp == NULL)
//		{
//			printf("fail\n");
//			exit(-1);
//		}
//		else
//		{
//			ps->arr = temp;
//			ps->capacity = newcapacity;
//		}
//	}
//}
void SListPushback(SL* ps,SQDataType x)
{//首先进行动态内存分配mallocint newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;if (ps->capacity == ps->size){SQDataType* temp = malloc(newcapacity * sizeof(SQDataType));if (temp == NULL){printf("erro\n");exit(-1);}else{ps->arr = temp;ps->capacity = newcapacity;}}ps->arr[ps->size] = x;ps->size++;
}void SListPushFront(SL* ps, SQDataType x)
{//程序开始先检查一下需不需要扩容SqListCheck(ps);//ps已经是指针变量了指向SL类型//头插就是把所有的数据往后挪动一位，空出来索引为0的位置，将新数据插入进去int end = ps->size - 1;//由于我们每次插入数据之后，size都会++所以这里end表示的是索引值while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;
}
void SqListDeleteFront(SL* ps)
{//和静态一样，只需要覆盖就好了int start = 0;while (start < ps->size){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;
}
void SqListDeleteback(SL* ps)
{//直接把有效长度减一就可以了，很简单ps->size--;
}
void SqListInter(SL* ps, int pos, SQDataType x)
{	assert(pos < ps->size);//断言一下看是否插入合法SqListCheck(ps);//检查一下，长度不够的话就扩容int end = ps->size - 1;//跟头插差不多，循环条件改到pos 就可以了while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;//赋值要插入的值给索引pos的位置ps->size++;}
void SqListDelete(SL* ps, int pos)
{assert(pos < ps->size);//断言一下看是否删除合法int start = pos+1;while (start <=ps->size){ps->arr[start-1] = ps->arr[start];start++;}ps->size--;}
void SqListModity(SL* ps, int pos, SQDataType x)
{assert(pos < ps->size);//断言一下看是否改变合法//改直接改就行了，看是根据索引改，还是根据真实序号改//这里我们以索引为例ps->arr[pos] = x;}
void SqListFound(SL* ps, SQDataType x)
{int count = 0;for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("此元素是第%d个元素\n", i);count++;break;}}if (count == 0){printf("顺序表中没有这个元素\n");}}
void SqListDestory(SL* ps)
{free(ps->arr);ps->arr = NULL;ps->capacity = ps->size = 0;
}

测试函数

#include"SList_02.h"
void test()
{SL s;SListInit(&s);SListPushback(&s, 5);SListPushback(&s, 7);PrintSList(&s);SListPushFront(&s, 3);SListPushFront(&s, 9);SListPushFront(&s, 6);PrintSList(&s);SListPushFront(&s, 8);SListPushFront(&s, 11);SListPushFront(&s, 16);SListPushFront(&s, 15);SListPushFront(&s, 1);PrintSList(&s);SqListDeleteFront(&s);SqListDeleteFront(&s);PrintSList(&s);SqListDeleteback(&s);SqListDeleteback(&s);PrintSList(&s);SqListInter(&s, 2, 50);PrintSList(&s);SqListInter(&s, 5, 60);PrintSList(&s);SqListDelete(&s, 2);PrintSList(&s);SqListDelete(&s, 5);PrintSList(&s);SqListModity(&s, 3, 25);PrintSList(&s);SqListModity(&s, 3, 29);PrintSList(&s);SqListFound(&s, 29);SqListFound(&s, 1);SqListDestory(&s);}
int main()
{test();return 0;
}