嘉兴秀洲区建设局网站,wordpress模板导出,网络广告的计费方式,年度网站信息化建设工作计划文章目录 一、引言二、动态顺序表的基本概念三、动态顺序表的实现1、结构体定义2、初始化3、销毁4、扩容5、缩容5、打印6、增删查改 四、分析动态顺序表1、存储方式2、优点3、缺点 五、总结1、练习题2、源代码 一、引言
想象一下#xff0c;你有一个箱子#xff08;静态顺序… 文章目录 一、引言二、动态顺序表的基本概念三、动态顺序表的实现1、结构体定义2、初始化3、销毁4、扩容5、缩容5、打印6、增删查改 四、分析动态顺序表1、存储方式2、优点3、缺点 五、总结1、练习题2、源代码 一、引言
想象一下你有一个箱子静态顺序表它的大小是固定的你只能在这个箱子里面放东西或者拿出来如果东西放不下了箱子就满了没办法再放更多。但现在我们有了一种更灵活的箱子 —— 动态顺序表。这个箱子不仅能放东西还能根据需要自动变大或变小非常方便。
不过要想玩转这个神奇的箱子我们得先对里面的 “东西” 数据的存放方式有所了解也就是得熟悉数组和指针。如果你对这些还不太熟悉别担心我已经为你准备了一篇文章作为参考传送门。读完之后你会发现它们其实并不复杂。 二、动态顺序表的基本概念
动态顺序表简单来说就是一个可以 “长大” 或 “缩小” 的箱子。它不像静态顺序表那样一开始就确定了大小而是根据我们需要存放的东西的多少来动态地调整自己的大小。
当我们往动态顺序表里放东西时如果箱子满了它就会自动去找一个更大的箱子然后把原来的东西和新东西一起放进去。这个过程就像是我们换了一个更大的家然后把所有家具都搬进去一样。
反过来如果我们从动态顺序表里拿走了很多东西箱子变得空荡荡的那它也会考虑换个小点的箱子住毕竟节省空间也是一种美德嘛。
总之动态顺序表就是这样一个既智能又灵活的箱子它能够帮助我们更加高效地管理和存储数据。 三、动态顺序表的实现
1、结构体定义
首先我们需要定义一个结构体来表示动态顺序表这个结构体将包含指向数组元素的指针、当前存储的元素数量以及分配的空间大小。
typedef int DataType;
typedef struct {DataType* arr;//指向动态数组的指针int size;//当前存储的元素个数int capacity;//当前动态数组的容量
}Seq;2、初始化
初始化动态顺序表时我们需要为其分配一个初始的空间大小并设置当前存储的元素数量为0。
void Init(Seq* ps, int capacity)
{capacity 0 ? capacity 2 : capacity;DataType* pos (DataType*)malloc(sizeof(DataType) * capacity);if (pos NULL){fprintf(stderr, 内存分配失败\n);exit(EXIT_FAILURE);}ps-array pos;ps-capacity capacity;ps-size 0;
}3、销毁
使用完动态顺序表后需要释放分配的内存避免内存泄漏。
void Destroy(Seq* ps)
{if (ps NULL)return;free(ps-array);ps-array NULL;ps-capacity 0;ps-size 0;
}4、扩容
当向动态顺序表中添加元素时如果当前空间已满则需要进行扩容操作。扩容通常会将容量加倍。
void Reserve(Seq* ps)
{if (ps-size ps-capacity){int capacity ps-capacity 0 ? 2 : ps-capacity * 2;DataType* pos (DataType*)realloc(ps-array, capacity * sizeof(DataType));if (pos NULL){fprintf(stderr, 内存分配失败\n);exit(EXIT_FAILURE);}ps-array pos;ps-capacity capacity;}
}5、缩容
当删除动态顺序表中的元素时如果当前空间过大则需要进行缩容操作。
void Shrink(Seq* ps)
{if (ps-capacity 64 ps-size ps-capacity / 2.5){int capacity ps-capacity / 2;DataType* pos (DataType*)realloc(ps-array, capacity * sizeof(DataType));if (pos NULL){fprintf(stderr, 内存分配失败);exit(EXIT_FAILURE);}ps-array pos;ps-capacity capacity;}
}5、打印
为了方便调试和查看动态顺序表中的内容我们可以实现一个打印函数将所有元素打印出来。
void Print(Seq* ps, void (*Pr) (DataType))
{for (int i 0; i ps-size; i){Pr(ps-array[i]);}printf(NULL\n);
}6、增删查改
实现顺序表的基本操作让顺序表更具有实用性。
void PushFront(Seq* ps, DataType data)
{Insert(ps, 0, data);
}void PopFront(Seq* ps)
{Erase(ps, 0);
}void PushBack(Seq* ps, DataType data)
{Insert(ps, ps-size, data);
}void PopBack(Seq* ps)
{Erase(ps, ps-size - 1);
}void Insert(Seq* ps, int x, DataType data)
{assert(x 0 x ps-size);Reserve(ps);for (int i ps-size - 1; i x; i--){ps-array[i 1] ps-array[i];}ps-array[x] data;ps-size;
}void Erase(Seq* ps, int x)
{assert(ps ! NULL ps-size 0 x 0 x ps-size);for (int i x; i ps-size - 1; i){ps-array[i] ps-array[i 1];}ps-size--;
}int Find(Seq* ps, DataType data)
{for (int i 0; i ps-size; i){if (ps-array[i] data){return i;}}return -1;
}void Modify(Seq* ps, int x, DataType data)
{assert(ps ! NULL ps-size 0 x 0 x ps-size);ps-array[x] data;
}四、分析动态顺序表
1、存储方式
顺序表是线性表的一种线性表的逻辑结构是连续的物理结构是不一定连续的。顺序表使用数组进行存储数组在内存中是连续的所以顺序表的物理结构是连续的。
2、优点
顺序表在随机访问时具有很高的效率因为数组在内存中是连续的所以可以通过下标直接访问到对应的元素。
3、缺点
顺序表在插入和删除元素时需要移动大量元素所以效率较低。另外顺序表的大小是固定的如果需要扩容需要重新分配内存这也会带来一定的开销。 五、总结
1、练习题
移除元素合并两个有序数组盛水最多的容器接雨水合并区间插入区间
2、源代码
对于动态顺序表的源代码我已经开源在GItee传送门 建议读者仔细阅读源代码理解数据结构的设计思路尝试修改和扩展功能以加深理解。通过编写测试案例来验证理解和代码的正确性。
