当前位置:首页 >> IT/计算机 >>

第一章 数据结构绪论


吴 超 云 安庆师范学院

学习数据结构的意义
是为研究和解决如何有效地组织和处理非数值数 据而产生的理论、技术和方法。 据而产生的理论、技术和方法。 程序=数据结构 数据结构+算法 程序 数据结构 算法 是计算机科学中的一门综合性的专业基础课。 是计算机科学中的一门综合性的专业基础课。 涉及计算机软件、硬件以及数学等 涉及计算机软件、 数据结构在软件开发中的地位: 数据结构在软件开发中的地位: 系统分析 系统设计 系统实现 系统维护

数据结构发展趋势
包括两个方面: 包括两个方面: 一是面向专门领域中特殊问题的数据结构的 研究和发展,如图形数据结构、 研究和发展,如图形数据结构、知识数据结 空间数据结构, 构、空间数据结构, 另一方面,从抽象数据类型的角度,用面向 另一方面,从抽象数据类型的角度, 对象观点来讨论数据结构, 对象观点来讨论数据结构,已成为新的发展 趋势。 趋势。

教学要求
1、学会从问题入手,分析研究计算机加工的 学会从问题入手, 数据结构的特性, 数据结构的特性,以便为应用所涉及的数据选 择适当的逻辑结构、 择适当的逻辑结构、存储结构及其相应的操作 算法, 算法,并初步掌握时间和空间分析技术 2、进行复杂程序设计的训练,书写符合软件 、进行复杂程序设计的训练, 工程规范的文件,编写的程序代码应结构清晰、 工程规范的文件,编写的程序代码应结构清晰、 正确易读, 正确易读,能上机调试并排除错误

学习方法: 学习方法:
理解课程内容 勤于习题练习 加强上机实践

内容框架
基础数据结构 线性数据结构(第二、三章) 非线性数据结构 (数组和广义表) 应用数据结构(查找、内部排序、外部 排序、文件、动态存储管理等)

教材章节安排
绪论 线性表 栈和队列 串 数组和广义表 树和二叉树

图 动态存储管理 查找 内部排序 外部排序 文件

其中:线性表、栈与队列、二叉树、图、 查找与排序为重点。重点中二叉树、图 和查找又是难点。

与其它课程的关系
先修——C语言、离散数学

后续课的基础如
操作系统、数据库、编译原理、面向对象 的程序设计、人工智能 …

课时安排: (5学分)
数据结构——68学时 上机——34学时 考试方式
作业+平时+上机: 期末考试: 70% 30%

(主要考核对概念的理解、方法的掌握和算法的实现情况)

教材:
教材名称 作者 出版社 出版日期 《数据结构》(C语言版) 耿国华 高等教育出版社 2005年7月第1版

参考文献
[1]张乃孝等 《算法与数据结构――C语言描述》 高等教育出 版社 2002 [2]刘大有等 《数据结构》 高等教育出版社 2001 [3]李根强等 《数据结构C++描述》 中国水利水电出版社 2001 [4]黄国瑜等 《数据结构(C语言版)》 清华大学出版社, 2001 [5] 算法+数据结构=程序 算法+数据结构= 沃思著 科学出版社 [6]William Ford、William Topp ,《DATA STRUCTURES with C++》,Prentice Hall, Inc.,1996 [7]严蔚敏等 数据结构 语言版》清华大学出版社 语言版》 严蔚敏等 数据结构C语言版 清华大学出版社1997

第一章 绪论

1.1 数据结构讨论的范畴 1.2 基本概念 1.3 抽象数据类型的表示和实现 1.4 算法和算法的分析

1.1 数据结构讨论的范畴
例如: 例如 数值计算的程序设计问题 结构静力分析计算 ─━ 线性代数方程组

非数值计算的程序设计问题
书目自动检索系统 书目卡片
登录号 书名 作者名 分类号 出版单位 出版时间 价格:
001 002 003 004 …… 高等数学 理论力学 高等数学 线性代数 ……

线性表

书目文件

樊映川 罗远祥 华罗庚 栾汝书 ……

S01 L01 S01 S02 ……

按书名
高 等 数 学 001, 003… … 理 论 力 学 002, … … .. 线 性 代 数 004, … … …… … … ..

按作者名
樊映川 华罗庚 栾汝书 ……. 0 0 1, … 0 0 2, … . 0 0 4, … . …….

按分类号

L S ……

002,… 001,003, ……

人机对奕问题



……..

……..

…...

…...

…...

…...

多叉路口交通灯管理问题



C AB AC AD B BA BC BD E A D

DA EA EB

DB EC

DC ED

1.2

基本概念

一、数据与数据结构 二、数据类型 三、抽象数据类型

一、数据与数据结构
数据: 数据:
所有能被输入 被输入到计算机中,且能被 被输入 计算机处理的符号 处理的符号的集合。 处理的符号 可见数据是计算机操作的对象 计算机操作的对象的总称。 计算机操作的对象 是计算机处理的信息的 信息的某种特定的 信息的 符号表示形式 表示形式。 表示形式

数据元素( Element) 数据元素(Data Element):
是数据(集合)中的一个“个体 个体” 个体 是数据结构中讨论的基本 基本单位 基本

数据对象
性质相同的数据元素的集合

数据项: 数据项: 是数据结构中讨论的最小 最小单位 最小
数据元素是数据项的集合 例如:描述一个运动员的数据元素可以是
姓名 俱乐部名称 出生日期 参加日期 职务 业绩

年月日

称之为组合项

数据结构: 结构的数据元素的集合 数据结构: 结构 带结构
假设用三个 4 位的十进制数 三个 位的十进制数表示一个含 12 位 数的十进制数。 数的十进制数。 例如: 例如: 3214,6587,9345 ─ a1(3214),a2(6587),a3(9345)

则在数据元素 a1、a2 和 a3 之间存在着 次序” “次序”关系 <a1,a2>、<a2,a3> > > 3214,6587,9345 ≠ 6587,3214,9345 a1 a2 a3 a2 a1 a3

带结构 数据结构: 结构的数据元素的集合 数据结构: 结构
又例,在2行3列的二维数组{a1, a2, a3, a4, a5, a6} 中六个元素之间 a1 a2 a3 存在两个关系: a4 a5 a6

行的次序关系: 行的次序关系
row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}

列的次序关系: 列的次序关系:
col = {<a1,a4>,<a2,a5>,<a3,a6>}

a1 a3 a5 a2 a4 a6

a1 a2 a3 a4 a5 a6

带结构 数据结构: 结构的数据元素的集合 数据结构: 结构
再例,在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系 次序关系: 次序关系

{<ai, ai+1>| i=1, 2, 3, 4, 5}
可见,不同的“关系 关系”构成不同的“结构 结构” 关系 结构 或者说,数据结构 相互之间存在着某 数据结构是相互之间存在着某 数据结构 种逻辑关系的数据元素的集合。 种逻辑关系的数据元素的集合

数据类型
性质相同的值的集合以及定义在这 个值集合上的一组操作的总称 原子类型:不可分解,包括标准类 型和指针类型 结构类型:

数据的逻辑结构 逻辑结构可归结为以下四类: 四类: 逻辑结构 四类

线性结构 树形结构 图状结构 集合结构

数据结构的形式定义为: 数据结构的形式定义 数据结构是一个二元组 Data_Structures = (D, S)
其中:D 是数据元素的有限集, 数据元素的有限集
S 是 D上关系的有限集。 关系的有限集

例 1-4 其中: 其中:

复数的数据结构定义如下 Complex=(C, Complex=(C,R)

C是含两个实数的集合﹛C1,C2﹜,分别 是含两个实数的集合﹛ 表示复数的实部和虚部。R={P}, 表示复数的实部和虚部。R={P},P是定义 在集合上的一种关系{ C1,C2〉 在集合上的一种关系{〈C1,C2〉}。

课题组由1名教师、1~3名研究生 1~6名本科 名研究生、 例1-5 课题组由1名教师、1~3名研究生、1~6名本科 生组成;成员关系是:教师指导研究生、 生组成;成员关系是:教师指导研究生、研究生 指导1~2名本科生。 指导1~2名本科生。 1~2名本科生

定义DS如下: 定义 如下: 如下 Group=(D,R) ( , )
D={T,G1,…,Gn,S11,…Snm} 1≤n≤3, 1≤m≤2 R={R1,R2} R1={<T,Gi>|1 ≤ i ≤ n , 1 ≤ n ≤ 3} R2={<Gi,Sij>|1≤i≤n ,1≤ j ≤ m , 1 ≤ n ≤ 3 , 1 ≤ m ≤ 2 }

数据的逻辑结构—只抽象反映数据元 素的逻辑关系 数据的存储(物理)结构—数据的逻 辑结构在计算机存储器中的实现
数据的逻辑结构与存储结构密切相关 算法设计 算法实现 逻辑结构 存储结构

数据的存储结构
—— 逻辑结构在存储器中的映象 映象
“数据元素”的映象 ?
二进制位串

“关系”的映象 ?
有序对

存储结构分为: 顺序存储结构——借助元素在存储器中的 相对位置来表示数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址 的指针表示数据元素间的逻辑关系

存储地址 存储内容 Lo Lo+m 元素1 元素1 元素2 元素2 …….. Lo+(i-1)*m 元素i 元素i …….. Lo+(n-1)*m ( 元素n 元素n

顺序存储

Loc(元素 元素i)=Lo+(i-1)*m 元素 (

h
1345

链式存储
以附加信息(指针) 以附加信息(指针) 表示后继关系

h
元素1 元素1 1400 元素2 元素2 1536

元素3 元素3 1346

元素4 元素4



存储地址 1345 1346 ……. . 1400 ……. . 1536

存储内容 元素1 元素1 元素4 元素4 …….. .. 元素2 元素2 …….. .. 元素3 元素3

指针 1400 ∧ ……. . 1536 ……. . 1346

数据结构的定义
按某种逻辑关系组织起来的一批数据, 按某种逻辑关系组织起来的一批数据,按 一定的映象方式把它存放在计算机存贮 器中, 器中,并在这些数据上定义了一个运算 的集合,就叫做数据结构 数据结构。 的集合,就叫做数据结构。 数据结构的内容可归纳为三个部分, 数据结构的内容可归纳为三个部分,逻辑 结构、存储结构、运算集合: 结构、存储结构、运算集合: 数据结构是一门主要研究怎样合理地组织 数据、建立合适的数据结构、 数据、建立合适的数据结构、提高计算机 执行程序所用的时空效率的学科。 执行程序所用的时空效率的学科。

二、数据类型
是一个值的集合 集合和定 数据类型 是一个值的集合和定 义在此集合上的一组操作的总称。 义在此集合上的一组操作的总称。 操作的总称 原子类型:不可分解, 原子类型:不可分解,包括标准类 型和指针类型 结构类型: 结构类型:

例如,C 语言中提供的基本数据类型有: 整型 int 浮点型 float 双精度型 double 字符型 char 逻辑型 bool

三、抽象数据类型
简称ADT) (Abstract Data Type 简称 )

是指一个数学模型以及 定义在此数学模型上的一 组操作。 组操作。

例如,抽象数据类型复数的定义: 例如,抽象数据类型复数的定义:
ADT Complex {
数据对象: 数据对象: D={e1,e2|e1,e2∈RealSet } = | ∈ 数据关系: 数据关系: R1={<e1,e2> | e1是复数的实数部分 = 是复数的实数部分 | e2 是复数的虚数部分 }

基本操作: 基本操作: AssignComplex( &Z, v1, v2 ) 操作结果: Z,其实部和虚部 操作结果:构造复数 Z,其实部和虚部 的值。 分别被赋以参数 v1 和 v2 的值。 DestroyComplex( &Z) 操作结果:复数Z被销毁。 操作结果:复数Z被销毁。 GetReal( Z, &realPart ) 初始条件:复数已存在。 初始条件:复数已存在。 操作结果: 返回复数Z 操作结果:用realPart返回复数Z的实部值。 返回复数 的实部值。

GetImag( Z, &ImagPart ) 初始条件:复数已存在。 初始条件:复数已存在。 操作结果: 返回复数Z 操作结果:用ImagPart返回复数Z的虚部值。 返回复数 的虚部值。 Add( z1,z2, &sum ) 初始条件: 是复数。 初始条件:z1, z2是复数。 是复数 操作结果: 返回两个复数z1, 操作结果:用sum返回两个复数 z2 的 返回两个复数 和值。 和值。

} ADT Complex

ADT 有两个重要特征 有两个重要特征:
描述程序处理的实体 数据抽象 用ADT描述程序处理的实体 时,强调的是其本质的特征、其所能完 强调的是其本质的特征、 成的功能以及它和外部用户的接口( 成的功能以及它和外部用户的接口(即 外界使用它的方法)。 外界使用它的方法)。

数据封装

将实体的外部特性和其内部

实现细节分离, 实现细节分离,并且对外部用户隐藏 其内部实现细节。 其内部实现细节。

抽象数据类型的描述方法
抽象数据类型可用( , , )三元组表示。 抽象数据类型可用(D,S,P)三元组表示。

其中: 是数据对象; 其中:D 是数据对象; S 是 D 上的关系集; 上的关系集; P 是对 D 的基本操作集。 的基本操作集。

ADT 抽象数据类型名 { 数据对象: 数据对象的定义〉 数据对象:〈数据对象的定义〉 数据关系: 数据关系的定义〉 数据关系:〈数据关系的定义〉 基本操作: 基本操作的定义〉 基本操作:〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 其中基本操作的定义格式为: 基本操作名(参数表) 基本操作名(参数表) 初始条件:〈初始条件描述〉 初始条件: 初始条件描述〉 操作结果:〈操作结果描述〉 操作结果: 操作结果描述〉

赋值参数 只为操作提供输入值。 只为操作提供输入值。 打头, 引用参数 以&打头,除可提供输入值外, 打头 除可提供输入值外, 还将返回操作结果。 还将返回操作结果。 初始条件 描述了操作执行之前数据结构 和参数应满足的条件,若不满足, 和参数应满足的条件,若不满足,则操 作失败,并返回相应出错信息。 作失败,并返回相应出错信息。 说明了操作正常完成之后, 操作结果 说明了操作正常完成之后,数 据结构的变化状况和应返回的结果。 据结构的变化状况和应返回的结果。若 初始条件为空,则省略之。 初始条件为空,则省略之。

1.3 抽象数据类型的表示和实现
抽象数据类型需要通过固有数据 类型( 类型(高级编程语言中已实现的数据 类型)来实现。 类型)来实现。
例如,对以上定义的复数。 例如,对以上定义的复数。

// -----数据类型的定义 数据类型的定义

typedef struct { float realpart; ; float imagpart; ; }complex; ;
// -----基本操作的函数原型说明 基本操作的函数原型说明 void Assign( complex &Z, float realval, float imagval ); ; // 构造复数 Z,其实部和虚部分别被赋以参数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值

float GetReal( complex Z ); ;
// 返回复数 Z 的实部值 float Getimag( complex Z ); ; // 返回复数 Z 的虚部值 void add( complex z1, complex z2, complex &sum ); ; // 以 sum 返回两个复数 z1, z2 的和

// -----基本操作的实现 基本操作的实现 void add( complex z1, complex z2, complex &sum ) { // 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; }

{ 其它省略 }

1.4 算法和算法的分析
一、算法 二、算法设计的原则 三、算法效率的衡量方法和准则 四、算法的存储空间需求

一、算法
算法是规则的有限集合, 算法是规则的有限集合,是为解决特定问题 而规定的一系列操作。 而规定的一系列操作。一个算法必须满足以 下五个重要特性: 个重要特性:

1.有穷性 2.确定性 4.有输入 5.有输出

3.可行性

对于任意一组合法输入值, 1.有穷性 对于任意一组合法输入值, 在执行有穷步骤之后一定能结束, 有穷步骤之后一定能结束 在执行有穷步骤之后一定能结束,即: 算法中的每个步骤都能在有限时间内完成。 有限时间内完成 算法中的每个步骤都能在有限时间内完成。 2.确定性 对于每种情况下所应执行的 操作,在算法中都有确切的规定 确切的规定, 操作,在算法中都有确切的规定,使算法 的执行者或阅读者都能明确其含义及如何 执行。并且在任何条件下, 执行。并且在任何条件下,算法都只有一 条执行路径。 条执行路径。

3.可行性 算法中的所有操作都必须足 够基本,都可以通过已经实现的基本操作 够基本, 运算有限次实现之。 运算有限次实现之。 4.有输入 作为算法加工对象的量值, 作为算法加工对象的量值, 通常体现为算法中的一组变量。 通常体现为算法中的一组变量。有些输入 量需要在算法执行过程中输入, 量需要在算法执行过程中输入,而有的算 法表面上可以没有输入, 法表面上可以没有输入,实际上已被嵌入 算法之中。 算法之中。

它是一组与“输入” 5.有输出 它是一组与“输入”有 确 定关系的量值, 定关系的量值,是算法进行信息加 工后得到的结果, 工后得到的结果,这种确定关系即 为算法的功能。 为算法的功能。

算法描述的工具
1.算法、语言、程序的关系 .算法、语言、 先分析数据结构中算法、语言、程序的关系: 先分析数据结构中算法、语言、程序的关系: 算法:描述了数据对象的元素之间的关系( ⑴ 算法:描述了数据对象的元素之间的关系(包括数据 逻辑关系、存贮关系描述)。 逻辑关系、存贮关系描述)。 描述算法的工具:(自然语言、 :(自然语言 ⑵ 描述算法的工具:(自然语言、框图或高级程序设计 语言)算法的描述可用自然语言、框图或高级程序设 语言)算法的描述可用自然语言、 计语言,自然语言简单但易于产生二义。 计语言,自然语言简单但易于产生二义。框图直观但 不擅长表达数据组织结构, 不擅长表达数据组织结构,而其中以高级程序语言较 为准确但又比较严谨。 为准确但又比较严谨。 程序是算法在计算机中的实现( ⑶ 程序是算法在计算机中的实现(与所用计算机及所用 语言有关) 语言有关)

2.设计实现算法过程步骤: .设计实现算法过程步骤:
●找出与求解有关的数据元素之间的关 建立结构关系) 系(建立结构关系) 确定在某一数据对象上所施加运算(操作 操作) ●确定在某一数据对象上所施加运算 操作 ●考虑数据元素的存储表示 ●选择描述算法的语言 设计实现求解的算法, ●设计实现求解的算法,并用程序语言加以描述

C语言说明 语言说明
1. 预定义常量和类型 . 本书中用到以下常量符号, 本书中用到以下常量符号,如True、False、 、 、 MAXSIZE等,约定用如下宏定义预先定义: 等 约定用如下宏定义预先定义: # define TRUE 1 # define FALSE 0 #define MAXSIZE 100 # define OK 1 # define ERROR 0

2.本书中所有的算法都以如下所示函数的 本书中所有的算法都以如下所示函数的 形式加以表示
[数据类型 函数名([形式参数及说明 ) 数据类型] 函数名( 形式参数及说明 形式参数及说明]) 数据类型

3.赋值语句 赋值语句 4.条件选择语句 条件选择语句 5.循环语句 循环语句 6.输入、输出语句 输入、 输入

函数结果的带出方式(返回函数值) 函数结果的带出方式(返回函数值)
1.全局变量方式 全局变量方式 2.数组方式 数组方式 3.结构体方式 结构体方式 4.指针方式 指针方式

二、算法设计的原则
设计算法时,通常应考虑达到以下目标: 设计算法时,通常应考虑达到以下目标: 1.正确性 . 2. 可读性 . 3.健壮性 . 4.高效率与低存储量需求 .

1.正确性
首先算法应当满足以特定的“规格说 首先算法应当满足以特定的“ 明”方式给出的需求。 方式给出的需求。 其次对算法是否“正确”的理解可以 其次对算法是否“正确” 有以下四个层次: 有以下四个层次: a.程序中不含语法错误; 程序中不含语法错误; b.程序对于几组输入数据能够得出 满足要求的结果; 满足要求的结果;

c.程序对于精心选择的、典型、苛刻且 程序对于精心选择的、典型、 带有刁难性的几组输入数据能够得出满足 要求的结果; 要求的结果; d.程序对于一切合法的输入数据都能得 出满足要求的结果; 出满足要求的结果;

通常以第 c 层意义的正确性作为衡 量一个算法是否合格的标准。 量一个算法是否合格的标准。

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

3.健壮性 .
当输入的数据非法时, 当输入的数据非法时,算法应当恰当 地作出反映或进行相应处理, 地作出反映或进行相应处理,而不是产 生莫名奇妙的输出结果。并且,处理出 生莫名奇妙的输出结果。并且, 错的方法不应是中断程序的执行, 错的方法不应是中断程序的执行,而应 是返回一个表示错误或错误性质的值, 是返回一个表示错误或错误性质的值, 以便在更高的抽象层次上进行处理。 以便在更高的抽象层次上进行处理。

4.高效率与低存储量需求 .
通常,效率指的是算法执行时间; 通常,效率指的是算法执行时间; 算法执行时间 存储量指的是算法执行过程中所需的 存储量指的是算法执行过程中所需的 最大存储空间, 最大存储空间,两者都与问题的规模 有关。 有关。

三、算法效率的衡量方法和准则 通常有两种衡量算法效率的方法: 通常有两种衡量算法效率的方法:

事后统计法
缺点: 缺点:1.必须执行程序 2.其它因素掩盖算法本质

事前分析估算法

和算法执行时间相关的因素: 和算法执行时间相关的因素:
1.算法选用的策略 2.问题的规模 3.编写程序的语言 4.编译程序产生的机器代码的质量 5.计算机执行指令的速度

一个特定算法的“运行工作量” 一个特定算法的“运行工作量” 算法的 的大小,只依赖于问题的规模 的大小,只依赖于问题的规模 (通常用整数量n表示),或者说, 表示),或者说, 通常用整数量 表示),或者说 它是问题规模的函数。 它是问题规模的函数。

假如, 的增长, 假如,随着问题规模 n 的增长, 算法执行时间的增长率和 f(n) 的增长 率相同,则可记作: 率相同,则可记作:

T (n) = O(f(n))
为算法的(渐近 时间复杂度。 渐近)时间复杂度 称T (n) 为算法的 渐近 时间复杂度。

算法评价的标准: 算法评价的标准:时间复杂度和空间复杂度。

时间复杂度
指在计算机上运行该算法所花费的时间。 指在计算机上运行该算法所花费的时间。 用“O(数量级)”来表示,称为“阶”。 (数量级) 来表示,称为“ 常见的时间复杂度有: 常见的时间复杂度有: 2 O(1) O(logn) O(n ) O( n ) ( ) ( ) ( ( 常数阶 对数阶 线性阶 平方阶

空间复杂度
指算法在计算机上运行所占用的存储空 间。度量同时间复杂度。 度量同时间复杂度。

例 void mult(int a[], int b[], int& c[] ) 一 { 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)

例 void select_sort(int& a[], int n) { 中整数序列重新排列成自小至大有序的整数序列。 二 // 将 a 中整数序列重新排列成自小至大有序的整数序列。 选 择 排 序

for ( i = 0; i< n-1; ++i ) { j = i; // 选择第 i 个最小元素 for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j = k; if ( j != i ) a[j] ←→ a[i] } 基本操作: 基本操作: } // select_sort
比较(数据元素) 比较(数据元素)操作 时间复杂度: 时间复杂度: O(n2)

例 void bubble_sort(int& a[], int n) { 三 // 将 a 中整数序列重新排列成自小至大有序的整数序列。 中整数序列重新排列成自小至大有序的整数序列。 冒 泡 排 序 for (i=n-1, change=TRUE; i>1 && change; --i) { change = FALSE; // change 为元素进行交换标志 for (j=0; j<i; ++j) if (a[j] > a[j+1]) { a[j] ←→ a[j+1]; change = TRUE ;} } // 一趟起泡 } // bubble_sort

基本操作: 基本操作: 赋值操作 时间复杂度: 时间复杂度: O(n2)

语句频度: 语句频度:是指该语句重复执行的次数 例3 {++x;s=0;} 自增看成是基本操作, 将x自增看成是基本操作,则语句频度 自增看成是基本操作 即时间复杂度为O 为1,即时间复杂度为O(1) 例4、for(i=1;i<=n;++i) 、 {++x;s+=x;} 语句频度为: 其时间复杂度为: 语句频度为:n 其时间复杂度为: O(n) 即时间复杂度为线性阶。 即时间复杂度为线性阶。

例4、for(i=1;i<=n;++i) for(j=1;j<=n;++j) {++x;s+=x;} 语句频度为:n2 语句频度为: 其时间复杂度为: 其时间复杂度为:O(n2) 即时间复杂度为平方阶。 即时间复杂度为平方阶。

例5for(i=2;i<=n;++i) for(j=2;j<=i;++j) {++x;a[i,j]=x;} , 语句频度为: 语句频度为: 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2) 时间复杂度为 即此算法的时间复杂度为平方阶

以下六种计算算法时间的多项式是最常用的。 以下六种计算算法时间的多项式是最常用的。 其关系为: 其关系为: O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3) 指数时间的关系为: 指数时间的关系为: O(2n)<O(n!)<O(nn)
取得很大时, 当n取得很大时,指数时间算法和多项式时间算法 在所需时间上非常悬殊。因此, 在所需时间上非常悬殊。因此,只要有人能将现有指 数时间算法中的任何一个算法化简为多项式时间算法, 数时间算法中的任何一个算法化简为多项式时间算法, 那就取得了一个伟大的成就。 那就取得了一个伟大的成就。

有的情况下, 有的情况下,算法中基本操作重复执行的次数还 随问题的输入数据集不同而不同。例如: 随问题的输入数据集不同而不同。例如:
Void bubble-sort(int a[],int n) , for(i=n-1;change=TURE;i>1 && change;--I) { change=false; for(j=0;j<i;++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1]; change=TURE} } 最好情况: 次 最好情况:0次 最坏情况: 最坏情况:1+2+3+…+n-1 =n(n-1)/2 平均时间复杂度为:O(n2) 平均时间复杂度为

四、算法的存储空间需求

算法的空间复杂度定义为: 算法的空间复杂度定义为: S(n) = O(g(n))
的增大, 表示随着问题规模 n 的增大, 算法运行所需存储量的增长率 的增长率相同。 与 g(n) 的增长率相同。

算法的存储量包括:
1.输入数据所占空间 . 2.程序本身所占空间 . 3.辅助变量所占空间 .

? 计算 !+2!+…+n! 计算1! ! ? 复数的定义和基本操作

#include "stdio.h" main() { int jch; int n=11; jch=ssum(n); printf("1!+2!+...+n!\n %ld",jch); }

int ssum(int n) { /* 计算 计算1!+2!+…+n! */ int p=1,s=0;int i; for (i=1;i<=n;++i) { p=p*i;s=s+p; } return s; }

/* 创建一个复数 */ complex Create(float c1,float c2) { complex c; c.realpart=c1; c.imagpart=c2; return c; } /* Create */ /* 输出一个复数 */ void outputc(complex z) { printf("\n %f+%f i \n\n", z.realpart,z.imagpart); }

/* 求两个复数相加之和 */ complex Add(complex z1,complex z2) { complex sum; sum.realpart=z1.realpart+z2.realpart; sum.imagpart=z1.imagpart+z2.imagpart; return sum; } /* Add */

/* 主函数 */ main() { complex h1,h2,h3,h4;float real,imag; float a1=3.0,b1=4.0,a2=1.2,b2=1.3; h1=Create(a1,b1); outputc(h1); h2=Create(a2,b2); outputc(h2); real=GetReal(h1); printf("\n realpart=%f\n",real); imag=GetImag(h1); printf("\n imagpart=%f\n",imag); h3=Add(h1,h2); outputc(h3); h4=Sub(h1,h2); outputc(h4); } /* main */

本章要求
熟悉数据结构各名词术语的含义, ◎ 熟悉数据结构各名词术语的含义,掌握 基本概念, 基本概念,掌握数据的逻辑结构和存储 结构之间关系 了解抽象数据类型的定义、 ◎ 了解抽象数据类型的定义、表示和实现 方法 ◎ 掌握算法的描述和算法分析的方法 掌握估算算法时间复杂度的方法。 ◎ 掌握估算算法时间复杂度的方法。

小结
数据结构定义: 数据结构定义: 数据结构是指相互之间存在一种或多种特定关 系的数据元素集合, 系的数据元素集合,是带有结构的数据元素的 集合,它指的是数据元素之间的相互关系, 集合,它指的是数据元素之间的相互关系,即 数据的组织形式。 数据的组织形式。 数据结构的内容可归纳为三个部分, 数据结构的内容可归纳为三个部分, 逻辑结构、存储结构和运算集合。 逻辑结构、存储结构和运算集合。 按某种逻辑关系组织起来的一批数据, 按某种逻辑关系组织起来的一批数据,按一定的 映象方式把它存放在计算机存贮器中, 映象方式把它存放在计算机存贮器中,并在这 些数据上定义了一个运算的集合, 些数据上定义了一个运算的集合,就叫做数据 结构。 结构。

算法的定义: 算法的定义:
算法是规则的有限集合, 算法是规则的有限集合,是为解决特定问题而规定的 一系列操作。 一系列操作。

算法的五个特性 :
有限性、 有限性、确定性 、可行性 、输入 、输出

算法设计的四个要求: 算法设计的四个要求:
算法的正确性、可读性、健壮性、 算法的正确性、可读性、健壮性、高效率和低存储量

时间复杂度——语句频度 语句频度 时间复杂度 最坏时间复杂度 算法的空间复杂度


相关文章:
第一章 数据结构绪论_图文.ppt
第一章 数据结构绪论 - 数据结构 考核方式:考查 主讲:周淘晴 第一章 绪论
数据结构第一章绪论练习题.doc
数据结构第一章绪论练习题 - 一、选择题 1.组成数据的基本单位是( c )。 (A) 数 据项 (D)数据变量 2.数据结构是研究数据的( c )以及它们之间的相 互...
数据结构:第一章 绪论_图文.ppt
数据结构:第一章 绪论 - N. 沃思(Niklaus Wirth)教授: 算法+数据结构=程序 不了解施加于数据上的算法就无法决 定如何构造和组织数据, 反之,算法的选择常常在...
数据结构 第一章 绪论_图文.ppt
数据结构 第一章 绪论 - 第一章 绪论 教学目标 1. 了解数据结构研究的主要内容 2.掌握数据结构中涉及的基本概念 3. 掌握算法、算法的时间复杂度及其分析的 ...
第一章数据结构绪论._图文.ppt
第一章数据结构绪论. - 数据结构(C语言版) 严蔚敏 吴伟民 编著 信息工程学
数据结构第一章 绪论_图文.ppt
数据结构第一章 绪论 - 《数据结构》 主讲教师: 刘晓华 毕业院校: 中国矿业
数据结构第一章 绪论_图文.ppt
数据结构第一章 绪论 - 山东科技大学 信息学院 数据结构教程 第一章 绪 论 课前思考 1.1 数据结构讨论 的范畴 1.2 基本概念 1.3 算法和算法 的量度 课...
数据结构 第一章 绪论_图文.pdf
数据结构 第一章 绪论 - 数据结构与算法 1 内容提要 z课程简介 z第一章 绪论 2 导言-1 1 z z z z z z 汉字结构 细胞结构 物质结构 地球的内部结构 ...
数据结构 第一章 绪论_图文.ppt
数据结构 第一章 绪论 - 数据结构及其C语言 实现 数据结构(C语言版) 授课
第一章 数据结构绪论_图文.ppt
第一章 数据结构绪论 - 第一章 绪论 中国海洋大学信息学院 魏振钢 Tel:0
1数据结构第一章绪论_图文.ppt
1数据结构第一章绪论 - 算法与数据结构 教材:《数据结构(C语言版)》。严蔚敏,吴伟民 编著。清华大学出版社。 参考文献: 1 《数据结构》 。张选平,...
第一章 数据结构---绪论.doc
第一章 数据结构---绪论 - 数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班 课程导入 课程性质:专业必修...
数据结构 第一章 绪论_图文.ppt
数据结构 第一章 绪论 - 数据结构 Data structure 课堂纪律与考
数据结构 PPT第一章 绪论_图文.ppt
数据结构 PPT第一章 绪论 - 教材: 《数据结构》(C语言版) 严蔚敏 吴伟民 编著 授课教师:涂风华 开始日期:2011年9月6日 第1章 绪论 1.1 什么是数据结构 1...
数据结构 第一章 绪论_图文.ppt
数据结构 第一章 绪论 - 数据结构 遥感信息工程学院 邬建伟 关于数据结构课程 数据结构, 数据结构,起源于程序设计需求: 是讨论“描述现实世界实体的数学模型 非...
数据结构课后习题解答第一章 绪论.doc
数据结构课后习题解答第一章 绪论 - 第一章 绪论 1.1 试写一个算法,自大到
数据结构第一章绪论_图文.ppt
数据结构第一章绪论 - 课程内容: ?计算机软件的基础知识数据结构 课时安排: ?数据结构64学时 ?上机16学时 ?4,5,6,7,10,11,12,13周,周一...
数据结构 第一章 绪论_图文.ppt
数据结构 第一章 绪论 - 第一章绪论 主讲人:彭延军 山东科技大学 信息学院 数据结构教程 第一章 绪 论 课前思考 1.1 数据结构讨论 的范畴 1.2 基本...
数据结构new 第一章 绪论_图文.ppt
数据结构new 第一章 绪论 - 数据结构 吉海颖 管理科学与工程学院 juliaji@163.com 学时数:54 学分:4 教材:严蔚敏等,数据结构(C语言版),清华 大学出版社,1...
数据结构绪论资料_图文.ppt
数据结构 ? (C语言版)严蔚敏等编著,清华 大学出版社 参考书 ? 数据结构 ? (用面向对象方法与C++描述) 殷人昆等编著,清华大学出版社 第一章 绪论 ? ? 什么...