数据结构应用实例

来自计算思维百科
跳转至: 导航搜索

首先介绍一个有关数据结构的实例----计算机与人对弈问题。

计算机之所以能和人对弈是因为有人将对弈的策略事先存入计算机。由于对弈的过程是在一定规则下随机进行的,所以,为了使计算机能灵活对弈就必须对对弈过程中所有发生的情况以及相应的策略都考虑周全,并且,一个“好”的棋手在对弈过程时不仅要看棋盘当时的状态,还应能预测棋局发展的趋势,甚至最后的结局。因此,在对弈问题中,计算机操作的对象是对弈过程中可能出现的棋盘状态——称为格局。例如,图1(a)所示为井字棋的一个格局,而格局之间的关系由比赛规则决定。通常,这个关系不是线性的,因为从一个棋盘格局可以派生出几个格局,例如从图1(a)的格局可以派生出5个格局,如图1(b)所示,而从每个新的格局又可以派生出4个可能出现的格局。因此,若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上,则可得到一颗倒长的“树”。“树根”是对弈开始之前的棋盘格局,而所有的“叶子”就是可能出现的结局,对弈的过程就是从树根沿树杈到某个叶子的过程。“树”可以是某些非数值计算问题的数学模型,它就是一种数据结构。

3.2.1.png3.2.2.png

        图1 井字棋对弈“树”

除树之外,常用的数据结构还包括表、图等,这些结构,可以方便我们更好地表示不同类型的数据元素之间的关系。简单来说,数据结构(Data Structure)就是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。其主要讨论和研究三方面的问题:

  1. 数据集合中各种数据元素之间所固有的逻辑关系,即数据的逻辑结构;
  2. 在岁数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
  3. 如何实现各种数据结构上的运算。

研究数据结构的主要目的是为了提高数据处理的效率,包括提高数据处理的速度,节省数据处理过程中所占用的计算机存储空间。