本文目录导航：

• 什么是算法与数据结构
• 01 - 数据结构和算法的意识
• 什么是算法与数据结构

什么是算法与数据结构

算法是一系列处置疑问的明晰指令，能在有限期间内对给定输入发生所需输入。

若算法存在毛病或不实用于特定疑问，则无法获取有效处置。

不同的算法或许须要不同的期间和空间效率。

算法的关键特色包含：1. 有穷性：算法必需在有限步骤内成功。

2. 确切性：算法的每一步必需明白定义。

3. 输入：算法可有零个或多个输入以定义初始形态。

4. 输入：算法至少有一个输入，反映对输入的处置结果。

5. 可行性：算法能实践运转，且可经过有限次笔算成功。

计算机迷信家尼克劳斯·沃思的著述《数据结构十算法=程序》表现了算法在计算机迷信中的外围肠位。

数据结构是计算机组织和存储数据的方法，触及数据元素的逻辑相关和操作。

数据结构的选用对程序设计的效率和品质至关关键。

数据结构的钻研始于1968年，是计算机迷信的基础课程，触及数学、计算机配件和软件。

它不只是普通程序设计的基础，也是编译程序、操作系统、数据库系统等的关键。

计算机迷信中，消息处置依赖于消息的示意和结构。

数据元素是数据的基本单位，组合项和原子项造成了复杂的数据结构。

关键字用于识别数据元素，数据对象是性质相反的数据元素的汇合。

在处置疑问时，计算机须要阅历形象数学模型、设计算法和编程测试等步骤。

算法的选用和效率深受数据结构影响。

数据处置包含查找、拔出、删除等操作。

数据结构有逻辑结构、存储结构和运算三种方式。

逻辑结构定义数据元素之间的相关，存储结构触及数据的物理示意。

数据结构分为线性结构和非线性结构，如树形结构和图形结构。

存储结构包含顺序存储和链式存储等。

逻辑结构和存储结构是数据结构的两面，算法的选用和成功均依赖于它们。

01 - 数据结构和算法的意识

了解数据结构和算法的一些基本概念，关键把握期间复杂度的计算

数据结构是指一切数据元素以及数据元素之间的相关，可以看做是相互之间存在着某种特定相关的数据元素的汇合，即可以把数据结构看成是 带结构的数据元素的汇合 。

数据的逻辑结构是从逻辑相翻开形容数据的，经常将数据的逻辑结构简称为数据结构。

汇合：

树形结构：

图形结构：

逻辑结构在计算机中的存储方式。依赖于计算机言语

顺序存储结构：

链式存储结构：

索引存储结构：

散列（哈希）存储结构：

数据类型是一组性质相反的值的汇合和定义在此汇合上的一组操作的总称，数据类型是数据结构在计算机的详细表现。

留意：

算法是对特定疑问求解步骤的一种形容

个性：有穷性、确定性、可行性、有输入、有输入

算法设计好后，还须要剖析算法的优劣，从两方面思考

一个算法由管理结构和原操作造成，算法的运算期间取决于两者的综合成果，算法口头期间大抵为基本运算时所需期间与运转次数的乘积。

因此一个算法的口头效率可以由其最基本的运算的口头次数来权衡。

计算公式：T(n)=O(f(n))

说明：

留意：O 的作用在于只求出T(n)的最高阶项，疏忽低阶项和常数

O(1) 没有启动循环的算法中，基本运算次数与疑问规模有关，所以是常数

对数阶 O(log2n) 次数为x，而2的x次方等于n，那么就是对数阶

线性阶 O(n) 只要一层循环

平方阶 O(n^2)

立方阶 O(n^3) 三层循环，必需就是n^3了

排序： O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)

也叫加权平均期间复杂度，将口头的概率也参与计算。

是一种不凡的加权平均期间复杂度，把耗时多的操作摊派到耗时低的操作。

这个期间复杂度 其实是O(1),而不是O(n)

算法空间复杂度是指计算算法所需的存储空间， 其计算公式为S(n) = n(f(n)) 所以在调查算法的空间复杂度，关键思考算法口头所须要的暂时占用的存储空间大小的量度。

数组逆序,将一维v1.43数组a中的n个数逆序寄存在原数组中.

复杂度计算:

说明：

什么是算法与数据结构

算法（Algorithm）是一系列处置疑问的明晰指令，也就是说，能够对必定规范的输入，在有限期间内取得所要求的输入。

假设一个算法有毛病，或不适宜于某个疑问，口头这个算法将不会处置这个疑问。

不同的算法或许用不同的期间、空间或效率来成功雷同的义务。

一个算法的优劣可以用空间复杂度与期间复杂度来权衡。

算法可以了解为有基本运算及规则的运算顺序所造成的完整的解题步骤。

或许看成依照要求设计好的有限确实切的计算序列，并且这样的步骤和序列可以处置一类疑问。

一个算法应该具备以下五个关键的特色： 1、有穷性： 一个算法必需保障口头有限步之后完结； 2、确切性： 算法的每一步骤必需有确切的定义； 3、输入：一个算法有0个或多个输入，以描写运算对象的初始状况，所谓0个输入是指算法自身定除了初始条件； 4、输入：一个算法有一个或多个输入，以反映对输入数据加工后的结果。

没有输入的算法是毫有意义的； 5、可行性： 算法准则上能够准确地运转，而且人们用笔和纸做有限次运算后即可成功。

计算机迷信家尼克劳斯-沃思曾著过一本驰名的书《数据结构十算法= 程序》，可见算法在计算机迷信界与计算机运行界的位置。

数据结构是计算机存储、组织数据的方式。

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

理论状况下，精心选用的数据结构可以带来更高的运转或许存储效率。

数据结构往往同高效的检索算法和索引技术有关。

普通以为，一个数据结构是由数据元素依据某种逻辑咨询组织起来的。

对数据元素间逻辑相关的形容称为数据的逻辑结构；数据必需在计算机内存储，数据的存储结构是数据结构的成功方式，是其在计算机内的示意；此外探讨一个数据结构必需同时探讨在该类数据上口头的运算才有意义。

在许多类型的程序的设计中，数据结构的选用是一个基本的设计思考起因。

许多大型系统的结构阅历标明，系统成功的艰巨水平和系统结构的品质都重大的依赖于能否选用了最优的数据结构。

许多时刻，确定了数据结构后，算法就容易获取了。

有些时刻事件也会反上来，咱们依据特定算法来选用数据结构与之顺应。

不论哪种状况，选用适宜的数据结构都是十分关键的。

选用了数据结构，算法也随之确定，是数据而不是算法是系统结构的关键起因。

这种洞见造成了许多种软件设计方法和程序设计言语的发生，面向对象的程序设计言语就是其中之一。

在计算机迷信中，数据结构是一门钻研非数值计算的程序设计疑问中计算机的操作对象（数据元素）以及它们之间的相关和运算等的学科，而且确保经过这些运算后所获取的新结构依然是原来的结构类型。

“数据结构”作为一门独立的课程在国外是从1968年才开局设立的。

1968年美国唐·欧·克努特传授开创了数据结构的最后体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地论述数据的逻辑结构和存储结构及其操作的著述。

“数据结构”在计算机迷信中是一门综合性的专业基础课。

数据结构是介于数学、计算机配件和计算机软件三者之间的一门外围课程。

数据结构这一门课的内容不只是普通程序设计（特意是非数值性程序设计）的基础，而且是设计和成功编译程序、操作系统、数据库系统及其余系统程序的关键基础。

计算机是一门钻研用计算机启动消息示意和处置的迷信。

这外面触及到两个疑问： 消息的示意 消息的处置 而消息的示意和组又间接相关四处置消息的程序的效率。

随着计算机的遍及，消息量的参与，消息范畴的拓宽，使许多系统程序和运行程序的规模很大，结构又相当复杂。

因此，为了编写出一个“好”的程序，必需剖析待处置的对象的特色及各对象之间存在的相关，这就是数据结构这门课所要钻研的疑问。

妇孺皆知，计算机的程序是对消息启动加工处置。

在大少数状况下，这些消息并不是没有组织，消息（数据）之间往往具备关键的结构相关，这就是数据结构的内容。

数据的结构，间接影响算法的选用和效率。

计算机处置一个详细疑问时，大抵须要经过下列几个步骤：首先要从详细疑问中形象出一个适当的数学模型，而后设计一个解此数学模型的算法（Algorithm），最后编出程序、启动测试、调整直至获取最终解答。

寻求数学模型的实质是剖析疑问，从中提取操作的对象，并找出这些操作对象之间含有的相关，而后用数学的言语加以形容。

计算机算法与数据的结构亲密相关，算法无不依靠于详细的数据结构，数据结构间接相关到算法的选用和效率。

运算是由计算机来成功，这就要设计相应的拔出、删除和修正的算法 。

也就是说，数据结构还须要给出每种结构类型所定义的各种运算的算法。

数据是对主观事物的符号示意，在计算机迷信中是指一切能输入到计算机中并由计算机程序处置的符号的总称。

数据元素是数据的基本单位，在计算机程序中理论作为一个全体思考。

一个数据元素由若干个数据项组成。

数据项是数据的无法宰割的最小单位。

有两类数据元素：一类是无法宰割的原子型数据元素，如：整数5，字符 N 等；另一类是由多个款项造成的数据元素，其中每个款项被称为一个数据项。

例如形容一个在校生的消息的数据元素可由下列6个数据项组成。

其中的出身日期又可以由三个数据项：年、月和日组成，则称出身日期为组合项，而其它无法宰割的数据项为原子项。

关键字指的是能识别一个或多个数据元素的数据项。

若能起惟一识别作用，则称之为 主 关键字，否则称之为 次 关键字。

数据对象是性质相反的数据元素的汇合，是数据的一个子集。

数据对象可以是有限的，也可以是有限的。

数据处置是指对数据启动查找、拔出、删除、兼并、排序、统计以及便捷计算等的操作环节。

在早期，计算机关键用于迷信和工程计算，进入八十年代以后，计算机关键用于数据处置。

据有关统计资料标明，如今计算机用于数据处置的期间比例到达80%以上，随着期间的推移和计算机运行的进一步遍及，计算机用于数据处置的期间比例必将进一步增大。

数据结构是指同一数据元素类中各数据元素之间存在的相关。

数据结构区分为逻辑结构、存储结构（物理结构）和数据的运算。

数据的逻辑结构是对数据之间相关的形容，有时就把逻辑结构简称为数据结构。

逻辑结构方式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的相关的有限集。

数据元素相互之间的相关称为结构。

有四类基本结构：汇合、线性结构、树形结构、图状结构（网状结构）。

树形结构和图形结构全称为非线性结构。

汇合结构中的数据元素除了同属于一种类型外，别无其它相关。

线性结构中元素之间存在一对一相关，树形结构中元素之间存在一对多相关，图形结构中元素之间存在多对多相关。

在图形结构中每个结点的前驱结点数和后续结点数可以恣意多个。

数据结构在计算机中的示意（映像）称为数据的物理（存储）结构。

它包含数据元素的示意和相关的示意。

数据元素之间的相关有两种不同的示意方法：顺序映象和非顺序映象，并由此获取两种不同的存储结构：顺序存储结构和链式存储结构。

顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑相关由存储单元的邻接相关来表现，由此获取的存储示意称为顺序存储结构。

顺序存储结构是一种最基本的存储示意方法，理论借助于程序设计言语中的数组来成功。

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑相关是由附加的指针字段示意的。

由此获取的存储示意称为链式存储结构，链式存储结构理论借助于程序设计言语中的指针类型来成功。

索引存储方法：除建设存储结点消息外，还建设附加的索引表来标识结点的地址。

散列存储方法：就是依据结点的关键字间接计算出该结点的存储地址。

数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑相关）可以把数据结构分红线性结构和非线性结构。

线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。

线性表若驳回链式存储示意时一切结点之间的存储单元地址可延续可不延续。

逻辑结构与数据元素自身的方式、内容、相对位置、所含结点个数都有关。

算法的设计取决于数据（逻辑）结构，而算法的成功依赖于驳回的存储结构。

数据的运算是在数据的逻辑结构上定义的操作算法，如检索、拔出、删除、降级的排序等。