数据结构学习笔记——绪论

一、绪论

1.1什么是数据结构

概念：简单的来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。

数据在计算机中进行处理，要考虑：

（1）数据本身的数学性质

（2）数据的存储结构

程序设计的实质是：对确定的问题选择一种好的结构，加上设计一种好的算法

数据结构介于：数学、计算机硬件、计算机软件之间。

1.2 基本概念和术语

1.2.1 相关概念

数据：对客观事物的符号表示；

数据元素：数据的基本单位，数据元素可以有多个数据项组成；

数据项：数据不可分割的最小单位；

数据对象：性质相同的数据元素的集合，是数据的一个子集；

数据结构：相互之间存在一种或多种特定关系的数据元素的集合；

1.2.2 根据数据元素之间关系的不同特性，通常有以下四类基本结构：

（1）集合

（2）线性结构

（3）树形结构

（4）图状结构或网状结构

1.2.3数据的逻辑结构和物理结构

逻辑结构：数据之间的逻辑关系

物理结构：数据结构在计算机中的表示

1.2.4数据元素之间的关系的两种表示方法：

顺序映像和非顺序映像

特点：

顺序映像：借助元素在存储器的相对位置来表示数据元素之间的逻辑关系

非顺序：借助指示元素存储地址的指针表示数据元素之间的逻辑关系

由此到两种不同的存储结构：

1、顺序存储结构

2、链式存储结构

任何一个算法的设计取决于选他的数据（逻辑）结构，

而算法的实现依赖于采用的存储结构。

1.2.5结构类型和非结构类型

非结构的原子类型：C语言中的基本类型（整形、实型、字符型和枚举类型）、指针类型、空类型

结构类型：由若干成分按照某种结构组成的，可以分解，成分可以是非结构的也可以是结构的。

1.3抽象数据类型的表示与实现

1.4算法和算法分析

1.4.1算法概念及特性

概念：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中一个指令表示一个或多个操作。

5个特性：

（1）有穷性（2）确定性（3）可行性（4）输入（5）输出

1.4.2算法设计的要求

一个“好”的算法该有的目标：

（1）正确性

（2）可读性

（3）健壮性

（4）效率与低存储量需求

1.4.3算法效率的度量（时间复杂度、空间复杂度）

（1）事后统计（2）事前分析估算

时间复杂度(渐近时间复杂度)：
$T(n)=O(f(n))$
例：

//(a)
{
    ++x;
    s=0;
}
//(b)
for(i=1;i<=n;i++){
    ++x;
    s+=x;
}
//(c)
for(j=1;j<=n;++j){
    for(k=1;k<=n;++k){
        ++x;
        s+=x;
    }
}

其中语句的频度分别为 1、n、n^{2，则其时间复杂度分别为O(1)、O(n)、O(n}2)，分别称为常量阶、线性阶和平方阶。时间复杂度还有对数阶O(log n)、指数阶O(2^n)。

我们尽可能使用多项式阶的算法O(n^k)，而不希望使用指数阶算法

基本操作执行次数（或语句频度），只需求出他关于n的增长率或阶即可

例：

for(i=2;i<=n;++i)
    for(j=2;j<=i-1;++j){
        ++x;
        a[i][j] = x;
    }

语句++x执行次数关于n的增长率为n^2，他的语句频度表达式为
$(n-1)*(n-2)/2$
空间复杂度：
$S(n)=O(f(n))$