这周开始自学数据结构与算法，在B站看了些视频也有了一个初步的了解，由于是初学，一些概念还是记清楚点比较好，这篇博客就按我的学习顺序来总结一下本周学习内容。

初入门

一、基础定义

数据结构：

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。

数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。 

数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1.集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2.线性结构：数据结构中的元素存在一对一的相互关系；

3.树形结构：数据结构中的元素存在一对多的相互关系；

4.图形结构：数据结构中的元素存在多对多的相互关系。

数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1.集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2.线性结构：数据结构中的元素存在一对一的相互关系；

3.树形结构：数据结构中的元素存在一对多的相互关系；

4.图形结构：数据结构中的元素存在多对多的相互关系。

数据的物理结构

指数据的逻辑结构在计算机存储空间的存放形式。

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。

数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与个数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。

关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。 

数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。

线性结构

简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：

1、线性结构是非空集。 

2、线性结构有且仅有一个开始结点和一个终端结点。 

3、线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。 

线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。 

非线性结构

简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点： 

1、非线性结构是非空集。 

2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。

在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。

常用的数据结构

在计算机科学的发展过程中，数据结构也随之发展。程序设计中常用的数据结构包括如下几个。 

数组(Array)

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构，在各种编程语言中都有对应。一个数组可以分解为多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。 

栈( Stack)

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。

队列(Queue)

队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素时，称为空队列。 

链表( Linked List)

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。

树( Tree)

树是典型的非线性结构，它是包括，2个结点的有穷集合K。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点，而且可以有两个后继结点，m≥0。

图(Graph)

图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。

堆(Heap)

堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。

散列表(Hash)

散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。 

算法定义：

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

算法的基本特点：

（1）输入输出：算法具有0个或多个输入，至少有一个或多个输出；

（2）有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成；

（3）确定性：算法的每一步骤都具有确定的含义，不会出现二义性。

（4）可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成；

算法设计要求：

（1）正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案；

（2）可读性：算法设计的另一目的是为了便于阅读、理解和交流

（3）健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果；

（4）时间效率高存储量低：时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。设计算法应该尽量满足时间效率高和存储量低的需求。

常用算法

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算： 

(1)检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。 

(2)插入。往数据结构中增加新的节点。 

(3)删除。把指定的结点从数据结构中去掉。 

(4)更新。改变指定节点的一个或多个字段的值。

(5)排序。把节点按某种指定的顺序重新排列。例如递增或递减。 

以上是我觉得入门数据结构和算法需要了解的东西！！！

时间复杂度和空间复杂度

时间复杂度

（1）时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。

（2）时间复杂度

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。

按数量级递增排列，常见的时间复杂度有：

常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

这是我截取的视频中的常见时间复杂度表:

空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:

S(n)=O(f(n))

算法执行期间所需要的存储空间包括3个部分：

算法程序所占的空间；

输入的初始数据所占的存储空间；

算法执行过程中所需要的额外空间。

在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

线性表

一、顺序表（数组）

1. 性质：① 随机访问（查找快，直接定位） ② 存储密度高，只存储数据元素 ③ 插入、删除操作需要大量移动元素( 插入平均移动  n/2 个元素，删除平均移动 (n-1)/2 个元素 )

2. 顺序表的插入：时间复杂度：O(n) ; 空间复杂度：O(1)

//先判断插入是否合法（省略）for(inti=L.length;i>=pos;i--)//pos为插入位置，数组下表从0开始L.data[i]=L.data[i-1];L.data[i-1]=e;//e为插入元素L.length++;//线性表长度加1

3. 顺序表的删除：时间复杂度：O(n) ; 空间复杂度：O(1)

//先判断删除是否合法（省略）for(inti=pos;i<L.length;i++)//pos为删除位置，数组下表从0开始L.data[i-1]=L.data[i];L.length--;//线性表长度减1

4. 顺序表的访问：时间复杂度：O(1) （基于随机访问）

5. 顺序表的遍历和交换太简单了，估计看完一遍书绝大部分的人都会吧

6. 算法分析（以后会开一个专题说的，现在这个阶段先把基础打好，有能力的同学可以试试写一写数组逆置； 用O(n)的方法删除数组中不等于5的元素； 归并操作； 二分查找）这些后面都会说的

二、链表

1. 单链表

性质： 非随机存储（查找要逐个遍历），所以查找比较慢 、插入删除操作快（已经找到了位置的前提下）

①头指针指向链表的第一个结点，头结点的带头结点链表的第一个结点（通常不存储信息）。

PS：为什么要设立头结点？ 可以对链表统一操作，边界操作统一

有头结点：第一个有效数据的地址为 L->next

无头结点：第一个有效数据的地址 L

②建立：头插法、尾插法（设一个指向表尾的结点指针rear）

③插入： O（n） 如下图理解

在第i个位置 插入

p=GetElem(L,i-1);//时间复杂度O(n)s->next=p->next;//①  注意①②顺序不能换，假如交换了就断链了，i-1就找不到原来i了p->next=s;//② （注意，单单只是将这个插入操作有时候只强调插入，即后两行代码，为O(1)）

注意一个小细节，我的图跟书上的不一样，我的 “→”箭头的起始端是跟“圆圈”连起来的，其实“→”就是next域，“圆圈”就是data域，连起来才是一个结构体。而书上的箭头跟圆圈是分开的，我觉得这样不助于我们学生理解。以后我都用下面的写法来画结点这样才能完整的保留结点的存储特性。

书上的写法

有助于理解的写法

④删除： O（n） 如下图理解

删除 第i个元素

p = GetElem(L, i-1);    //时间复杂度O(n) 后面的操作为O(1)

q = p->next;

p->next = q->next;

free(q);

问：带有尾指针的单链表，在表尾插入一个元素的时间复杂度是O（1），但是删除表尾的元素时间复杂度是O(n)。 大家可以思考一下为什么？

答：

不知道大家发现没有，插入（删除）操作，都是要找到插入（删除）元素之前的一个元素，我们上面是用“p”来指向的，都是通过这个“p”来完成后续操作的。

在带有尾指针rear的链表,插入直接用 rear->next = s 就可以了，因为rear正是待插入结点的前驱节点。

而删除表尾元素，就要找到rear的前驱结点，由于单链表所以要进行一次遍历，找到rear的前驱结点，再进行删除操作。

PS:大家知道为什么要设立head头结点这么一说了吧，正是因为有了head结点这一个前驱结点，插入(删除)操作才会统一。（链表为空的插入，链表还剩下一个的时候删除）

总之，在单链表的操作中，大家一定要重视待插入（删除）的前驱结点的学习。上面总结出来的大家一定要好好理解。

2. 双链表：在单链表的基础上，结构体增加一个指向前驱结点的prior的指针

3. 循环单链表：在单链表的基础上，在表尾的next指向表头 r->next = L;

4. 循环双链表：在循环单链表基础上，结构体增加一个指向前驱结点的prior的指针，加上L->prior = r；r->next = L;

5. 静态链表：用连续的块内存空间当链表使用（跟操作系统中文件管理中的文件分配方式的显示链接一样）

以上说的都离不开单链表的基本操作，只要把单链表理解透彻，这些都是小Case。

我觉得一个适合自己的笔记，不是什么都写的非常详细，只是让自己有个索引，具体的书都是很清楚的，我就没有必要在做了重复了，免得话就跟抄书没有什么区别了。

三、顺序表与链表的选用：

通常比较稳定的线性表，用顺序存储。（静态）

频繁做插入、删除操作的线性表，用链式存储（动态）

访问查找比较多的 —— 顺序表

插入、删除比较多的，要求占空间小 —— 链表