第01章：绪论(第1讲)

1、严蔚敏 吴伟民清华大学出版社（C语言版）语言版）数据结构课程地位 数据结构与其它课程关系图：数据结构与其它课程关系图：数据结构数据库数据库人工智能人工智能专业基础课专业基础课操作系统操作系统编译原理编译原理非线性程序设计非线性程序设计离散数学离散数学语言程序设计语言程序设计计算机原理设计计算机原理设计数据结构课程学习特点数据结构的数据结构的基本概念基本概念（第（第1 1章）章）基本的数据结构基本的数据结构 线性结构线性结构非线性结构非线性结构基本的基本的数据处理技术数据处理技术 查找技术查找技术（第（第9 9章）章）关于本书内容编写说明关于本书内容编写说明基基本本结结构构（三部分）（三部分）排

2、序技术排序技术（第（第1010章）章）线性表（第线性表（第2 2章）章）栈和队列（第栈和队列（第3 3章）章）串（第串（第4 4章）章）数组和广义表（第数组和广义表（第5 5章）章）树树 （第（第6 6章）章）图图 （第（第7 7章）章）第1章 绪 论登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表线性表成绩表

3、.CEDABABACADBABCBDDADBDCEAEBECED数据结构数据结构就是要研究各类数据结构上的各种运算就是要研究各类数据结构上的各种运算根据数据元素间关系根据数据元素间关系(结构结构)的基本特性划分，有四种基本数据结构的基本特性划分，有四种基本数据结构: 存储结构分为：顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构数据的逻辑结构分为：线性结构 线性表、栈、队列、字符串、数组、广义表逻辑结构非线性结构树、图元素元素n n.元素元素i i

4、.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 15361536 . . . . . 15361536 元素元素3 3 13461346 链式存储链式存储 h 数据的逻辑结构数据的逻辑结构 数据的存

5、储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面： 数据类型高级语言中指数据的取值范围及其上可进行的操作的总称例 C语言中，提供int, char, float, double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型typedef struct int num; char n

6、ame20; float score;STUDENT;STUDENT stu1,stu2, *p;类描述算法的语言选择 类语言：类语言是接近于高级语言而又不是严格的高级语言，类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述以便把注意力主要集中在算法处理步骤本身的描述上。上。对C语言作以下描述：1.预定义常量和类型 # define TRUE 1 # define FALSE 0 # define MAXSIZE 100 # define OK 1 # defin

7、e ERROR 0对C语言作以下描述： 数据类型 函数名（形式参数及说明） 内部数据说明； int max(a,b) 执行语句组； if (a=b) return a; /*函数名*/ else return b; 2.函数的表示形式：3.赋值语句赋值语句对C语言作以下描述：（1）简单赋值简单赋值 1）变量名）变量名=表达式表达式 eg: a=b+1; 2） 变量变量+， eg: i+; 3） 变量变量- -， eg: i-;（2）串联赋值串联赋值变量变量1=变量变量2=变量变量3=变量变量k=表达式表达式 eg: a=b=c=d=eg: a=b=c=d= =k+1;对C语言作以下描述：（4）

8、条件赋值条件赋值变量名变量名=条件表达式？表达式条件表达式？表达式1:表达式表达式2 eg: a=1 b=2 ? 0:1eg: a=1 b=2 ? 0:1 （3）成组赋值成组赋值(, 变量变量k=(, , , )数组名数组名1 1 下标下标11下标下标2=2=数组名数组名2 2 下标下标11下标下标22 eg: a12=b124.条件选择语句对C语言作以下描述：if () 语句; if (ab) k+;if () 语句1; if(ab) k+; else 语句2; else k-;情况语句switch (） case 判断值1: 语句组 1； break; case 判断值2: 语句组 2；

9、break; case 判断值n: 语句组n; break; default: 语句组； break; 对C语言作以下描述：eg：switch (B) case 0: printf(“请输入0”）； break; case 1: printf(“请输入1”）； break; default printf(“错误”）； break; 对C语言作以下描述：对C语言作以下描述：5.循环语句循环语句for 语句语句for (；）循环体语句；循环体语句；for（i=2；i=20;i+) k=i+1;while 语句语句while (） 循环体语句；循环体语句； while(i=10) i-;对C语言作以

10、下描述：do while 语句语句do 循环体语句循环体语句 while (）dodoi-; while(i=10)while(i=10) 对C语言作以下描述：6.输入、输出函数输入、输出函数scanf getchar、printf putchar7.其它一些语句其它一些语句 return、break、continue8.注释语句注释语句 /*字符串字符串*/9.一些基本的函数一些基本的函数 max，min，abs，eof1.4 算法的描述和算法分析n算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性1. 有限性：有限步骤之内正常结束，不能形成无穷循环2. 确

11、定性：算法中的每一个步骤必须有确定含义，无二 义性得以实现。 3. 输 入： 有多个或0个输入 4. 输 出： 至少有一个或多个输出。5. 可行性：原则上能精确进行，操作可通过已实现基本 运算执行有限次而完成。 算法设计的要求 l 正确性正确性 l 易读性易读性 l 健壮性健壮性 l 高效率和低存储量高效率和低存储量例如要求n个数的最大值问题给出算法如下： max:=0; for（i=1 ；imax) max=x; 算法、语言、程序的关系1. 算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存储关系描述）。2. 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。3.程序

12、是算法在计算机中的实现。设计实现算法过程步骤1. 找出与求解有关的数据元素之间的关系2. 确定在某一数据对象上所施加运算3. 考虑数据元素的存储表示4. 选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描述。评价算法的标准 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量。（1）事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。 缺点：必须先运行依据算法编制的程序。 所得时间统

13、计量依赖于硬件、软件等环境 因素，掩盖算法本身的优劣。（2）事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适。性能评价性能评价定义：定义： 对问题规模与该算法在运行时所占的空间对问题规模与该算法在运行时所占的空间S与所与所耗费的时间耗费的时间T给出一个数量关系的评价给出一个数量关系的评价。 问题规模问题规模N对不同的问题其含义不同：对不同的问题其含义不同： 对矩阵是阶数；对矩阵是

14、阶数； 对多项式运算是多项式项数；对多项式运算是多项式项数； 对图是顶点个数；对图是顶点个数； 对集合运算是集合中元素个数。对集合运算是集合中元素个数。语句频度 定义：定义：语句频度是指该语句在一个算法中重复执行的次语句频度是指该语句在一个算法中重复执行的次数。数。例如：例如：两个两个矩阵矩阵相乘相乘算法语句算法语句 对应的对应的语句频度语句频度 1 1forfor（i=0i=0；i n;i+i n;i+） n n 2 2for for （j=0j=0；jn;j+jn;j+） n n2 2 3 cij=0; n 3 cij=0; n2 2 4 for (k=0;k n; k+) n 4 for

15、 (k=0;k n; k+) n3 3 cij=cij+aik cij=cij+aik* *bkj; nbkj; n3 3 总执行次数：总执行次数：Tn=2n3+2n2 +n算法的时间复杂度 算法的时间复杂度，即是算法的时间量度记算法的时间复杂度，即是算法的时间量度记做：做： T(n)=O(f(n)例如给出例如给出X=X+1（1）x=x+1 ；时间复杂度为；时间复杂度为O(1)，称为常量阶；，称为常量阶；（2）for (i=1; i= n; i+) x=x+1; 时间复杂度为时间复杂度为O(n)，称为线性阶；，称为线性阶；（3）for (i=1; i= n; i+)for (j=1;j= n;

16、 j+) x=x+1; 时间复杂度为时间复杂度为O(n2), 称为平方阶。称为平方阶。 一个算法由控制结构（顺序、分支和循环）和基本操作构成。所谓基本操作是指数据类型固有的操作，如加、减、乘、除等。通常以基本操作重复的次数来作为时间复杂度的度量。常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个:O(1) 常数型常数型 O(n)线性型线性型 O(n2)平方型平方型 O(n3)立方型立方型 O(2n)指数型指数型 O(log2n)对数型对数型O(nlog2n)二维型二维型按时间复杂度由小到大排列的频率表：按时间复杂度由小到大排列的频率表：常用的时间复杂度频率计数 常用的时间复杂度

17、频率表：常用的时间复杂度频率表：loglog2 2n nn nnlognlog2 2n nn n2 2n n3 32 2n n一般讲：前一般讲：前3种可实现，种可实现，后后3种虽理种虽理论上是可实论上是可实现的，实际现的，实际上只有对上只有对N限制在很小限制在很小范围才有意范围才有意义，当义，当N较较大时，不可大时，不可能实现。能实现。 0 01 10 01 11 12 21 12 22 24 48 84 42 24 48 81616646416163 38 8242464645125122562564 4161664642562565096509665536655365 5323216016010241024327683276821474836482147483648不必追求高效算法，不必追求高效算法，低效算法可由高速低效算法可由高速计算机来弥补的看计算机来弥补的看法是错误的。法是错误的。最坏时间复杂度 定义：定义：讨论算法在最坏情况下的时间复杂度，讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时即分析最坏情况下以估计出算法执行时间的上界。间的上界。例如起泡排序算法例如起泡排序算法void bubble(int a, int length)将将a中整数数