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