首页  思维导图  详情



 



小梁数据结构

2025-12-21 20:46:37   0  举报





仅支持查看

AI智能生成

期末速成

大学

模板推荐

作者其他创作

大纲/内容

数据结构

基本术语

数据(所有元素集合)

数据元素：数据结构基本单位（记录）

数据项：数据元素具体信息（元素）

数据对象：相同属性的数据元素集合（具有条件的元素集合）

数据>数据对象>数据元素>数据项

组织方式

逻辑结构（唯一性）

线性结构（1：1）

线性表

栈、队列

串、数组

非线性结构（1：∞ | ∞：∞）

树形结构

图形结构

物理结构（存储结构）

顺序存储（连续）

链式存储（不一定连续）

数据本身信息

一个或多个指向其他元素的指针

算法

基本特征

输入（可以没有输入）

输出（一定要有输出）

确定性

有穷性

可行性

评价

正确性

可读性

健壮性

高效性

时间代价

时间复杂度

常数：O（1）

对数：O（log2（n））

线性：O（n）

平方：O（n²）

语句频度：代码执行的次数

单层循环（n）

嵌套循环（n*m）

空间代价

空间复杂度

组成部分

输入数据所占空间（输入的数据）

辅助存储空间：固定不变（临时变量、局部变量、常量）

临时空间：动态增加（数组、链表节点、栈帧）

类型

常数O（1）：所需空间不会随输入规划变化

线性O（n）：所需空间与输入数据量成正比

线性表（1：1）

特点

有序性

唯一性

动态性

常见操作

插入

删除

访问

搜索

排序

表示和实现

顺序表（逻辑相邻，物理相邻）

优点

时间（随机存取表中任一元素）

空间（存储密度大）

缺点

时间（插入、删除某一元素需要移动大量元素）

空间（浪费存储空间，是静态存储方式，元素个数不能自由扩充）

链表（逻辑相邻，物理不一定相邻）：数据+指针

分类

单链表（一个指针）

双链表（两个指针）

循环链表（首尾相连）

存储结构

头指针（第一个结点的指针）

首元节点（第一个元素的结点）

头结点（首元结点前的一个结点，存首元结点的位置信息）

栈和队列

栈（先进后出，后进先出）

顺序栈：只能在栈顶删除和插入

常规操作

初始化（S.top = S.base）

栈是否为空（S.top == S.base）

长度（S.top - S.base）

清空栈（S.top = S.base）

进栈

出栈

链栈

队列（先进先出）

顺序存储

循环队列：队满（rear+1）%M个元素 == front

链式存储

串、数组、广义表

串

常见名词

主串

字串

字符位置

字串位置

串相等

空格串

匹配

bf算法

KMP算法

数组

存储方式

行列存储

矩阵

对称矩阵：地址(i(i-1)/2+j)

广义表

广义表（LS：表名，ai：子表、元素（原子），n：长度）：广义表是可能含有 0 个或多个子表的表

去表头（先找第一个子表，没有就找第一个原子），去表尾（去掉表头剩下的）

特点

次序性

有长度

有深度（括号的重数）

可递归（自己可作为自己的子表）

可共享

树、二叉树

树（1:∞）

二叉树

性质

第i层上至多有2^(i-1)个结点，至少有1个

深度为k的二叉树至少有(2^k)-1个结点，至少有k个

叶子数n0=n1+1

具有n个节点的完全二叉树的深度必为[log2(n)]+1

完全二叉树从上至下，从左到右编号，若编号为i，则左孩子必为2i，右孩子必为2i+1，双亲必为i/2

区分

满二叉树：每一层都充满结点（特殊情况）

完全二叉树（最后一层叶子不满）

遍历

先序，中序，后序

<br>

哈夫曼编码

编码过程（遇0向左，遇1向右）

WPL、权值、带权路径  WPL=权值*带权路径

<br>

哈夫曼树（权值大的结点靠近根）

 Collect

Get Started

数据结构-概述

 Collect

Get Started

数据结构与算法汇总

 Collect

Get Started

【数据】数据结构，查询排序算法

 Collect

Get Started

数据结构





0 条评论

下一页