备战软考Day02-数据结构与算法

1.基本概念与三要素

1.什么是数据

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

2.数据元素、数据项

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

例如：一波顾客就代表数据元素，号数，取号时间，就餐人数就称为数据项

3.数据结构

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

2.三要素：

• 逻辑结构

• • 集合：各个元素同属一个集合，别无其他关系。
  • 线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯前驱;除了最后一个元素，所有元素都有唯一后继。
  • 树形结构：数据元素之间是 一对多的关系。
  • 图状结构：数据元素之间是多对多的关系。

• 物理结构（存储结构）

• • 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
  • 链式存储：逻辑上相邻的元素在物理位置上可以不相邻
  • 索引存储：在存储元素信息的同时，还建立附加的索引表。
  • 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储

• 数据的运算：数据结构+算法

2.算法

1.五个特性

1. 有穷性:一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性:算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
3. 可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4. 输入:一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
5. 输出:一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

2.算法效率的度量

时间复杂度：时间开销与问题规模n之间的关系

空间复杂度：空间开销（内存开销）与问题规模n之间的关系

函数递归调用带来的内存开销：S(n) = O(n) 空间复杂度=递归调用的深度

3.线性表

1.定义

线性表是具有相同数据类型的n (n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为:

L=(a1, a2,..., ai,ai+1,. an)

几个概念:

ai是线性表中的“第i个”元素线性表中的位序。

a1是表头元素;an是表尾元素。

除第一个元素外，每个元素有且仅有一个直接前驱;除最后一个元素外每个元素有且仅有一个直接后继。

2.存储结构

3.插入删除操作

顺序存储：插入元素前要移动元素以挪出空的存储单元，然后再插入元素。删除元素时同样需要移动元素，以填充被删除元素的存储单元。

链式存储：

4.栈和队列

1.栈的定义：

线性表是具有相同数据类型的n (n20)个数据元素的有限序列，其中n为表长，当n=0时线 性表是一个空表。若用L命名线性表，则其一般表示为:

L=(a1, a2, ..., ai, ai+1,..,an)

栈(Stack)是只允许在一端进行插入或删除操作的线性表

2.队列的定义：

队列是一.种先进先出(FIFO)的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾(Rear)允许删除元素的一端称为队头(Front)。

3.循环队列：

5.串、数组、矩阵和广义表

1.串（String）定义：

串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为S ='a1 a2~~~ an'，其中S是串名，a1 a2 an是串值。

(1)空串:长度为零的串，空串不包含任何字符。

(2)空格串:由一个或多个空格组成的串。

(3)子串:由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。

(4)串相等:指两个串长度相等且对应位置上的字符也相同

(5)串比较:两个串比较大小时以字符的ASCI码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCI码值大者所在的串为大;若其中一个串先结束，则以串长较大者为大。

2、对串进行的基本操作有以下几种。

(1)赋值操作StrAssign(s,):将串t的值赋给串s。

(2)连接操作Concat(s,t):将串t接续在串s的尾部，形成一个新串

(3)求串长StrLength(s):返回串s的长度。

(4)串比较StrCompare(s,t):比较两个串的大小

(5)求子串SubString(,tart,len):返回串s中从start开始的、长度为len的字符序列。

3、串的存储结构

(1)串的顺序存储：定长存储结构

(2)串的链式存储：块链

子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。

4.数组

答：a+(2*5+3)*2=a+26

注：len代表字节长度

5.稀疏矩阵

使用代入法，就求出来答案为：A

6.广义表

答：1.长度：3，深度2 2.head(head(tail(LS1)))

6.树和二叉树

1.树的基本概念

2.树的遍历

3.反向构造二叉树

4.树转为二叉树

5.查找二叉树（二叉排序树）

6.构造霍夫曼树（最优）

7.线索二叉树

8.平衡二叉树

7.图

1.基本概念

1. 有向图
2. 无向图
3. 完全图:在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图。在有向图中,若每对顶点之间都有二条有向边相互连接,则称该图为完全图。
4. 度，入度与出度

2.存储结构（邻接矩阵）

3.存储结构（邻接表）

4.遍历

5.拓扑排序

6.最小生成树（普利姆算法）

普利姆算法（Prim's Algorithm）是一种用于在加权无向图中寻找最小生成树的贪心算法。最小生成树是指连接图中所有顶点的边的权重之和最小的树。普利姆算法通常用于那些边的权重各不相同的图。

普利姆算法的基本思想是从图中的任意一个顶点开始，逐渐构建最小生成树，每次迭代都选择与当前生成树连接权重最小的边，并将这条边及其对应的顶点加入到生成树中，直到所有顶点都被包含在生成树中。

7.最小生成树（克鲁斯卡尔算法）

克鲁斯卡尔算法（Kruskal's Algorithm）是一种用于在加权无向图中寻找最小生成树的贪心算法。这个算法的核心思想是先对图中的所有边按照权重进行排序，然后从最小的边开始选择，每次选择不会与已选择的边构成环的边，直到选择的边数达到顶点数减一为止。

8.查找

1.基本概念

1. 查找 --在数据集合中寻找满足某种条件的数据元素的过程称为查找。
2. 查找表(查找结构)--用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成。
3. 关键字 -- 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
4. 查找长度--在查找运算中，需要对比关键字的次数称为查找长度。
5. 平均查找长度(ASL,Average Search Length)--所有查找过程中进行关键字的比较次数的平均值。

2.顺序查找

顺序查找，又叫“线性查找”，通常用于线性表。

算法思想：从头到脚挨个找（反过来也ok）

3.折半查找

又称为：二分查找，仅适用于有序的顺序表。

mid，向下取整

4.分块查找

5.哈希表（散列表）

散列表(Hash Table)，又称哈希表、是一种数据结构，特点是:数据元素的关键字与其存储地址直接相关,

例:有一堆数据元素，关键字分别为{19,14,23,1,68,20,84,27,55,11,10,79}散列函数 H(key)=key%13

若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”

通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

解决方法：

• • 开放地址法
  • 链地址法
  • 再哈希法
  • 建立一个公共溢出区

9.排序

1.基本概念

排序:就是重新排列表中的元素，使表中的元素满足按关键字有序的过程

稳定与不稳定排序：1 3 6 4 1 如果排序完，前面的1仍然在后面的1前面，则为稳定排序

内部排序与外部排序

2.排序方法分类：

1.插入类排序：

直接插入排序：

希尔排序

2.交换类排序:

冒泡排序

快速排序

3.选择类排序:

简单选择排序

堆排序.

4.其他

归并排序

基数排序（又称为桶排序）

3.排序评价指标

10.算法设计与分析

1.分治法-分而治之

对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

要求:

• 该问题的规模缩小到一定的程度就可以容易地解决
• 该问题可以分解为若干个规模较小的相同问题。
• 利用该问题分解出的子问题的解可以合并为该问题的解
• 该问题所分解出的各个子问题是相互独立的。

一般来说分治算法在每一层递归上都有3个步骤。

(1)分解。将原问题分解成一系列子问题。

(2)求解。递归地求解各子问题。若子问题足够小，则直接求解。

(3)合并。将子问题的解合并成原问题的解

2.回溯法-深度优先搜索法

回溯法是种选优搜索法,按选优条件向前搜索,以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择这种走不通就退回再走的技术就是回溯法。

3.贪心法-局部最优

总是做出在当前来说是最好的选择，而并不从整体上加以考虑,它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。也常用于解决最优化的问题。

用贪心法求解的问题一般具有两个重要的性质。

(1)最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。

(2)贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。

4.动态规划法-整体最优

基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。

动态规划算法通常用于求解具有某种最优性质的问题，在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。

对一个给定的问题，若其具有以下两个性质，则可以考虑用动态规划法来求解。

(1)最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。

(2)重叠子问题。指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。

例题