数据结构与算法入门

第一章 绪论

1.1数据结构讨论的范畴

        算法+数据结构=程序设计

        算法：怎么处理，编制的方案如何？

        数据结构：信息如何表示？如何在计算机中实现？

        程序设计：为计算机处理问题编制的一组指令集。（代码）

举例：计算机博弈问题--跳棋

算法：对弈的规则和策略： 几步一跳，连跳几步……

数据结构：如何在计算机中表示棋盘，棋子……，每步的后继步骤如何表示……

1.2数据结构的定义

一门研究非数值计算的程序问题中计算机操作对象以及他们之间关系和操作的学科。

研究内容：

1.数据的逻辑结构：数据之间的逻辑关系（我们明白）

2.数据的存储结构： 逻辑结构在计算机中的表示（计算机明白）

3.操作算法：如何组织数据，以便查找，存取（插入，删除，修改，查询，排序等）（组织数据的算法）

1.3数据结构的基本概念

        1.数据:计算机操作对象的总称。

          举例：整数，实数，音频，视频，图像等

        2.数据元素：数据的基本单位，是数据这一集合中的“个体”。

例如：人员信息表

姓名	性别	出生日期	……
李四	男	2001/10/9

                注：数据元素是基本单位，但不是最小单位（数据项）

        3.数据对象：性质相同的数据元素的集合。例如，整数数据对象集，字母字符数据对象集。 

        4.数据结构：带有结构的数据元素的集合。

        例如：二维数组，行列次序关系

        5.四种基本逻辑结构：

        1）集合：结构中的数据元素之间除了“同属于一个集合的关系外，别无其他关系。（具备某种共同的属性）

        2）线性结构：数据元素之间一对一的关系

        3）树形结构：一对多的关系

        4）图（网）状结构：多对多的关系

        6.形式定义：

        Data_Structure= (D,S)

        D:数据元素的有限集；S:D上关系的有限集。

        7.存储结构：如何将数据结构用计算机进行表示。

          主要指：数据的表示与数据之间关系的表示。

        8.*两种存储结构：

        1）顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

        2）链式结构：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

        9.数据类型：一个值的集合和定义在这个值集上的一组操作的总称。包括：

        1）基本类型（int，float等）

        2）构造类型（数组，结构体等）

        10.抽象数据类型：（D,S,P)

        1）数据抽象

        2）数据封装

 1.4算法与算法分析

1.算法：对问题求解的一种描述，是解决问题的一个有限长的操作序列。

特征：1)有穷性  2)确定性  3)可行性  4)输入  5)输出

2.评价算法好坏的标准

1）准确性：算法应当满足具体问题的需求

        1.程序不含语法错误

        2.对于几组输入能得到满足要求的结果

        3.对精心选择的典型，带有刁难性的数据能得到满足要求的结果

        4.对一切合法数据能得到满足要求的结果

2）可读性：易于理解

3）健壮性：对输入非法做出适当处理

4）时间复杂性

5）空间复杂性

3.算法效率的度量

        运行前分析估算，运行后统计

4.算法与程序的联系与区别

        1）同：表达问题的逻辑过程

        2）异：算法独立于具体的程序，与编程语言无关。算法是解决问题的思路，程序不能离开算法单独存在。

第二章 线性表

1.1数组

数组是一种数据结构，它用于存储相同类型的元素，并按照一定的顺序排列。数组中的每个元素都可以通过索引（或下标）来访问，索引通常从0开始递增。为什么从零开始呢？因为索引的本质是内存地址的偏移量。首个元素的地址偏移量是0，因此它的索引为0。

  

1.2数组的特点

数组的优点：

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。

空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。

支持随机访问：数组允许在𝑂(1)时间内访问任何元素。

数组的局限性：

缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。连续空间存储是一把双刃剑，其存在以下局限性。

插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。

长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。

空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

常见误区：

顺序表是什么？顺序表是数组的一种实现方式。不要把这几个概念混淆！！！ 

 2.1链表

「链表linkedlist」是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

 2.2链表的类型

1.单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空None。

单向链表 

2.环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

 循环链表

3.双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

双向链表 

 3.1列表

「列表list」是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。

链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。

数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。 

 为解决此问题，我们可以使用「动态数组dynamicarray」来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。

实际上，许多编程语言中的标准库提供的列表是基于动态数组实现的，例如Python中的list、Java中的ArrayList、C++中的vector和C#中的List等。在接下来的讨论中，我们将把“列表”和“动态数组”视为等同的概念。

4.重点回顾

        数组和链表是两种基本的数据结构，分别代表数据在计算机内存中的两种存储方式：连续空间存储和分散空间存储。两者的特点呈现出互补的特性。

        数组支持随机访问、占用内存较少；但插入和删除元素效率低，且初始化后长度不可变。

        链表通过更改引用（指针）实现高效的节点插入与删除，且可以灵活调整长度；但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、环形链表、双向链表。（双向循环链表啥的这里先不讲）

        列表是一种支持增删查改的元素有序集合，通常基于动态数组实现。它保留了数组的优势，同时可以灵活调整长度。

        列表的出现大幅提高了数组的实用性，但可能导致部分内存空间浪费。

        程序运行时，数据主要存储在内存中。数组可提供更高的内存空间效率，而链表则在内存使用上更加灵活。

        缓存通过缓存行、预取机制以及空间局部性和时间局部性等数据加载机制，为CPU提供快速数据访问，显著提升程序的执行效率。

        由于数组具有更高的缓存命中率，因此它通常比链表更高效。在选择数据结构时，应根据具体需求和场景做出恰当选择。

 第三章 栈和队列

1.1栈

栈是一种遵循先入后出的线性数据结构。我们通常把它比作叠盘子，如果一摞盘子，我们要想取出最下面的那一个，就需要先将最上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数，字符，对象等），就得到了栈这种数据结构。

 栈的先入后出规则

 1.2栈的实现

栈遵循先入后出的运行机制，因此我们只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表。换句话说，我们可以“屏蔽”数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。

1.基于链表的实现

基于链表实现队列的入队出队操作

对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为“头插法”。而对于出栈操作，只需将头节点从链表中删除即可。

2.基于数组的实现

基于数组实现大体与链表是一样的。使用数组实现栈时，我们可以将数组的尾部作为栈顶。如图所示，入栈与出栈操作分别对应在数组尾部添加元素与删除元素，时间复杂度都为𝑂(1)。

 基于数组实现栈的入栈出栈操作

1.3两种实现的对比

两种实现对比支持操作两种实现都支持栈定义中的各项操作。

数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。

时间效率在基于数组的实现中，入栈和出栈操作都在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。然而，如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为𝑂(𝑛)。

在基于链表的实现中，链表的扩容非常灵活，不存在上述数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。

不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。综上所述，当入栈与出栈操作的元素是基本数据类型时，例如int或double，我们可以得出以下结论。

基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。

基于链表实现的栈可以提供更加稳定的效率表现。空间效率在初始化列表时，系统会为列表分配“初始容量”，该容量可能超出实际需求；并且，扩容机制通常是按照特定倍率（例如2倍）进行扩容的，扩容后的容量也可能超出实际需求。

因此，基于数组实现的栈可能造成一定的空间浪费。然而，由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。

综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。

1.4栈的典型应用

浏览器中的后退与前进、软件中的撤销与反撤销。

每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。

程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

1.5队列

「队列queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

如图所示，我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删
除队首元素的操作称为“出队”。

 队列的先入先出规则

1.6队列常用操作

队列的常见操作如表所示。需要注意的是，不同编程语言的方法名称可能会有所不同。我们在此采用与栈相同的方法命名。

方法名	描述	时间复杂度
push( )	元素入队，即将元素添加至队尾	O（1）
pop( )	队首元素出队	O（1）
peek( )	访问队首元素	O（1）

队列操作效率