目录

• 《数据结构》
  • 第 一 章 绪论

《数据结构》

第 一 章 绪论

早期的计算机主要用于数值计算，现在，计算机主要用于非数值计算，包括处理字符、表格 和图像等具有一定结构的数据。如何合理地组织数据、高效地 处理数据，这就是 “数据结构”主要研究的问题。

1.1 数据结构的研究内容

数据结构是一门研究非数值计算程序设计中的操作对象， 以及这些对象之间的关系和操作的学科。元素之间存在简单一对一的线性关系，这类数学模型称为 ＂线性” 的数据结构。元素之间是一对多的层次关系， 这类数学模型称为 “树 ” 的数据结构。元素之间是多对多的网状关系，施加于对象上 的操作依然有查找、插入和删除等。这类数学模型称为 “图 ” 的数据结构。

1.2 基本概念和术语

1.2.1 数据、 数据元素、 数据项和数据对象

数据是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号 的总称。

数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。数据元素用于完整地描述一个对象，如前一节示 例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。

数据项是组成数据元素的、有独立含义的、不可分割的最小单位。数据对象是性质相同的数据元素的集合，是数据的一个子集。

1.2.2 数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合 数据结构包括逻辑结构和存储结构两个层次。

1. 逻辑结构数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，可以看作是从具体问题抽象出来的数学模型

数据的逻辑结构有两个要素： 一是数据元素；二是关系。关系是指数据元素间的逻辑关系。通常有四类基本结构，复杂程度依次递进:(1) 集合结构 (2) 线性结构 (3) 树结构 (4) 图结构或网状结构

集合结构、树结构和图结构都属于非线性结构。线性结构包括线性表、栈和队列、字符串、数组、 广义表。非线性结构包括树和二叉树、有向图和无向图

1. 存储结构 数据对象在计算机中的存储表示称为数据的存储结构。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。

(1) 顺序存储结构 顺序存储结构通常借助程序设计语言的数组类型来描述。

(2) 链式存储结构 无需占用一整块存储空间，所以链式存储结构通常借助于程序设计语言的指针类型来描述。

1.2.3 数据类型和抽象数据类型

1. 数据类型 在程序设计语言中，每一个数据都属于某种数据类型。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

2. 抽象数据类型 抽象数据类型一般指由用户定义的、表示应用问题的数学模型，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

1.3算法和算法分析

1.3.1 算法的定义及特性

算法是为了解决某类问题而规定的一个有限长的操作序列。

(1)有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。

(2) 确定性。对千每种情况下所应执行的操作，在算法中都有确切的规定。

(3) 可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

(4) 输入。一个算法有零个或多个输入。

(5) 输出。一个算法有一个或多个输出。

1.3.2 评价算法优劣的基本标准

(1)正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。

(2) 可读性。一个好的算法，首先应便千人们理解和相互交流，其次才是机器可执行性。

(3) 健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理。

(4) 高效性。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。

1.3.3 算法的时间复杂度

1. 问题规模和语句频度

不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模。问题规模 是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。问题规模n对不同的问题含义不同，n越大算法的执行时间越长。

一个算法的执行时间大致上等千其所有语句执行时间的总和， 而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。

一条语句的重复执行次数称作语句频度。

算法分析并非精确统计算法实际执行所需时间，而是针对算法中语句的执行 次数做出估计，从中得到算法执行时间的信息。

2.算法的时间复杂度定义

为了客观地反映一个算法的执行时间， 可以只用算法中的 “基本语句＂ 的执行次数来度量算法的工作量。 “基本语句” 指的是算法中重复执行次数 和算法的执行时间成正比的语句， 它对算法运行时间的贡献最大。

算法的执行时间是随问题规模增长而增长的， 因此对算法的评价通常只需考虑其随问题规模增长的趋势。用"O"来表示数量级。 一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n), 算法的时间量 度 记作 T(n) = 0(f(n)) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同， 称做算法的渐近时间复杂度， 简称时间复杂度。

x=90;y=100;
while(y >0)
   if(x>100)
       {x=x-10;y--;}
    else x++;    

时间复杂度：1100

for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        a[i][j]=0

时间复杂度：O(n^2)

s=0;
for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        s+=B[i][j];
sum=s;

时间复杂度：O(n^2)

i=1;
while(i<=n)
    i=i*3;

时间复杂度：log3n