数据结构与算法分析

1.在顺序表中插入或删除一个元素，需要平均移动(表中一半)元素，具体移动的元素个数与(表长和该元素在表中的位置)有关。

2.如果有两个数，每个数的所有约数(除它本身以外)的和正好等于对方，则称这两个数为互满数，求出3000内所有的互满数，并显示输出。

def Sum(n):

sum=0

for i in range(1,n):

if n%i==0:

sum+=i

return sum

print "互满数为："

for j in range(1,3000):

k=Sum(j)

if k>j and Sum(k)==j:

print j,"和",k

3.假设一棵二叉树的中序序为DCBGEAHFIJK和后序序列为DCEGBFHKJIA.请画出该树。

4.最短路径问题

最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。

迪杰斯特拉(Dijkstra)在做了大量观察后,首先提出了按路径长度递增序产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。

算法的基本思想是:把图中顶点集合分成两组，第一组为集合S，存放已求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是V-S(用U表示)，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个把U中的顶点加到S中，直到S中包含全部顶点，而U为空。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

(1)初始时，S只包含源点，S={v}，v的距离为0。U包含除v外的其他顶点，U中顶点的距离为顶点的权或∞ 。

(2)从U中选取一个距离最小的顶点k，把k加入到S中

(3)以k 作为新考虑的中间点，修改U中各顶点的距离。

(4)重复步骤(2)、(3)直到所有顶点都包含在S中。

时间复杂度：O(V^3)

//有权图的Dijikstra(遍历整个数组寻找最小路径顶点)

bool Dijikstra(int vertex){

//根据初始结点初始化距离数组与路径数组

for(int i = 0 ; i < this->Nv+1 ; i++){

//在构造函数里dist已经全部初始化为MAX

//G存在边时为权重，没有边时为MAX

this->dist[i] = this->G[vertex][i];

if(this->dist[i] < MAX){

this->path[i] = vertex;

}

}

this->dist[vertex] = 0;//初始结点的距离为０

this->collected[vertex] = 1;//初始结点标记为已收录

while(1){

//V是未被收录定点中dist最小者

int V = this->FindMinVertex();

if(V == -1){//未找到这样的V则跳出循环

break;

}

this->collected[V] = 1;// 标记为已经被收录

// 遍历图中每个顶点

for(int w = 1 ; w < this->Nv+1 ; w++){

//若w是V的邻接点且未被收录

if(this->collected[w] == 0 && this->G[V][w] < MAX){

if(this->G[V][w] < 0) { // 存在负边时

return false; // 结束算法

}

//若收录V使得dist[w]变小

if(this->dist[V] + this->G[V][w] < this->dist[w]){

//更新dist[w]

this->dist[w] = this->dist[V] = this->G[V][w];

this->path[w] = V;//更新路径

}

}

}

}

return true;

}

最短路径算法中的Floyd算法，这是针对多源最短路径的一个经典算法。

算法思想：

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)。

从任意节点i到任意节点j的最短路径不外乎2种可能，一是直接从i到j，二是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

时间复杂度：O(V^3)

算法过程：

1)首先把初始化距离dist数组为图的邻接矩阵，路径数组path初始化为-1。其中对于邻接矩阵中的数首先初始化为正无穷，如果两个顶点存在边则初始化为权重。

2)对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是就更新它。

状态转移方程为

如果 dist[i][k]+dist[k][j] < dist[i][j]

则 dist[i][j] = dist[i][k]+dist[k][j]

bool Floyd(){

for(int k = 1 ; k < this->Nv+1 ; k++){ //k代表中间顶点

for(int i = 1 ; i < this->Nv+1 ; i++){//i代表起始顶点

for(int j = 1 ; j < this->Nv+1 ; j++){//j代表终点

if(this->dist[i][k] + this->dist[k][j] < this->dist[i][j]){

this->dist[i][j] = this->dist[i][k] + this->dist[k][j];

if(i == j && this->dist[i][j] < 0){//发现了负值圈

return false;

}

this->path[i][j] = k;

}

}

}

}

return true;

}

5.图的定义

6.图的存储

邻接矩阵：一维数组存储顶点信息，二维数组存储边或弧的信息

缺点：当边或弧的数目较少时，会造成较大的存储空间的浪费

邻接表：一维数组存储顶点信息，每个顶点的所有邻接点用单链表存储

缺点：对有向图的处理，有时需要再建立一个逆邻接表

7.图的遍历

7.1深度优先遍历

GRAPH = {

'A': ['B', 'F'],

'B': ['C', 'I', 'G'],

'C': ['B', 'I', 'D'],

'D': ['C', 'I', 'G', 'H', 'E'],

'E': ['D', 'H', 'F'],

'F': ['A', 'G', 'E'],

'G': ['B', 'F', 'H', 'D'],

'H': ['G', 'D', 'E'],

'I': ['B', 'C', 'D'],

}

Searched = set() # 记录访问过的顶点

def dfs(graph, start):

if start not in Searched:

print(start)

Search.add(start)

for node in graph[start]:

if node not in Searched:

dfs(graph, node)

def bfs(graph, start):

queue = []

queue.append(start)

Searched = set()

while queue:

cur_node = queue.pop(0) # 队列 FIFO

if cur_node not in Searched:

print(cur_node)

Searched.add(cur_node)

for node in graph[cur_node]:

queue.append(node)

8.二分查找

# 返回 x 在 arr 中的索引，如果不存在返回 -1defbinarySearch(arr, l, r, x):

# 基本判断if r >= l: mid = int(l + (r - l)/2) # 元素整好的中间位置 if arr[mid] == x: return mid # 元素小于中间位置的元素，只需要再比较左边的元素 elif arr[mid] > x: return binarySearch(arr, l, mid-1, x) # 元素大于中间位置的元素，只需要再比较右边的元素 else: return binarySearch(arr, mid+1, r, x) else: # 不存在 return -1

# 测试数组

arr = [2, 3, 4, 10, 40] x = 10

# 函数调用

result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1: print("元素在数组中的索引为 %d" % result)

else: print("元素不在数组中")

9.归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

9.1. 基本思想

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

(1)分解(Divide)：将n个元素分成个含n/2个元素的子序列。

(2)解决(Conquer)：用合并排序法对两个子序列递归的排序。

(3)合并(Combine)：合并两个已排序的子序列已得到排序结果。

9.2. 实现逻辑

9.2.1 迭代法

① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

② 设定两个指针，最初位置分别为两个已经排序序列的起始位置

③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

④ 重复步骤③直到某一指针到达序列尾

⑤ 将另一序列剩下的所有元素直接复制到合并序列尾

9.2.2 递归法

① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素

② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

③ 重复步骤②，直到所有元素排序完毕

9.2.3. 动图演示

具体的我们以一组无序数列｛14，12，15，13，11，16｝为例分解说明，如下图所示：

上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

10.时间复杂度，空间复杂度，稳定性

辅助记忆

★时间复杂度记忆

▷冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n2)O(n2)(一遍找元素O(n)O(n)，一遍找位置O(n)O(n))

▷快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)O(nlogn)(一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn))

★稳定性记忆-“快希选堆”(快牺牲稳定性)

▷排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

11.常用的排序方法

1 冒泡排序

冒泡排序从小到大排序：一开始交换的区间为0~N-1，将第1个数和第2个数进行比较，前面大于后面，交换两个数，否则不交换。再比较第2个数和第三个数，前面大于后面，交换两个数否则不交换。依次进行，最大的数会放在数组最后的位置。然后将范围变为0~N-2，数组第二大的数会放在数组倒数第二的位置。依次进行整个交换过程，最后范围只剩一个数时数组即为有序。

代码：

def bubbleSort(arr):

n = len(arr)

# 遍历所有数组元素

for i in range(n):

for j in range(0, n-i-1):

if arr[j] > arr[j+1] :

arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("排序后的数组:")for i in range(len(arr)):

print ("%d" %arr[i])

2 选择排序

选择排序从小到大排序：一开始从0~n-1区间上选择一个最小值，将其放在位置0上，然后在1~n-1范围上选取最小值放在位置1上。重复过程直到剩下最后一个元素，数组即为有序。

代码：

def selection_sort(arr):

# 第一层for表示循环选择的遍数

for i in range(len(arr) - 1):

# 将起始元素设为最小元素

min_index = i

# 第二层for表示最小元素和后面的元素逐个比较

for j in range(i + 1, len(arr)):

if arr[j] < arr[min_index]:

# 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标

min_index = j

# 查找一遍后将最小元素与起始元素互换

arr[min_index], arr[i] = arr[i], arr[min_index]

return arr

selection_sort([11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22])

#返回结果 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

3 插入排序

插入排序从小到大排序：首先位置1上的数和位置0上的数进行比较，如果位置1上的数大于位置0上的数，将位置0上的数向后移一位，将1插入到0位置，否则不处理。位置k上的数和之前的数依次进行比较，如果位置K上的数更大，将之前的数向后移位，最后将位置k上的数插入不满足条件点，反之不处理。

代码：

def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >=0 and key < arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = key arr = [12, 11, 13, 5, 6]

insertionSort(arr)

print ("排序后的数组:")

for i in range(len(arr)): print ("%d" %arr[i])

4 归并排序

归并排序从小到大排序：首先让数组中的每一个数单独成为长度为1的区间，然后两两一组有序合并，得到长度为2的有序区间，依次进行，直到合成整个区间。

代码：

def merge(arr, l, m, r): n1 = m - l + 1 n2 = r- m #创建临时数组 L = [0] * (n1) R = [0] * (n2) # 拷贝数据到临时数组 arrays L[] 和 R[] for i in range(0 , n1): L[i] = arr[l + i] for j in range(0 , n2): R[j] = arr[m + 1 + j] # 归并临时数组到 arr[l..r] i = 0 # 初始化第一个子数组的索引 j = 0 # 初始化第二个子数组的索引 k = l # 初始归并子数组的索引 while i < n1 and j < n2 : if L[i] <= R[j]:arr[k] = L[i]i += 1 else:arr[k] = R[j]j += 1 k += 1 # 拷贝 L[] 的保留元素 while i < n1: arr[k] = L[i] i += 1 k += 1 # 拷贝 R[] 的保留元素 while j < n2: arr[k] = R[j] j += 1 k += 1 def mergeSort(arr,l,r): if l < r: m = int((l+(r-1))/2) mergeSort(arr, l, m) mergeSort(arr, m+1, r) merge(arr, l, m, r) arr = [12, 11, 13, 5, 6, 7] n = len(arr) print ("给定的数组")

for i in range(n): print ("%d" %arr[i]), mergeSort(arr,0,n-1)

print ("\n\n排序后的数组")

for i in range(n): print ("%d" %arr[i])

5 快速排序

快速排序从小到大排序：在数组中随机选一个数(默认数组首个元素)，数组中小于等于此数的放在左边，大于此数的放在右边，再对数组两边递归调用快速排序，重复这个过程。

代码：

def partition(arr,low,high): i = ( low-1 ) # 最小元素索引 pivot = arr[high] for j in range(low , high): # 当前元素小于或等于 pivot if arr[j] <= pivot:i = i+1 arr[i],

arr[j] = arr[j],

arr[i]

arr[i+1],

arr[high] = arr[high],

arr[i+1] return ( i+1 ) #arr[]->排序数组#low->起始索引#high-> 结束索引 # 快速排序函数def quickSort(arr,low,high): if low < high: pi = partition(arr,low,high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quickSort(arr,0,n-1)

print ("排序后的数组:")

for i in range(n): print ("%d" %arr[i])

6 堆排序

6.1 过程

堆排序从小到大排序：首先将数组元素建成大小为n的大顶堆，堆顶(数组第一个元素)是所有元素中的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素建立成大顶堆，再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。注：完全二叉树

假设二叉树深度为n，除了第n层外，n-1层节点都有两个孩子，第n层节点连续从左到右。如下图

注：大顶堆

大顶堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值。

即，根节点是堆中最大的值，按照层序遍历给节点从1开始编号，则节点之间满足如下关系：(1<=i<=n/2)

代码：

defheapify(arr, n, i):

largest = i

l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 if l < nandarr[i] < arr[l]: largest = l if r < nandarr[largest] < arr[r]: largest = r if largest != i:

#交换 arr[i],arr[largest] = arr[largest],arr[i] heapify(arr, n, largest) defheapSort(arr): n = len(arr) # Build a maxheap. foriinrange(n, -1, -1): heapify(arr, n, i) # 一个个交换元素 foriinrange(n-1, 0, -1):

# 交换 arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]

heapSort(arr)n = len(arr)

print("排序后")

for i in range(n): print("%d" %arr[i])

7 希尔排序

7.1 过程

希尔排序是插入排序改良的算法，希尔排序步长从大到小调整，第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换，直至步长为1，步长选择是关键。

7.2 动图

代码：

def shellSort(arr): n = len(arr) gap = int(n/2) while gap > 0: for i in range(gap,n): temp = arr[i] j = i while j >= gap and arr[j-gap] >temp: arr[j] = arr[j-gap] j -= gap arr[j] = temp gap = int(gap/2) arr = [ 12, 34, 54, 2, 3] n = len(arr) print ("排序前:")

for i in range(n): print(arr[i]), shellSort(arr) print ("\n排序后:")

for i in range(n): print(arr[i])

8 基数排序

8.1 过程

基数排序是基于数据位数的一种排序算法。

它有两种算法

①LSD–Least Significant Digit first 从低位(个位)向高位排。

②MSD– Most Significant Digit first 从高位向低位(个位)排。

时间复杂度O(N*最大位数)。

空间复杂度O(N)。

8.2 图解

对a[n]按照个位0~9进行桶排序：

对b[n]进行累加得到c[n]，用于b[n]中重复元素计数

！！！b[n]中的元素为temp中的位置！！！跳跃的用++补上：

temp数组为排序后的数组，写回a[n]。temp为按顺序倒出桶中的数据(联合b[n],c[n],a[n]得到)，重复元素按顺序输出：

12. 动态规划法与分治法的区别：

1．共同点：  

将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的

解得到原问题的解。 

2. 不同点： 

○1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。 

○2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低 

二、动态规划法与贪心法的区别 

1、共同点：  

都要求问题具有最优子结构性质。 

2、不同点： 

○1求解方式不同：  

动态规划法：自底向上；具有最优子结构性质的问题有些只能用动态规划法，

有些可用贪心法。贪心法：自顶向下； ○2对子问题的依赖不同： 

动态规划法：依赖于各子问题的解，所以应使各子问题最优，才能保证整体最优；贪心法：依赖于过去所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解。

如果喜欢平台中的文章，认为对您复习有指导和帮助的话，请动动你的小指头。点击下方【喜欢作者】，给个赞赏以资鼓励，让我再接再厉。