数据结构基础知识

基本概念

1.数据（data): 所有能输入到计算机中并被计算机程序加工、处理的符号的总称。如：整数、实数、字符、声音、图象、图形等。
2.数据元素(data element): 数据的基本单位。（元素、记录、结点、顶点）在计算机程序中通常作为一个整体进行考虑和处理。
3.数据项(data item): 是数据的不可分割的最小单位。如：姓名、年龄等一个数据元素可由一个或多个数据项组成。如: (姓名、年龄)
4.数据对象(data object): 由性质相同(类型相同)的数据元素组成的集合。数据对象是数据的一个子集。例1 由4个整数组成的数据对象 D1={20,-30,88,45} 例2 由正整数组成的数据对象 D2={1,2,3,…} 例3 由26个字母组成的数据对象 D3={A,B,C,…,Z} 其中：D1，D3是有穷集，D2是无穷集
5.数据结构(data structure): 相互之间存在一种或多种特定关系的数据元素的集合。 数据元素之间的关系称为结构。

6.数据的逻辑结构: 各数据元素之间的逻辑关系（逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。主要是对于人这个层面如何设计存储数据的方式）。 数据结构(逻辑结构)分为线性结构和非线性结构。

7.数据的存储结构：数据结构在计算机存储器中的映象(mapping)。存储结构也称为：存储表示,物理结构,物理表示。存储结构分为顺序存储结构（向量，数组等）和非顺序存储结构（链表等）。另外数据的运算与采用何种存储结构有关。
8.数据类型（data type): 是一个值的集合和定义在这个值上的一组操作的总称。 (1)原子类型(如：int,char,float等) (2)结构类型(如：数组,结构,联合体等）
9.抽象数据类型(Abstract Data Type): 与计算机的实现无关的数据类型。形式定义：

ADT 抽象数据类型名 { 
1.数据对象 
2.数据关系:一个或多个关系 
3.一组基本操作/运算 
} ADT 抽象数据类型名

算法与算法特征

1.算法定义：求解一个特定任务的指令的有限序列。
2.算法的五个特征：

(1)有穷性：在有限步(或有限时间)之后算法终止。例.{ i=0；s=0； while (i<=10) s+=i； i++； }
(2)确定性：无二义性。例1：将4或5与X相加。例2：{ x=5；y=10； z=x+++y； printf(“%d,%d,%d”,x,y,z)； } x+++y 解释为：x + (++y)？还是 (x++)+ y？
(3)可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，每条指令都充分基本，原则上可由人仅用笔和纸在有限的时间内也能完成。 for( i=1,s=0；i<1000000000000；++i) s++
(4)输入：有0或多个输入量。
(5)输出：至少有一个输出量

3.算法设计要求

(1)正确性 a.无语法错误； b.对n组输入产生正确结果； c.对特殊输入产生正确结果； d.对所有输入产生正确结果。
(2)可读性：“算法主要是为了人的阅读与交流”。
(3)健壮性
(4)高效与低存储量

4.算法的时间复杂度：算法(或程序)中基本操作(或语句)重复执行的次数的总和。设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)；时间复杂度记作T(n),假定存在一个常数c和一个函数g(n),当n>n0时，有： f(n)< c*g(n),则称有： T(n)=O(g(n))。

常见的时间复杂度有O(1),O(logn),O(n),O(nlogn),O(n^2),O(n^3),O(2^n);O(1)称成为常量阶/常量数量级

5.算法的空间复杂度 执行算法所需存储空间的大小。 S(n)=O(f(n)) 其中：f(n)为算法使用的单元数 O(f(n))：存在M，f(n)小于等于M*F(n)