vps 建网站 代理,室内设计公司logo,qq短网址生成,制作我的第一个网页目录 前言一、定义与特点二、类型三、基本操作四、应用场景五、优缺点六、元素插入和删除动态图解插入删除 七、代码模板八、使用顺序表的经典例题1.求奇数的乘积代码题解 2.数值统计代码题解 九、总结结语 前言
顺序表示最基础的数据结构之一#xff0c;它也是我们学习开始学… 目录 前言一、定义与特点二、类型三、基本操作四、应用场景五、优缺点六、元素插入和删除动态图解插入删除 七、代码模板八、使用顺序表的经典例题1.求奇数的乘积代码题解 2.数值统计代码题解 九、总结结语 前言
顺序表示最基础的数据结构之一它也是我们学习开始学习数据结构的第一个必须要掌握的数据结构学习数据结构一定是由浅到深所以我们最好是先学习简单的在学习有难度的因为直接学习难的数据结构很容易劝退让我们来深入了解顺序表。
一、定义与特点
定义顺序表Sequence List是线性表的一种实现方式它使用一段地址连续的存储单元依次存储线性表的数据元素。
特点 1.数据元素在物理存储上是连续的这使得顺序表在访问元素时具有较高的效率。 2.顺序表支持随机访问即可以通过索引直接访问表中的任意元素时间复杂度为O(1)。 3.顺序表的插入和删除操作可能需要移动大量的元素尤其是在插入或删除中间位置的元素时时间复杂度为O(N)其中N是表中元素的数量。
二、类型
静态顺序表静态顺序表在初始化后其空间大小就不能更改。这意味着如果空间不足就无法向表中添加新的元素而如果空间过大则可能造成内存的浪费。因此静态顺序表在实际应用中具有一定的局限性。
动态顺序表动态顺序表则可以根据需要动态地调整空间大小。当空间不足时可以自动扩容当空间过多时也可以进行缩容尽管在实际应用中缩容并不常见。这使得动态顺序表在实际应用中更加灵活和高效
三、基本操作
初始化为顺序表分配必要的存储空间并初始化相关参数如有效数据个数、容量等。
销毁释放顺序表所占用的存储空间以避免内存泄漏。 插入在顺序表的指定位置插入一个新的元素。这可能需要移动其他元素来腾出位置。
删除从顺序表中删除指定位置的元素。这同样可能需要移动其他元素来填补位置。
查找在顺序表中查找指定值的元素并返回其位置如果存在。这通常通过遍历数组来实现。
访问通过索引直接访问顺序表中的指定元素。这是顺序表的一个主要优点。
四、应用场景
顺序表适用于需要频繁访问元素的场景因为顺序表支持随机访问可以在常数时间内访问到表中的任意元素。此外顺序表也适用于元素个数相对稳定的场景因为频繁的插入和删除操作可能会导致顺序表的效率下降。
五、优缺点
优点 支持随机访问访问速度快。 在物理存储上是连续的有利于CPU高速缓存的命中率。
缺点 插入和删除操作可能需要移动大量的元素效率较低。 在空间不足时需要扩容扩容操作可能比较耗时且浪费空间尽管通常采用两倍扩容策略来减少扩容次数。
六、元素插入和删除动态图解
插入 删除 七、代码模板
#includeiostream
using namespace std;#define eType intstruct SequentialTable {eType* elements;int size;int capacity;
};void initailizeTable(SequentialTable* list, int capacity) {//1.初始化顺序表list-elements new eType[capacity];//elements申请内存为eType类型的内存空间相当于数组容量为capacitylist-capacity capacity;list-size 0;}void destroyTable(SequentialTable* list) {//销毁顺序表delete[] list-elements;//将elements内存空间销毁
}int getSize(SequentialTable* list) {//顺序表长度return list-size;
}bool isEmpty(SequentialTable* list) {//顺序表是否为空return list-size 0;
}void insertElement(SequentialTable* list,int index, eType x) {//插入元素 index为插入位置x为插入的元素if (index0 || indexlist-size) {throw std::invalid_argument(Invalid index);//插入位置非法那么抛出异常}if (list-size list-capacity) {//如果顺序表长度大于容量那就扩容int newCapacity 2 * list-capacity;//容量扩大为原来的两倍eType* newElements new eType[newCapacity];for (int i 0; i list-size; i) {newElements[i] list-elements[i];}delete[] list-elements;//释放原来内存空间list-elements newElements;list-capacity newCapacity;}for (int i list-size; i index; i--) {list-elements[i] list-elements[i - 1];}list-elements[index] x;list-size;//注意插入元素长度加一
}void deleteElement(SequentialTable* list, int index) {if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}if (list-size 0) {//如果顺序表没有元素那么进行不了删除操作抛出异常throw std::invalid_argument(Invalid index);}for (int i index; i list-size - 1; i) {list-elements[i] list-elements[i 1];}list-size--;//长度减一
}int findElement(SequentialTable* list, eType x) {//找出元素的索引for (int i 0; i list-size; i) {if (x list-elements[i])return i;}return -1;//找不到返回-1
}eType getElement(SequentialTable* list, int index) {//返回索引对应的元素if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}return list-elements[index];
}void updateElement(SequentialTable* list, int index, eType x) {//更新元素if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}list-elements[index] x;
}int main() {//测试代码SequentialTable st;initailizeTable(st, 10);for (int i 0; i 10; i) {insertElement(st, i, i * 10);}deleteElement(st, 0);cout st.elements[0] endl;insertElement(st, 0, 0);cout st.elements[0] endl;cout isEmpty(st) endl;cout findElement(st, 70) endl;cout getElement(st, 7) endl;updateElement(st, 0, 1);cout st.elements[0] endl;return 0;
}八、使用顺序表的经典例题
1.求奇数的乘积
帅哥们这个蓝色字体可以点进去看原题
代码题解
#includeiostream
using namespace std;#define eType intstruct SequentialTable {eType* elements;int size;int capacity;
};void initailizeTable(SequentialTable* list, int capacity) {//1.初始化顺序表list-elements new eType[capacity];//elements申请内存为eType类型的内存空间相当于数组容量为capacitylist-capacity capacity;list-size 0;}void destroyTable(SequentialTable* list) {//销毁顺序表delete[] list-elements;//将elements内存空间销毁
}int getSize(SequentialTable* list) {//顺序表长度return list-size;
}bool isEmpty(SequentialTable* list) {//顺序表是否为空return list-size 0;
}void insertElement(SequentialTable* list,int index, eType x) {//插入元素 index为插入位置x为插入的元素if (index0 || indexlist-size) {throw std::invalid_argument(Invalid index);//插入位置非法那么抛出异常}if (list-size list-capacity) {//如果顺序表长度大于容量那就扩容int newCapacity 2 * list-capacity;//容量扩大为原来的两倍eType* newElements new eType[newCapacity];for (int i 0; i list-size; i) {newElements[i] list-elements[i];}delete[] list-elements;//释放原来内存空间list-elements newElements;list-capacity newCapacity;}for (int i list-size; i index; i--) {list-elements[i] list-elements[i - 1];}list-elements[index] x;list-size;//注意插入元素长度加一
}void deleteElement(SequentialTable* list, int index) {if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}if (list-size 0) {//如果顺序表没有元素那么进行不了删除操作抛出异常throw std::invalid_argument(Invalid index);}for (int i index; i list-size - 1; i) {list-elements[i] list-elements[i 1];}list-size--;//长度减一
}int findElement(SequentialTable* list, eType x) {//找出元素的索引for (int i 0; i list-size; i) {if (x list-elements[i])return i;}return -1;//找不到返回-1
}eType getElement(SequentialTable* list, int index) {//返回索引对应的元素if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}return list-elements[index];
}void updateElement(SequentialTable* list, int index, eType x) {//更新元素if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}list-elements[index] x;
}int main() {//测试代码int n;while (cin n) {SequentialTable s;initailizeTable(s, 1);for (int i 0; i n; i) {int x;cin x;insertElement(s, i, x);}int ret 1;for (int i 0; i s.size; i) {int val getElement(s, i);if (val 1)ret * val;}cout ret endl;}return 0;
}2.数值统计
帅哥们这个蓝色字体可以点进去看原题
代码题解
#includeiostream
using namespace std;#define eType double//元素类型struct SequentialTable {eType* elements;int size;int capacity;
};void initailizeTable(SequentialTable* list, int capacity) {//1.初始化顺序表list-elements new eType[capacity];//elements申请内存为eType类型的内存空间相当于数组容量为capacitylist-capacity capacity;list-size 0;}void destroyTable(SequentialTable* list) {//销毁顺序表delete[] list-elements;//将elements内存空间销毁
}int getSize(SequentialTable* list) {//顺序表长度return list-size;
}bool isEmpty(SequentialTable* list) {//顺序表是否为空return list-size 0;
}void insertElement(SequentialTable* list,int index, eType x) {//插入元素 index为插入位置x为插入的元素if (index0 || indexlist-size) {throw std::invalid_argument(Invalid index);//插入位置非法那么抛出异常}if (list-size list-capacity) {//如果顺序表长度大于容量那就扩容int newCapacity 2 * list-capacity;//容量扩大为原来的两倍eType* newElements new eType[newCapacity];for (int i 0; i list-size; i) {newElements[i] list-elements[i];}delete[] list-elements;//释放原来内存空间list-elements newElements;list-capacity newCapacity;}for (int i list-size; i index; i--) {list-elements[i] list-elements[i - 1];}list-elements[index] x;list-size;//注意插入元素长度加一
}void deleteElement(SequentialTable* list, int index) {if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}if (list-size 0) {//如果顺序表没有元素那么进行不了删除操作抛出异常throw std::invalid_argument(Invalid index);}for (int i index; i list-size - 1; i) {list-elements[i] list-elements[i 1];}list-size--;//长度减一
}int findElement(SequentialTable* list, eType x) {//找出元素的索引for (int i 0; i list-size; i) {if (x list-elements[i])return i;}return -1;//找不到返回-1
}eType getElement(SequentialTable* list, int index) {//返回索引对应的元素if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}return list-elements[index];
}void updateElement(SequentialTable* list, int index, eType x) {//更新元素if (index 0 || index list-size) {throw std::invalid_argument(Invalid index);}list-elements[index] x;
}int main() {//测试代码int n;while (cin nn) {SequentialTable s;initailizeTable(s, 1);for (int i 0; i n; i) {eType x;cin x;insertElement(s, i, x);}int pcnt 0, zcont 0, ncnt 0;for (int i 0; i s.size; i) {eType val getElement(s, i);if (val 1e-8) pcnt;else if (val -1e-8) ncnt;else zcont;}cout ncnt zcont pcnt endl;}return 0;
}九、总结
综上所述顺序表是一种基于数组实现的线性数据结构具有随机访问速度快、物理存储连续等优点。然而它也存在插入和删除操作效率低、扩容操作耗时等缺点。因此在选择数据结构时需要根据具体的应用场景和需求来权衡利弊。
结语
学习编程是一个很艰难漫长的过程我们要克服一切困难学习算法本就是由易到难不会的地方就问我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节加油我相信你一定能行。 想看更多内容可以关注我看我作品关注我让我们一起学习编程希望大家能点赞关注支持一下让我有持续更新的动力谢谢大家。
