IT女神节(致敬中国IT界永远的女神严蔚敏-数据结构)
创始人
2024-05-30 00:44:04
0

          我们都知道程序=数据结构+算法。相信很多人都学过严蔚敏的数据结构的课程。作为一个码农,在这不管是3.7女神节,还是3.8妇女节。我觉得都有必要向这些教育界的老前辈致敬。今天我就梳理梳理,最经典的数据结构教材。

严蔚敏介绍(来自百度百科)

严蔚敏(1938.04—),女,汉族。清华大学计算机系教授,长期从事数据结构教学和教材建设,和吴伟民合作编著的《数据结构》曾获“第二届普通高等学校优秀教材全国特等奖”和“1996年度国家科学技术进步奖三等奖”。成为我国大中专院校学习“数据结构”使用最多的教材版本。 

数据结构书籍封面:

我们来看看书籍目录:(大家看看自己还有多少还给老师了?)其实我们在面试中经常问的比较基础的东西就是这些东西。

第1章 结论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分析
1.4.1 算法
1.4.2 算法设计的要求
1.4.3 算法效率的度量
1.4.4 算法的存储空间需求
第2章 线性表
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
第3章 栈和队列
3.1 栈
3.1.1 抽象数据类型栈的定义
3.1.2 栈的表示和实现
3.2 栈的应用举例
3.2.1 数制转换
3.2.2 括号匹配的检验
3.2.3 行编辑程序
3.2.4 迷宫求解
3.2.5 表达式求值
3.3 栈与递归的实现
3.4 队列
3.4.1 抽象数据类型队列的定义
3.4.2 链队列--队列的链式表示和实现
3.4.3 循环队列--队列的顺序表示和实现
3.5 离散事件模拟
第4章 串
4.1 串类型的定义
4.2 串的表示和实现
4.2.1 定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.3 串的模式匹配算法
4.3.1 求子串位置的定位函数Index(S,T,pos)
4.3.2 模式匹配的一种改进算法
4.4 串操作应用举例
4.4.1 文本编辑
4.4.2 建立词索引表
第5章 数组和广义表
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 广义表的定义
5.5 广义表的存储结构
5.6 m元多项式的表示
5.7 广义表的递归算法
5.7.1 求广义表的深度
5.7.2 复制广义表
5.7.3 建立广义表的存储结构
第6章 树和二叉树
6.1 树的定义和基本术语
6.2 二叉树
6.2.1 二叉树的定义
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
6.4.3 树和森林的遍历
6.5 树与等价问题
6.6 赫夫曼树及其应用
6.6.1 最优二叉树(赫夫曼树)
6.6.2 赫夫曼编码
6.7 回溯法与树的遍历
6.8 树的计数
第7章 图
7.1 图的定义和术语
7.2 图的存储结构
7.2.1 数组表示法 [2] 
7.2.2 邻接表
7.2.3 十字链表
7.2.4 邻接多重表
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的连通性问题
7.4.1 天向图的连通分量和生成树
7.4.2 有向图的强连通分量
7.4.3 最小生成树
7.4.4 关节点和重连通分量
7.5 有向无环图及其应用
7.5.1 拓扑排序
7.5.2 关键路径
7.6 最短路径
7.6.1 从某个源点到其余各项点的最短路径
7.6.2 每一对顶点之间的最短路径
第8章 动态存储管理
8.1 概述
8.2 可利用空间表及分配方法
8.3 边界标识法
8.3.1 可利用空间表的结构
8.3.2 分配算法
8.3.3 回收算法
8.4 伙伴系统
8.4.1 可利用空间表的结构
8.4.2 分配算法
8.4.3 回收算法
8.5 无用单元收集
8.6 存储紧缩
第9章 查找
9.1 静态查找表
9.1.1 顺序表的查找
9.1.2 有序表的查找
9.1.3 静态树表的查找
9.1.4 索引顺序表的查找
9.2 动态查找表
9.2.1 二叉排序树和平衡二叉树
9.2.2 B_树和B+树
9.2.3 键树
9.3 哈希表
9.3.1 什么是哈希表
9.3.2 哈希函数的构造方法
9.3.3 处理冲突的方法
9.3.4 哈希表的查找及其分析
第10章 内部排序
10.1 概述
10.2 插入排序
10.2.1 直接插入排序
10.2.2 其他插入排序
10.2.3 希尔排序
10.3 快速排序
10.4 选择排序
10.4.1 简单选择排序
10.4.2 树形选择排序
10.4.3 堆排序
10.5 归并排序
10.6 基数排序
10.6.1 多关键字的排序
10.6.2 链式基数排序
10.7 各种内部排序方法的比较讨论
第11章 外部排序
11.1 外存信息的存取
11.2 外部排序的方法
11.3 多路平衡归并的实现
11.4 置换-选择排序
11.5 最佳归并树
第12章 文件
12.1 有关文件的基本概念
12.2 顺序文件
12.3 索引文件
12.4 ISAM文件和VSAM文件
12.4.1 ISAM文件
12.4.2 VSAM文件
12.5 直接存取文件(散列文件)
12.6 多关键字文件
12.6.1 多重表文件
12.6.2 倒排文件 [2] 

 重点学习数据结构:

一、线性表

线性表又称线性存储结构,是最简单的一种存储结构,专门用来存储逻辑关系为“一对一”的数据。

在一个数据集中,如果每个数据的左侧都有且仅有一个数据和它有关系,数据的右侧也有且仅有一个数据和它有关系,那么这些数据之间就是“一对一“的逻辑关系。

示例图:

 线性表的存储:

在具有“一对一“逻辑关系的数据集中,每个个体习惯称为数据元素(简称元素)

二、 栈和队列

栈:

对于逻辑关系为“一对一”的数据,除了用顺序表链表存储外,还可以用栈结构存储。
栈是一种“特殊”的线性存储结构,它的特殊之处体现在以下两个地方:
1、元素进栈和出栈的操作只能从一端完成,另一端是封闭的。

2、栈中无论存数据还是取数据,都必须遵循“先进后出”的原则,即最先入栈的元素最先出栈。

 队列:

队列用来存储逻辑关系为“一对一”的数据,是一种“特殊”的线性存储结构。

顺序表链表相比,队列的特殊性体现在以下两个方面:
1、元素只能从队列的一端进入,从另一端出去。

2、队列中各个元素的进出必须遵循“先进先出”的原则,即最先入队的元素必须最先出队。

 三、串

对于由多个字符(≥ 0)组成的字符串(例如 "maoheyeren"),数据结构单独提供了一种存储结构,称为串结构。

字符串中的字符之间具有“一对一”的逻辑关系,所以严格意义上讲,串存储结构也属于线性存储结构。和顺序表链表队列这些线性存储结构不同的是,串存储结构专门用来存储字符串。

空串指的是未存储任何字符的串,整个串的长度为 0。

String s = "";

空格串指的是由多个(>0)空格字符组成的串结构,整个串的长度为包含空格字符的个数。

String s = "    ";

子串和主串

maoheyerenmao

四、数组和广义表

数组是对线性表的扩展,是一种“特殊”的线性存储结构,用来存储具有多种“一对一”逻辑关系的数据。

实际场景中,存储具有 N 种“一对一”逻辑关系的数据,通常会建立 N 维数组

一维数组和其它线性存储结构很类似,用来存储只有一种“一对一”逻辑关系的数据

一维数组:

 二维数组用来存储包含两种“一对一”逻辑关系的数据。二维数组可以看作是存储一维数组的一维数组

二维数组:

 五、树和二叉树

树结构通常用来存储逻辑关系为 "一对多" 的数据。

 和链表类似,树存储结构中也将存储的各个元素称为 "结点"。

通常,我们将一棵树中几个结点构成的“小树”称为这棵树的“子树”。
一个结点拥有子树的个数,就称为该结点的度(Degree)。

从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层,依次类推。

如果一棵树中,各个结点左子树和右子树的位置不能交换,那么这棵树就称为有序树。反之,如果树中结点的左、右子树可以互换,那么这棵树就是一棵无序树。

由 m(m >= 0)个互不相交的树组成的集合就称为森林。

空树指的是没有任何结点的树,连根结点都没有。

二叉树:

简单地理解,满足以下两个条件的树就是二叉树:

  1. 本身是有序树;
  2. 树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2;

 

 

六、图 

图结构常用来存储逻辑关系为“多对多”的数据。比如说,一个学生可以同时选择多门课程,而一门课程可以同时被多名学生选择,学生和课程之间的逻辑关系就是“多对多”。

 

相关内容

热门资讯

安卓能刷索尼系统,索尼系统升级... 你有没有想过,你的安卓手机竟然也能变身成为索尼的忠实粉丝呢?没错,就是那个以高品质影音设备闻名的索尼...
yunos系统能刷安卓系统吗,... 亲爱的读者们,今天我要和你聊聊一个超级实用的话题——YunOS系统能不能刷安卓系统呢?是不是觉得有点...
安卓系统禁用菜单键,全面解析禁... 手机里的菜单键是不是有时候让你头疼?比如,你正全神贯注玩游戏,突然一个不小心按到了菜单键,游戏就中断...
安卓系统是什么钱包,一触即达 你知道吗?现在手机可是我们生活中不可或缺的好伙伴,而在这众多手机应用中,有一种特别的存在,那就是安卓...
安卓系统计步器设置,功能实现与... 你有没有发现,现在的人越来越注重健康生活了?手机上的各种健康应用也跟着火了起来,其中最火的莫过于计步...
安卓系统画画拍照软件,轻松创作 你有没有想过,用手机画画拍照也能变得这么有趣呢?现在,我就要给你揭秘那些在安卓系统上超好用的画画拍照...
安卓设备文件系统,安卓设备文件... 你有没有想过,你的安卓手机里那些密密麻麻的文件夹,它们其实就像是一个个神秘的宝藏库呢?今天,就让我带...
安卓系统9跟10,Androi... 你有没有发现,手机里的安卓系统就像是个不断成长的娃,从安卓9到安卓10,简直就像是从青涩的小伙子变成...
安卓系统怎么选择北斗,如何轻松... 亲爱的手机控们,你们有没有想过,你的安卓手机里藏着一个强大的北斗导航系统呢?没错,就是那个咱们国家自...
车载安卓系统怎么清理,畅享驾驶... 亲爱的车主朋友们,你们的车载安卓系统是不是也像你的手机一样,用久了就变得有点“臃肿”了呢?别急,今天...
在线安卓系统升级,安卓系统在线... 哇哦,你有没有发现,你的手机最近是不是变得有点儿“活泼”了?没错,说的就是你,那个陪伴你日常生活的安...
miui8.5安卓系统,安卓系... 亲爱的手机控们,今天我要和你聊聊一个超级实用的手机系统——MIUI 8.5,它可是基于安卓系统的一款...
纯c 的安卓系统,纯C语言构建... 亲爱的读者们,你是否曾想过,手机里的安卓系统竟然可以只用纯C语言编写?没错,这就是今天我们要探索的神...
mac苹果系统怎么切换安卓系统... 亲爱的果粉们,你是否曾想过,在苹果的优雅世界里,也能体验到安卓的狂野与自由?今天,就让我带你一起探索...
黑莓安卓系统格机,轻松恢复手机... 亲爱的手机控们,你们有没有想过,那些曾经陪伴我们度过无数时光的黑莓手机,竟然也能玩转安卓系统呢?没错...
安卓系统苹果占用大小,安卓与苹... 你有没有发现,现在手机圈里有个大话题:为什么安卓手机的运存和苹果手机差那么多呢?这就像两个好朋友,一...
电脑原生运行安卓系统,开启智能... 你有没有想过,在电脑上也能像玩手机一样,轻松运行安卓系统呢?没错,这就是今天我要跟你分享的神奇技能—...
安卓系统 蓝牙键盘对应,连接、... 你有没有想过,用手机打字的时候,是不是有时候觉得屏幕键盘太小,手指头跳来跳去,就像在键盘上跳迪斯科一...
怎么体验原生安卓系统,探索系统... 亲爱的手机控们,你是否曾对那些简洁流畅、原生味道十足的手机系统心生向往?没错,我说的就是原生安卓系统...
安卓录音系统音频,音频采集、处... 你有没有想过,你的安卓手机里藏着一个小小的录音师呢?没错,就是那个看似普通的录音功能,它可是有着大大...