-
计算机的发展与用途：
- 早期的计算机：最初，计算机主要是用来进行数学运算，像是加减乘除这种“数值计算”。它们主要用在科学研究、工程计算等需要大量数字计算的领域。
- 现在的计算机：现代的计算机用途广泛，已经不仅仅局限于处理数字。它们还处理许多其他类型的数据，比如文字、表格、图片等。这些数据往往有着一定的结构和联系，比如文字是按照顺序排列的，表格里的数据是按照行和列组织的，图片是由像素构成的。
-
数据的联系和组织：
- 数据之间通常存在某种关系，比如一篇文章里的文字是按照顺序排列的，表格里的数据之间有行和列的对应关系。这些关系帮助我们理解和处理数据。
- 合理组织数据：为了有效处理这些数据，我们需要先弄清楚数据之间的关系，并合理地组织它们。比如说，如果我们要在一篇文章里查找某个词，提前把文字按顺序组织好会让查找变得更快、更高效。
-
数据结构的作用：
- 数据结构就是研究如何有效地组织和处理这些数据的学问。简单来说，数据结构帮助我们回答这样的问题：我们如何才能把数据安排得更合理，以便更快速地处理它们？
- 设计高效的算法：数据结构的研究也包括设计处理这些数据的方法，即“算法”。好的数据结构可以让算法运行得更快，消耗更少的资源。
-
本章内容简介：
- 这一章将会介绍一些关于数据结构的基本概念，比如什么是数组、链表、树等不同的数据组织方式。
- 还会讨论如何分析这些算法的效率，帮助我们选择最合适的方法来解决问题。
学习更多嵌入式电子知识，C语言编程技术，欢迎抖音扫码关注
一.数据结构的研究内容
1.数值计算：
- 抽象数学模型：首先，需要从实际问题中抽象出一个数学模型。这就像是把现实问题简化成数学问题，用数学公式来表示。
- 设计算法：接下来，设计一个算法，也就是一系列步骤，来解决这个数学问题。
- 编写程序：然后，把这个算法写成计算机程序，让计算机来执行。
- 测试和调试：最后，通过测试和调试，确保程序可以正确解决问题。
举个例子：
- 全球天气预报：需要解决的数学模型是球面坐标系下的二阶椭圆偏微分方程。这听起来复杂，但实际上就是通过一组复杂的数学公式来预测天气变化。
- 人口增长预测：对应的数学模型是常微分方程，这种方程可以用来预测未来人口的增长趋势。
解决这些数学方程的算法属于计算数学的研究范围，常见的算法有高斯消元法、差分法、有限元法等。
2.非数值计算：
- 与数值计算不同，非数值计算的问题无法用数学方程来表示。这类问题更多地涉及数据结构的研究。数据结构研究的是如何高效地存储和操作数据，而不是通过数学公式来解决问题。
3.案例
下面通过几个案例来提前大概看一下几种常见的数据结构
3.1.案例1
学生学籍管理系统是高等院校用来统一管理学生信息的一个计算机系统。通过这个系统，学校可以方便地记录和查找学生的基本信息，比如学号、姓名、性别、籍贯、专业等。
- 存储学生信息
- 学生的所有基本信息都会被存储在一个叫做“学生基本信息表”的数据库表中。
- 每个学生的信息都会占据表中的一行，类似于一个“档案”，包括学号、姓名、性别、籍贯、专业等信息。
- 信息顺序存放
- 每个学生的信息记录按照一定的顺序排列，比如按照学号的大小、入学时间等。这些记录形成了一种“线性序列”。
- 这种“线性关系”意味着学生的信息是按顺序依次存放的，就像一列火车车厢一个接一个排列。
- 查找信息
- 由于学生的信息是按照一定的顺序排列的，当学校需要查找某个学生的信息时，可以通过系统快速找到这个学生的记录。
线性表
- 线性表的定义
线性表是一种数据结构，其中的元素按照线性顺序排列。
- 应用场景
诸如：“学生学籍管理系统”、“图书馆的书目管理系统”和“库存管理系统”，都是使用线性表来管理数据的例子。比如，在图书馆中，书籍可以按一定顺序（例如书名、作者）排列，这样便于查找和管理。
- 操作类型
在处理这些线性表时，计算机通常需要进行几种基本操作：
- 查找：找到某个特定的元素，比如找一本书。
- 插入：在表中增加一个新元素，例如新进的一本书。
- 删除：从表中移除一个元素，比如借出一本书后将其从系统中删除。
3.2.案例2
- 人机对弈的基本原理：
- 对弈策略的存储：计算机能够与人下棋，是因为事先把各种可能的棋局变化和策略都存储在计算机中。换句话说，计算机已经“知道”在不同情况下该如何下棋。
- 棋局的变化：在下棋的过程中，每一步都会形成一个新的棋盘布局。不同的布局意味着棋局朝不同的方向发展。这就像是从一个点开始，往不同的方向延伸出许多可能的路径。
- 用“树”来表示棋局：
- 树结构的概念：可以把棋局的发展想象成一棵“倒长的树”。树的根部是游戏的起始状态（比如井字棋的空棋盘），每一步棋都像是树的分枝，从根部向外扩展，直到棋局结束。树的叶子就是终局状态，比如一方获胜、平局或是棋盘被填满。
- 树结构的特点：在这棵树中，每一个节点代表一种棋盘布局，而从一个节点到另一个节点的路径代表下一步棋的选择。最终，整场游戏就变成了从根到叶子的一条路径。
1. 棋局的开始和发展
想象一下我们在玩井字棋。游戏一开始，棋盘是空的（没有棋子）。这是游戏的起点，也就是所谓的“根节点”。
2. 每一步都是一次选择
当你下第一步棋时，比如你选择把“X”放在中间，那么棋盘的状态就改变了。这时，棋盘上出现了一个“X”在中间的状态。接下来，轮到对手下棋，对手有可能在任何一个空位放“O”，这又会形成一个新的棋盘状态。
3. 用“树”来表示所有可能的情况
我们可以用一个“树”结构来表示这个过程。树的根是游戏的初始状态（空棋盘）。从根开始，每一步下棋会产生一个新节点，这个节点代表一个新的棋盘状态。这样，每一次新的选择（比如选择下在中间或角落）就像从树的一个分支向下生长出新的分支。
- 根节点（空棋盘）：游戏的起点。
- 分支节点：每一次下棋后的新棋盘状态。
- 叶子节点：当游戏结束（比如某一方获胜或平局）时，这就是树的最末端，没有更多的下棋选择了。
4. 计算机的决策过程
计算机会从“树”的根节点开始，沿着每一条可能的路径往下走，看每一步棋的可能结果。它会考虑所有可能的棋盘状态（树的每一个节点），并评估哪条路径最有可能赢（或者最不可能输）。通过这种方式，计算机能够选择最优的下一步棋。
5. 简单总结
- 树的根：游戏开始的初始状态（空棋盘）。
- 树的枝干：每一步棋形成的新状态。
- 树的叶子：游戏结束的状态（胜利、失败或平局）。
整个树就像是一个地图，指引计算机从游戏的开始到结束，每一条路径（从根到叶子）代表一次完整的游戏过程。通过分析这些路径，计算机可以决定如何下棋才能赢得比赛。
- 树结构的应用：
- 计算机处理：在计算机处理这种棋局问题时，实际上是在处理一棵树。计算机会分析这棵树的各种可能路径，找出最优的下棋策略。
- 类似的应用：树结构不仅用于棋类对弈，还广泛应用于其他领域，比如计算机的文件系统（文件夹和文件的层次关系）、公司组织结构等。它们的共同特点是存在“层次关系”，即一个对象可以有多个子对象，而这些子对象之间是上下级的关系。
- 主要操作：
- 查找：寻找树中某个节点（比如某个棋局）的位置。
- 插入：在树中增加一个新的节点（比如下一步棋局）。
- 删除：从树中移除一个节点（比如撤销一步棋）。
- 总结：
树结构是一种强大的数据表示方式，在人机对弈中，它帮助计算机处理复杂的棋局变化，使得计算机能够灵活应对人类的各种下棋策略。这种树结构还被广泛应用于其他需要处理层次关系的场景中。
3.3.案例3
最短路径问题
- 问题描述
假设你要从城市A到城市B旅行，但有多条路线可以选择，每条路线的交通费用不同。你想找到一条花费最少的路线。那么，如何做出最优选择呢？
- 抽象成“图”的问题
为了更好地理解和解决这个问题，我们可以用“图”的结构来表示：
- 顶点（节点）：图中的每个顶点代表一个城市。例如，城市A和城市B就是两个顶点。
- 边（连线）：顶点之间的边代表城市之间的道路或航线。每条边都有一个“权值”，这个权值就是两个城市之间的交通费用。
- 有向图：如果两座城市之间的道路是单向的（比如从A到B有路，但从B到A没有路），那么这条边就是有方向的，这样的图就叫“有向图”。
- 解决最短路径问题
我们要做的就是在这个图中找到从城市A到城市B的所有可能路径，然后计算每条路径上所有边（交通费用）的总和，选择其中总和最小的一条路径，这就是最短路径。
假设从城市A到城市B有两条路：
- 路线1经过城市C，总费用是A到C的费用加上C到B的费用。
- 路线2是直接从A到B的费用。
- 数学模型和算法
在计算机科学中，我们把这个问题用“图结构”来表示，然后使用专门的算法来计算最短路径。例如，常用的算法有Dijkstra算法和Bellman-Ford算法。
- 图结构的应用
这种图结构不仅能用来解决城市间最短路径的问题，还能应用在许多其他领域，比如：
- 网络工程：确定从一个网络节点到另一个节点的最快数据传输路径。
- 网络通信：找到数据包从一个源点到达目的地的最短通信路径。
在这些应用中，元素之间的关系不是简单的一对一，而是复杂的多对多的网状关系。我们可以对这些元素进行查找、插入和删除操作，以解决不同的实际问题。
从上面三个实例可以看出，非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图的数据结构。因此，简单地说，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。
4.数据结构学科的起源和发展
- 数据结构的起源
- 早期的零散存在：在20世纪60年代初期，“数据结构”这个概念并不是一个独立的领域，而是散见于操作系统、编译原理等课程中。这些课程里偶尔会涉及到如何组织和管理数据，但没有形成一个系统化的学科。
- 数据结构成为独立学科
- 1968年的重要事件：1968年，“数据结构”正式成为美国一些大学计算机科学系的一门独立课程。同年，著名计算机科学家D.E.Knuth教授发表了《计算机程序设计艺术》第一卷《基本算法》。这本书是第一本系统阐述“数据结构”基本内容的著作，对这一领域的形成和发展起到了重要作用。
- 数据结构与程序设计
- 大型程序和文件系统的出现：随着计算机技术的发展，特别是大型程序和大规模文件系统的出现，结构化程序设计成为程序设计的主要方法学。简单来说，编写程序时，选用一个合适的数据结构，再配合一个好的算法，就能更有效地解决问题。著名科学家Wirth教授提出的“算法+数据结构=程序”这一观点，集中反映了这一思想。
- 数据结构的重要性
- 核心课程的地位
如今，数据结构被认为是计算机科学中的一门核心基础课程。它不仅涉及计算机硬件（如编码理论、存储装置和访问方法等），还与计算机软件（如编译器和操作系统）密切相关。无论是编写程序还是设计操作系统，都需要考虑如何在存储器中有效分配和管理数据。
- 数据组织和信息检索
在信息检索中，如何组织数据，以便快速查找和访问数据元素，也是数据结构研究的重要内容。因此，数据结构可以被看作是连接数学、计算机硬件和软件的一门核心课程。
- 数据结构的持续发展
- 面向特定领域的发展
随着计算机应用领域的扩大，针对特定领域的特殊问题，新的数据结构不断被研究和发展。
- 抽象数据类型
最近，越来越多的人开始从抽象数据类型的角度研究数据结构。这意味着，研究者更加关注如何定义和操作数据类型，使其更加通用和灵活，这也成为了当前数据结构研究中的一个新趋势。
-
总结
数据结构从早期的零散知识逐渐发展成一门独立的学科，并在计算机科学中占据核心地位。它的重要性体现在程序设计、操作系统和信息检索等多个领域。随着技术的进步，数据结构研究不断深入，特别是在面向特定领域和抽象数据类型的研究方向上，显示出强大的生命力。
标签：棋盘,01,计算机,路径,算法,序论,数据结构,节点 From： https://blog.csdn.net/weixin_48681435/article/details/145234672