数据结构笔记总结学习资料-DATAABSTRACT资源-CSDN文库

数据结构

课程资源

需积分: 5 94 浏览量 2024-10-02 18:33:35 上传评论收藏 598KB PDF 举报

资源推荐

资源详情

资源评论

抽象与具体思维

递归模型

一个建立在对象T0上的复杂事务F0若能分解成分别建立在T0的有限相似对象T1、T2……Tc上的

相对简单的相似子事务F1、F2……Fc，则可根据T0与相似对象之间的关联运用自我调用的递归函数

F0来解决。以下所说的递归函数指的就是自我调用的递归函数。

当准备对T0进行建立解决方案的递归函数F0时，可先从与F0相似的最简单的再也不能分解的事

务以及稍复杂一点点的相似事务入手（简单就易入手，稍复杂以能足够体现递归规律），F0的构建

过程是一个由模糊到清晰的过程，首先无论如何F0必定会发展成一个多叉树，一定可用树描述函数

F0的自我嵌套图，也可用树来描述T0与子对象之间的关系。

事务或递归函数F0在主函数体也就是最外层函数体里面若可能有c或目前不确定次(如循环)自

我调用，那么家族F0可发展成c叉或不定叉树。将F0主函数体中第n次自我调用称为家族F0的n号遗

传递归器，遗传递归器是整个家族的血液，也存在于每个子孙中。将家族F0的成员Fx传入的实参数

中的(被研究对象T0的子孙)Tx称作影响其生育的遗传因子。将 F0主函数体中的用来约束无限递归以

及执行的某操作统称为调制规则，调制规则是整个家族的家规和使命。家族F0中的成员Ff的调制规

则决定每个遗传递归器的开启和关闭，也就是能决定要不要生任意号如与n号遗传递归器相对应的

第n个孩子。不生第n个孩子就是打掉第n个孩子即流产，属非正常消亡，因此不考虑流产掉的孩子

，下面所说的消亡指的就是正常消亡，第n个孩子与第n个生下的孩子是不一样的概念。家族F0的家

族树中不包含流产的子孙。

树F0按层次由上到下由左到右将结点编号为F0,F1,F2,F3,……Ft，将其对应的树T0的结点编号

为T0,T1,T2,T3,……Tt。家族F0中同层次同亲父的子孙集称为家兵，其亲父也可称家，家族。家包

事务 F0

子孙事务 F1

子孙事务 F2

子孙… …

含家父和家兵，家兵是针对同个主函数体环境而言的，家族Fx是针对整个事务Fx。为了方便研究将

F0中每个家兵和家父对应的T0中的结点集也干脆分别称着家兵和家父。

家族F0的发展过程

事务F0执行的过程就是家族F0的成员F0,F1,F2,F3,……Ft 依个生成和依个消亡的非并发过程

，事务Fx消亡就代表事务Fx执行完毕，或家族Fx的家族使命完成。家族F0的成员的消亡次序即为对

树F0进行后序遍历的次序，也是家族F0的成员的完成断后处理的次序，该次序F0成员对应T0中的成

员的次序即为事务F0放弃对T0成员对象研究的次序。家族F0的成员的生成次序(对树F0进行先序遍

历的次序)也就是树T0成员结点开始被研究的顺序，也是家族F0的成员的完成1号遗传递归器是否启

用的判断的次序。家族F0的成员的完成2号遗传递归器是否启用的判断的次序即为对树F0进行中序

遍历的次序。

根F0的首个出生子女为Fa1，F0便暂不制订生小孩计划，而是Fa1去生它们的首个出生子女Fa2

,这里说明首个出生子女不一定是1号遗传递归器复制出来的后代。Fa1暂停生育，Fa2接着去生它们

的首个出生子女Fa3,……依照一个潜规则即没有后代才有生育权，这样F0的家族成员就一个接着一

个出生了，一直到出现第一个独生子女Fam的首个独生子女Fan（Fan当然有生育权，但因调制规则

约束一个都不能生，即断后），那么执行子事务Fan，执行完毕Fan立即消亡，并将消亡的信息（可

无信息）传给家父，Fan的家族使命也就完成。Fan就是家族F0成员的消亡次序中的第一位。Fam因

后代Fan消亡而没有后代，没有后代就获得生育权，Fam根据调制规则来决定要不要接着生，若能生

目前就不会消亡，Fam若不能再生即断后也以同样的方式来消亡（若有生育权或没有在世后代的家

族成员，但不能再生称为断后）。家族F0的发展是一个要么出生成员和要么消亡成员的单个事件的

连续过程，当所有成员全部消亡那么事务F0执行完毕。每个弟兄的出生都是在它的哥哥消亡之后，

也就是只有消亡才会生成兄弟，每个还未消亡的成员在自家中都是独苗即不能见它的兄弟，要见只

能见它的孩子。F0树描述的是家族F0的家族成员（当然指的是出生过的）之间辈份上下关系即家谱

图。

树F0与T0之间结构关系

树F0按层次由上到下由左到右将结点编号为F0,F1,F2,F3,……Ft，将其对应的树T0的结点编号为T

0,T1,T2,T3,……Tt。一般来若T0的家族成员是为F0建造递归函数的需要而分解的那么则有结点F0

,F1,F2,F3,……Ft之间辈份关系结构与T0,T1,T2,T3,……Tt之间辈份关系结构完全相同。若T0的家

族成员及关系结构已存在,那么F0,F1,F2,F3,……Ft之间辈份关系结构与T0,T1,T2,T3,……Tt之间

辈份关系结构可能不同。

当家族T0有自已原有的关系和结构时，并且F0,F1,F2,F3,……Ft之间辈份关系结构与T0,T1,

T2,T3,……Tt之间辈份关系结构不同，将家族T0中成员原有的关系封印，用 F0中家父与家兵的扭曲

的辈份关系，代替原有的辈份关系，这样就有F0,F1,F2,F3,……Ft之间辈份关系结构与T0,T1,T2,

T3,……Tt之间辈份关系结构完全相同。那么根据隐藏的扭曲的关系结构图就能够知道T0中家族成

员被家族F0调用的次序（干脆叫生成次序）和放弃（干脆叫消亡次序）的次序，也很清楚每个家兵

处在哪个主调函数中。

消亡结果信息用途

消亡结果信息即返回值。树F0每个结点消亡若有消亡结果信息并将消亡结果信息传送给亲父

，亲父直接向上传递或处理或暂保存消亡信息以作为生成将来自已消亡时消亡结果信息的资料（比

如Fna消亡信息为统计Fna家族成员的个数）。不传给亲父的传消亡结果信息是无意义的，不如干脆

不要生成这条消亡结果信息。如事务Fan执行完毕，并有消亡结果信息，而且事务Fan已成功完成F

0的家族使命，Fan将消亡结果信息也就成功消息上传家父，家父只需向上一级传达成功消息后并消

亡，上级也依照这样的方式依次传递成功消息并消亡，最终F0得到成功消息便正式宣布家族F0使命

告成。

调制规则中全局变量

遗传递归器组前对全局变量v的操作在家族F0每个成员生成后生子前完成，遗传递归器组间对

全局变量v的操作在成员生对应子女并等待该子女消亡后准备生下一个子女前完成，遗传递归器组

后对全局变量v的操作在成员断后并消亡前完成。在分析F0调制规则时应从第一个消亡的成员开始

。

二叉树定义

完全二叉树：若设二叉树的高度为h，则共有h+1层。除第h层外，其它各层(0h-1)的结点数都

达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。

二叉树性质

1，若二叉树的层次从0开始, 则在二叉树的第i层最多有2

个结点。

2，高度为k的二叉树最多有 2

k+1

-1个结点。

3，对任何一棵二叉树, 如果其叶结点个数为 n

, 度为2的非叶结点个数为 n

, 则有n

==n

＋1

。证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n ==n

；e==2*n

==n–1；因此，有 2*n

==n

–1；n

==n

+1。

4，具有n个结点的完全二叉树的高度为log

(n+1)-1或log

n。

5，具有n个结点的完全二叉树从上至下从左至右编号为0, 1, 2, …,n-1。则有如下：

若i == 0, 则 i 无双亲，若i > 0, 则 i 的双亲为(i -1)/2。

若2*i+1 < n, 则 i 的左子女为2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2。

若 i 为偶数, 且i != 0, 则其左兄弟为i-1，若 i 为奇数, 且i != n-1, 则其右兄弟为i

+1。

i 所在层次为log

(i+1)。

6，记滿二叉树第i层(从0层开始)结点个数为N

，0至i层结点总数为C

，则有N

为二进制数第i

位(从0开始)所表示的值，N

i+1

==2*N

，C

==N

i+1

-1==2*N

-1，父结点序号为其子结点序号一半左右。

霍夫曼树

树的路径长度：各叶结点到根结点的路径长度之和。

树的带权路径长度：树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。

霍夫曼树：带权路径长度达到最小的扩充二叉树即为霍夫曼树(在霍夫曼树中，权值大的结点

离根最近,主要用途是实现数据压缩,霍夫曼编码是一种无前缀编码。解码时不会混淆)。

霍夫曼算法

(1) 由给定的n个权值{w

, w

, …, w

n-1

}，构造具有n棵扩充二叉树的森林F = {T

, T

, …, T

n-1

}，其中每一棵扩充二叉树T

只有一个带有权值w

的根结点，其左、右子树均为空。

(2) 重复以下步骤, 直到F中仅剩下一棵树为止：

剩余12页未读，继续阅读

评论收藏

内容反馈

梵心白莲

粉丝: 473
资源: 984

数据结构笔记总结学习资料-DATA ABSTRACT

最新资源

数据结构笔记总结学习资料-DATA ABSTRACT

数据结构笔记精华.docx

C++数据结构与算法学习笔记

数据结构 严蔚敏版 学习笔记 第一章____绪论.pdf

数据结构与算法基础.pdf

2010-1011学习笔记归纳

学习笔记java _day02

pythonlist是数组还是链表实现的-数组和链表结构（python）-1 数组和链表.pdf

SNMP的学习笔记（doc文档）

ASN.1学习笔记1

JAVA学习笔记必看经典四.pdf

C#总复习笔记.docx

泰牛程序员韩顺平2017php视频教程笔记

整理后java开发全套达内学习笔记（含练习）

c++笔记_LF.pdf

RoomDatabase:Android体系结构组件-房间持久性库示例

Softuni:西南软件学院解决方案

相关实用应用程序（Windows可用）

李飞飞自传 我看见的世界 The World I see

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

交易系统‘盲评’技术方案详解(百度文库转载)

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

Java客户管理CRM源码带手机端和小程序，1.前端：Vue 2.后端：Springboot 3.数据库：MySQL 小程序是用

Maxwell电磁有限元仿真 环形halbach磁体阵列仿真，构建匀强匀梯度静磁场

《中国智能网联汽车技术规程（C-ICAP）》（2024版）管理规则

咖啡馆管理系统 SSM毕业设计 源码+数据库+论文（JAVA+SpringBoot+Vue.JS）.zip

最新资源

数据结构严蔚敏版学习笔记第一章____绪论.pdf

李飞飞自传我看见的世界 The World I see

Maxwell电磁有限元仿真环形halbach磁体阵列仿真，构建匀强匀梯度静磁场

咖啡馆管理系统 SSM毕业设计源码+数据库+论文（JAVA+SpringBoot+Vue.JS）.zip