数据结构-第1章 绪论

数据结构

(DataStructure)使用教材指定教材：[1]严蔚敏等,《数据结构(C语言版)》,清华大学出版社[2]严蔚敏等,《数据结构习题集(C语言版)》,清华大学出版社参考教材:[1]耿国华,《数据结构》,高等教育出版社[2]杨秀金等,《数据结构》,西安电子科技大学出版社[3]许卓群,《数据结构》,高等教育出版社[4]唐策善等,《数据结构》,高等教育出版社课程考核方式与要求本课程为考试课，满分100分，分为平时成绩和期末考试成绩两部分。平时成绩：占30%。包括出勤、作业、课堂练习、上机、课堂纪律、回答问题、课间擦黑板等。期末考试：占70%，闭卷笔试，按各章知识点要求，突出重点，考核学生综合应用能力。特别提醒：上课时要带好教材、笔、练习本!课程性质及教学目的《数据结构》是信息管理与信息系统专业本科生的一门专业基础必修课。其教学目的就是要培养学生的数据抽象能力，学会分析研究计算机加工的数据的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技巧,培养良好的程序设计技能。课程地位

数据结构程序设计语言离散数学计算机原理面向对象程序设计操作系统数据库编译原理人工智能课程内容本课程的基本内容分为三个部分：第一部分：绪论第二部分：基本的数据结构包括：线性结构——线性表、栈和队列、

串、数组和广义表非线性结构——树、图第三部分：基本的数据处理技术包括：查找技术和排序技术

1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论1.1什么是数据结构计算机的主要应用：程序=数据结构+算法科学计算数据处理发展到计算机加工处理的对象：纯数值发展到字符、表格和图像等1968年，设立《数据结构》课程计算机解决问题的步骤:具体问题设计编制分析抽象测试调整数学模型算法程序最终解答登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目信息书目文件按书名按作者名按分类号索引表线性表例1书目自动检索系统树……..……..…...…...…...…...例2人机对奕问题CEDABABACADBABCBDDADBDCEAEBECED图例3.多叉路口交通灯管理问题是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科《数据结构》定义1.2基本概念和术语1、数据(Data)：一切能够由计算机接受和处理的对象。

2、数据元素(DataElement)：是数据的基本单位，在程序中作为一个整体加以考虑和处理。

3、数据项(DataItem)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。

数据元素数据项4、数据结构(Datastructure)

相互之间存在一种或多种特定关系的数据元素的集合。例如:线性结构:

树形结构:图形结构:5．数据类型(DataType)

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如:C语言中的整型变量,其值集为某个区间上的整数,定义在其上的操作为加,减,乘,除和取模等算术运算。6. 抽象数据类型(AbstractDataType)抽象数据类型(简称ADT)定义了一个数据对象,数据对象中各元素间的结构关系,以及一组处理数据的操作.抽象数据类型的最本质特点是:数据抽象和信息隐蔽.抽象的本质是抽取反映事物的本质点,忽略非本质的细节,从而使设计的数据结构更具一般性,可以解决一类问题.信息隐蔽就是对用户隐藏数据存储和操作实现的细节,使用者仅需了解操作或界面服务,通过界面服务来访问数据.

数据结构的内容逻辑结构存储结构运算集合逻辑结构定义:数据之间逻辑关系描述.形式化描述:数据结构是一个二元组Data_Structure=(D,S)其中:D是数据元素的有限集,S是D上关系的有限集.

例如:DS2=(D2,R2)D2={a,b,c,d,e,f}R2={T}T={<a,b>,<a,c>,<a,d>,<d,e>,<e,f>}abcdef四种基本的逻辑结构集合、线性结构、树形结构、图形结构存储结构定义:存储结构(又称物理结构)指逻辑结构在计算机中的存储映像,是逻辑结构在计算机中的实现,包括数据的表示和关系的表示.分类:

顺序存储结构:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系.

链式存储结构:借助指示元素存储地址的指针表示数据元素之间的逻辑关系.运算集合讨论数据的目的是在计算机中实现操作,因此在数据结构上的运算集合是很重要的部分.数据结构就是研究一类数据的表示及其相关操作的集合.例如:工资表的查找,删除和插入操作.1.3抽象数据类型的表示与实现数据类型

定义：一个值的集合和定义在这个值集上的一组操作的总称。C语言中的基本数据类型

intcharfloatdoublevoid

整型字符型浮点型双精度型无值抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作数据结构+定义在此数据结构上的一组操作=抽象数据类型例如：矩阵+（求转置、加、乘、 求逆、求特征值） 构成一个矩阵的抽象数据类型抽象数据类型的描述抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

ADT抽象数据类型名{

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

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

基本操作：〈基本操作的定义〉 }ADT抽象数据类型名其中,数据对象、数据关系用伪码描述；基本操作定义格式为 基本操作名（参数表） 初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。抽象数据类型的表示和实现

抽象数据类型可以通过固有数据类型(高级编程语言中已实现的数据类型)来实现抽象数据类型类class数据对象数据成员基本操作成员函数(方法)例如，抽象数据类型复数的定义：

数据对象：

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

数据关系：

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

|e2

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

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的和值。}ADTComplex假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果1.4算法和算法分析算法(Algorithm)定义算法的特性算法设计的要求算法描述工具算法性能分析算法(Algorithm)定义解决某一特定问题的具体步骤的描述，是指令的有限、有序序列。算法的特性一算法设计的要求正确性可读性健壮性(鲁棒性)高效率与低存储量正确性实例:例:求n个数的最大值max=0;for(i=1;i<=n;i++){scanf(“%f”,&x);if(x>max)max=x;}可读性健壮性高效率与低存储量算法描述工具1．算法、语言、程序的关系⑴算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。⑵描述算法的工具：（自然语言、框图或高级程序设计语言）算法的描述可用自然语言、框图或高级程序设计语言，自然语言简单但易于产生二义。框图直观但不擅长表达数据组织结构，而其中以高级程序语言较为准确但又比较严谨。⑶程序是算法在计算机中的实现（与所用计算机及所用语言有关）2．设计实现算法过程步骤：

找出与求解有关的数据元素之间的关系（建立结构关系）

确定在某一数据对象上所施加运算

考虑数据元素的存储表示

选择描述算法的语言

设计实现求解的算法，并用程序语言加以描述。算法描述工具高级语言描述算法，具有严格准确的优点，但用于描述算法，也有语言细节过多的弱点，为此采用类语言形式本课程算法采用类C语言作为描述工具.类C语言简要说明1．

预定义常量和类型本书中用到以下常量符号，如True、False、MAXSIZE等，约定用如下宏定义预先定义：

#define

TRUE

1

#define

FALSE

0

#define

OK

1

#define

ERROR

0#define

INFEASIBLE-1#define

OVERFLOW-2//Status是函数的类型,其值是函数结果状态代码

typeintStatus;类C语言简要说明2.本书中所有的算法都以如下所示函数的形式加以表示，其中的结构类型使用前面已有的定义。

函数的形式:

函数类型

函数名（[形式参数及说明]）{

//算法说明

语句序列}

//函数名类C语言简要说明3．

赋值语句简单赋值：（1）变量名=表达式;

（2）变量++;

（3）变量--；串联赋值：变量1=变量2=变量3=…=变量k=表达式；成组赋值：（变量1，变量2，变量3，…变量k=（表达式1，表达式2，表达式3，…表达式k）；结构名=结构名;结构名=(值1,……，值k);变量名[]=表达式；

变量名[起始下标..终止下标]=变量名[起始下标..终止下标];交换赋值:变量名←→变量名条件赋值:变量名=条件表达式？表达式1:表达式2；类C语言简要说明4．

条件选择语句（1）

if（〈表达式〉）语句；（2）

if（〈表达式〉）语句1；

else

语句2；（3）

开关语句1switch

(<表达式>）{

case

值1:

语句组1；

break;

case

值2:

语句组2；

break;……

case

值n:

语句组n;

break;

[default:

语句组；]

}类C语言简要说明（4）

开关语句2switch

{

case

条件1:

语句组1；

break;

case

条件2:

语句组2；

break;……

case

条件n:

语句组n;

break;

[default:

语句组；]

}类C语言简要说明5．

循环语句（1）

for语句for(<表达式1>；<表达式2>；<表达式3>）{循环体语句；}（2）

while语句while(<条件表达式>）

{循环体语句；

}（3）

do-while语句do{循环体语句}while(<条件表达式>）类C语言简要说明6．

结束语句函数结束语句return表达式;return;switch结束语句break;异常结束语句exit(异常代码);类C语言简要说明7．

输入和输出语句输入语句scanf([格式串],变量1,变量2,……，变量n);输出语句printf(([格式串],表达式1，表达式2，……表达式n);switch结