购物网站开发实例,成都有哪些好玩的地方和景点,在线代理上网,赣州网站建设jxgzg3文章目录 6.对比#xff1a;顺序表链表6.1逻辑结构6.2物理结构#xff08;存储结构#xff09;6.2.1顺序表6.2.2链表 6.3数据运算#xff08;基本操作#xff09;6.3.1初始化6.3.2销毁表6.3.3插入、删除6.3.4查找 6.对比#xff1a;顺序表链表
6.1逻辑结构
顺… 文章目录 6.对比顺序表链表6.1逻辑结构6.2物理结构存储结构6.2.1顺序表6.2.2链表 6.3数据运算基本操作6.3.1初始化6.3.2销毁表6.3.3插入、删除6.3.4查找 6.对比顺序表链表
6.1逻辑结构
顺序表和链表都是线性结构。
6.2物理结构存储结构
6.2.1顺序表
顺序存储 优点
使用顺序存储每个数据元素大小相同所以可以随机访问即可以在O(1)时间内找到第i个元素。存储密度高每个节点只存储数据元素。
缺点
拓展容量不方便使用大片连续的空间即便采用动态分配的方式实现拓展长度的时间复杂度也比较高。插入、删除操作不方便需要移动大量元素。
6.2.2链表
链式存储 优点
离散分配空间分配方便改变容量方便。单链表的节点是通过指针来连接的因此在插入、删除节点时不需要移动其他节点只需要修改指针的指向即可。
缺点
由于链表每个节点只存储了指向下一个节点的指针只能顺序存储不可随机存储所以访问节点时需要从头指针开始依次遍历访问直到找到需要的节点或者到达链表的结尾。存储密度低每个结点除了存储数据元素还存储了指针。
6.3数据运算基本操作
6个基本操作创销增删改查
顺序表链表数据弹性可扩容√增、删√查找√
6.3.1初始化
顺序表
需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量若分配空间过大则浪费内存资源。
静态分配静态数组容量不可以改变。动态分配动态数组malloc、free容量可改变但需要移动大量元素时间代价高。
链表
只需分配一个头结点(也可以不要头结点只声明一个头指针之后方便拓展。
6.3.2销毁表
顺序表
修改Length 0释放空间 静态分配静态数组系统自动回收空间。动态分配动态数组malloc、 free需要手动free。
链表
依次删除各个结点free。
6.3.3插入、删除
顺序表
插入/删除元素要将后续元素都后移/前移。
时间复杂度O(n)时间开销主要来自移动元素。
链表
插入/删除元素只需修改指针即可。
时间复杂度O(n)时间开销主要来自查找目标元素。
若元素占用空间很大那么移动元素花费的时间要比查找元素花费是时间代价更大。
6.3.4查找
顺序表
按位查找使用顺序存储每个数据元素大小相同所以可以随机访问即可以在**O(1)**时间内找到第i个元素。
按值查找O(n)。若表内元素有序可在 O(log_2n) 时间内找到。
链表
按位查找由于单链表每个节点只存储了指向下一个节点的指针只能顺序存储不可随机存储所以访问节点时需要从头指针开始依次遍历访问直到找到需要的节点O(n)。
按值查找只能遍历O(n)
