【数据结构导论】第一章-概论
数据结构、数据、数据元素和数据项的概念
数据结构
计算机组织数据和存储数据的方式。是相互之间存在一种或多种特定关系的数据元素的集合。
数据
所有被计算机存储、处理的对象。
数据元素
数据的基本单位。在程序中作为一个整体而加以考虑和处理。
数据项
数据元素的组成部分。在数据库中又被称为字段或域。
数据项和数据存储结构
数据结构的作用
合理的数据结构可降低程序设计的复杂性，提高程序执行的效率。
数据、数据元素、数据项三者关系
从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据元素组成，而数据元素又可由若干个数据项组成。
数据逻辑结构
数据的逻辑结构是指数据元素之间的逻辑关系，数据元素之间逻辑关系的整体称为逻辑结构。
数据存储结构
数据的逻辑结构在计算机中的实现，称为数据的存储结构（或物理结构）一般情况下，存储结构包括以下两个部分：（1）存储数据元素（2）数据元素之间的关联方式
四类基本逻辑结构的特点
线性结构
结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。
集合
任意两个结点之间都没有邻接关系，组织形式松散。
树形结构：
树形结构具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层的多个结点乡邻接，但下层结点只能和上层的一个结点相邻接。
图结构：
其中任何两个结点都可以相邻接。
顺序存储结构
顺序存储方式是指所有存储结点存放在连续的存储区内。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构
链式存储方式是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表述数据之间的逻辑关系。
逻辑结构和存储结构的关系
一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储映像。
运算、算法和算法分析
运算
指某种逻辑结构上施加的操作，即对逻辑结构的加工。
基本运算
包括：建立、查找、读取、插入和删除
算法分析
一个算法规定了求解给定问题所需的处理步骤和其执行顺序，使得给定问题能在有限时间内被求解
时间复杂度
假如问题的输入规模为 n，一般情况下，一个算法的计算量是问题规模 n 的函数。T(n) = O(f(n))
其中f(n) 为问题规模 n 的某个函数，大 O 为渐进表示法。
时间复杂度是算法的渐进时间复杂度的简称。
空间复杂度：
一个算法的空间复杂度为该算法所耗费的存储空间，也是问题规模 n 的函数S(n)= O(g(n))
运算与数据结构的关系
相互依赖，不可分割的关系。
算法的评价因素：
一个问题可以有不同的求解算法，评价算法好坏的因素包括以下几点：
评价算法好坏的因素：
能够正确的实现预定的功能，满足具体问题的需要。
易于阅读、理解和交流，便于调试、修改和扩充。
即使输入非法数据，算法也能适当的做出反应或处理，不会产生预料不到的运行结果。
算法的时间性能（效率）和空间性能（效率），前者是算法包含的计算量，后者是算法需要的存储量。