网站建设j介绍ppt模板,宁波企业网站优化推广,网站免费正能量不用下载,校园引流推广方法喜欢《数据结构》部分笔记的小伙伴可以订阅专栏#xff0c;今后还会不断更新。#x1f9d1;#x1f4bb; 此外#xff0c;《程序员必备技能》专栏和《程序员必备工具》专栏#xff08;该专栏暂未开设#xff09;日后会逐步更新#xff0c;感兴趣的小伙伴可以点一下订阅… 喜欢《数据结构》部分笔记的小伙伴可以订阅专栏今后还会不断更新。 此外《程序员必备技能》专栏和《程序员必备工具》专栏该专栏暂未开设日后会逐步更新感兴趣的小伙伴可以点一下订阅、收藏、关注 谢谢大家 逻辑结构
不管是顺序表还是链表都属于线性表都是线性结构
物理结构/存储结构
顺序表采用了顺序存储的方式
优点支持随机存取、存储密度高缺点大片连续空间分配不方便、改变容量不方便 链表采用链式存储的方式优点离散的小空间分配方便、改变容量方便缺点不可随机存取、存储密度低需要指针
数据的运算/基本操作
复习回忆思路创销、增删改查
创
顺序表
需要预分配大片连续空间若分配空间过小之后不方便扩展容量若分配空间过大则浪费内存资源 链表只需要分配一个头结点也可以不要头结点只声明一个头指针之后方便扩展 如果我们的线性表采用静态分配静态数组。那么容量不可改变动态分配动态数组。即便使用malloc, free函数改变容量但是需要移动大量元素时间代价很高
销
链表
free依次删除各个结点——手动回收空间 顺序表修改length 0——系统自动回收空间 由malloc申请的地址是内存中的堆区堆区不会由系统自动回收 所以在写代码的时候malloc和free必须成对出现 增、删
顺序表
插入/删除元素要将后续的元素都后移/前移时间复杂度 O ( n ) O(n) O(n)时间开销主要来自移动元素如果数据元素很大则移动的时间代价很高 链表插入/删除元素只需要修改指针即可时间复杂度 O ( n ) O(n) O(n)时间开销主要来自查找目标元素查找元素的时间代价更低
查
顺序表
按位查找 O ( 1 ) O(1) O(1)按值查找 O ( n ) O(n) O(n)若表内元素有序可在 O ( l o g 2 n ) O(log_2 n) O(log2n)时间内找到如二分查找* 链表按位查找 O ( n ) O(n) O(n)按值查找 O ( n ) O(n) O(n)
如何抉择
表长难以估计、经常要增加/删除元素————链表 表长可预估、查询搜索操作较多————顺序表
知识回顾
开放式问题的回答思路
可以先探讨逻辑结构再讨论存储结构然后再探讨一些比较重要的基本操作的实现效率最后得出结论
