数据结构(C语言版) 第1章 绪论

理论课教材：

数据结构（C语言版）严蔚敏吴伟民编著数据结构1.0学习数据结构的主要意义和要求

1.1数据结构讨论的范畴1.2基本概念1.3抽象数据类型的表示和实现1.4算法和算法的度量第一章绪论学习数据结构的主要意义和要求数据结构和算法是计算机学科的两大支柱

数据结构是程序设计的基础

程序=算法+数据结构要求：意义：（1）掌握各类基本数据结构类型和相应的存储结构（2）提高阅读和编写算法的能力（3）能针对给定问题，选择相适应的数据结构，并能设计和分析算法1.1数据结构讨论的范畴程序

=算法

+数据结构程序设计：为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型非数值计算的程序设计问题例1书目自动检索系统例2人机对奕问题例3多叉路口交通灯管理问题例1书目自动检索系统书目文件按书名按作者名按分类号索引表线性表例2人机对奕问题树……..……..…...…...…...…...例3多叉路口交通灯管理问题图CEDABABACADBABCBDDADBDCEAEBECED数据结构定义

数据结构是一门讨论“描述现实世界实体”的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据（data)—所有能被输入到计算机中，且能被计算机处理的符号的集合，是计算机操作的对象的总称。数据元素（dataelement）—是数据（集合）中的一个“个体”，是数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)。数据对象（dataobject)—是性质相同的数据元素的集合，是数据的一个子集。1.2基本概念和术语根据数据元素间关系的基本特性，有四种基本结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图1.2基本概念和术语数据结构(datastructure)—是相互之间存在一种或多种特定关系的数据元素的集合1.2基本概念和术语数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)

其中:D是数据元素的有限集，

S是D上关系的有限集。数据元素的映象方法：例用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系链式映象

以附加信息(指针)表示后继关系数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的映象换句话说

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构数据的逻辑结构与存储结构密切相关存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构存储地址

存储内容

指针

1345

元素1

1400

1346

元素4∧…….……..…….

1400

元素2

1536…….……..…….

1536

元素3

1346

链式存储h1536元素21400元素11346元素3∧元素41345h元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列数据逻辑结构层次关系图1.2基本概念和术语在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef

自己定义数据类型typedefstruct

{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;数据类型：是一个值的集合和定义在此集合上的一组操作的总称。1.2基本概念和术语不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。抽象数据类型

(AbstractDataType简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。“抽象”的意义在于数据类型的数学抽象。一个抽象的数据类型的模块通常应包含定义、表示和实现三部分。抽象数据类型定义格式ADT

抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}ADT

抽象数据类型名抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；

S是D上的关系集；

P是对D的基本操作集。

赋值参数只为操作提供输入值。引用参数以&打头，除可提供输入值外，还可返回操作结果。其中基本操作的定义格式为:

基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。基本操作例如，抽象数据类型复数的定义：

数据对象： //D

D＝{e1,e2｜e1,e2∈RealSet}

数据关系： //S

R1＝{<e1,e2>|e1是复数的实数部分

|e2

是复数的虚数部分}ADTComplex{基本操作： //P

AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex1.3抽象数据类型的表示和实现

抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。ADT有两个重要特征:数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。本书采用的C语言核心子集(1)预定义常量类型://函数结果状态代码#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是//函数的结果状态代码typedefintStatus(2)数据元素类型约定为ElemType(3)基本操作的算法都用以下形式的函数描述

函数类型函数名（函数参数表）{ //算法说明 语句序列

}函数名(4)赋值语句(5)选择语句

if和switch(6)循环语句

for,while,do-while(7)结束语句

return,break,exit(8)输入输出语句

scanf,printf(9)注释

单行注释//(10)基本函数

max,min,abs,eof…(11)逻辑运算

&&,||,!//-----基本操作的函数原型说明void

Assign(complex&Z,floatrealval,floatimagval)；

//构造复数Z,其实部和虚部分别被赋以参

//数realval

和imagval

的值floatGetReal(cpmplexZ)；

//返回复数Z的实部值float

GetImag(complexZ)；

//返回复数Z的虚部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回两个复数z1,z2的和//-----基本操作的实现voidadd(complexz1,complexz2,complex&sum){

//用sum返回两个复数z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略}typedefstruct{floatrealpart；

floatimagpart；}complex；//-----存储结构的定义例如，对以上定义的复数。1.4算法和算法的度量算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列一个算法必须满足以下五个重要特性：1．有穷性

对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2．确定性

算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且在任何条件下，算法都只有一条执行路径，即对于相同的输入只能得出相同的输出。3．可行性

算法中的所有操作都可以通过已经实现的基本操作运算有限次来实现。4．有输入一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5．有输出一个算法有零个或多个输出，这些输出是同输入有着某些特定关系的量。算法特性算法的评价—衡量算法优劣的标准正确性(correctness)

可读性(readability)

健壮性(robustness)

效率与低存储量算法设计的要求1．正确性

首先，算法应当满足以特定的“规格说明”方式给出的需求。

其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d．程序对于一切合法的输入数据都能得出满足要求的结果；算法设计的要求2.可读性

算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。3．健壮性

当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4．高效率与低存储量需求

通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。算法设计的要求算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量

1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分

缺点：必须先运行依据算法编制的程序

所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣

算法效率的度量2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于：

依据的算法选用何种策略

问题的规模

程序语言

编译程序产生机器代码质量

机器执行指令速度算法效率的度量

同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适

假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度。

一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。算法效率的度量注意：T(n)是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而O(f(n))是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。f(n)是n趋向无穷大时与T(n)为同阶无穷大。算法=控制结构+原操作（固有数据类型的操作）算法的执行时间

=

原操作(i)的执行次数×原操作(i)的执行时间

算法的执行时间

与

原操作执行次数之和

成正比

从算法中选取一种对于所研究的问题来说是基本操作

的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。如何估算算法的时间复杂度voidmult(inta[],intb[],int&c[]){

//以二维数组存储矩阵元素，c为a和b的乘积

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];}//for}//mult基本操作:

乘法操作时间复杂度:

O(n3)例一两个矩阵相乘voidselect_sort(int&a[],intn){//将a中整数序列重新排列成自小至大有序的整数序列。基本操作:

比较(数据元素)操作时间复杂度:

O(n2)j=i;//

选择第i个最小元素for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){}//select_sortif(j!=i)