应用软件开发的基础知识-数据结构与算法

2023-11-18 10:01:30 浏览数 (2)

数据结构与算法

数据结构与算法是计算机科学的基础，是软件开发中必不可少的知识。对于应用开发人员来说，掌握数据结构与算法的基本概念和原理，以及常见数据结构和算法的应用场景，是十分必要的。

常用的数据结构

线性数据结构

  • 数组：数组是一种线性表，可以存储相同类型的多个元素，具有固定的长度。
  • 链表：链表是一种线性表，每个元素都有指向下一个元素的指针，具有可变的长度。
  • 栈：栈是一种先进后出的数据结构，只能在栈顶进行插入和删除操作。
  • 队列：队列是一种先进先出的数据结构，只能在队头进行插入操作，只能在队尾进行删除操作。

非线性数据结构

  • 树：树是一种非线性表，由节点和边组成，每个节点最多有两个子节点。
  • 图：图是一种非线性表，由顶点和边组成，任意两个顶点之间可以有一条边。

在应用开发中常用的常见数据结构及其应用场景：

数组：数组是线性的数据结构，可以用来存储有序的数据。数组的常见应用场景包括：

存储列表数据，例如商品列表、用户列表等。

存储排序后的数据，例如排序后的成绩单、电话簿等。

链表：链表是线性的数据结构，每个元素都包含一个指向下一个元素的指针。链表的常见应用场景包括：

存储有序或无序的数据，例如社交网络中的好友列表、消息列表等, 实现队列和栈等数据结构。

栈 ： 常用于存储需要先进后出的数据，例如浏览器的历史记录、函数调用栈等。

队列： 常用于存储需要先进先出的数据，例如打印机的打印队列、生产者消费者模型等。

树：树是一种非线性的数据结构，每个元素都包含一个或多个子元素。树的常见应用场景包括：存储层次数据，例如文件系统、目录结构，实现查找、排序等算法。例如文件系统、目录结构、组织结构等。

图：图是一种非线性的数据结构，每个元素都包含一个或多个邻接元素。图的常见应用场景包括：

存储路径数据，例如地图、交通路线等，社交网络、供应链等，实现图论算法，例如最短路径算法、最小生成树算法等。

常用的算法

  • 排序：排序是一种将数据按照特定顺序进行排列的过程。常见的排序算法有冒泡排序、选择排序、插入排序、归并排序、快速排序等。
  • 查找：查找是一种在数据集中找到满足特定条件的元素的过程。常见的查找算法有顺序查找、二分查找等。
  • 图算法：图算法是针对图的数据结构设计的算法。常见的图算法有最短路径算法、最小生成树算法、拓扑排序等。
  • 动态规划：动态规划是一种分治思想的算法，将一个复杂的问题分解为多个子问题，然后递归地求解子问题，最后将子问题的答案合并得到原问题的答案。
  • 分治算法：分治算法是一种将一个问题分解为多个子问题，然后递归地求解子问题，最后将子问题的答案合并得到原问题的答案。

常用算法的应用场景

  • 排序算法的应用场景:
    • 数据库：数据库中的数据需要按照特定的顺序进行排列，比如按照时间、大小、重要性等。
    • 操作系统：操作系统中的文件、进程等需要按照特定的顺序进行排列，比如按照创建时间、优先级等。
    • 搜索引擎：搜索引擎中的索引数据需要按照特定的顺序进行排列，比如按照搜索频率、相关性等。
  • 查找算法的应用场景: - 数据库：数据库中的数据需要快速查找，比如根据关键字查找数据记录。 - 操作系统：操作系统中的文件、进程等需要快速查找，比如根据文件名、进程号等查找。 - 搜索引擎：搜索引擎中的索引数据需要快速查找，比如根据关键字查找搜索结果。 图算法的应用场景
  • 图算法应用场景:
    • 地图导航：地图中的道路可以表示为图，最短路径算法可以用于计算从一个地点到另一个地点的最短路径。
    • 交通规划：交通网络可以表示为图，最短路径算法可以用于计算从一个地方到另一个地方的最短路径。
    • 社交网络：社交网络可以表示为图，最小生成树算法可以用于计算连接所有节点的最小权重边集。
  • 动态规划的应用场景
    • 最优化问题：动态规划可以用于解决很多最优化问题，比如背包问题、最长子序列问题等。
    • 编译器：动态规划可以用于编译器中的优化，比如代码序列化、常量折叠等。
    • 密码学：动态规划可以用于密码学的算法设计，比如哈希算法、加密算法等。
  • 分治算法的应用场景
    • 排序：分治算法可以用于实现快速排序、归并排序等高效的排序算法。
    • 查找：分治算法可以用于实现二分查找等高效的查找算法。
    • 图算法：分治算法可以用于实现最短路径算法、最小生成树算法等图算法。
    • 其他：分治算法还可以用于解决很多其他问题，比如求阶乘、计算斐波那契数列等。

算法复杂度参考

数据结构/算法

常见使用场景

使用范围

算法复杂度

数组

存储相同类型的多个元素

固定长度

O(1)

链表

存储需要动态添加或删除元素的数据

可变长度

O(1)

栈

存储需要先进后出的数据

固定长度

O(1)

队列

存储需要先进先出的数据

可变长度

O(1)

树

存储具有层次结构的数据

可变长度

O(log n)

图

存储具有连接关系的数据

可变长度

O(n)

排序

对数据进行排序

一般

O(n log n)

查找

在数据集中找到满足特定条件的元素

一般

O(n)

图算法

解决图中的问题

图

O(n^2)

动态规划

解决具有重复子问题的问题

一般

O(n)

分治算法

将一个复杂的问题分解为多个子问题

一般

O(n log n)

应用开发性能与效率

数据结构和算法的选择是影响应用程序性能的重要因素。在选择数据结构和算法时，要综合考虑以下因素：

  • 应用程序的需求：包括需要处理的数据类型、数据规模、数据访问频率等。
  • 数据的存储方式：不同的数据结构有不同的存储方式，对数据的访问效率也不同。
  • 算法的执行效率：不同的算法有不同的执行效率，算法的执行效率会影响应用程序的性能。

例如，如果应用程序需要频繁查找数据，可以使用二分查找算法来提高查找效率。如果应用程序需要存储大量数据，可以使用压缩算法来降低数据的空间占用。

应用开发资源与占用

数据结构和算法的选择也会影响应用程序的资源占用。在选择数据结构和算法时，要综合考虑应用程序的需求和性能，尽量选择既能满足需求又能降低资源占用的方案。

例如，链表的空间占用比数组更高，但链表的插入和删除操作比数组更高效。在选择数据结构和算法时，要根据应用程序的具体需求进行权衡。

以下是一些提高应用开发性能和效率的建议：

  • 使用合适的数据类型：使用合适的数据类型可以降低应用程序的空间占用。
  • 使用合适的数据结构：使用合适的数据结构可以降低应用程序的空间占用和操作时间。
  • 使用合适的算法：使用合适的算法可以降低应用程序的操作时间。
  • 使用异步操作：使用异步操作可以避免阻塞主线程，提高应用程序的响应速度。
  • 使用合适的框架和库：使用合适的框架和库可以提高开发效率和性能。

在应用开发过程中，要注意性能和效率的平衡。过分追求性能可能会导致资源占用增加，影响应用程序的稳定性。

常用语言算法库

按照类别，以 C、 Python 、 Go 、 Rust 、 JavaScript 语言为例，语言开发者(公司)和社区提供的算法函数库总结如下：

类别

C

Python

Go

Rust

JavaScript

数组

stdlib.h / int a10;

typing / list

stdlib / []int

std / Vec<T>

stdlib / Array.from()

链表

stdlib.h / struct node { int data; struct node *next; };

collections / collections.deque

stdlib / *linkedlist.List

std / LinkedList<T>

linkedlist / LinkedList()

栈

stdlib.h / struct stack { int top; int data10; };

collections / collections.deque

stdlib / *stack.Stack

std / Stack<T>

stack / Stack()

队列

stdlib.h / struct queue { int front; int rear; int data10; };

collections / collections.deque

stdlib / *queue.Queue

std / Queue<T>

queue / Queue()

树

stdlib.h / struct tree { int data; struct tree left; struct tree right; };

collections / collections.defaultdict

stdlib / *tree.Tree

std / Tree<T>

tree / Tree()

图

stdlib.h / struct graph { int vertex_num; int edge_num; struct edge *edges; };

networkx / import networkx as nx

stdlib / *graph.Graph

std / Graph<T>

graph / import graphlib as gl

排序

stdlib.h / qsort(arr, n, sizeof(int), cmp);

typing / sorted()

sort / sort.Slice()

std / sort::sort()

stdlib / Array.sort()

查找

stdlib.h / binary_search(arr, n, x);

typing / bisect.bisect_left()

sort / sort.Search()

std / std::search()

stdlib / Array.find()

图算法

stdlib.h / dfs(graph, start_vertex);

networkx / nx.dfs(graph, start_vertex)

graph / graph.DFS()

std / graph::dfs()

graph / gl.dfs(graph, start_vertex)

动态规划

stdlib.h / dpn = max(dpn-1, dpn-2);

tabulation / import tabulation as tb

std / dpn = max(dpn-1, dpn-2);

std / dpn = max(dpn-1, dpn-2);

std / dpn = max(dpn-1, dpn-2);

分治算法

stdlib.h / merge_sort(arr, start, end);

divide_and_conquer / import divide_and_conquer as dc

sort / sort.Slice()

std / sort::sort()

stdlib / Array.sort()

说明

表格中标记为 stdlib.h 的表示标准库头文件，需要包含到程序中。

表格中标记为 import 的表示第三方库，需要先安装。

表格中标记为 typing 的表示 Python 的类型注解，可以不用。

计算机基础 软件开发

0 人点赞