数据结构概述
2021-05-27 12:36:07 13 举报AI智能生成
考研整理数据结构思维导图
作者其他创作
大纲/内容
五个特征
算法定义
五个特性：有穷性、确定性、可行性、输入、输出
效率的度量
时间复杂度
空间复杂度
三要素
逻辑结构：数据元素之间逻辑关系，独立于计算机
线性结构
线性表：具有相同数据类型的n个数据元素有限序列
一般线性表: 第二章--线性表
顺序存储
顺序表：第一个元素存储在线性表起始位置
第 i 个元素后面紧跟第 i+1个元素
第 i 个元素后面紧跟第 i+1个元素
选择：求移动节点平均次数 王道P14
综合应用题：实现对顺序表的增删查改 P17
链式存储
指针实现
单链表
双链表
循环链表
数组实现
静态链表
受限线性表
栈和队列
串
线性表推广
数组
循环单链表：每一个元素都有直接前驱和直接后继
非线性结构
集合
树形结构
一般树
二叉树
图状结构
有向图
无向图
存储结构（物理结构）：包括数据元素的表示和关系的表示
顺序存储：逻辑相邻、物理位置相邻
优点：1.实现随机存取 2.元素占用最少的存储空间
PS：存储和存取不同，存取分为随机存取和顺序存取，王道P3记录笔记
PS：存储和存取不同，存取分为随机存取和顺序存取，王道P3记录笔记
缺点：1.只能使用相邻的一整块存储单元，可能产生较多的外部碎片
链式存储：物理位置不需相邻
优点：1.不会出现碎片现象 2.能充分利用所有存储单元
缺点：1.每个元素因存储指针还需要额外存储空间 2.只能实现顺序存储
索引存储：存储元素同事，建立附加索引表
PS：索引表中每一项称作索引项，其一般形式（关键字，地址）
PS：索引表中每一项称作索引项，其一般形式（关键字，地址）
优点：检索速度快
缺点：1.附加的索引表占用存储空间 2.增删数据需要修改索引表
散列存储（哈希存储）：根据元素关键字直接计算出该元素存储地址
优点：增、删、查速度快
缺点：如果散列函数不好，会出现存储单元冲突，解决冲突耗时大
数据运算
0 条评论
下一页
