1. 什么是数据结构
一般而言, 使用计算机解决一个具体的问题时, 大致需要经过以下几个步骤:
从具体的问题中抽象出一个适当的数学模型;
设计一个求解该数学模型的算法;
编写程序, 进行测试, 调整, 直至得到最终的问题解答.
对实际问题建立数学模型的实质是: 分析问题, 并从中提取操作的对象, 并找出这些对象间含有的关系, 然后使用数学的语言加以描述.
数据结构 (data structure) 可以定义为: 相互之间存在一种或多种特定关系的数据元素的集合.
在任何问题中, 数据元素都不是孤立存在的, 而是存在着某种相互牵连的关系, 这种关系称为结构(structure). 根据关系特性的不同, 通常有 4 种基本结构:
集合, 数据元素之间除了同属一个集合外, 别无其他关系;
线性结构, 数据元素之间存在一对一的关系;
树形结构, 数据元素之间存在一对多的关系;
图状结构或网络结构, 数据元素之间存在多对多的关系.
数据结构的形式定义为: 数据结构是一个二元组
Data Structure = (D,S)
其中, D 是数据元素的有限集, S 是 D 上关系的有限集.
2. 算法
算法是求解特定问题的一种分步骤描述, 它是指令的有限序列, 每一条指令对应一个或多个操作, 算法具有以下 5 个重要特性:
有穷性, 一个算法总是在执行有穷步后结束, 且每一步可在有穷步内完成;
确定性, 算法的每一条指令, 必须具有确切的含义, 不会产生二义性, 在任何条件下, 相同的输入只能得出相同的输出;
可行性, 算法中描述的操作都是可行的;
输入, 算法中存在 0 个或多个输入, 这些输入取决于特定的对象集合;
输出, 算法存在 1 个或多个输出, 这些输出是同输入有着某些特定关系的量.
算法设计, 需要考虑以下目标:
正确性(correctness), 算法应当满足具体问题的需求, 要以指定的方式进行输入和输出;
可读性(readability), 算法主要是为了供人阅读与交流的, 其次是机器执行;
健壮性(robustness), 当输入数据非法时, 算法也能适当地做出反应并进行进行处理, 而不会出现莫名其妙的输出结果, 或者崩溃;
效率和低存储, 效率指的是算法执行时间, 存储需求指算法执行过程中所需最大存储空间.
算法中基本操作重复执行的次数是问题规模 n 的某个函数 f(n), 算法的时间度量可以记作
T(n) = O(f(n))
它表示随问题规模 n 的增大, 执行时间的增长率和 f(n)的增长率相同, 这就是算法的时间复杂度(time complexity).
数据结构(C 语言版)学习 --day1, 初识数据结构
来源: http://www.bubuko.com/infodetail-2567820.html