树

树的抽象数据类型：

 ADT  树（tree）
    树是由一个根结点和若干课子树构成。树中结点具有相同数据类型及层次关系。
Operation
    root：返回根结点。
    nodes：树的结点数
    depth：树的深度
    ...
EndADT

树的存储结构：

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

双亲表示法

在每个结点中，拥有指向双亲结点的指针（可以扩展子结点或者兄弟结点）。

孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根结点，叫多重链表表示法；把每个结点排列起来，以单链表做存储结构，叫孩子表示法。

孩子兄弟表示法

一个结点设置两个指针，分别指向该结点的第一个子结点和该结点的右兄弟。

树

树的其他相关概念：

• 结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。
• 双亲在同一层的结点互称为堂兄弟。
• 树中结点的最大层次称为书的深度（Depth）或高度。
• 如果左右子树是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
• 森林（Forest）是m（m >= 0）课互不相交的树的集合。

线性结构 VS 树结构：

线性结构：

• 第一个数据元素：无前驱
• 最后一个数据元素：无后续
• 中间元素：一个前驱，一个后续

树结构：

• 根结点：无双亲，唯一
• 叶结点：无孩子，可以多个
• 中间结点：一个双亲，多个孩子

树

树：n（n>=0）个结点的有限集。

特点：

• n=0时，称为空树。
• 在任意一颗非空树中：
  （1）有且仅有一个根结点
  （2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。

结点分类：

• 结点拥有的子树数称为结点的度（Degree）。
• 度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。
• 除根节点之外，分支结点也称为内部结点。
• 树的度是树内结点的度的最大值。

串

串：是由零个或多个字符组成的有限序列，又叫字符串。

字符串在开发的时候很常用，以Objective-C为例，有可变字符串和不可变字符串，两者的实现数据结构应该有点区别；一个是链式存储结构，一个是顺序存储结构。

字符串的抽象数据类型：
ADT 串（String）
Data
串中元素仅由一个字符组成，相邻元素具有前驱和后续关系。
Operation
StringEmpty(S)：若串S为空，返回true，否则返回false。
…
EndADT

按存储结构分类：

• 顺序存储结构的字符串
• 链式存储结构的字符串

字符串的模式匹配

朴素的模式匹配算法：核心思想，需要匹配的字符串和主串从下标0开始匹配，一旦子串不匹配，则子串又从下标0开始匹配，主串则挪到下标1，不断的循环这个过程，直到主串或者字串当前的下标超过字符串的长度或者匹配成功返回。

栈与队列

栈：限定在表尾进行插入和删除的线性表。
栈是一种LIFO(Last In First Out)的线性表，也就是数据元素遵循后进先出的原则。

栈的抽象数据类型：
ADT 栈(Stack)
Data
具有线性表一样的性质。
Operation
top：获取栈顶元素
count：栈的长度
isEmpty：栈内元素是否为空
push(data)：元素进栈
pop()：元素出栈
removeAll()：清空栈内元素
EndADT

按栈的存储结构分类：

• 栈的顺序存储结构
  单栈
  共享栈
• 栈的链式存储结构

共享栈：

两个顺序栈共享存储空间，栈1的栈顶在下标0处，栈2的栈顶在下标n-1处。

线性表

总结：

（1）若线性表需要频繁查找，很少进行插入和删除操作时，使用顺序存储结构；反之，使用链式存储结构。
（2）如果提前知道线性表需要的存储空间，可以使用顺序结构；如果不知道线性表中的数据元素变化有多大，即不确定需要多大的存储空间，则使用链式存储结构。

链式线性表的基本分类：

单向链表
静态链表 -> 使用顺序结构实现链式线性表
双向链表 -> 每个节点除了数据元素，还包含一个指向上一个节点的指针和一个指向下一个节点的指针
循环链表 -> 线性表的尾部指向头节点，形成一个闭环

线性表

顺序线性表

顺序线性表：使用一段连续的地址存储单元放置线性表的数据元素。
举个例子：数组。

顺序线性表的优缺点：
优点：

• 可以快速获取下标的数据元素，时间复杂度为O(1)
• 逻辑关系是一对一的关系，连续存储单元足以储存，不需要增加额外的存储空间

缺点：

• 插入和删除操作需要移动大量的元素，时间复杂度为O(n)
• 线性表的存储空间大小难以确定，并且不好扩展
• 造成存储空间碎片

链式线性表

链式线性表：线性表的数据元素可以存储在随意的存储单元，每一个节点不仅仅包括数据元素还有一个指向下一个节点的指针（基本的单链表）。

链式（单链表）和顺序线性表优缺点对比：
存储分配方式：

• 顺序 -> 一段地址连续的存储空间
• 链式 -> 任意地址存储空间

时间性能：

• 查找
  顺序 -> O(1)
  链式 -> O(n)
• 插入和删除
  顺序 -> O(n)
  链式 -> 寻找相应的节点，时间复杂度为O(n)，然后，插入和删除为O(1)

空间性能：

• 顺序 -> 需要提前分配存储空间，分配大了，浪费空间，分配小了，容易发生上溢
• 链式 -> 不需要提前分配空间，只要有存储空间分配就行，数据元素个数只受可分配存储空间大小的限制

线性表

线性表：零个或者多个数据元素的有限序列。

性质：

• 数据元素可以为空
• 数据元素有
• 数据元素之间的逻辑结构为线性结构，也就是一对一的关系
• 数据元素类型相同

举个例子：

举个例子：
白羊 -> 金牛 -> 双子 -> 巨蟹 -> 狮子 -> 处女 -> 天秤 -> 射手 -> 摩羯 -> 水平 -> 双鱼

线性表的抽象数据类型：
ADT 线性表（List）
Data
      线性表的数据对象集合为{a1, a2, ......, an}，每一个元素的类型都是DataType。其中，除第一个元素a1外，每一个元素有且仅有一个直接前驱元素，除了最后一个元素an外，每一个元素有且仅有一个直接后续元素。数据元素之间的关系是一对一的关系。
Operation
       count：线性表元素个数。
       first：头指针。
       last：尾指针。
       isEmpty()：若线性表为空，返回true，否则返回false。
       remove()：将线性表清空
       node(i)：将线性表中的第i个位置的元素返回。
       insert(data,i)：在线性表中的第i个位置插入新数据data。
EndADT

2019年后端新技术5

CakePHP

cakephpCakePHP是一个用PHP编写的开源web开发框架，从一开始就在市场上非常流行。它基于模型-控制器-视图和关联数据映射的概念。通过使用CakePHP, processionals可以轻松地以结构化和快速的方式开发web应用程序。使用CakePHP的最大优势之一是它提供了详细的文档和实用指南，以及非常容易编写代码的框架。

因此，开发人员可以使用这个框架轻松地创建web应用程序。如果您选择这个框架进行开发，那么通过编写相对较少的代码，您将能够实现更多的功能。您甚至可以通过这个框架重用旧项目的代码，从而使CakePHP web应用程序开发速度更快。

2019年后端新技术4

Symfony

symfony是一个PHP框架，非常适合大型或复杂的企业级项目。这是一个非常稳定的框架。Symfony 3.1(当前版本)帮助全栈开发人员创建可伸缩的网站，以灵活地更改业务需求。

Symfony可以使用一些最大的开源平台，如PHPBB、Piwik和Drupal。Symfony由一组PHP组件、一个应用程序框架、一个社区和一种哲学组成，所有这些组件协同工作，帮助实现web上的一个共同目标。这些原因使得Symfony成为web开发的高级框架。