高薪算法+计算机职称考试数据结构算法与数据结构

数据结构 -《大话数据结构》读书笔记(1)

2018-01-02  本文已影响937人  Q以梦为马

前公司的经理大哥建议过我，说趁年轻要深入学习算法与数据结构，设计模式， APP 架构，当然也包括 iOS 底层的一些知识......半年多过去了，算法数据结构方面的书多少算是看过一些，但都是走马观花似的一掠而过，根本没留下什么印象......2018 突然就到了......接下来会多读书，并记录下来，算是对自己的督促，更希望对看到的朋友有所帮助。

文章共分为三篇
第一篇：数据结构 -《大话数据结构》读书笔记(1)

一、数据结构绪论
二、算法
三、线性表

第二篇：数据结构 -《大话数据结构》读书笔记(2)

四、栈与队列
五、串
六、树
七、图

第三篇：数据结构 -《大话数据结构》读书笔记(3)

八、查找
九、排序


一、数据结构绪论

1.1 数据结构

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

1.2 基本概念和术语

数据不仅仅包括整形、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

比如动物类中，牛、马、羊、鸡、鸭、鹅就是其数据元素。

比如人这样的数据元素，有眼、耳、鼻、口、手、脚这些数据项，也可以有姓名、年龄、性别、出生地址、联系电话等数据项，具体哪些数据项，要根据你的系统决定。

所谓性质相同，是指数据元素具有相同数量和类型的数据项，比如人都有姓名，性别，生日等相同的数据项。

1.3 逻辑结构和物理结构：

按照视点的不同，可以把数据结构分为逻辑结构和物理结构。

数据是数据元素的集合，那么根据物理结构的定义，实际上就是如何把数据元素存储到计算机的存储器中。数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最关键的，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。

数据元素的存储结构形式有两种：顺序存储和链式存储。

顺序存储结构

顺序存储结构说白了就是排队占位，大家都按顺序排好，每个人占一小段控件，大家谁也别插谁的队。数组就是这样的顺序存储结构。

链式存储结构

数据元素的存储关系并不能反应其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。链式存储结构比较灵活，数据存在哪里不重要，只要有一个指针存放了相应的地址就能找到它了。比如现在去银行医院等地方，去了先领一个号，等着叫号，在等待的时候你可以做任何事情，只要及时回来就行。

1.4 抽象数据类型：

数据类型是按照值的不同进行划分的，在高级语言中，每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。

在C语言中，按照取值的不同，数据类型可以分为两类：

比如在大型机、小型机、PC、平板电脑、PDA，甚至智能手机都拥有“整数”类型，也需要整数间的运算，那么整型其实就是一个抽象数据类型，尽管它在上面提到的这些在不同计算机中实现方法上可能不一样，但由于其定义的数学特性相同，在计算机编程者看来，它们都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。

二、算法

2.1 算法定义

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

2.2 算法的特性

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

算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果，算法的每个步骤被精确定义而无歧义。

2.3 算法设计的要求

算法不是唯一的，同一个问题，可以有很多种解决问题的算法。好的算法应该具有以下几点要求：

算法的“正确”通常在语法上有很大的差别，大体分为以下四个层次。

  1. 算法程序没有语法错误；
  2. 算法程序对于合法的输入数据能够产生满足要求的输出结果；
  3. 算法程序对于非法的输入数据能够得出满足规格说明的结果；
  4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

一般情况下，我们把层次 3 作为算法是否正确的标准。

我们写代码的目的，一方面是为了让计算机执行，另一方面是为了便于他人阅读，让人理解和交流，自己将来也可能阅读，如果可读性不好，时间长了自己都不知道写了什么，可读性是算法好坏的一个很重要的标志。

综上，好的算法，应该具有正确性、可读性、健壮性、高效性和低存储量的特点。

2.4 函数的渐进增长

例子 1：
A 算法与 B 算法，A 算法要做 2n+3 次操作；B 算法要做 3n+1 次操作。问哪个执行的更快？

由上图可知，当 n = 1，算法 A 效率不如算法 B；当 n = 2 时，两者效率相同；当 n > 2 时，算法A开始优于算法 B了。得出结论，加法常数可以忽略。

例子 2：

C 算法与 D 算法，C 算法要做 4n+8 次操作；D 算法要做 2 n*n +1 次操作。问哪个执行的更快？


由上图可知，当 n <= 3 时，算法 C 差于算法 D；当 n > 3 时，算法 C 的优势开始越来越优于算法 D 了。得出结论：与最高次项相乘的常数并不重要。

2.5 算法时间复杂度

这样用大写 O() 来体系那算法时间复杂度的记法，我们称之为大 O 记法。

一般情况下，随着n的增大，T(n) 增长最慢的算法为最优算法。

得到的结果就是大 O 阶。

2.6 算法空间复杂度

一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入的数据量而言是个常数，则称此算法为原地工作，空间复杂度为 O(n)。

通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常都是指时间复杂度。

三、线性表

3.1 线性表定义

零个或多个数据元素的有限序列。

首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其它元素都有且只有一个前驱一个后继。

然后，线性表强调是有限的，即元素个数是有限的。

3.2 线性表的抽象数据类型

对于一个线性表来说，插入或者删除数据都是必须的操作，因此线性表的抽象数据类型定义如下：

ADT线性表(List)
Data
线性表的数据对象集合为 (a1, a2, a3, ……, 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.3 线性表的顺序存储结构

3.3.1 顺序存储定义

先来看看线性表的两种物理结构的第一种——顺序存储结构。

线性表的顺序存储示意图如下：

线性表的顺序存储
3.3.2 顺序存储方式

线性表的顺序存储结构，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用 C 语言（其它语言也相同）的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为 0 的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

/* 存储空间初始分配量 */
#define MAXSIZE 20 

/* ElemType 类型根据实际情况而定，这里假设为 int */
typedef int ElemType;

typedef struct {
    /* 数组存储数据元素，最大值为 MAXSIZE */
    ElemType data [MAXSIZE];
    /* 线性表当前长度 */
    int length;
}SqList;
3.3.3 数据长度与线性表长度区别

在任何时刻，线性表的长度都应该小于等于数组的长度。

3.3.4 地址计算方法

C 语言中的数组是从 0 开始第一个下标的，线性表的第 i 个元素是要存储在数组下标为i - 1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系（如下图）。

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

3.4 顺序存储结构的插入和删除

3.4.1 插入算法的思路
  1. 如果插入位置不合理，抛出异常
  2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
  3. 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置
  4. 将要插入元素填入位置 i 处
  5. 表长加 1
3.4.2 删除算法的思路
  1. 如果删除位置不合理，抛出异常
  2. 取出删除元素
  3. 从删除元素开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
  4. 表长减 1
3.4.3 插入和删除的时间复杂度
3.4.4 线性表顺序存储结构的优缺点

3.5 线性表的链式存储结构

3.5.1 顺序存储结构的不足

顺序存储结构最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。

3.5.2线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

在顺序结构中，每个数据元素只需要存数据元素信息就可以了，但在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

为了表示每个数据元素 a(i) 与其直接后继数据元素 a(i+1) 之间的逻辑关系，对数据元素a(i)来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素a(i)的存储映像，称为结点(Node)。

N 个结点链接成一个链表，即为线性表（a1，a2，…，a（n））的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。如下图所示：

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。最后一个结点指针为“空”，如下图所示：

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储诸如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。如下图所示：

3.5.3 头指针与头结点的异同

3.6 单链表的读取

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的，但在单链表中，必须得从头开始找。因此，对于单链表实现获取第 i 个元素的数据的操作 GetElem ，在算法上，相对要麻烦一些。

3.7 单链表的插入和删除

3.7.1单链表的插入

假设存储元素 e 的结点为 s，要实现结点 p、p->next 和 s 之间逻辑关系的变化，只需将结点 s 插入到结点 p 和 p->next 之间即可。如何插入？

用不着惊动其它结点，只需让 s->next 和 p->next 的指针做一点改变即可。

s->next=p->next; p->next=s;

解读代码：让 p 的后继结点改成 s 的后继结点，再把结点 s 变成 p 的后继结点。

3.7.2单链表的删除

假设存储元素 a 的结点为 q，要实现结点 q 删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可。

q=p->next; p->next=q->next;

解读代码：让 p 的后继结的后继结点改成 p 的后继结点。

3.8 单链表的整表创建与删除

3.8.1 单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而链表和顺序存储结构不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始化状态起，依次建立各元素结点，并逐个插入链表。

3.8.2 单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便留出空间给其它程序或软件使用。

3.9 单链表结构与顺序存储结构优缺点

下一篇：数据结构 -《大话数据结构》读书笔记(2)
上一篇下一篇

猜你喜欢

热点阅读