再读数据结构

再次读《大话数据结构》这本书，回过头再跟着书系统的走一遍，记录巩固下基础。

1. 数据结构绪论

数据结构是相互之间存在一种或多种特定关系的数据元素集合。

1.1 基本概念与术语

• 数据： 描述客观事物的符号，是计算机中可以操作的对象。包括数值、字符、声音、图像、视频等等。
• 数据元素：组成数据的、有一定意义的基本单位。如人类中，数据元素是人，畜类中 牛、马、羊都是数据元素。
• 数据项：一个数据元素可以由若干个数据项组成。比如人这样数据元素，可以有眼、鼻、嘴、手等等这些数据项。数据项是数据不可分割的最小单位。在数据结构中，我们把数据项定义为最小单位，有助于更好的解决问题。
• 数据对象：是性质相同的数据元素的集合，是数据的子集。
• 数据结构：结构，简单的理解就是关系，即数据元素相互间关系形成的集合。

1.2 逻辑结构与物理结构

物理结构是面向计算机的，逻辑机构是面向问题的。 其基本目标就是将数据及其逻辑关系存储到计算机的内存中。

1.2.1 物理结构

数据在计算机内的存储形式，也称之为存储结构。

• 顺序存储 : 数据元素存放在地址连续的储存单元中。
  

• 链式存储: 把数据元素存放在任意的存储单元里。数据元素的存储关系不能反映其逻辑关系，需要指针存放数据元素的地址。
  

1.2.2 逻辑结构

数据对象中数据元素之间的关系，逻辑结构分为以下四种：

• 集合结构：集合结构中的数据元素同属一个集合，他们之间没有任何关系。
  

• 线性结构: 线性结构中的数据元素之间是一对一的关系。
  

• 树形结构: 树形结构中的数据元素是一对多的关系。
  

• 图形结构: 图形结构中的数据元素是多对多的关系。
  

另外，我们用示意图表示数据的逻辑结构时，要注意两点：

• 每个数据元素看做一个节点，用圆圈表示
• 元素间的逻辑关系用节点之间的连线表示，如果这个关系是有方向的，那么用带箭头连线表示

1.3 抽象数据类型

1.3.1 数据类型

数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

我的理解中，数据类型分一下：

• 计算机只认0、1数值类型
• 编程语言既要面向计算机、又要面向开发人员，则基于0、1包装了便于开发使用的类型：整形、长整形、字符型、字符串等等
• 开发人员基于开发语言为了满足业务需要，可能需要包装更多的数据类型

1.3.2 抽象数据类型

对已有的数据类型进行抽象，就有了抽象数据类型。
抽象数据类型（Abstract Data Type, ADT）: 是指一个数学模型及定义在该模型上的一组操作，后面会用以下格式来表示抽象数据类型：

ADT 抽象数据类型名称
DATA
    数据元素之间逻辑关系的定义
Operation
    操作1
        初始条件
        操作结果描述
    操作2
        ...
    操作n
        ...
endADT

2. 算法

2.1 算法的定义

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

2.2 算法的特性

五个基本特性：输入、输出、有穷性、确定性和可行性

2.3 算法效率的度量方法

2.3.1 事后统计方法

所谓“是骡子是马，拉出来溜溜”。比较容易想到的方法就是，通过对算法的数据测试，利用计算机的计时功能，来度量不同算法效率的高低，平常见到的benchmark就应该属于此类。

2.3.2 事前统计方法

为了对算法的评判更加科学，计算机前辈们研究出一种叫做事前分析估算的方法。事前分析估算方法：在计算机程序编制之前，依据统计方法对算法进行估算
如以下有两种方法实现的指定范围内的求和实现：
第一种算法：

int i, sum = 0, n = 100;        /* 执行 1 次 */
for (i = 1; i <= n; i++) {      /* 执行 n+1 次 */
    sum = sum + i;              /* 执行 n 次 */
}
printf("%d", sum);              /* 执行 1 次*/

第二种算法：

int sum = 0, n = 100;           /* 执行 1 次*/
sum = (1 + n) * n/2;            /* 执行 1 次*/
printf("%d", sum);              /* 执行 1 次*/

显然第一种算法执行了 2n + 3次，第二种算法是3次; 事实上两个算法的首、尾语句都是一样的，我们把循环看作一个整体，那么两个算法其实就是n次与1次的差距。算法好坏显而易见。

2.4 函数的渐进增长

随着n的增加，算法A比算法B越来越好(执行的次数比B少)。于是我们可以得出结论，算法A总体上要算法B。 此时我们给出这样的定义，输入规模n，在没有限制的情况下，只要超过一个数值N，这个函数总是大于另一个函数，我们称函数是渐进增长的。
从中可以发现，随着n的增大，后面的+3、+1其实不影响最终算法变化，所以，我们可以忽略这些加法常数。
我们来看第二个例子，算法C是4n + 8，算法D是2n² + 1:

对比可以看出：最高次项相乘的常数并不重要

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项(最高阶项)

2.5 算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的数量。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。
用大写的O()来体现算法时间复杂度的记法，称之为大O记法。比如O(n)、O(1)、O(n²)我们取的非官方名称分别为：线性阶、常数阶、平方阶。

2.6 推导大O阶方法

推导大O阶：

1. 用常数 1 取代运行时间中所有的加法常数
2. 在修改后的运行次数函数中，只保留最高阶
3. 如果最高阶存在且不为1，则去除与这个项相乘的常数

2.7 常见的时间复杂度

3 线性表

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

• 序列，即元素间有顺序，若存在多个元素，则第一个元素无前驱，最后一个无后继，其他每个元素有且只有一个前驱和后继
• 有限

3.1 线性表的抽象数据类型

ADT 线性表(List)
Data
    线性表的数据对象集合为{a₁,a₂...an}，每个元素的类型均为DataType。其中第一个元素除外，每一个元素有且只有一个直接前驱元素；最后一个元素除外，每一个元素有且只有一个直接后继元素。数据之间的关系是一对一。
Operation
    InitList(*L): 初始化操作，建立一个空的线性表 L。
    ListEmpty(L): 若线性表为空，返回true，否则返回false。
    ClearList(*L): 将线性表清空。
    GetElem(L, i, *e): 将线性表L中的第i个元素返回给e。
    LocateElem(L, e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中的序号表示成功；否则，返回0表示失败。
    ListInsert(L*, i, e): 在线性表L中的第i个位置插入新元素e。
    ListDelete(L*, i, *e): 删除线性表L中第i个位置的元素，并用e返回其值。
    ListLength(L): 返回线性表L的元素个数。
endADT

对于实际问题中涉及的更复杂的操作，完全可以基于以上的基本操作的组合来实现。

3.2 线性表的顺序存储结构

下面看一下线性表的两种物理存储结构的第一种，顺序存储结构：用一段连续的存储单元依次存储线性表的数据元素。
顺序存储示意图：

在内存中申请一段连续的地址，用来存储元素，那么这段地址长度意味着这个线性表的长度，实际使用个数代表元素实际长度。

3.2.1 顺序结构的插入与删除

排队插入示意图：

插入算法思路：

• 检查插入位置
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量(java ArrayList Arrays.copy 新开辟空间)
• 从最后元素向前遍历至第i个位置，分别将他们向后移动一位 ——(插入位置的后面的元素都需要站起来往后挪位置)
• 新元素插入位置i处
• 表长加1

删除示意图：

删除算法思路：

• 检查删除位置
• 去除删除元素
• 从删除元素位置开始遍历到最后一个元素，分别将他们向前移动一个位置
• 表长减1

优点：

• 无需为表达元素间的逻辑关系而增加存储空间
• 可以快速地取表中任一位置的元素

缺点:

• 插入和删除操作需要移动大量元素
• 确定存储空间大小的问题(多了浪费，少了不够用，再申请影响性能)

3.4 线性表的链式存储结构

线性表顺序结构存储最大的问题就是插入、删除时，其他位置的元素需要挪位置，链式存储结构的线性表能够解决此问题。链式存储结构不考虑相邻位置，那有空位就到哪里，只是让每个元素知道它的下一个元素的位置在哪里。

• 节点（Node）分为两部分，数据域与指针域，数据域存储元素数据信息，指针域存储下一个节点地址。
  单链表中，用C语言描述如下：

  typedef struct Node {
      ElemType data;
      struct Node *next;
  } Node;
  typedef struct Node *LinkList; /*定义LinkList*/

3.4.1 单链表的读取

在顺序存储结构的线性表中，我们根据元素位置取元素是非常容易的。但在单链表中，没有办法一开始就知道，必须得从头开始找。
获取链表第i个数据的算法思路：

• 声明一个节点p指向链表第一个节点，初始化j从1开始；
• 当 j<i 时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1；
• 若到链表末尾p为空，则说明第i个元素不存在
• 否则查找成功，返回节点p的数据

单链表中没有定义表长，所以事先不知道要循环多少次，其核心思想就是工作指针后移

3.4.2 单链表的插入与删除

插入示意图：

我们可以看出来，新元素的插入，主要操作：新元素指针域指向后一个元素，更新前一个元素的指针域指向新元素。

删除示意图：

同样可以看出来，元素的删除，主要操作：被删除元素的前一个元素更新指针域为被删除元素的指针域地址、销毁(返回)被删除元素

3.5 静态链表

用数组描述的链表叫做静态链表 ，数组元素由两个数据域组成：

• data 存放数据元素
• cur 游标，相当于单链表中的next指针，存放该元素的后继元素在数组中的下表

3.6 循环链表

将终端节点的指针指向头结点，是整个单链表形成一个环，这种头尾相连的单链表称为单循环链表。

3.7 双向链表

在单链表的节点中增加一个指针，将其指向前驱节点

3.8 线性表总结

4 栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表

4.1 栈

手枪的弹匣就像是栈，放子弹进弹匣就是入栈，开枪打出子弹则是出栈。

4.1.1 栈的抽象数据类型

ADT 栈(stack)
DATA
    同线性表。元素具有相同的类型，相邻元素有前驱、后继关系。
Operation
    InitStack(*s): 初始化操作，建立一个空栈S。
    DestoryStack(*S): 若栈存在，则销毁它。
    ClearStack(*S): 将栈清空。
    StackEmpty(*S): 若栈为空，返回true，否则返回false。
    GetTop(S, *e): 若栈存在且非空，用e返回S的栈顶元素。
    Push(*S, e): 若栈存在，则插入新元素e到S中，并成为栈顶元素。
    Pop(*S, *e): 删除栈S中的栈顶元素，并用e返回其值。
    StackLength(S): 返回栈S中的元素个数。
endADT

由于栈本身是一个线性表，所以之前提到过的线性表的顺序存储和链式存储，对于栈也同样适用。

4.1.2 栈的顺序存储结构

看下栈的结构定义：

typedef int SElementType; /* SElementType 类型根据实际情况而定，这里假设为int*/
typedef struct{
    SElementType data[MAXSIZE];
    int top;    /* 用于记录栈顶 */
}SqStack;

栈就像”阉割”版的线性表，强调的是栈顶的操作，高级语言中一般会提供push、pop、peek这样的方法。
这里用java简单的实现了顺序存储的栈MyStack

4.1.3 栈的链式存储结构

栈的链式存储结构，简称链栈。
栈的操作都是在栈顶上的，那链式存储的栈将栈顶放到链表的头部还是尾部呢？ 链表本身有头指针，栈也需要栈顶指针，所以合二为一，将栈顶放在单链表的头部。
这里就不过多介绍链式存储的栈了，其对比顺序存储栈的特点体现在链式存储上。

4.2 队列

队列就像排队买票，强调的是新来的人排在队尾，买票的人在队头，强调先进先出。

4.2.1 队列的抽象数据类型

ADT 队列(Queue)
DATA
    同线性表。元素具有相同的类型，相邻元素具有前驱、后继关系。
Operation
    InitQueue(*Q): 初始化队列Q。
    DestoryQueue(*Q): 销毁队列Q。
    ClearQueue(*Q): 清空队列Q。
    QueueEmpty(Q): 若队列为空，则返回false，否则返回true。
    GetHead(Q, *e): 若队列Q非空，则用e返回队列Q的队头元素。
    EnQueue(*Q, e): 入队列，插入新的元素e至队列Q中并成为队尾。
    DeQueue(*Q, e): 出队列，删除队列Q中的队头元素，并用e返回。
    QueueLength(Q): 返回队列Q的元素个数。
endADT

4.2.2 循环队列

同样，队列也是一种特殊的线性表，也有顺序存储和链式存储。

队列顺序存储的问题：与顺序存储的线性表不同，如果单纯用数组首个元素作为队列头，最后一个元素作为队列尾，那么元素出队列，数组内的元素就需要往前移动，很明显队列就是专门用来处理入队、出队的数据类型，不像线性表的数据是单调读多、单调写多。所以就有了循环队列来解决这个问题。
头尾相连顺序存储结构的队列。
使用front表示头，rear表示尾。

这样有一个问题，空队列时 front == rear、队列满时也是如此，那怎么区分呢？
有两种方法：

• 另外定义一个flag，用来记录队列为空或已满
• 队列留空一格，也就是说队列满时，数组中还有一个空闲单元

用java实现的循环队列：MyArrayQueue.java

5. 串

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

5.1 串的比较

两个数字很容易比较大小。2 > 1，这完全正确，可是两个字符串比较呢？比如“silly”、“stupid”这样同样表达“愚蠢的”单词字符串，它们在计算机中的大小取决于挨个字母的前后顺序。首个字母“s”忽相等，第二个字母“i”字母比“t”字母靠前，所以i < t，故 silly < stupid。
实际上，串的比较是通过组成串的字符之间的编码来进行的，比如这里的纯英文字母可以采用ascii编码来比较。

5.2 串的抽象数据类型

串的逻辑结构和线性表和相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符，哪怕串的字符是“123”，或者“2010-10-10”，其中每个元素都是字符，它们只能理解为长度为3和长度为10的字符串。
因此，对于串的基本操作与线性表的操作是由很大差别的。线性表关注的是单个元素的操作，比如操作一个元素、插入或删除一个元素，但字符串更多的是查找字符串位置、得到指定位置子串、替换子串等操作。

ADT 串(String)
Data
    串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
    StrAssign(T, *chars): 生成一个其值等于字符串常量chars的串T。
    StrCopy(T, S): 由串S复制得串T。
    ClearString(S): 将串清空。
    StringEmpty(S): 若串S为空，返回true，否则返回false。
    StrLength(S): 返回串S的元素个数，即串长度。
    StrCompare(S, T): 若S>T，返回值大于0，若S=T，返回0，若S<T，返回值小于0。
    Concat(T, S1, S2): 用T返回S1和S2联接而成的新串。
    SubString(Sub, S, Pos, len): 串S存在，1≤pos≤StrLength(S)，且0≤len≤StrLength(S)-pos+1，用Sub返回串S的第pos个字符起长度为len的子串。
    Index(S, T, Pos): 串S和T存在，T是非空串，1≤pos≤StrLenght(S)。若主串S中存在和串T值相等的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则为0。
    Replace(S, T, V): 串S、T、V存在，T是非空串。用V替换主串S中出现的所有与T相等不重叠的子串。
    StrInsert(S, pos, len): 串S、T存在，1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T。
    StrDelete(S, pos, len): 串S存在，1≤pos≤StrLenght(S)-len+1。从串S中删除第pos个字符起长度为len的子串。
endADT

5.3 串的存储结构

5.3.1 串的顺序存储结构

串的顺序存储结构使用一组地址连续的存储单元来存储串中的字符串序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长的数组来定义。

5.3.2 串的链式存储结构

串的链式存储结构与线性表是相似的，实际中链式存储的串除了在连接串有一定方便之外，总的来说不如顺序存储灵活。

5.4 朴素的模式匹配算法

子串的定位操作通常称作串的模式匹配，比如要从主串S=”goodgoogle”中，找到T=”google”这个子串的位置。我们通常需要下面的的步骤：

1. 主串S第1位开始，S与T前三个字母都匹配成功，但第4个字母d与g匹配失败。
   
2. 主串S从第2位开始，o与g匹配失败
   
3. 主串S从第3位开始，o与g匹配失败
   
4. 主串S从第4位开始，d与g匹配失败
   
5. 主串S从第5位开始，6个字母全部匹配，匹配成功
   
   总的来说，就是对主串的每一个字符串作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完为止。
   下面我们用基本的数组来实现这个算法：CharSequenceCompare.java
   最好的情况就是一开始就匹配成功，比如“googlegood”中去找“google”时间复杂度为O(1)。平均是(n+m)/2次查找，复杂度为O(n+m)，最坏的情况O((n-m+1)*m)。对于计算机来说，都是处理的二进制0和1的串，一个字符的ASCII码看成是8位的二进制位01，模式匹配操作可说是随处可见，刚才的算法显得太过低效了。

5.5 KMP模式匹配算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作，简称KMP算法。

5.5.1 KMP模式匹配算法原理

如果主串S=abcdefgab，匹配串T=abcdex，如果用前面的朴素算法的话，前5个字母，两个串完全相等，直到第6个字母，“f”与“x”不等，如图：

接下来，按照朴素算法，2、3、4、5、6，首字符与子串T的首字符均不等。
似乎这也是理所当然，原来的算法就是这么设计的。仔细观察发现，对于要匹配的子串T来说，“abcdex”首字母“a”与后面的串“bcdex”中任意一个字符都不相等，那么对于图中①来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第5位字符相等。即②、③、④、⑤的判断都是多余的。
注意这里是理解KMP算法的关键。如果我们知道T串中首字符“a”与T中后面的字符均不相等(注意这是前提)。而T串的第二位的“b”与S串中的“b”在图中①已经判断是相等的，那么也就意味着T串中首字符“a”与S串中第二位“b”是不需要判断也知道他们是不可能相等的，这样上图中②这一步就可以省略。如下：

同样道理，在我们知道T串首字符“a”与T中后面的字符均不相等的前提下，T串的“a”与S串后面的“c”、“d”、“e”也都可以在①之后就可以确定不相等，所以算法②③④⑤没有必要，只保留①⑥即可，如下图：

跟着书中的这些文字转的有些晕了，停顿耗费了不少时间，跟着例子敲了以下的实现，就此带过了！
java实现：CharSequenceKMPCompare.java