数据结构的起源
计算机从解决数值计算问题到解决生活中的问题
现实生活中的问题涉及不同个体间的复杂关系
需要在计算机程序中描述生活中个体间的联系
数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系
不是研究复杂的算法
数据结构中的基本概念
数据—程序的操作对象,用于描述客观事物
数据的特点:
可以输入到计算机
可以被计算机程序处理
数据是一个抽象的概念,将其进行分类后得到程序设计语言中的类型。如:int,float……
数据元素:组成数据的基本单位
数据项:一个数据元素由若干数据项组成
数据对象 – 性质相同的数据元素的集合 (比如:数组,链表)
数据元素之间不是独立的,存在特定的关系,这些关系即结构
数据结构指数据对象中数据元素之间的关系
数据结构:研究关系
节点和节点之间的关系(数组、链表、树、图)
数据的逻辑结构
指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。逻辑结构可细分为4类:
(集合)----数据元素间除“同属于一个集合”外,无其它关系
线性结构----一个对一个,如线性表、栈、队列
树形结构----一个对多个,如树
图状结构----多个对多个,如图
数据的物理结构
物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机
存储结构可分为4大类:顺序、链式、索引、散列
最常用的存储结构为:
顺序存储结构----借助元素在存储器中的相对位置来表示数据元素间的逻辑关系
链式存储结构----借助指示元素存储地址的指针表示数据元素间的逻辑关系
数据的逻辑结构与存储结构密切相关
算法设计à逻辑结构
算法实现à存储结构
数据的运算
在数据的逻辑结构上定义的操作,它在数据存储结构上实现
最常见的数据运算有5种:
插入、删除、修改、查找、排序
算法概念
算法是特定问题求解步骤的描述
在计算机中表现为指令的有限序列
算法是独立存在的一种解决问题的方法和思想
对于算法而言,语言并不重要,重要的是思想
算法和数据结构区别
数据结构只是静态的描述了数据元素之间的关系
高效的程序需要在数据结构的基础上设计和选择算法
程序=数据结构+算法
总结:
算法是为了解决实际问题而设计的
数据结构是算法需要处理的问题载体
数据结构与算法相辅相成
算法特性
输入:算法具有0个或多个输入
输出:算法至少有1个或多个输出
有穷性:算法在有限的步骤之后会自动结束而不会无限循环
确定性:算法中的每一步都有确定