的支持。 扩展界面支持库六：对多功能条控件进行的小的改进。 农历日期支持库：修改农历日期框控件调用“增减日期”“置农历日期”“置公历日期”等方法后未及时更新显示文本的BUG。 数据结构支持库：修改"链表.加入节点"方法有时不能按键值正确排序的BUG。 其它一些支持库的改进和修正 4、以下支持库被修正或增加新功能： 互联网服务支持库 网络传送支持库 mysql支持库 Sqlite数据库支持库：增加了20个命令以直接返回相关数据（而不是写入到参数变量中）。 扩展界面支持库三：增加了提示文本功能，同时更新了卷帘式菜单和高级选择夹的属性编辑对话框并增加了相关方法；在卷帘式菜单控件的“项目”属性编辑对话框中，如果项目名称为空文本，则显示为“未命名”，以便于用户以鼠标点击选中。 扩展界面支持库五：“汽球提示框”更名为“气球提示框”并增加“批量关联组件”方法，以方便用户动态指定提示文本；修改其“提示框即将弹出”事件的参数“手柄横向坐标”“手柄纵向坐标”，由屏幕坐标改为客户坐标，以方便用户处理。 数据图表支持库：曲线图和柱状图增加了“显示标注”和“提示文本”属性；鼠标指向曲线图和柱状图的相应区域时会有提示框弹出并显示当前数据值。 1、“新建”对话框布局改变，将一些新建项目进行了分类，大家可以在Samples和Wizard目录中组织目录，“新建”对话框会自动列出。 2、新的“文本代码编辑器”工具。 代码编辑方式是以文本方式编辑，在每一行程序编辑完成后不必回车确认，直接下移光标继续输入。或按[Shift+回车]可代替原单键[回车]形式。 可以将代码以文本方式复制到记事本，或从记事本将文本代码粘贴回来，系统自动恢复为程序代码。 “系统配置”中可以设置改变编辑区字体及字号。 “系统配置”中的“输入新语句后自动检查语法错误”项选中时，当光标在代码行末时回车，就可以编译当前行检查是否有语法错误，并在提示面板中提示出来。默认为选中。 若“系统配置”的“输入新语句后自动检查语法错误”项未勾选，代码编辑时将不会弹出错误提示，代码编辑后的运算符号不会规范整理，而会在调试或编译时给出错误提示，或使用全程提示工具检查，或通过按[Shift+回车]编译当前行进行检查。 3、新的“全程提示”工具，当用户将鼠标移至常量、变量、属性表等名称上停留片刻，会显示当前名称的相关信息。对未事先声明的变量不作任何提示。 4、新的“寻找替换管理器”工具。可以在当前程序集中进行寻找与替换。 5、新的“程序调试管理器”工具。新设计的“调用表”面板与“监视表”面板代替了原调试面板，具体使用与原来的调试方法类似，可用“查看表达式/变量”菜单查看当前子程序变量值。 6、新的“整体搜寻管理器”工具。提示夹中增加“搜寻1”、“搜寻2”两个面板。使用“整体搜寻”菜单命令可将搜寻结果显示在其中，并且可以对比查看。 7、新的“条件断点管理器”工具。新增“条件断点”菜单，可以设置断点时给定一组条件，方便调试，如果断点不是条件公式，就会自动转换为普通断点。 8、新的“组件排列管理器”工具。当没有安装扩展组件、OCX组件或COM组件时，不显示分类，当组件排列拥挤时，自动增加分类。 9、新的“配色方案管理器”工具。编辑代码区与属性表的配色方案已合并，且支持任意颜色自由定制，大家可将自定义的配色方案拷贝到Clr目录中，就可在列表中看到。 请使用菜单“工具”→“系统配置”→“程序显示”→“颜色配置”，在下拉列表中选择本Clr目录中的颜色配置文件。 10、“提示”面板中显示命令帮助内容时，将会显示当前命令所处的上级支持库分类信息，以利于用户查询所在支持库。 11、调试中断后回到代码编译界面，可将鼠标移到变量上查看变量值提示。 12、备注直接使用单引号标注，并兼容打开以前版本的代码自动改为单引号标注形式。 13、热键调整：如原直接使用键盘的方向键可展开命令，现在需要使用[ALT+方向键]才可以展开，“单步跟踪”热键有所改动。 编辑时原[F1]热键插入文件名称路径现改为[F2]热键插入。[F10]可删除一行，[CTRL+K]可屏蔽一行。 14、菜单调整：如“配置”子菜单移至“程序”菜单下，增加“条件断点”菜单，原“易向导”菜单改为“执行易向导”菜单.....具体请自行对比。 15、Samples目录中增加大量的经典例程，供大家学习交流。 16、Ecom易模块目录中新增若干易模块及例程。 17、易向导中增加“通用密码登录管理向导”及“OpenGL向导”。 18、系统配置对话框的“编译选项”中新增“是否使用Windows通用组件库6.0版”选项，默认不选中。如果选中，编译后的程序将使用6.0版风格的组件。 19、推出了以下新的支持库： 农历月历支持库中新增“农历月历”组件 拖放支持库 正则表达式支持库 进程通讯支持库 BT下载支持库 网络通讯支持库二 扩展界面支持库三中增加“高级选择夹”组件（本库必须在易语言4.0以上版本中使用） 应用接口支持库 OpenGL支持库 DirectX发支持库 SQLite数据库支持库 控制台操作支持库 扩展界面支持库五 20、办公组件支持库已升级，推荐大家使用该升级后的支持库。 21、新表格组件改名为高级表格以区分基本支持库中的表格，方便大家定义数据类型。 22、网络传送支持库更新及易语言下载快车已更新。 23、基本组件中的打印机组件已支持自定义纸张，“开始打印”方法中当“纸张”参数为-1时,可以自定纸张宽高。 24、“打印机”对象和“打印设置信息”数据类型中的打印纸类型新增了100多种扩展打印纸类型。 25、系统核心支持库中的“寻找字节集”和“倒找字节集”命令各增加一个参数。 26、窗口组件的基本事件中加入了“滚轮被滚动”事件，以支持鼠标滚轮编程。 27、核心库“其它”类别中增加了“DLL命令调用转向”命令，以支持程序中对非固定文件名DLL中的输出命令进行调用。 28、编辑组件的文本型属性时可以编辑多行文本。 29、组件箱右上角增加一个按钮,可以在组件图标排列与组件名列表中切换。 30、“输出调试文本”命令支持通用数据类型。 31、编译使用了易模块的易程序时，由过去仅在易语言安装目录ECOM下寻找所需要的易模块文件改为首先在易程序所处目录下寻找，然后再去ECOM目录下寻找。 32、易模块管理对话框中新增了“创建指定易模块文件的接口程序集”按钮。 33、为规范编程,多个易语言打开同一个源代码时，将会提示切换到打开的程序中，否则请另存为新文件名后再打开，以保护程序。但如果你用新建方式打开程序时，不受此保护。 34、修改了用户程序当支持库不存在时弹出的出错信息。 35、所有带图片组属性的组件选索引时支持直接通过选取图片组的方式输入。在索引项目后多了一个按钮,点击按钮后弹出图片组预选窗口，直接选中图片即可。 36、扩展界面库一中的树型框增加了“右键单击项目”事件。 37、系统颜色配置里面新增了“窗体设计器背景”项。 38、编译时实施了严格的重复名称检查，编译选项中新增“严格的重复名称检查”选项，为了兼容以前的程序，默认为不选中，建议将其选中。 39、支持库列表中增加排序功能，可按拼音顺序排列支持库。具体是支持库面板的鼠标右键菜单中增加“排序”子菜单。 40、核心支持库中的“窗口”数据类型增加了“置父窗口”方法。 41、核心库中的“数值转换”类中新增了“到字节”、“到短整数”、“到整数”、“到长整数”、“到小数”命令。 42、核心库中的“位运算”类中新增了“左移”、“右移”、“合并整数”、“合并短整数”命令。 43、核心库中的“变体型”数据类型新增“取字节集”方法，并且其“赋值”方法支持置入字节集类型数据。 44、核心库中的“载入”命令被改进，当以对话框方式载入不可视窗口时，不再强制显示并等待，而直接返回， 然后可以通过设置该窗口的可视属性为真来显示该对话框。此改进后，可以进行以下操作： 载入 （窗口1, , 真） 窗口1.标题 = "演示" 窗口1.可视 = 真 45、核心库中的“从字节集转换”命令更名为“取字节集数据”，并增加一个参数，以支持从字节集中随意取出部分数据。 46、核心库中的“打印机”对象有所改进，并且增加了四个方法用作在Windows2000/NT/XP下设置自定义纸张类型。 47、“支持库配置”对话框上方加入了查找功能。 48、“支持库配置”对话框下方增加了删除支持库按钮。 49、“系统配置”对话框内“颜色配置”部分增加了“导入”按钮。 50、左侧支持库列表中数据类型部分列入了成员事件并加入了全面的提示。 51、属性表下方的事件组合框内对已有事件子程序的事件进行了标记，并将自有事件和固定事件分开。 52、鼠标指针属性新增“手型”类型。 53、对列表式组件箱进行了排序。 54、窗口设计器中右键单击组件后所弹出的菜单内新增了“查看数据类型定义”菜单项。 55、组件右键菜单中加入“锁定”和“解除锁定”菜单，锁定组件时只能使用键盘的光标键移动或使用SHIFT的组合改变大小。 56、当前系统正在编辑一份易程序时,双击打开新易程序时,会弹出询问对话框,用户可以选择重新启动一份易语言系统打开程序。 57、输入备注时不再有提示框出现。 58、单行编辑框文字垂直居中。 59、恢复了调试变量表。 60、恢复了在行尾回车时自动询问增加未定义的变量、子程序、常量名（仅当“输入新语句后自动检查语法错误”系统设置被选中时有效）。 61、打印机对象改正了默认纸张的设置问题。 62、核心支持库增加“置错误提示管理”命令，用作支持用户自行提示严重错误信息。 63、核心支持库中的“选择夹”组件增加了“是否填充背景”、“背景颜色”两个属性，用作解决“隐藏自身”属性为真时选择夹内 一些子组件的刷新问题。 64、系统的“程序”菜单中新增“重新名称关联”菜单项。 65、加入了源代码加密功能。 66、核心库中“服务器”组件的“取回客户”方法支持在“数据到达”事件中使用。 67、核心库中“媒体播放”类别中增强了对MP3播放的支持。 68、核心库中“系统处理”类别中增加了“多文件对话框 ”命令。 69、编译器所支持语法格式改进，返回值支持直接引用其成员，如“a.方法1 ().a1.方法2 ()”语句格式现在已经可以使用。 70、系统的“工具->系统配置”菜单中新增“目的程序安全”选项夹。 71、系统的“编辑”菜单中新增“到最近修改处”菜单项。 72、改进了各种编程语言对易语言DLL的调用支持。 73、新增扩展界面支持库六、DirectX3D支持库。 74、自定义鼠标指针支持彩色。 75、易模块管理功能被去除，支持新的易模块引入功能，且易模块公开支持项目增多。 76、系统自带易模块中新增3D图形引擎支持易模块。 2、源程序编辑窗口右键菜单中新增“收缩屏蔽”功能，可以用作一次性屏蔽大段代码。 3、系统不再默认载入所有支持库，而必须在支持库配置中指定。 4、源程序的载入速度得到提高。 5、推出了以下新的支持库： 易向导支持库 农历日期支持库 远程服务支持库 扩展界面支持库三 互联网服务支持库 邮件接受支持库 多媒体支持库 表格支持库 超级菜单支持库 保密通讯支持库 办公组件支持库 2、编写DLL时其中的公开子程序可以接受文本数据类型参数，且可以返回文本和字节集型数据。 3、支持源程序代码的收缩和展开（操作方法：选中程序块后单击右键选“收缩”菜单项，在子程序头上可以直接左键单击子程序名左边的减号）。 附，易语言面向对象开发特性简要说明： 1、易语言支持类的构造、析构、继承、虚拟方法、多态、封装特性。 2、对象的构造： 构造顺序为：先构造基类对象，再构造其继承类对象，如果类中具有对象成员，则先于其所处对象构造。 3、对象的析构： 析构顺序为：先析构继承类对象，再析构基类对象，如果类中具有对象成员，则在其所处对象后析构。 4、继承： 任何类均可以指定另外一类作为其基类，继承层数不限。 5、虚拟方法： 在基类中的方法可以被其继承类中的同名方法覆盖，当调用此方法时，系统自动根据所调用的对象 实体去调用对应的方法。 6、多态性： 可以将一个继承类对象赋予到其基类数据类型变量中，此时对此基类对象变量进行操作，将反映出继承类对象的特性。 7、类的封装： A、类的所有成员数据变量只能由该类本身的方法代码所访问，属于私有性质。 B、在继承类中可以以“类名.方法名”的方式指定访问基础类中的方法。 C、只有标记为“公开”的方法才能在类代码外部通过该类的对象实体来访问。 4、“到字节集”、“到文本”命令被增强。 5、“数值到人民币”改名为“数值到金额”。 6、“取系统语言”命令支持linux，并增加日文类别。 7、“取操作系统类别”命令支持linux。 8、所有COM封装对象的“取子对象”方法更改为“取接口”，并增加一参数以取出指定接口。 正式版的新增功能： 1、对微软COM技术的全面支持，包括ActiveX组件、OLE自动机、COM类型库等等，详细说明请见ESDN帮助 2、跨平台的网络通讯支持库 3、跨平台的Mysql数据库支持库,且功能全面加强 4、跨平台的多线程支持库 5、EXCEL2000支持库(直接操作Excel) 6、WORD2000支持库(直接操作Word) 7、PowerPoint2000支持库(直接操作PowerPoint) 8、数据图表支持库(柱形图，饼形图、曲线图) 9、脚本语言支持库(可以运行VB script Jave script等脚本) 10、文本语音支持库(提供对文本转语音输出以及语音识别的支持) 11、易语言支持库在运行时支持动态加载 12、枚举常量的支持(详细说明见ESDN帮助) 13、更新了setup安装程序（即菜单"编译生成安装软件"的功能改进，解决了反安装时删除全部目录的问题，添加额外文件时增加了批量添加，还有更多安装功能的增强!） 14、部分功能的加强(如：树型框可以高速批量加入项目、标准输入命令支持密码输入、启动多线程支持参数等等) 15、其他很多地方改进。 2、增加了Windows动态链接库(DLL)的编写，用易语言能编写出DLL供自己以及其他编程语言(VB,VC,Delphi等)调用。 3、增加了控制台操作的2个命令“标准输出”、“标准输入”， 4、增加了3个命令：“指针到文本”(文本操作)，“指针到字节集”(字节集操作)、“写到内存”(其他)，最佳使用场合在易语言回调子程序和易语言DLL公开子程序中用作对外输出数据。 5、增加了图形图像支持库 - 格式1.0版，支持多种图片格式的转换。 6、增加了XP风格界面库1.1版，支持部分控件的4种风格类型的转换。 7、增加了文件压缩/解压缩支持库1.0版，支持.zip格式的压缩解压，同时用本库压缩的.zip文件也可以被其他压缩软件使用 8、增加了多线程支持库1.1版，供对多线程的支持，并通过实现进入许可证机制以避免多线程冲突。 9、增加了数据库操作支持库1.0版，本支持库用来访问各种类型数据库。 10、增加了MySql支持库1.1版，本支持库实现对MySql的支持。 11、扩展界面支持库二1.1版中增加了“IP编辑框”窗口组件，支持对IP地址的输入和编辑。 12、修改了易模块的接口结构，在支持原有结构的基础上，增加了新的接口创建方式。 13、开发环境增加了即时输入提示。 版的新增功能： 1、增加了扩展界面支持库二，包含超级按钮、高级影像框、分隔条、 超级编辑框等窗口单元，包含图片组处理、文档格式转换等分类命令。 2、增加了端口访问支持库，以支持对计算机端口的直接访问。 3、图片组支持真彩且制作工具性能提升。 4、表格拖动选择闪烁的问题已经解决。 5、系统配置中可以设置不显示程序备注。 6、数据源支持设置基于单元格的只读属性。 3、增加了树型框的事件和方法。 4、改进了打印预览。 5、运行时树型框的“项目”属性可以读出当前项目数据。 6、可以在“程序设置”对话框中设置程序版本号。 7、改正了读取SQL SERVER数据库出现的问题。 8、改正了xp下托盘图标弹出菜单单击桌面不消失的问题。 2、试用限次在各版本之间不再累加。 3、支持数据库加密。系统核心支持库数据库类别中增加了“是否已加密”、 “置数据库密码”、“密码输入框”、“复制密码”命令。“打开”命令 的数据库密码参数已经启用，改进了数据库管理器和易之表以支持加密 数据库； 4、数据操作支持库一中增加了对RSA数字签名和验证的支持（提供了“数字 签名钥匙测试.e”例程），并增加了对RC4加密算法的支持； 1、增加了对OCX组件（即ActiveX组件）的支持。 易语言 3.1 正式版相对 3.0 版的新增功能： 1、支持独立编译，独立编译后的易语言程序可以脱离易语言系统单独运行。 易语言3.0 正式版相对测试五版的新增功能： 1、增加电子注册支持。 易语言3.0 测试五版本相对于测试版三新增功能： 1、“系统处理”命令类别中加入了对配置文件进行操作及取操作系统类别的命令。 2、改进了调试过程中查改容器的功能（移到了工具条上）。 3、完成了安装制作工具的开发，具体请见系统setup目录中的readme.txt文件说明。 只是由于目前编译功能尚未开放，所以暂时不能被使用。 易语言3.0 测试三版本相对于测试版二新增功能： 1、加入了程序调试支持系统。 易语言3.0 Beta版本相对于2.51版本新增加的功能和需要注意点: 一、新增功能： 建立了完全的易程序编译器系统，支持全编译，可以直接将程序编译为CPU指令码 运行，从而突破了长期以来的速度瓶颈。 二、新增特性： 1、子程序指针值为该子程序的内存代码地址，可以直接传递给DLL命令用作回调。 2、只有被使用到的代码和数据才会被编译到可执行文件中。 3、如果需要屏蔽子程序中的某段程序使之不会被编译输出，直接使用类似： “判断循环首（假）”或 “如果真（假）”括住该语句块即可。 4、程序配置中允许设置任

数据结构与算法简述和CS综述整理。本文非基础的教程，本文会列出大量学习和参考网站。老惯例，一个文章是一个集大成（本文借助了语音输入（PC 版 讯飞输入法）由此加速码字，但仍保持简洁的文风）。

数据结构 + 算法 = 程序。数据结构：现实问题的符合计算机存储的建模；算法：解决现实问题的步骤（符合有穷性，确定性，可行性等）。

文末四个附录为 Github 上或其它地方的有极大学习价值的教程或库：

• 附：CS 综合学习类。

• 附：嵌入式 综合学习类。

该部分涉及十几个 Github 仓库，鉴于挨个下载很麻烦，这里我全部下载并整理好了（四部分仓库 + 硬件领域面经集合 1.42 GB 侵删）：

链接： 提取码：XHYN --来自百度网盘超级会员V4的分享

1. C语言三剑客：《C和指针》、《C陷阱与缺陷》和《C专家编程》，经典永流传 →

2. 数据结构与算法（线性表/树/图/哈希 + 排序/搜索/规划等等等 按需学） →

3. 计算机专业科学看的《计算机组成原理》/《计算机体系结构》，《计算机操作系统》/《现代操作系统》/《深入理解计算机系统》，《编译原理》，《深入分析GCC》，网络协议如《计算机网络》、《TCP-IP详解卷一/卷二/卷三》等 →

4. 可选 《CPU自制入门》 →

5. 走向：嵌入式 Linux 方向、FPGA / 芯片设计方向、具体某算法方向等等。

更多学习路线可详细参考 的总结，比较全面了。

没给出链接的 网搜名字即可。

• 该回答列举了一些不错的数据结构与算法方面的书籍。

• 《算法导论》（经典）是计算机学科的算法入门书。

• 《计算机体系结构》（经典），《计算机操作系统》/《现代操作系统》/《深入理解计算机系统》。

• 《编码的奥秘》，相关介绍/推荐 。《编译原理》（经典），《深入分析GCC》。

• 网络协议如《计算机网络》、《TCP-IP详解卷一/卷二/卷三》，。

• 嵌入式应用相关：《GNU Make》，《Debugging with GDB》，《Linux 高级程序开发》，《POSIX 多线程程序设计》，《嵌入式Linux基础教程》，《嵌入式Linxu应用开发完全手册》，《嵌入式Linxu应用程序开发详解》。

• 嵌入式底层相关：内核相关：《深入理解Linux内核》，《Linux内核源代码情景分析》，《Linux内核设计与实现》；驱动相关：《Linux设备驱动程序》，《Linux设备驱动开发详解》，《Linux驱动开发入门与实践》。

相关有趣/耐看书或视频

• 图解系统 小林。图解网络 小林。

• 手绘图解HTTP。30张图解HTTP常见面试题。

• 从沙子讲到CPU，从编辑器讲到编译器，从高阶C语言讲到内存管理，从GNU讲到多任务编程。

时间复杂度表示一个算法内执行语句的数量在最坏的情况下随着循环次数 n 的增加而增长的数量级。一个算法内语句的使用次数（频度）表示为 f(n)，n 为算法内循环语句的循环数，n 的变化直接改变 整个算法的语句使用次数；时间复杂度 O(g(n)) 的定义为，对于一个算法，当且仅当存在正整数 c 和 n0，使得 f(n) ≤ cg(n) 对于所有 n ≥ n0 成立，则该算法的渐进时间复杂度为

程序的执行时间不仅依赖于问题规模，还可能随着数据的状态不同而变化，即其时间复杂度会变化，一般评价算法时候取最坏的情况的时间复杂度。

一个软件项目，数据结构设计的好，后面进行功能实现时候的调用、修改和查询会特别方便，可以达到事半功倍的效果。

• 线性表：顺序（数组）、链式（链表（单链表、双向链表、循环链表（单向、双向），静态链表（借助数组实现）））、特殊（栈（FILO）、队列（FIFO））。

• 树：二叉树、红黑树等。

• 图：无向图、有向图等。

• 按照逻辑关系（元素的连接关系）：

  集合，线性（数组、栈、队列、链表等），树状（一对多），图状（多对多）。

• • 顺序存储：如数组，要提前申请空间（静态分配（编译时进行）或动态分配（malloc & free））。优点：物理位置连续而紧凑，可 随机 / 直接 存取；缺点：会产生内存碎片，增、删改动时前后要跟着变（需要移动大量元素）。

  • 链式存储：如链表，要提前申请空间（动态分配（malloc & free））。优点：链式、离散、节点化，空间可动态分配，改动方便（改节点的指向）；缺点：空间占用大，查找不便（需要遍历整个链表）。

  • 索引存储：“索引-数据” 的结构形式。

• 每个基本数据结构要实现的基本操作：增（插入）、删（删除）、改（更新）、查（检索），判（判空，判满）、排（排序）、复（复位）。

• 更复杂的操作可用以上基本操作实现。

具体概念在 “” 一文的 “时间、空间复杂度” 一节有提到。。。

• 查找：顺序存储结构 O(1)，单链表 O(n)。

• 插入和删除：顺序存储结构 O(n)，单链表 O(1)。

一些基本的简单实现参考/数据结构简单实现/文件夹里面。

以下为树的基本概念（定义、基本操作、性质、存储结构等）、二叉树（定义、基本操作、存储、遍历等）、平衡二叉树、红黑树等。

树是由一个或一个以上的节点（node）组成，存在一个特殊节点称为树根（root），它是n（n>=0）个节点的有限集。n=0时称为空树。n>0时，有限集的元素构成一个具有层次感的数据结构。

• 节点的度：一个节点拥有子树的数目。例如A的度为2，B的度为1，C的度为3。

• 树的高度：也称为树的深度，树中节点的最大层次。

• 有序树：树中节点各子树之间的次序是重要的，不可以随意交换位置。

• 无序树：树种节点各子树之间的次序是不重要的。可以随意交换位置。

• 森林：0或多棵互不相交的树的集合。

引自：《数据结构教程》。

1. 非空树的节点总数等于树中所有节点的度之和加1。

2. 度为 k 的非空树的第 i 层，最多有 k^(i-1) 个节点（i ≥ 1）。

1. 求结点 x 所在树的根节点。或求树 T 的根节点。

2. 求树 T 中结点 x 的双亲结点。

3. 求树 T 中节点 x 的第 i 个孩子节点。

4. 求树 T 中节点 x 右边 的兄弟节点。

5. 把以 S 为根结点的树插入到 树 T 的 节点 x 的第 i 个子节点位置上。

6. 删除树 T 中 节点 x 的第 i 棵树。

7. 对一棵树进行遍历，按照某种次序遍历树所有节点并得到一个由所有节点组成的序列。

采用链式存储方式居多。除了储存节点本身的数据信息之外，还必须做到把树中各个节点之间的连接关系反映在存储结构中。

• 多重链表表示法：分为 定长链接数目 和 不定长链接数目。

引自：《数据结构教程》。

二叉树结构被广泛用来解决计算机领域中的各种实际问题。例如，在排序、检索、数据库管理系统以及人工智能等许多方面，二叉树都提供了强而有效的支持。

每一个节点最多只有两颗子树。在二叉树中严格区分节点的左、右子树，其次序不能随意颠倒。因此二叉树是有序树。

二叉树又可以分为满二叉树和完全二叉树。

• 顺序存储结构：顺序存储结构固有一些缺陷，使得二叉树的插入、删除等操作不方便，而且效率比较低（线性表的固有缺点）。

• 链式存储结构：更适合，更广泛。两种：二叉链表结构 和 三叉链表结构。

  二叉链表结构：链表中每一个链接点由三个域组成分，别为数据域和两个指针域，后者分别给出该节点的左、右节点的存储地址。

  三叉链表结构：相比于二叉链表结构，多增加一个用来指向双亲节点的指针域，这样在查找二叉树中某个节点的双亲节点时候不用遍历整个二叉树。就是空间换时间（如查找的时间等）。

有关二叉树的许多操作几乎都是建立在二叉树的遍历之上。二叉树是一种非线性结构，因此需要寻找一种规律，使得二叉树中的所有节点能够排列在一个线性序列中，这就叫遍历。

若以符号 D、L 和 R 分别表示访问根节点、遍历根结点的左子树 和 遍历根结点的右子树 三个过程，并且限定先左后右的顺序，则通常采用三种遍历方式：DLR、LDR、LRD，分别称之为 前序遍历、中序遍历、后续遍历。还有 按层次 的遍历顺序。

遍历可以用递归的方式（对于很大的树容易栈溢出）。非递归方法，通常利用一个栈结构。

下面举例按照 中序遍历 顺序遍历的程序。

按照层次遍历（或叫 广度优先遍历） 即 若被遍历的二叉树非空，则依次访问二叉树的第1层、第2层......直到最后一层，对每一层的访问按照从左到右的顺序进行。 该方法通常用一个队列实现。下面举例程序。

在二叉树的结点上加上线索的二叉树称为线索二叉树。对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

引自：《数据结构教程》。

二叉排序树用于排序、查找/检索，可以大大提高查找的时间效率（在一般情况下，查询效率比链表结构要高）。二叉排序树又叫二叉查找树。有人说，当需要完成的功能是插入、删除和检索，二叉排序树具有比迄今为止研究过的任何数据结构都有更好的性能。

二叉排序树要么是空，要么具有如下特点：

• 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；

• 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；

• 二叉排序树的左右子树也要求都是二叉排序树；

如下图所示就是一个二叉排序树。

引自：《数据结构教程》。

二叉排序树中插入数据，同样需要按照二叉排序树的原则进行。每次将一个新的元素插入到二叉排序树中，该元素对应的节点都是插在叶节点位置，插入的过程没有移动二叉树中其他节点。一个数据元素序列不一定按照值的大小进行排列，但当对其构造成为一棵二叉排序树以后，对该二叉排序树进行中序遍历得到的序列是一个按值大小排列的序列。

平衡二叉树（AVL树）

平衡二叉树，又称为 AVL 树。实际上就是遵循以下两个特点的二叉树：

• 每棵子树中的左子树和右子树的深度差不能超过 1；

• 二叉树中每棵子树都要求是平衡二叉树；

其实就是在二叉树的基础上，若树中每棵子树都满足其左子树和右子树的深度差都不超过 1，则这棵二叉树就是平衡二叉树。

把二叉树中每个节点的左子树深度与右子树深度之差定义为该节点的平衡因子，因此平衡二叉树中每个节点的平衡因子只能是 1、0 或 -1。

引自：《数据结构教程》。

二叉排序树的形态，事先无法预料，随意性很大，得到的往往是一颗很不 “平衡” 的二叉树，深度差越大，其运算时间也越长，丧失了其优势。为了克服二叉排序树的这个缺陷，需要在插入和删除节点的同时对二叉树的形态结构进行必要的调整，使二叉排序树始终处于一种平衡状态。

理论上已经证明，具有 n 个节点的平衡树的深度在任何情况下都不会比具有相同节点数目的理想平衡数的深度高出 45% 以上。因此再平衡树上进行查找操作虽然比理想平衡树要慢一些，但通常比任意生成的二叉排序树中进行查找要快得多，其时间复杂度的数量级仍为O(Log_2(n))。

红黑树是一种二叉查找树。

红黑树与AVL树的对比

• 如果插入一个节点引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除节点引起树的不平衡时，最坏情况下，AVL需要维护从被删节点到根节点这条路径上所有节点的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度；

• 但是由于红黑树没有AVL树那么高度平衡，所以红黑树的查找性能相比AVL树要差一些，查找上的这一点性能差相比数据的插入和删除时的旋转性能是值得的，这就是为什么很多场合是用的红黑树，而不是AVL树，例如STL中的map和set。因此，RB-Tree在需要大量插入和删除节点的场景下效率更高。自然，由于AVL高度平衡，因此AVL的查找效率更高。

• B树是对二叉查找树的改进，B树大量应用在数据库和文件系统当中。

• 还有哈夫曼树、字典树等等树种。。

引自：《数据结构教程》。

图可以使得元素之间的关系是 多对多。图中任意两个数据元素之间都可能存在连接关系。图作为一种数据结构，可以表达数据元素之间广泛存在着的更为复杂的关系。在众多应用之中，如电子线路分析、工程计划分析、寻找最短路径等等，图是描述这类关系的一个十分自然的模型。有关图论的内容是离散数学的主要内容之一，这里仅仅介绍一些概念和存储方法。

1. 有向图/无向图：若图中每一条边都是没有方向的，则为无向图。如图中每一条边都具有方向，则称为有向图。

2. 通常需要将图中顶点按照一个顺序进行标号，如果某个顶点在一个序列中的位置为 i，那么该顶点为顶点 i。

3. 权/网：与边有关的数据信息被称为权。在具体应用中权值可以有实际意义，比如线路的长度或等级、电路中两个端点之间的电阻电流或电压值等等。每条边上都带权的图称为网络，或 网。问题所属的领域不同，顶点和边的实际意义也就不同。

4. 度：顶点的度是指连接在某顶点 v 的边数，记 TD(v)。对于有向图，某顶点 v 的入度是指以顶点 v 为终点的弧的数目，记 ID(v)，某顶点 v 的出度是指以顶点 v 为起点的弧的数目，记 OD(v)，有 TD(v) = ID(v) + OD(v)。如果用 n 表示图中顶点的数目，用 e 表示边或弧的数目，用 TD(vi) 表示顶点 vi 的度，则有以下关系：2e = 从 i = 1 到 i = n 累加 TD(vi)。从这个关系可知，具有 n 个顶点的无向图最多有 n(n - 1)/2，这样的图称为 完全图，具有 n 个顶点的有向图最多有 n(n - 1) 条边，这样的有向图称为 有向完全图。若一个图接近于完全图则称为稠密图，若边或弧的数目很少的图为稀疏图。

5. 路径/环（回路）/有跟图：在无向图中两个顶点之间的顶点序列可以使得两顶点之间连通一条通路，即路径。这条路径上所包含边的数目被称为该路径的长度。对于有向图，则该路径也是有相的。对于 带权图 路径长度，是指路径上所有边的权值之和。若出发顶点和结束顶点为一个顶点，则该路径为回路或环。在一个有向图中，若存在一个顶点，使得从该顶点出发的路径可以到达图中其他所有顶点，则称该有向图为有根图，该顶点为该有向图的根。

6. 子图：一个图的子集，包括图的一部分顶点和边。

7. 图的连通：对于无向图，若从定点 vi 到顶点 vj（i ≠ j）有路径，则称 vi 到 vj 之间是连通的。如果无向图中任意两个顶点之间都是连通的，则称该无向图为连通图。无向图中的极大连通子图称为该图的连通分量，显然对于一个图其只有一个。若有向图中任意两个顶点之间都是连通的，则称该有向图是 强连通图，有向图 中的 极大 强连通子图 称为该 有向图 的 强连通分量。

8. 生成树：一个 连通图 的 极小连通子图 称为该图的一个 生成树。生成树中不含有回路，在生成树中添加任意一条边必然会产生回路，若在生成树中减少任意一条边则一定会使它成为非连通的。

9. 生成森林：若一个有向图恰好有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树，一个有向图的生成森林由若干棵有向树组成。

1. 邻接矩阵法（不适合稀疏图，因为空间性价比低）。

2. 有向图的十字链表法。略。

从给定图中任意指定的顶点出发，按照某个原则系统的访问图中的其他顶点，每个顶点仅仅被访问一次，得到由该图中顶点组成的一个序列，这个过程称为图的遍历。

图的遍历 通常采用 深度优先搜索 与 广度优先搜索 方式进行。具体看本文下面的 “DFS & BFS（深度/广度优先搜索）”一节。

深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。（引自 ）

广度优先搜索，其遍历原则是从图中指定顶点出发，访问该顶点后再依次访问该顶点的各个未被访问过的邻接点，然后从这些邻接点出发，按照同样的原则依次访问他们的未被访问过的邻接点，以此类推，直到图中所有访问过的顶点的临界点都被访问，若此时图中还存在未被访问过的顶点，则从另一个未被访问过的顶点出发，继续进行上述过程，直到图中所有顶点都被访问。广度优先搜索与深度优先搜索不同，首先访问指定的出发点，然后依次访问该顶点的所有未被访问过的邻接点，再接下来访问邻接点的未被访问过的邻接点，以此类推，实现这个过程需要设置一个队列结构。

图的存储方式、遍历的出发点、遍历的方式等的不同均会使遍历后的序列各不相同。

最小生成树、最短路径、AOV网与拓扑结构排序、AOE网与关键路径等。

咳咳嗯...算法嘛，咱也不是 CS 科班学生，咱就说，算法是对已经建模后的问题的解决的具体途径和方法，是学习 对于编程来讲的 一些 已经成熟/成型的 完成问题的计算的 套路和思想。

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。一个串（流口水）中任意个连续的字符组成的子序列为该串的子串。串的编码方式即字符编码如 ASCII编码、Unicode编码等。

串中的元素都是字符，串的操作主要与 字符串的操作 而非 单个元素 有关，其多为 查找子串位置、得到指定位置子串、替换子串等操作，如下：

显而易见，标准库如 string.h 给出了串的基本操作 API，关于 C 标准库的详细使用可参考 “” 一文的 “7 C 标准库的使用” 一节。

串的匹配算法（也可叫串的模式匹配）

串的模式匹配算法-BF算法（或叫暴力算法）

主串 S 从 i = 0 位置开始与 模式串 P 从 j = 0 位置开始一个字符一个字符的匹配是否一样，如果相同则 i 和 j 均加一然后再判断是否匹配，若不同则 i 回到 这次匹配开始的位置同时 j 回到首位，继续挨个匹配。一图说明：

串的快速模式匹配算法-KMP算法

主要思想就是相比于 BF 算法，为了加速匹配，找一些规律，当匹配失效的时候 j 不用每次回到 P 的 开头位置，而是根据（注意，不了解的推荐先看下面给出的教程文章，这里是明白后的总结） 模式串的 各个字串的 各个前缀、后缀子串的 最大公共元素长度 来构造 next 数组，j 每次移动的位数根据 next 来调整。

图的遍历 通常采用 深优先搜索（DFS） 与 广度优先搜索（BFS） 方式进行。“如果把树看做一种特殊的图的话，DFS 就是前序遍历”。

有的人理解为用“动态规划”的思想（写出优化目标和状态转移方程（或者叫递归关系式））去理解和建模问题使得找出问题的优化解可以不用遍历所有可能解（剪枝，或去除不可能为最优解的计算从而节省时间，或者去除重叠的子问题）；常用一种实现方法为用缓存存储数据来减少重复计算（把穷举的计算过程展开为一棵树，然后找出其中重复计算的部分，用缓存来保留一份之前要重复计算的结果，来减少重复计算），还有其它许多技巧和方法。

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

可使用分治法求解的一些经典问题：

分治算法的一个核心在于子问题的规模大小是否接近，如果接近则算法效率较高。

分治算法和动态规划都是解决子问题，然后对解进行合并；但是分治算法是寻找远小于原问题的子问题（因为对于计算机来说计算小数据的问题还是很快的），同时分治算法的效率并不一定好，而动态规划的效率取决于子问题的个数的多少，子问题的个数远小于子问题的总数的情况下（也就是重复子问题多），算法才会很高效。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

1. 建立数学模型来描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每一子问题求解，得到子问题的局部最优解。

4. 把子问题的解局部最优解合成原来解问题的一个解。

1. 从问题的某一初始解出发；

2. while 能朝给定总目标前进一步 do；

3. 求出可行解的一个解元素；

4. 由所有解元素组合成问题的一个可行解。

1. 不能保证求得的最后解是最佳的；

2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

引自： 来说明贪心算法的缺陷：　

先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。

依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。

这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让“还需要凑出的部分”变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。

但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：

15=1×11+4×1 （贪心策略使用了5张钞票）

15=3×5 （正确的策略，只用3张钞票）

为什么会这样呢？贪心策略错在了哪里？

刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。

在这里我们发现，贪心是一种只考虑眼前情况的策略。

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

• 回溯法的求解目标是找出解空间中满足约束条件的所有解，想必之下，分支限界法的求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

• 另外还有一个非常大的不同点就是，回溯法以深度优先的方式搜索解空间，而分支界限法则以广度优先的方式或以最小耗费优先的方式搜索解空间。

• 《常用算法程序集》 第五版(C C++)和第六版(C++) 徐士良等著。

• -欢迎来到GitHub最大的开源算法库，介绍 。

• CS 相关的学习路线大总结：。

• 杂且全：CS-Notes 算法和刷题、操作系统、网络、数据库、系统设计等 。网站版 。

• 杂且全：easy-cs 网络、算法、系统设计、Java、MySQL、分布式、聊人生等 。

• 算法学习：hello-algorithm 基础、刷题、面经和汇总 。网站版 。

附：嵌入式 综合学习类

• CS-Notes 算法和刷题、操作系统、网络、数据库、系统设计等 。网站版 。

四个附录，该部分涉及十几个 Github 仓库，鉴于挨个下载很麻烦，这里我全部下载并整理好了（四部分仓库 + 硬件领域面经集合 1.42 GB 侵删）：

链接： 提取码：XHYN --来自百度网盘超级会员V4的分享