顺序表的结构和扩充
顺序表的结构和扩充
顺序表的结构
顺序表的完整信息包括两部分:
- 数据区
- 信息区,即元素存储区的容量和当前表中已有的元素个数
顺序表的扩充
数据区更换为存储空间更大的区域时。
两种扩充策略
- 每次扩充增加固定数目的存储位置,如每次扩充增加10个元素位置,这种策略可以成为线性增长。
- 特点:节省空间,但是扩充操作频繁,操作次数多
- 每次扩充容量加倍,如每次扩充增加一倍存储空间
- 特点:减少了扩充操作的执行次数,但可能会浪费空间资源,以空间换时间,推荐的方式。
元素存储区替换
顺序表存储在连续的空间,则只能整体搬迁。