参考教材：数据结构C语言版（严蔚敏，杨伟民编著）

参考课程：青岛大学王卓老师：数据结构与算法基础

思维导图：XMind、幕布         

正在备考，结合自身空闲时间，不定时更新，会在里面加入一些真题帮助理解数据结构

第一章：绪论

1.1基本概念和术语

数据（data）：

什么是数据？

1.数据是信息的载体，是对客观事物的符号表示。

2.能输入到计算机并被计算机程序处理的符号的总称（能被计算机识别、存储和加工）。

数值型数据：整数、实数。

非数值型数据：图像、声音、文字等。

数据元素（data element）：

定义

数据元素是组成数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据元素也称元素、记录、结点、顶点。

数据元素与数据的关系

数据元素是集合（数据）的个体。

数据项

一个数据元素可由若干个数据项组成。数据项是构成数据元素不可分割的最小单位。

数据对象（data object）：

数据对象是性质相同的数据元素的集合，是数据的一个子集。例：

数据对象与数据的关系

数据对象是集合（数据）的子集。

数据、数据对象、数据元素、数据项四者关系：

数据 ≥ 数据对象 > 数据元素 > 数据项

数据是由数据元素组成，数据元素是由数据项组成

数据结构（data structure）：

定义

Data Structure=（D,S）：D是数据元素的有限集，S是D上关系的有限集

（2015中国石油大学）数据结构的定义为（D,S），其中D是（数据元素）的集合。

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

结构：数据元素之间的关系 

（2013中科大）数据结构是具有结构的数据对象（X）

解析：这个说法有些模糊，通常数据结构是计算机存储、组织数据的方式，它不仅仅是一个“具有结构的数据对象”，还涉及到数据的运算和操作。数据结构包括数据的逻辑结构、数据的物理存储结构以及数据上定义的操作。所以，仅仅说数据结构“数据结构是具有结构的数据对象”是不全面的。

数据结构的三要素

一、逻辑结构

数据的逻辑结构：数据元素之间的逻辑关系（2013中科大）。逻辑结构独立于计算机，与数据的存储无关。

（2019广东工业大学）与数据元素本身的形式、相对位置和个数无关的是：数据逻辑结构

解析：所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构；

所谓数据的存储结构，是指数据的逻辑结构在计算机存储空间中的存放形式，与数据元素本身的形式、相对位置和个数有关，逻辑结构与物理存储无关

逻辑结构的种类

（一）线性结构：线性表，栈，队列，双队列，串（一维数组)

一对一：结构中的数据元素之之间存在一个对一个的关系，有且仅有一个开始和一个终端点。

除第一个元素外，其他元素有且只有一个前趋；

除最后一个元素外，其他元素有且只有一个后继！

​

（二）非线性结构：树形结构、图状结构（网状结构）、二叉树

一个结点可能有多个直接前趋和直接后继

①树形结构：一对多

结构中的数据元素之间存在一个对多个的关系。

②图状结构（网状结构）：多对多

结构中的数据元素之间存在多个对多个的关系。

（三）其他结构：集合

①集合：也可用其他结构来表示

​  

结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

（2013中科大）数据的逻辑结构与数据元素本身的内容和形式无关。

数据的逻辑结构只关心数据之间的逻辑关系，而不关心数据元素本身的内容和形式。 

二、物理结构（存储结构）

数据元素及其关系（数据结构）在计算机中的表示（又称映象）称为数据的物理结构或存储结构

四种基本的存储结构

（一）顺序存储结构（重点）

用一组地址连续的存储单元依次存储线性表的各个数据元素，数据元素之间的逻辑关系由元素的存储位置来表示

C语言中用数组来实现顺序存储结构

优点：节省存储空间。
缺点：不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

（二）链式存储结构（重点）

用一组任意的存储单元存储线性表的数据元素，各个元素之间的关系用指针来表示(这组存储单元可以是连续的,也可以是不连续的)。指针————地址

（三）索引存储结构（了解）

在存储结点信息的同时，还建立附加的索引表。索引——index

索引表的每一项都是索引项

索引项的一般形式是：（关键字、地址）

关键字：可以区分不同数据元素的数据项

例：下方的通讯录就是一个索引表

（四）散列存储结构（哈希存储）（了解）

根据元素的关键字直接计算出该元素的存储地址，也称哈希（Hash）存储

三、逻辑结构与存储结构的关系 

1.存储结构是逻辑关系的映象与元素本身的映象。

2.逻辑结构是数据结构的抽象，存储结构是数据结构的实现。

3.两者综合建立了数据元素之间的结构关系

四、数据的运算和实现

施加在

运算：针对逻辑结构，指出运算的功能

运算的实现：针对存储结构，指出运算的具体操作步骤。

针对不同的存储结构，对应的运算实现方式也不一样。

数据类型：

数据类型就是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

数据类型=值的集合+值集合上的一组操作

C语言中基本数据类型：

整型：int    长整型：long int        短整型：short int      

浮点型（单精度）：float   浮点型（双精度）：double   字符型：char  布尔型：bool

不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。

例如：bool类型的值为：true、false。可进行的操作：与、或、非...

作用：

约束变量或常量的取值范围；约束变量或常量的操作

抽象数据类型（ADT）：

抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。与其在计算机内部如何表示无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

抽象数据类型的形式定义

用三元组表示（D，S，P）：D是数据对象，S是D上的关系集，P是对D的基本操作集。

定义抽象数据类型：

ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>
}ADT抽象数据类型

数据对象和数据关系的定义用伪码（伪代码）描述。

基本操作的定义格式为：

基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>

赋值参数只为操作提供输入值；

引用参数以&打头，除了可以提供输入值，还将返回操作结果。

1.2算法与算法分析

1.2.1算法（algorithm）

算法就是对特定问题求解步方法和步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

说白了算法就是解决问题的方法和步骤，第一步要怎么做，第二步要怎么做，第三部要怎么做......
然后列出指令的这样一个序列。
例如：
step1：xxx
step2：xxx
step3：xxx
....    ...

1.2.2算法的描述

自然语言：英文、中文

流程图：传统流程图、NS流程图

伪代码：类语言：类C语言（与C语言类似，但缺少了一些必要的语法细节）

程序代码：C语言程序、Java程序......

举例：

自然语言：

举例：用算法求一元二次方程的根
1.输入方程的系数a、b、c
2.判断a是否等于0，如果等于0，则提示不是一元二次方程；不等于0执行第三步
3.计算△=b²-4ac
4.判断△，如果△=0，计算并输出两个相等实根；如果△＜0，输出没有实根；如果△＞0，输出不等实根
5.结束

传统流程图：

NS流程图：

1.2.3算法与程序 

 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法   程序是用某种程序设计语言对算法的具体实现。

程序  =  数据结构  +  算法

数据结构通过算法来实现操作，算法根据数据结构设计程序。

1.2.4算法的5个重要特征

（1）有穷性

一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。（不能是无穷）

（2）确定性

算法中的每一条指令都必须有确切的含义，无二义性。任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。

（3）可行性

一个算法是能行的，可以执行的。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现的。

（4）输入

一个算法有零个（因为有时候本身自带了输入）或多个的输入，这些输入取自于某个特定的对象的集合。

（5）输出

一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

1.2.5算法设计的要求

（1）正确性（Correctness）

算法应当满足具体问题的需求。程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。

（2）可读性（Readability）

可读性好有助于人对算法的理解，算法主要是为了人的阅读与交流，如果算法晦涩难懂，乱七八糟，很难理解，往往会隐藏很多错误，难以调试与修改

（3）健壮性（Robustness）

输出数据非法时，算法也能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。处理出错的方法，不应该是打印错误信息或异常，并中止程序的执行，而是返回一个表示错误或错误性质的值。

所以，我们要事先预料到可能会出现的问题和错误，事先进行判断，如果有事先处理错误的判断，那么这样的算法就是健壮性好的

（4）效率与低存储量需求（高效率Efficiency）

花尽量少的时间和尽量低的存储需求。

效率：算法执行的时间。        存储量需求：算法执行过程中所需的最大存储空间。

对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。

一个好的算法首先要具备正确性，然后是健壮性，可读性，在这几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度 。

算法的效率：时间效率、空间效率

时间效率：算法所耗的时间        空间效率：算法执行过程中所耗的存储空间

时间效率和空间效率有时是矛盾的