参考第一章绪论

第一章绪论数据结构

的范畴与数据结构相关的概念数据结构数据类型和抽象数据类型算法及其描述和分析时间复杂度Niklaus

Wirth(

)：算法+数据结构=程序设计程序设计：为计算机处理问题编制一组指令集算法： 处理问题的策略(怎么解决？)数据结构：问题的数学模型(数据怎么表示？)算法与数据结构的关系例子：求一组(n个)整数中的最大值。算法：

通过依次比较两个数的大小，找到最大值数据结构(模型)：•用什么样的数据结构来表示整数？例子：已知5名学生的成绩（语、数、英），请求出他们的平均分，并按平均分高低进行由低到高排序。sigwww.nn.问题求解的基本步骤2020/11/1871.7

关于学习数据结构数据结构课程地位数据结构课程学习特点（之后说明）关于本书内容编写说明（之后说明）8数据结构课程地位2020/11/18数据结构与其它课程关系图：数据库人工智能专业基础课操作系统编译原理非线性程序设计离散数学语言程序设计计算机原理设计数

据结构1.2数据结构的相关概念数据数据元素数据对象数据结构数据类型抽象数据类型(Data

Type--ADT)定义：数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。包含数值、字符、声音、图像等一切可以输入到计算机中的符号集合。例如对C源程序（VC6.0）C编译程序源程序（.cpp）目标程序（.obj）可执行程序（.exe）C

程序数据定义：数据元素是组成数据的基本单位

，是数据集合的 ，在计算机中通常作为一个整体进行考虑和处理。例如：数据元素学号籍贯出生年月住址101女河北1983.11..................数据项数据元素名称出生日期参加日期职务业绩年月日定义：数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数集合：N={0，±1，±2，…} 无限集字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}有限集运动员信息(数据元素)组成的信息表：数据对象组合项定义：数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元间的相互关系，即数据的组织形式。例如表结构：数据结构学号籍贯出生年月住址101女河北1983.11..................数据结构教研室系处研究机构学校树型结构图结构12543数据类型定义：数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-32768至 ，运算符集合（一组操作）为加、减、乘、除、取模，即+、-、*、/、%。数据类型决定了两个方面的内容：--取值范围--允许使用的一组运算（C语言中的基本数据类型.doc）高级语言中的数据类型分为两大类：原子类型：其值不可分解。如C语言中的标准类型（整型、实型、字符型、）。结构类型:其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。数据类型事实上，高级程序语言中的数据类型本身也是一种抽象：十进制表示的数据98.65、9.6E3等,它们是二进制数据的抽象;高级语言中，给出更高一级的数据抽象，如整型、实型、字符型等，更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。抽象数据类型－ADT抽象数据类型－ADTADT定义了一个数据对象、数据对象中各元素间的结构关系以及一组处理数据的操作。抽象数据类型与数据类型实质上是一个概念，只不过ADT更为广义，不仅限于各种不同计算机处理器中已定义并实现的数据类型，还包括用户自己定义的复杂数据类型。信息隐蔽：将实体的外部特征和其节分离，并且对外部用户隐藏其实现细实现细节。抽象数据类型－.

ADesTig是数据类型的进一步抽象。把数据类型和数据类型上的运算绑定并封装。有两个重要特征：数据抽象：强调程序处理的实体的本质特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。数据结构的内容数据结构：带结构的数据元素的集合。数据元素间的相互关系包括三个方面：数据的逻辑结构数据的物理结构数据的运算集合sig数据结构的逻辑结构可归结为以下四类：线性结构：树形结构：图形结构(网状结构)：集合结构：逻辑结构.集合结构：结构中的数据元

间除了同属于一个集合的关系外，无任何其它关系。图例：线性结构：结构中的数据元间存在着一对一的线性关系。图例：树形结构：结构中的数据元间存在着一对多的线性关系。图例：树图状结构：结构中的数据元间存在着多对多的线性关系。图例：图sig逻辑结构.逻辑结构也可归结为：线性结构——线性表、栈、队、字符串、数组、广义表逻辑结构非线性结构——树、图sig反映成分数据在计算机内的

安排。逻辑结构在

器中的映像。物理结构.sig数据元素的映像方法：例如：用二进制位(bit)的位串表示数据元素(321)10

(501)8

(A

(101)8

(00100物理结构..

signcom在计算机中有两种表示方法（如<x,y>--x先于y）顺序 结构

(数组结构)xy非顺序结构(记录结构)xy物理结构2

2

/11/130例如对工资表的增、删、改操作：基本工资工龄工资应扣工资实发工资100001女345．67145．4530．00451．12100002李

林男445．90185．6045．00586．50100003男345．00130．0025．00450．00100004赵

俊女560．90225．9065．00721．80100005孙

涛男450．60190．8050．00591．80…………………100121男1025．98365．53100．001291.51运算集合1.3算法算法：是规则的有限集合，是为解决特定问题而规定的一系列操作。解决问题的法或一个过程(策略)。特性：有限性：有限步骤之内正常结束，不能形成无穷循环。确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。输 入：有多个或0个输入。输 出：至少有一个或多个输出。可行性：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。1.3算法算法、语言、程序语言：描述算法的工具（也可用自然语言、框图描述算法）。程序是算法在计算机中的实现。程序可以不满足有限性，如操作系统，它是在无限循环中执行的程序，因而不是算法。一个好的算法一般应具有几个基本特征：正确性可读性健壮性（鲁棒性）高效率与低

量1.3算法设计正确性：例如要求n个数的最大值问题：max=0;for（i=1

；i<=

n

;i++）{ scanf("%f",x);if

(x>max)

max=x;}语法错误？当输入的全为正数时，结果正确？当输入的全为负数时，结果正确？时，算法应当能够加以识别并做出健壮性：当输入的数据处理高效率与低

量需求：效率：算法执行时间(T)量：算法执行过程中所需的最大空间。(S)两者都与问题的规模(n)有关耗费的时间T(n,I)算法性能C(n,I)占用的空间S(n,I)与算法执行时间相关的因素：算法执行的策略问题的规模n编写程序的语言编译程序产生的机器语言的质量计算机执行指令的速度时间2020/11/1840定义：一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。分析：不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。时间2020/11/18}总执行次数：Tn=2n3+2n2

+n41语句频度：指该语句在一个算法中重复执行的次数。例如：两个矩阵相乘算法语句对应的语句频度nn2n2n3{

c[i][j]=0;for

(k=0;k<

n;

k++)for（i=0；i<

n;i++）for

（j=0；j<n;j++）345c[i][j]=c[i][j]+a[i][k]*b[k][j];

n3时间2020/11/1842时间复杂度：语句频度的数量级，算法的时间量度。T(n)=O(f(n))表示随问题规模n的增大，算法执行时间的增长率和

f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。时间2020/11/18例如：给出X=X+1x=x+1

；－－时间复杂度为O(1)，称为常量阶；for

(i=1;

i<=

n;

i++)x=x+1;－－时间复杂度为O(n)，称为线性阶；for

(i=1;

i<=

n;

i++)for

(j=1;j<=

n;

j++)

x=x+1;－－时间复杂度为O(n2),称为平方阶。43时间2020/11/1844例如：两个矩阵相乘算法语句对应的语句频度nn2n2n3for

(k=0;k<

n;

k++)for（i=0；i<

n;i++）for

（j=0；j<n;j++）{

c[i][j]=0;45c[i][j]=c[i][j]+a[i][k]*b[k][j];

n3}总执行次数：Tn=2n3+2n2

+n时间复杂度练习时间复杂度：O(n3)习题12020/11/18按时间复杂度由小到大排列：O(1)常数型＜O(log2n)对数型＜O(n)线性型＜O(nlog2n)二维型＜O(n2)平方型＜O(n3)立方型＜O(2n)指数型46数据结构中常用的时间复杂度频率计数有7个:O(1)

常数型O(n)线性型O(n2)平方型O(n3)立方型O(nlog2n)二维型O(2n)指数型O(log2n)对数型时间例一：for

(i=1;

i<=n;

++i)for

(j=1;

j<=n;

++j)

{c[i][j]=0;for

(k=1;

k<=n;

++k)c[i][j]

=

a[i][k]

*

b[k][j];{时间复杂度：O(n3

)时间复杂度练习例二：for

(i=1;

i