目录
- 1.1数据结构的定义
- 1.2基本概念和术语
- 1.3抽象数据类型的实现和表示
- 1.4算法与算法分析
1.4.1.算法
1.4.2.算法设计的要求
1.4.3算法效率的度量
1.4.4算法的存储空间需求
1.1 数据结构的定义
目录
- 引例
- 定义
- 后记
引例
在设计程序的时候，我们一般要经历以下的步骤:
建立数学模型➡设计解决这个模型的算法➡用编程语言实现算法➡调试
建立数学模型这一步骤，实质上，是将问题中的对象抽象出来，并且找出各个对象间的关系，最后用数学语言表述出来。
课本中给出了，编排图书管理系统，人机对弈(按步骤下棋)，交叉路口的交通灯管理，这三个例子，它们分别对应着，表，树，图，这三个数据结构。
(1)编排图书系统:
图书管理系统，一般是通过一个链表，将每本书作为一个节点(node)，按一定顺序编排起来。这个节点包含着:书的编号，名称，价格，是否被借阅，以及借阅人，出入库时间等信息。
(2)人机对弈:
假定有一个棋盘，棋盘的走向是随着一步步落子的变化而变化的，如果我们把落子的位置(x,y)和落子次序{ i | i=1,2,3,...}分别标注出来，就可以形成一个链表式的结构。但是，如果棋子并,未落下，我们则可以用树的分支，来表述可能性。
每一次落子，对应一个节点，而下一次落子的可能性，则构成了这个节点生长出的树枝；而且，每一个节点都可以有树枝，从开始的落子，到之后一步步的落子的推演，开枝散叶，就形成了树的结构。
(3)交叉路口的交通灯管理:
假定有一个交叉路口，呈五角星状，路口分别标记为A,B,C,D,E,我们就可以将每一条通路(例如AE或是EA)记作一个节点，
设定规则，例如C,E为单行道，车辆在车道E只能离开，在车道C只能进入，而且车辆之间不能相互碰撞。
为了保证最大效率通行，我们按照上文中的方法，将通路抽离成节点，将不能同时运行的车道用线连接，这时就形成了以通路为节点，以是否能同时运行为关系的图状结构。
那么，如何解决这些问题呢？
定义
广义上的数学关系不再局限在数值计算上，而是形如以上的表、图、网之类的数据结构。总之，数据结构(Data Structure)是研究非数值计算问题中，计算机的操作对象以及其关系和操作的学科。
后记
表是常见的数据记录形式；而树，不仅仅可用于数据的分类管理，也可以应用在分步问题上，例如博弈、搜索、“生命游戏”；图，则应用范围更加广阔，常常应用在信息图谱、关系图、流量监控与控制等问题中。
