线性表&顺序表思维导图
线性表&顺序表详解
树图思维导图提供 线性表&顺序表 在线思维导图免费制作，点击“编辑”按钮，可对 线性表&顺序表 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：9c08b24a7d08b27e2b418ec25b74696b
思维导图大纲
第一次用，凑活看，有点不会搞思维导图模板大纲
线性表、顺序表及基本操作思维导图模板大纲
顺序表
存储结构
逻辑上相邻的数据元素物理上也相邻
特点
随机访问
O（1）时间找到第i个元素
存储密度高
拓展容量不方便，插入删除不方便
实现方式
静态分配
使用静态数组实现，无法改变大小
动态分配：使用动态数组实现
L.data = (ElemType*) malloc(sizeof(ElemType) * size);
存满时用malloc动态拓展，将数据元素复制到新的存储区域并用free释放原区域
等概率下平均移动元素次数
插入
n/2
有n+1个位置可插入，第一个位置插入移动n个，第二个位置插入移动n-1个……累加/(n + 1)
删除
(n - 1)/2
有n个位置可删除，删除第一个移动后面n-1个，删除第二个移动后面n-2个……累加/n
基本操作
插入
ListInsert(&L,i,e)：将元素e插到L的第i个位置
插入位置后的元素要后移：注意，从后往前依次后移
时间复杂度
最好O(1)，此时插入表尾，不需要移动元素
最坏O(N)，此时插入表头，原有n个元素全部后移
平均O(N)
删除
ListDelete(&L,i,&e)
将L的第i个元素删除，并用e返回
删除位置之前的元素都要前移：注意，从前往后依次前移
时间复杂度
最好O(1)，此时删除表尾，不需要移动元素
最坏O(N)，此时删除表头，后续n-1个元素全部前移
平均O(N)
按位查找
GetElem(L,i)
获取表中第i个位置的元素的值
L.data[i - 1]：时间复杂度O(1)
按值查找
LocateElem(L,e)
在顺序表L中查找第一个元素值等于e的元素，并返回其位序
时间复杂度：最好O(1),最坏O(N),平均O(N)
线性表
定义
具有相同数据类型的n个数据元素的有限序列，n为表长，n=0时为空表
ai是线性表中第i个，特点：位序从1开始
特性
第一个元素称为首元
最后一个元素称为尾元
除了第一个元素外，其余每个元素只有一个直接前驱；除了最后一个元素外，其余每个元素只有一个直接后继
基本操作
创建、销毁、增删改查
判空、判长、打印输出
相关思维导图模板
树图思维导图提供 9.战斗的基督教 在线思维导图免费制作，点击“编辑”按钮，可对 9.战斗的基督教 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：33d168acd0cd9f767f809c7a5df86e3a
树图思维导图提供 3A Unit 1 A Proper Job 在线思维导图免费制作，点击“编辑”按钮，可对 3A Unit 1 A Proper Job 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8d966446cda22e33b426cba15d3d981e
沪公网安备 31011502019485号
上海工商