类似wordpress的建站,郑州主动营销网站,建设软件资源网站,建设手机网站费用静态顺序表我们已经实现完毕了#xff0c;下来我们实现一下动态顺序表
静态链接#xff1a;数据结构之顺序表——动态顺序表(C语言版) 首先来了解一下两个顺序表的差别 一、内存管理的灵活性 动态分配与释放#xff1a;动态顺序表能够在运行时根据需要动态地分配和释放内存…静态顺序表我们已经实现完毕了下来我们实现一下动态顺序表
静态链接数据结构之顺序表——动态顺序表(C语言版) 首先来了解一下两个顺序表的差别 一、内存管理的灵活性 动态分配与释放动态顺序表能够在运行时根据需要动态地分配和释放内存空间。这意味着当数据量增加时它可以自动扩容以容纳更多的数据而当数据量减少时理论上也可以相应地释放不再需要的内存空间尽管这通常需要程序员手动操作或依赖垃圾回收机制具体取决于编程语言。这种灵活性使得动态顺序表能够更高效地管理内存资源。 避免内存浪费与静态顺序表相比动态顺序表能够更准确地根据实际需求分配内存空间从而避免了因预先分配过多内存而导致的内存浪费问题。同时它也能够在数据量减少时释放部分内存空间进一步提高了内存资源的利用率。 二、操作的便捷性 插入与删除操作的灵活性在动态顺序表中插入和删除操作可以更加灵活地进行。由于内存空间是动态分配的因此可以在不移动大量元素的情况下完成插入和删除操作尽管在某些情况下仍然需要移动部分元素以保持数据的连续性。相比之下静态顺序表在进行插入和删除操作时通常需要移动大量的元素这降低了操作的效率。 适应数据变化的能力动态顺序表能够更好地适应数据量的变化。当数据量增加时它可以自动扩容以容纳更多的数据而当数据量减少时它也可以相应地调整内存空间的大小。这种能力使得动态顺序表在处理不确定大小的数据集时更加高效和便捷 。 总而言之就是为了使我们的顺序表更加灵活长度不够去动态开辟。 下来我们通过代码来实现一下动态顺序表。 首先还是一样我们从头文件开始写起
#pragma once
//包含头文件
#includestdio.h
#includestdlib.h
#includeassert.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);
}下来我们完成初始化函数
//包含我们自己写的头文件
#includeSList_02.h
// 初始化顺序表
// 为顺序表分配初始内存并设置size为0capacity为指定的初始容量
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 *tmprealloc(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 pos1;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
#includestdio.h
#includestdlib.h
#includeassert.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);//释放函数函数
#includeSList_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 *tmprealloc(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-capacityrealloc(ps-arr,ps-capacityps-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 pos1;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;
}
测试函数
#includeSList_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;
}
