复习整理序言及数据结构绪论

柔情只为你懂 2023-10-08 13:05 35阅读 0赞

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

> If you give someone a program, you will frustrate them for a day; if  
> you teach themhow to program, you will frustrate them for a  
> lifetime.  
> (如果你交给某人一个程序，你将折磨他一整天;如果你教某人如何编写程序，你将折磨他一辈子。)

随着工作的不断深入，越发的感觉算法与数据结构的重要性，在工作闲暇之余刷算法的同时，也为没时间复习数据结构这门课懊恼不已，特在此立下flag

> 利用碎片化的时间，将这门课完整的整理一遍！

当然，只凭大脑记忆是很难完整的归纳总结整理复习的，在此特意买了本大话数据结构用于辅导记忆  
然后。。。。。发现这本书他喵的是C语言写的，不是Java~~~~~~不过也没关系，辅助而已，不慌·······整体上这门课还是学的挺好的，大学时还考过这门课的第一名呢

## 正文部分： ##

数据结构是计算机专业的基础课程，非科班出身的程序员可能都没听说过这门课程，这是一门**研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科**，这是一个程序员走向巅峰的必备之路，也是一门不太容易学好的课，里面有很多费脑子的东西，但如果系统的进行学习，相比较学习编码的难度，这个难度就显得不那么困难了。

### 数据结构的起源 ###

早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的，所以计算机解决问题，应该是先从具体问题中抽象出一个适当的数据模型，设计出一个解此数据模型的算法，然后再编写程序，得到一个实际的软件。  
  可现实中，我们更多的不是解决数值计算的问题，而是需要一些更科学有效的手段（比如表、树和图等数据结构)的帮助，才能更好地处理问题。所以数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。  
  1968年，美国的高德纳（Donakd E. Knuth)教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中,较系统地阐述了数据的逻辑结构和存储结构及其操作，开创了数据结构的课程体系。同年，数据结构作为一门独立的课程,在计算机科学的学位课程中开始出现。也就是说，那之后计算机相关专业的学生开始接受《数据结构》的“折磨”——其实应该是享受才对。  
  之后，70年代初，出现了大型程序，软件也开始相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视“数据结构”,认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。可见，数据结构在程序设计当中占据了重要的地位。

#### 1基本概念和术语 ####

说到数据结构是什么，我们得先来谈谈什么叫数据。  
  正所谓“巧妇难为无米之炊”，再强大的计算机，也是要有“米”下锅才可以干活的,否则就是一堆破铜烂铁。这个“米”就是数据。

##### 1.1数据 #####

**数据:是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合**。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。  
  比如我们现在常用的搜索引擎，一般会有网页、MP3、图片、视频等分类。MP3就是声音数据，图片当然是图像数据，视频就不用说了，而网页其实指的就是全部数据的搜索，包括最重要的数字和字符等文字数据。  
  也就是说，我们这里说的数据，其实就是符号，而且这些符号必须具备两个前提:

*  可以输入到计算机中。
 *  能被计算机程序处理。

>   对于整型、实型等数值类型，可以进行数值计算。  
>   对于字符数据类型，就需要进行非数值的处理。而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。

##### 1.2数据元素 #####

数据元素:是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。  
  比如，在人类中,什么是数据元素呀?当然是人了。  
  畜类呢?哈，牛、马、羊、鸡、猪、狗等动物当然就是禽类的数据元素。

##### 1.3数据项 #####

**数据项:一个数据元素可以由若干个数据项组成**。  
  比如人这样的数据元素，可以有眼、耳、鼻、嘴、手、脚这些数据项，也可以有姓名、年龄、性别、出生地址、联系电话等数据项，具体有哪些数据项，要视你做的系统来决定。  
  **数据项是数据不可分割的最小单位**。在数据结构这门课程中，我们把数据项定义为最小单位，是有助于我们更好地解决问题。所以，记住了，数据项是数据的最小单位。但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。就像我们讨论一部电影时，是讨论这部电影角色这样的“数据元素”，而不是针对这个角色的姓名或者年龄这样的“数据项”去研究分析。

##### 1.4数据对象 #####

**数据对象:是性质相同的数据元素的集合，是数据的子集**。  
  什么叫性质相同呢，是指数据元素具有相同数量和类型的数据项，比如，还是刚才的例子，人都有姓名、生日、性别等相同的数据项。  
  既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性质,在不产生混淆的情况下,我们都将数据对象简称为数据。  
  好了，有了这些概念的铺垫，我们的主角登场了。  
  说了数据的定义，那么数据结构中的结构又是什么呢?

##### 1.5数据结构 #####

结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。严格点说，结构是指各个组成部分相互搭配和排列的方式。在现实世界中,**不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构**。那数据结构是什么?

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

在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式。  
  为编写出一个“好”的程序，必须分析待处理对象的特性及各处理对象之间存在的关系。这也就是研究数据结构的意义所在。  
  定义中提到了一种或多种特定关系，具体是什么样的关系，这正是我们下面要讨论的问题。

#### 2逻辑结构与物理结构 ####

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

##### 2.1逻辑结构 #####

逻辑结构:**是指数据对象中数据元素之间的相互关系**。其实这也是我们今后最需要关注的问题。逻辑结构分为以下四种:

1.  集合结构  
    集合结构:**集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系**。各个数据元素是“平等”的，它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合。
2.  线性结构  
    线性结构:线性结构中的数据元素之间是一对一的关系
3.  树形结构  
    树形结构:树形结构中的数据元素之间存在一种一对多的层次关系
4.  图形结构  
    图形结构:图形结构的数据元素是多对多的关系

##### 2.2物理结构 #####

说完了逻辑结构，我们再来说说数据的物理结构（很多书中也叫做存储结构，你只要在理解上把它们当一回事就可以了)。  
  **物理结构:是指数据的逻辑结构在计算机中的存储形式**。  
  数据是数据元素的集合，那么根据物理结构的定义，实际上就是如何把数据元素存储到计算机的存储器中。存储器主要是针对内存而言的，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。  
  数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最为关键的，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。  
  数据元素的存储结构形式有两种:顺序存储和链式存储。

1.  顺序存储结构  
    顺序存储结构:**是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的**。

> 这种存储结构其实很简单，说白了，就是排队占位。大家都按顺序排好，每个人占一小段空间，大家谁也别插谁的队。我们之前学计算机语言时,数组就是这样的顺序存储结构。当你告诉计算机，你要建立一个有9个整型数据的数组时,计算机就在内存中找了片空地，按照一个整型所占位置的大小乘以9，开辟一段连续的空间，于是第一个数组数据就放在第一个位置，第二个数据放在第二个，这样依次摆放。

1.  链式存储结构  
      如果就是这么简单和有规律，一切就好办了。可实际上，总会有人插队，也会有人要上厕所、有人会放弃排队。所以这个队伍当中会添加新成员，也有可能会去掉老元素，整个结构时刻都处于变化中。显然，面对这样时常要变化的结构,顺序存储是不科学的。那怎么办呢?  
      现在如银行、医院等地方，设置了排队系统，也就是每个人去了，先领一个号，等着叫号，叫到时去办理业务或看病。在等待的时候，你爱在哪在哪，可以坐着、站着或者走动，甚至出去逛一圈，只要及时回来就行。你关注的是前一个号有没有被叫到，叫到了,下一个就轮到了。  
      **链式存储结构:是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的**。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。  
      显然，链式存储就灵活多了,数据存在哪里不重要，只要有一个指针存放了相应的地址就能找到它了。  
      之前香港有部电影叫《无间道》，还有部电视剧叫《潜伏》，都很火，不知道大家有没有看过。大致说的是，某一方潜伏在敌人的内部，进行一些情报收集工作。为了不暴露每个潜伏人员的真实身份，往往都是单线联系，只有上线知道下线是谁，并且是通过暗号来联络。正常情况下，情报是可以顺利地上传下达的，但是如果某个链条中结点的同志牺牲了，那就麻烦了，因为其他人不知道上线或者下线是谁，后果就很严重。比如在《无间道》中，梁朝伟是警方在黑社会中的卧底，一直是与黄秋生扮演的警官联络，可当黄遇害后，梁就无法证明自己是一个警察。所以影片的结尾，当梁朝伟用枪指着刘德华的头说,“对不起，我是警察。”刘德华马上反问道:“谁知道呢?”是呀，当没有人可以证明你身份的时候，谁知道你是谁呢?影片看到这里,多少让人有些唏嘘感慨。这其实就是链式关系的一个现实样例。  
      逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。