数据结构 1_绪 (2)

1、1数数 据据 结结 构构2第第 1 1 章章 绪论绪论3本章目录本章目录1.1数据结构的相关概念数据结构的相关概念 1.2数据类型和抽象数据类型数据类型和抽象数据类型 1.3算法与算法分析算法与算法分析 41.1 1.1 基本概念基本概念1. 1. 数据结构历史沿革数据结构历史沿革2. 2. 数据结构研究范畴数据结构研究范畴3. 3. 数据结构基本概念数据结构基本概念4. 4. 基本的逻辑结构基本的逻辑结构5. 5. 基本的物理结构基本的物理结构5数据结构历史沿革数据结构历史沿革6数据结构的发展数据结构的发展7数据结构的发展阶段数据结构的发展阶段8数据结构研究对象数据结构研究对象9数值计算的程

2、序设计问题数值计算的程序设计问题10非数值计算问题：非数值计算问题：学籍管理问题学籍管理问题11非数值计算问题：非数值计算问题：家庭成员的关系家庭成员的关系12如何实现对弈如何实现对弈?各格局之间是什么关系？各格局之间是什么关系？.非数值计算问题：非数值计算问题：人机对弈问题人机对弈问题13C1C2C3C4C6C5C7如何表示课程之间的先修关系？如何表示课程之间的先修关系？非数值计算问题：非数值计算问题：教学计划编排问题教学计划编排问题14图 1-2 煤气管道的铺设示意图 以上煤气管道线之间构成了网状结构，结构中的数据以上煤气管道线之间构成了网状结构，结构中的数据元素之间存在多对多的关系。元素

3、之间存在多对多的关系。非数值计算问题：非数值计算问题：煤气管道的铺设煤气管道的铺设15非数值计算问题：非数值计算问题： 多叉路口的交通灯设置多叉路口的交通灯设置16计算机处理问题的一般过程计算机处理问题的一般过程 问题数学模型建模实现求精机外表示机外表示处理要求处理要求逻辑结构逻辑结构基本运算基本运算存储结构存储结构算法算法17数据结构研究范畴数据结构研究范畴18表表1-1数据结构课程内容体系数据结构课程内容体系19数据结构地位数据结构地位20有关概念和术语有关概念和术语21数据、数据元素、数据项之间的关系数据、数据元素、数据项之间的关系22数据结构数据结构23典型逻辑结构典型逻辑结构2. 线

4、性表：数据元素之间存数据元素之间存在着一对一的线性关系；在着一对一的线性关系；3. 树：数据元素之间存在数据元素之间存在着一对多的层次关系着一对多的层次关系ABCDEFGHIJMKL4. 图：数据元素之间存在数据元素之间存在 着多对多的任意关系。着多对多的任意关系。BACDFE1. 集合：数据元素之间就是数据元素之间就是 “ “属于同一个集合属于同一个集合”24数据结构的形式定义数据结构的形式定义25 数组的形式定义数组的形式定义例：一维数组，A6=a1, a2, a3, a4, a5, a6R= | i=1, 2, 3, 4, 5D= a1, a2, a3, a4, a5, a6例：二维数组

5、D=a1, a2, a3, a4, a5, a6 R=row,col row = , col = , 26存储结构存储结构1. 1. 顺序存储顺序存储2. 2. 链式存储链式存储3. 3. 散列存储散列存储4. 4. 索引存储索引存储272829其它存储方法其它存储方法散列存储散列存储索引存储索引存储30逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系311.2 1.2 数据类型数据类型1. 1. 数据类型数据类型2. 2. 抽象数据类型抽象数据类型32数据类型数据类型33C C 语言中提供的基本数据类型语言中提供的基本数据类型34typedef struct int y; / 年号

6、Year int m; / 月号 Month int d; / 日号 Day DateType; / 日期类型定义定义“日期日期”为:定义定义“学生学生”为:typedef struct char id8; / 学号 char name16; / 姓名 char sex; / 性别M/F:男/女 DateType bdate; / 出生日期 Student; / 学生类型结构类型结构类型35抽象数据类型抽象数据类型36ADTADT是对数据类型的进一步抽象是对数据类型的进一步抽象 ADT逻辑结构逻辑结构操作集合操作集合数据结构数据结构存储结构存储结构算法设计算法设计类类成员变量成员变量成员函数成

7、员函数a. 使用视图使用视图 b. 设计视图设计视图 c. 实现视图实现视图 ADT的定义的定义 ADT的设计的设计 ADT的实现的实现ADTADT的不同视图的不同视图37抽象数据类型的形式化描述抽象数据类型的形式化描述38ADTADT描述描述操操作作说说明明39抽象数据类型复数的定义抽象数据类型复数的定义40复数的复数的ADTADT定义举例定义举例41C+C+实现的复数类型实现的复数类型Class complex private: float realpart; float imagpart; public: complex(float real,float imag)/构造函数 compl

8、ex();/析构函数 float GetReal();/返回复数的实部 float GetImag();/返回复数的虚部 .421.3 1.3 算法和算法分析算法和算法分析1.1.算法算法2.2.算法描述算法描述3.3.算法分析算法分析43算算 法法44算法特性算法特性45算法与程序算法与程序46算法设计要求算法设计要求47算法描述l 自然语言l 流程图l 程序设计语言l 类程序设计语言l 伪代码48mnr例：求两个自然数例：求两个自然数 mm 和和 n n 的的最大公约数最大公约数49 输入输入m 和和n； 求求m除以除以n的余数的余数r； 若若r等于等于0 0，则，则n为最大公约数，算法结

9、束；为最大公约数，算法结束；否则执行第步；否则执行第步； 将将n的值放在的值放在m中，将中，将r的值放在的值放在n中；中； 重新执行第步。重新执行第步。欧几里德算法：欧几里德算法：自然语言描述描述50优点：容易理解优点：容易理解缺点：冗长、二义性缺点：冗长、二义性使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 注意事项：避免写成自然段注意事项：避免写成自然段自然语言描述的特点自然语言描述的特点51N开始输入m和n r=m % nr=0m=n；n=r 输出n结束Y欧几里德算法：流程图欧几里德算法：流程图52流程图描述的特点流程图描述的特点53#include void main( )

10、coutCommonFactor(63, 54) endl;欧几里德算法：程序设计语言欧几里德算法：程序设计语言5455优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算法需要验证注意事项：将算法写成子函数注意事项：将算法写成子函数程序设计语言描述特点程序设计语言描述特点56伪代码伪代码（Pseudocode）：伪代码是自然语）：伪代码是自然语言和程序设计语言组成的混合结构，它比自言和程序设计语言组成的混合结构，它比自然语言更精确。它采用某一程序设计语言的然语言更精确。它采用某一程序设计语言的基本语法，操作指令可

11、以结合自然语言来设基本语法，操作指令可以结合自然语言来设计。计。优点：表达能力强，抽象性强，容易理解优点：表达能力强，抽象性强，容易理解伪代码伪代码57 1. r = m % n; 2. 循环下列操作，直循环下列操作，直到到 r 等于等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n;3. 输出输出 n ;欧几里德算法：伪码描述欧几里德算法：伪码描述58类程序设计语言类程序设计语言59欧几里德算法：欧几里德算法：类类C+C+描述描述intint CommonFactor(intCommonFactor(int m, m, intint n) n) intint r=

12、 m % n; r= m % n; while (r!=0) while (r!=0) m=n; m=n; n=r; n=r; r=m % n; r=m % n; return n; return n; #include void main( ) coutCommonFactor(63, 54) endl;60冒泡排序void sort (int A ,int n) int i, j, k; for(i=0;in-1;i+) for(j=0;jAj+1) t=Aj; Aj=Aj+1; Aj+1=t;void sort (int A ,int n) for(i=0;in-1;i+) for(j=

13、0;kAj+1) AjAj+1;程序设计语言类程序设计语言算法的(类)程序设计语言描述61类类C/C+C/C+语法概要语法概要赋值语句赋值语句简单赋值：x = 2; 串联赋值：x1 = x2 = x3 = 4 ;变量名=表达式变量名1=变量名k=表达式条件赋值：z= xy ? x:y ;交换赋值：x y ; 变量名=条件表达式？表达式T:表达式F变量名变量名62类类C/C+C/C+语法概要语法概要赋值语句赋值语句成组赋值: (x1,x2,x3) = (1,2,3) 变量名1，变量名k = 表达式1，,表达式k结构名 = 结构名 或 结构名 = (值1，值n)变量名 = 表达式array_A1.

14、5 = array_B3.7变量名变量名 起始下标起始下标. .终止下标终止下标 = = 变量名变量名 起始下标起始下标. .终止下标终止下标 63算法分析算法分析64与时间相关因素与时间相关因素65算法的执行时间算法的执行时间int Algo1( int n) if (n0) return 0; sum=0; for( i=0 ;i=n; i+ ) sum=sum + i ; return sum;算法 = 控制结构 + 原操作 算法执行时间= ( ( 基本操作基本操作(i)(i)的执行次数的执行次数基本操作基本操作(i)(i)的执行时间的执行时间 ) ) 算法的执行时间 与 原操作执行次数

15、之和 成正比 sum=sum=sumsum + i ; + i ;66定义定义 若存在两个正的常数若存在两个正的常数c和和n0，对于任意对于任意nn0，都有都有T( (n)cf( (n) )，则称则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之前的之前的情况无关情况无关紧要紧要T( (n) )cf( (n) )v当问题规模充分大时在渐近意义下的阶当问题规模充分大时在渐近意义下的阶算法分析算法分析大大OO符号符号67定理：若定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个是一个m次多项式，则次多项式，则A(n)=O(nm)。定理：大定理：大O

16、O符号运算符号运算(1)(log2n)(n)(nlog2n)(n2)(n3) (2n)(n!) (1)(1) 常量阶常量阶( (n n) ) 线性阶线性阶(n2) 平方阶平方阶(log2n) 对数阶对数阶(2n) 指数阶指数阶68例例1 + + x ; 例例2 for ( ( i=1; i=n; +i) ) + + x ; 算法分析举例一、二算法分析举例一、二69算法算法T(nT(n) )举例三举例三for ( i=1 ; in ; i+)for ( i=1 ; in ; i+) y=y+1 ; y=y+1 ;for ( j=0 ; j=n ; j+ )for ( j=0 ; j=n ; j+

17、 ) x+ ; x+ ; 70算法算法T(nT(n) )举例四举例四x=1 ;x=1 ;for ( i=1 ;i=n ; i+ )for ( i=1 ;i=n ; i+ ) for ( j=1 ; j=i ;j+ ) for ( j=1 ; j=i ;j+ ) x+ x+ ; ;71算法算法T(nT(n) )举例五举例五i=1;while (i=1&change;i-) change=False; for ( j = 0;j aj+1 ) aj aj+1;aj aj+1; change=TRUE ; /for / bubble_sort73最好情况、最坏情况、平均情况最好情况、最坏情况、平均情