数据结构 |【第一章】概念

ゝ一世哀愁。 2022-10-23 03:00 490阅读 0赞

### 文章目录 ###

*   *   *   *  前言
     *  概论
     *   *   *  什么是数据结构
             *   *  数据结构研究内容
             *  数据的逻辑结构
             *   *  概念和术语
                 *  数据的逻辑结构
             *  数据的存储结构
             *   *  顺序存储结构
                 *  链表存储结构
                 *  索引存储结构
                 *  散列存储结构
             *  算法
             *   *  概念
                 *  算法的效率评价
     *  本章小结
     *  课后习题
     *   *   *  选择题
             *  二、填空题
             *  三、判断题

#### 前言 ####

>   3月18号已经开学3天了。由于疫情，本学期大部分开学相对于往年都比较迟。本学期我开始学习了`数据结构`这门课程，使用的是`c语言`。由于大一上，c语言只接触到了指针前面的内容，并且没有花时间去认真学，基础相对薄弱，在本学期会重新在温习一遍。所以前段时间在复习c语言，并且按照学习进度写在[博客][Link 1]。这学期加上数据结构的课程，我会加快复习进度，并会学得深入一点，后续还会持续更新其他章节的内容。  
>   通过`数据结构`这门课程的学习，我会按照章节内容将笔记整理出来。在老师结束本章内容的时候同时发布这一章的内容，而且我会在每章结尾附上课后习题，习题答案会在下一章节的前面发布答案。希望同学一起学习，一起进步⛽。

## 概论 ##

> `数据`作为计算机加工处理的对象，在计算机中如何`表示、存储`是计算机科学研究的主要内容之一，更是计算机技术要解决的问题之一。若要让计算机更加有效地进行这些`非数值性处理`，就必须要弄清这些`操作对象的特点`，在计算机中的表示方式以及各个操作的具体实现手段。这就是 `数据结构` 这门课程的主要内容。

#### 什么是数据结构 ####

> **数据结构**：带有结构的数据元素的集合。  
> 是介于数学、计算机硬件和计算机软件三者之间的核心课程。数据结构是一般非数值计算机程序设计基础，也是设计和是实现汇编语言、编译程序、操作系统、数据库系统，以及其他程序和大型应用程序的重要基础。  
> **结构**：数据元素之间的互相关系。

> 数据结构包含以下两方面内容：
> 
>  *  构成集合的数据元素；
>  *  数据元素之间存在的关系。

> 著名科学家N. Writh提出 `算法+数据结构=程序` 的思想，明确指出了数据结构实际上是程序的主要部分。

##### 数据结构研究内容 #####

> 用计算机解决一个实际问题时，大致需要以下步骤：
> 
>  *  从具体问题抽象除一个适当的数学模型；
>  *  设计求解数学模型的算法；
>  *  编制、运行并调试程序，直到解决问题。
> 
> so，数学建模过程就是分析问题，并找出这些对象的关系，用数学语言来描述。

> 【例1】：  
> 井字棋人机对弈问题。井字棋对弈过程中,任何一方只要使相同的三个棋子连成一条直线即为胜方(可以是一行一列或一条对角线)。如果下一棋子由“x”方下,可以派生出五个子格局,如图1-1所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]

> 若将从对弈开始到结束的过程中所有的可能的格局画在一张图上,即形成了一棵倒的对弈“树”。“树根”是对弈开始时的第一步棋,而所有的“叶子”便是可能出现的结局。

#### 数据的逻辑结构 ####

##### 概念和术语 #####

**数据（Data）**：

> 所有能输入到计算机中且能被程序处理的`符号`的表示。

**数据元素（Data Element）**：

> `数据元素`也称为`结点`时数据的`基本单位`。例如：一个student的info为一个数据元素，一个stu信息中的每一项（学号、性别等）为一个数据项。`数据项`时数据处理中不可分割的`最小单位`。

**数据结构（Data Structure）**：

> 按某种`逻辑关系`组织起来的一批数据，按一定的`映像方式`把它存放在计算机存储器中，并在这些数据上定义了一个`运算的集合`。  
> 数据结构一般包括以下3方面内容：
> 
>  *  数据元素之间的逻辑关系，即数据的逻辑结构；
>  *  数据元素及其关系在计算机存储器内的表示，即数据的存储结构；
>  *  数据的匀速那， 即对数据施加的操作。

##### 数据的逻辑结构 #####

**定义**：

> 指 `数据元素` 之间逻辑关系描述。  
>   可用二元组表：`G=(D, R)`  
>     `D - 数据元素的有限集合；R - 是D上关系的有限集合；`数据的逻辑结构是从逻辑关系上`描述数据`，与`数据存储`无关，是`独立与计算机`的。

**数据的逻辑结构分类**：

> 根据数据元素之间的逻辑关系的不同特性可分为以下4类基本结构：
> 
>  *  集合：数据元素中除同 `属于一个集合` 的关系外，无其他关系。最简单的数据结构；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]

>  *  线性结构：数据元素之间存在 `一对一` 的关系；  
>        **特点**：存在先后关系，对任一节点，在前面的为 `直接前驱` ，至多一个；在后面的为 `直接后继` ，至多一个。

![在这里插入图片描述][20210318133044964.png]

>  *  树形结构：数据元素之间存在 `一对多` 的关系；  
>        **特点**：一个数据元素向上和一个数据元素相连为 `双亲结点`；向下和多个数据元素相连为 `孩子节点`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 2]

>  *  图形或网状结构：任意数据元素之间都阔以有关系，元素之间存在 `多对多` 关系。  
>        **特点**：一个结点可能有多个 `直接前驱` 和 `直接后继`>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 3]

#### 数据的存储结构 ####

> 数据在计算机中存储为数据的 `存储结构`【物理结构】
> 
>  *  顺序存储结构
>  *  链式存储结构
> 
> 数据的`存储结构`是逻辑结构在计算机存储器中的`实现`

**逻辑结构和存储结构的关系**：

> `存储结构`是逻辑关系的映像与元素本身映像，是数据结构的`实现`；`逻辑结构`是数据结构的`抽象`。

##### 顺序存储结构 #####

> 借助元素在`存储器`中的相对位置来表示数据元素间的逻辑关系。

> **特点**：
> 
>  *  可实现对各数据的随机访问。因为只要知道存储的首地址以及每个数据元素所占的存储单元，就可计算出各数据元素的存储地址。
>  *  但不利于数据元素`修改，插入、删除`等操作，需要移动一系列数据元素。

##### 链表存储结构 #####

> 借助于指示`元素存储地址的指针`表示数据元素间的`逻辑关系`。

> 【例】：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 4]

> **特点**：
> 
>  *  利于对数据元素`修改、插入、删除`，仅需修改数据元素的`指针字段值`，而不必移动数据元素。
>  *  由于逻辑上相邻的数据元素在存储位置中不一定相邻，so，链式存储结构`不能`对数据元素进行`随机访问`。

##### 索引存储结构 #####

> `索引存储`是在原有的存储结构的基础上，附加建立一个索引表,索引表中的每一项都由`关键字和地址`组成。索引表反映了按某一个关键字`递增或递减排列`的逻辑次序。采取索引存储的主要作用是为了提高数据的`检索速度`。

##### 散列存储结构 #####

> `散列存储`是通过构造散列函数来确定`数据存储地址或查找地址`。  
> 【例如】：某一地区进行2000年以后出生的人口统计。我们用“出生年份-2000=存储地址”来构造一个函数,即用出生年份减去2000得到的差值就是存储地址，这样就能方便的得到这样的调查表。

![在这里插入图片描述][20210318153412922.png]

#### 算法 ####

##### 概念 #####

**算法的定义**：

> `算法`是由若干条指令所组成的`有穷序列`，其中每条指令表示计算机的`一个或多个`操作。

**算法的特性**：

> 好算法具有以下5个特性：
> 
>  *  `有穷性`：一个算法必须`对任何合法的输入值`在执行`有限时间`内完成,不能形成无穷循环；
>  *  `确定性`：算法中的每一条指令必须有`确切的含义`，不会产生二义性；
>  *  `可行性`：算法中描述的操作都可以通过已经实现的基本运算执行`有限次`来实现；
>  *  `输入`：一个算法有`零个或多个`输入，这些输入取自于`某个特定对象`的集合；
>  *  `输出`：一个算法必有一个或多个输出，这些输出是与输入有着一定关系的量。.

**好算法应达到的目标**：

>    算法与数据结构是`相辅相成`的。解决某一`特定类型问题的算法`可以选定`不同的数据结构`，而且选择恰当与否直接影响算法的`效率`。反之，一种数据结构的优劣由各种算法的执行来体现。
> 
> --------------------
> 
>    设计一个好的算法通常需要考虑以下几个方面的要求：
> 
>  *  `正确性`：要求算法能够正确地执行`预先规定`的功能,并达到所`期望的性能`要求；
>  *  `可读性`：为了便于`理解、测试和修改`算法，算法应该具有良好的可读性；
>  *  `健壮性`：当输入`非法的数据`时,算法应能恰当地做出反应或进行`相应处理`，而不是产生莫名奇妙的输出结果。并且处理出错的方法不应是中断程序的执行，而是返回一个表示`错误或错误性质的值`，以便在更高的抽象层次上进行处理；
>  *  `高效性`：要求算法的执行时间要`尽可能地短`，算法的`效率`就越高；
>  *  `低存储量`：完成`相同的功能`，执行算法时所占用的附加`存储空间要尽可能地少`。

>   实际上，算法很难做到十全十美,因为上述要求有时会`相互抵触`。所以,实际操作中，应以算法`正确为前提`，根据具体情况而有所侧重。

##### 算法的效率评价 #####

>    一个好的算法首先要具备`正确性`、`可读性`和`健壮性`。在具备了这3个条件后，就应老虑算法的`效率问题`，即算法的`时间效率(所需运算的时间)和空间效率(所存储空间)`两方面。对于求解同一个问题，可以设计出若干个算法,对于不同的算法进行性能分析是数据结构的一个重要内容。

> **在算法满足正确性的前提下，如何评价不同算法的优劣呢？**：  
>    通常主要考虑`算法的时间复杂度和空间复杂度`这两方面。一般情况下,鉴于`运算空间`较为充足，所以把算法的`时间复杂度`作为重点分析。

**时间复杂度(Time Complexity )**：

> 一个算法所需的`运算时间`通常与`所解决问题的规模大小`有关。
> 
> --------------------
> 
>    问题规模是一个和输入有关的量，用`n表示问题规模的量`，通常把算法运行所需的时间T表示为n的函数，记为T(n)不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。
> 
> --------------------
> 
>    一个算法所需的`执行时间`就是该算法`中所有语句执行次数之和`。当n逐渐增大时T(n)的极限情况，一般简称为`时间复杂度`。

> 当讨论一个程序的`运行时间`时。注重的不是`T(n)`的具体值。而是它的`增长率`。`T(n)`的增长率与算法中数据的输入规模紧密相关。而`数据输入规模`往往用算法中的`某个变量的函数`来表示,通常是`f(n)`。随着数据输入规模的增大。`f(n)的增长率与T(n)的增长率相近`。因此`T(n)`同`f(n)`在数量级上是一致的。记作:

`T (n)=O(f(n))`

> 其中,大写字母O表示数量级`(Order of Magnitude )`的概念，`f(n)`为函数形式。

> 【例如】：若`T(n)=3n^2+5n+2`，则`3n^2+5n+2`的数量级与`n2`的数量级相同，所以`T(n)=O(n^2)`注意，当`T(n)`为多项式时，可只取其`最高次幂项`并`省略`其系数，其他的次幂项及系数均略去不写。一般地，对于足够大的`n`，常用的时间复杂度的大小次序如下：`O (1)<(log2n )<(n)<(nlog2n )<O(n^2)<(n^3)<(2^n)`算法时间复杂度的数量级越大，表示该算法的效率越低，反之越高。  
> 【例如】：O(1)为常数数量级，即`算法的时间复杂性与输入规模n无关`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 5]

**空间复杂度（Space Complexity）**：

> 一个算法的空间复杂度是指程序`运行开始到结束`所需要的`存储空间`。包括算法`本身所占用的存储空间`、`输入/输出数据`占用的存储空间以及算法在运行过程中的`工作单元`和实现算法所需`辅助空间`。类似于算法的时间复杂度，算法所需存储空间的量度记作：  
>                   `S (n)=(f(n))`  
> 其中，n为问题的规模，一个程序上机执行时,除了需要存储空间来存放本身所用的`指令、常数、变量和输入数据以外`，还需要一些对数据进行操作的工作单元和实现算法所必需的辅助空间。在进行时间复杂度分析时，如果所占空间量`依赖于特定的输入`，一般都是按`最差情况`来分析。

## 本章小结 ##

>  *  数据结构主要研究数据的`逻辑结构`、`存储结构`和`运算方法`。
>  *  数据的逻辑结构包括：`集合`、`线性结构`、`树形结构`、`图形结构`4种基本类型。
>  *  数据的存储结构包括：`顺序存储结构`、`链式存储结构`、`索引存储`、`散列存储`4种。
>  *  `顺序存储`可以采用`一维数组`来存储;`链式存储`可以采用`链表`来存储；`索引存储`则在`原有存储数据结构`的基础上，附加`建立一个索引表`来实现,主要作用是为了提高数据的检索速度；而`散列存储`则是通过`构造散列函数`来确定数据存储地址或查找地址。
>  *  算法是对特定问题求解步骤的一种描述,是指令的有限序列。算法具有:`有穷性`、`确定性`、`可行性`、`输入`、`输出`等特性。
>  *  一个好的算法应达到：`正确性`、`可读性`、`健壮性`、`高效性`和`低存储量`等目标。
>  *  算法的效率通常用`时间复杂度`与`空间复杂度`来评价，一个算法的`时间复杂度越好,则算法的效率就越高`。

## 课后习题 ##

#### 选择题 ####

> **1.数据结构通常是研究数据的( )及它们之间的相互联系。**  
> A.存储结构和逻辑结构 B.存储和抽象 C.联系和抽象 D.联系与逻辑

> **2.从逻辑上可以把数据结构分为( )两大类。**  
> A.动态结构、静态结构 B.顺序结构、链式结构  
> C.线性结构、非线性结构 D.初等结构、构造型结构

> **3.数据处理的基本单位是( )**  
> A.数据元素 B.数据项 C.数据类型 D.数据变量

> **4.数据结构中线性结构中元素对应关系为( )**  
> A.一对一 B.一对多 C.多对多 D.无关系

> **5.数据结构中树形结构中元素对应关系为( )**  
> A.一对一 B.一对多 C.多对多 D.无关系

> **6.数据结构中图形结构中元素对应关系为( )**  
> A.一对 B.一对多 C.多对多 D.无关系

> **7.数据在计算机存储器内表示时,物理地址和逻辑地址相同并且是连续的,称为( )**  
> A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构

> **8.非线性结构中的每个结点( )**  
> A.无直接前趋结点 B.无直接后继结点  
> C.只有一个直接前趋结点和一个直接后继结点  
> D.可能有多个直接前趋结点和多个直接后继结点

> **9.链式存储的存储结构所占存储空间( )**  
> A.分两部分,一部分存放结点的值,另一部分存放表示结点间关系的指针  
> B.只有一部分,存放结点的值  
> C.只有一部分,存储表示结点间关系的指针  
> D.分两部分,一部分存放结点的值,另一部分存放结点所占单元素

> **10.算法分析的两个主要方面是( )**  
> A.正确性和简单性 B.可读性和文档性 C.数据复杂性和程序复杂性 D.时间复杂度和空间复杂度

> **11.算法的计算量大小称为算法的( )**  
> A.现实性 B.难度 C.时间复杂性 D.效率

> **12.数据的基本单位是( )**  
> A.数据结构 B.数据元素 C.数据项 D.文件

> **13.每个结点只含有一个数据元素,所有存储结点相继存放在一个连续的存储区里,这种存储结构称为( )**  
> A.顺序存储 B.数据元素 C.索引存储 D.散列存储

> **14.每一个存储结点不仅含有一个数据元素,还包含一组指针,该存储方式是( )存储方式。**  
> A.顺序 B.链式 C.索引 D.散列

> **15.以下任何两个结点之间都没有逻辑关系的是( )**  
> A.图形结构 B.线性结构 C.树形结构 D.集合

> **16.在数据结构中,与所使用的计算机无关的是( )**  
> A.物理结构 B.存储结构 C.逻辑结构 D.逻辑和存储结构

> **17.下列四种基本逻辑结构中,数据元素之间关系最弱的是( )**  
> A.集合 B.线性结构 C.树形结构 D.图形结构

> **18.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )**  
> A.逻辑结构 B.存储结构 C.逻辑实现 D.存储实现

> **19.每一个存储结点只含有一个数据元素,存储结点存放在连续的存储空间,另外有一组指明结点存储位置的表,该存储方式是( )存储方式。**  
> A.顺序 B.链式 C.索引 D.散列

> **20.算法能正确的实现预定功能的特性称为算法的( )**  
> A.正确性B.易读性C.健壮性D.高效性

> **21.算法在发生非法操作时可以做出处理的特性称为算法的( )**  
> A.正确性 B.易读性 C.健壮性 D.高效性

> **22.下列时间复杂度中最坏的是( )。**  
> A.O(1) B .O(n) C .O (log2n) D .(n)

> **23.在下面的程序段中,对x的赋值语句的频度为()**

for (i =1;i<;i ++)for ( =;j<n;j ++)a++;

> A .(2n) B .O (n) C .O (n^2) D .O (log2n)

#### 二、填空题 ####

> 1.常见的数据结构有\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_。  
> 2.算法的5个重要特性是有穷性、可行性、**。  
> 3.评价算法的优劣通常主要考虑算法的\_\_\_\_\_\_\_和\_\_\_\_\_\_\_这两方面。  
> 4.线性结构中元素之间存在\_\_\_\_\_\_关系,树形结构中元素之间存在\_\_\_\_\_\_\_\_关系,图形结构中元素之间存在\_\_\_\_\_\_关系。  
> 5.数据的存储结构又称为\_\_\_\_\_\_。  
> 6.数据结构定义为(D,R),其中D是数据的有限集合,R是D上的\_\_\_\_\_\_\_\_的有限集合。  
> 7.算法的空间复杂度是指该算法所耗费的，它是该算法求解问题规模n的函数。  
> 8.算法是一个\_\_\_\_\_\_\_\_\_的集合,算法效率的度量可以分为和  
> 9.若一个算法中的语句频度之和为T(n)=7n+4n2,则算法的时间复杂度为**\_\_\_\_。  
> 10.设有一组数据元素需存储,为了方便查找某元素,数据宜采用\_\_\_\_\_\_\_存储结构;为了方便插入与删除某元素,数据宜采用\_\_\_\_\_\_\_\_存储结构。

#### 三、判断题 ####

1.数据的逻辑结构与数据元素本身的内容和形式无关。  
2.一个数据结构是由一个逻辑结构和这个逻辑结构上一个基本运算集构成的整体。  
3.数据元素是数据的最小单位。  
4.数据的逻辑结构和数据的存储结构是相同的  
5.程序和算法原则上没有区别,所以在讨论数据结构时可以通用。  
6.从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。  
7.数据的存储结构是数据的逻辑结构的存储映像。

[Link 1]: https://blog.csdn.net/weixin_45926547/article/details/114367570
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]: /images/20221022/027677e19eed4d40b8ba3497ca3c810f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]: /images/20221022/b6ac49fdca0e4ff891caef168541726d.png
[20210318133044964.png]: /images/20221022/3acc3ffdbb574963b61a9ea39a2e6724.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 2]: /images/20221022/31643a26c71745e085cbc90bc4281e42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 3]: /images/20221022/d2152a1185bf4a2fa9a86fe419619947.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 4]: /images/20221022/4a381b56611c444597184019549c7a52.png
[20210318153412922.png]: /images/20221022/b05523aeaa28454ba20ff7d99837fae4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 5]: /images/20221022/4828fe3be7d94a92acf58bda4810fe21.png