数据结构：为什么要学习数据结构、什么是数据结构基本概念、抽象数据类型、算法与算法分析

      博客中许多专业名词以及图源于《数据结构》严蔚敏版，《大话数据结构》这两本书，如果读者想要更加深入了解关于数据结构的内容可仔细阅读这两本书，这里只是简单总结下，写该博客的目的是为了学习及以后复习使用。

为什么要学习数据结构，它有什么用处？ ①首先，因为数据结构作为计算机专业的专业必修课程，是计算机考研的必考科目之一，如果打算报考计算机专业的研究生，你必须学好它；其次，数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一，想要顺利通过这些考试，你也必须学好它；最后，数据结构还是你打算今后学习计算专业其他课程的基础，如操作系统、编辑原理、数据库管理系统、软件工程、人工智能等。总而言之，你既然已经与计算机接轨就必须掌握好它。

②数据是计算机科学当中最关键的实体，而数据结构则可以将数据以某种组织形式存储，因此，数据结构的价值不言而喻。 无论你以何种方式解决何种问题，你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单，还是只是简单的电话簿问题。数据需要根据不同的场景，按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。好的数据结构与算法能够提升运行的效率，同样不好的数据结构与算法会多浪费空间与世界。 用处： (1)学习数据有效存储的方法        通过学习数据结构，更加准确和深刻地理解不同数据结构之间的共性和联系，学会选择和改进数据结构，高效地设计并实现各种算法，这才是数据结构的精髓。 (2)处理具有复杂关系的数据        现实中很多具有复杂关系的数据，无法通过简单的库函数调用实现。如同现在很多芯片高度集成，完全不需要芯片内部如何，直接使用就行了。但是，如果在现实中遇到一个复杂问题，一个芯片只能完成其中一个功能，难道要连接十几块芯片来解决这一个问题？这显然是不合适的，我们需要的是完成该复杂问题的一个芯片，因此需要运用所学的数据结构知识，高效处理具有复杂关系的数据。  

数据结构： 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

数据： 描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。 数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。 数据元素： 是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。 数据项： 一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。 数据对象： 是性质相同的数据元素的集合，是数据的子集。 数据结构： 是相互之间存在一种或多种特定关系的数据元素的集合。 其关系大致为：       举个例子来看：如图为一个结构体类型，结构体类型中的字符、整型等为数据，由该结构体类型定义出来的叫数据元素，用该数据类型定义的数组叫数据对象，每一个字段叫数据项。

逻辑结构： 指数据对象中数据元素之间的相互关系。 逻辑结构通常分为以下几种： (1)集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。 (2)线性结构：线性结构中的数据元素是一对一的关系。 (3)树形结构：树形结构中的数据元素之间存在一种一对多的关系。 (4)图形结构：图形结构的数据元素是多对多的关系。 物理结构： 指数据的逻辑结构在计算机中的存储形式。 (1)顺序存储结构：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。       简单来看，顺序存储结构就像排队占位，大家都按照顺序排好，每个人占一小段空间，谁也不能插队。我们之前学的数组就是这样的顺序存储结构。 (2)链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元是可以连续的，也可以不连续。       例如上面的排队问题，总是有人插队，也有人等不及离开，会出现新成员也会去除一部分成员，队伍结构时刻处于变化中。顺序存储就十分不方便了，此时我们采用链式存储结构。就像医院、银行等设置了排队系统，每个人到了先领一个号码，此时无论你的位置在哪里，只需要关系你前面一个号有没有被叫到，叫到了下一个就该你了。链式存储就十分灵活了，数据存储在哪里不重要，只要有一个指针存放了相应的地址就能找到它了。       逻辑结构是面向问题的，物理结构是面向计算机的，其基本目标就是将数据及其逻辑关系存储到计算机的内存中。  

什么是数据类型呢？ 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。 那么为什么需要数据类型呢？它有什么用？       就像我们住房子一样，都希望房子越大越好。但是没有钱，考虑房子是没有意义的。因此商品房推出了各种各样的房型，有别墅的，错层的，单间的，甚至出现了胶囊公寓，这就满足了不同人的需要。同样，在计算机中，内存也不是无线大的，你需要计算一个1+2=2，3+5=8这样的整型数字的加减乘除运算，显然不需要很大的内存空间。因此，就需要对数据类型分类，分出来多种数据类型，更好的利用它。       在C语言中，按照取值的不同，数据类型可以分两类： (1)原子类型：是不可以再分解的类型，包括整型、实型、字符型等。 (2)结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干个整型数据组成的。   那么为什么需要抽象数据类型呢？       无论什么计算机，什么计算机语言，大家都会面临着整数运算、实数运算、字符运算等操作，我们可以考虑把它们抽象出来。抽象是指抽取事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的细节，是对具体事务的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必须的信息。我们对已有的数据类型进行抽象，就有了抽象数据类型。 抽象数据类型（ADT）： 是指一个数学模型及定义在该模型上的一组操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 例如：各个计算机，不管是大型机、小型机、PC、平板电脑、PDA甚至智能手机都有“整数”类型，也需要整数间运算，那么整数就是一个抽象数据类型，尽管它在上面提到的这些在不同计算机中实现方法上可能不一样，但由于其定义的数学特性相同，在计算机编程者看来，它们都是相同的。因此，抽象的意义在于数据类型的数学抽象性。       一个抽象数据类型定义了：一个数据对象、数据对象中各元素之间的关系及对数据元素的操作。至于一个数据抽象数据类型到底需要哪些操作，只能由设计者根据实际需要来定。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立一个计算机能够处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。 抽象数据类型的标准格式：  

算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 此外，算法还具有下列5个重要特性： (1)有穷性： 一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。 (2)确定性： 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。 (3)可行性： 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有效次来实现的。 (4)输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。 (5)输出： 一个算法至少有一个或多个的输出，这些输出是同输入有着某些特定关系的量。   算法设计的要求：拥有正确性、可读性、健壮性、高效率和低存储量的特征。 (1)正确性： 指算法至少应该具有输出、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。 算法的“正确”通常在用法上有很大差别：大致分为下列4个层次。①要求最低，但是仅仅没有语法错误实在谈不上是好的算法；④最困难，我们几乎不可能逐一验证所有的输入都得到正确的结果。 ①算法程序没有语法错误。 ②算法程序对于合法的输入数据能够产生满足要求的输出结果。 ③算法程序对于非法的输入数据能够得出满足规格说明的结果。 ④算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。 (2)可读性：算法设计的另一目的是为了便于阅读、理解和交流。 (3)健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。 (4)时间效率高与低存储量需求：好的算法还应该具备时间效率高和存储量低的特点。   算法效率的度量方法： 1.事后统计方法：这种算法主要通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。 但这种方法有两个缺陷： ①必须先运行依据算法编制的程序。 ②所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。 2.事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。 经分析，我们发现，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： ①算法采用的策略、方法。 ②问题的输入规模。 ③书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低。 ④编译程序所产生的机器代码的质量。 ⑤机器指令执行的速度。         同一个算法用不同语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 算法的时间复杂度： 算法中基本操作执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T(n) = O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。 这样用大O()来体现算法时间复杂度的方法，我们称之为大O记法。一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。   推导大O阶方法： 这里就不一一举例子了：下面是常见的时间复杂度。 常见的时间复杂度所耗费的时间从小到大依次是： O(1)