L顺序存储
Lo+(i-1)*m
元素i
…….. Lo+（n-1)*m
元素n
Loc(元素i)=Lo+（i-1)*m
9
h
1345
链式存储
元素2 1536 元素3 1346 元素4
h
元素1 1400
∧
存储地址 1345 1346 ……. 1400 …….
存储内容 元素1 元素4 …….. 元素2 ……..
23
1.算法时间效率：用依据该算法编制的程序在 计算机上执行所消耗的时间来度量. 时间复杂度：基本操作重复执行的次数的 阶数 T(n)=o(f(n)).
例1：NXN矩阵相乘 for(i=1;i<=n;i++) //….. n+1 for(j=1;j<=n;j++) //……n(n+1) { c[i][j]=0; //……n*n for(k=1;k<=n;k++) // …..n*n(n+1) c[i][j]=c[i][j]+a[i][k]*b[k][j]; //…….n*n*n }
分类号： 出版单位： 出版时间： 价格：
3
例2
人机对奕问题
树
……..
……..
…...
…...
…...
…...
4
• 数据结构定义:
是一门研究非数值计算的程序设计问题中 计算机的操作对象以及它们之间的关系和 操作等等的学科.
5
1.2 基本概念和术语
• 数据（data)—所有能输入到计算机中去的描述客观事 物的符号 • 数据元素（data element）—数据的基本单位，也称节 点（node）或记录（record） • 数据项（data item）—有独立含义的数据最小单位， 也称域(field) • 数据结构（data structure)—数据元素和数据元素关 书目文件 系的集合
21
7. 在算法描述中可以使用的输入输出语句形式有：
输入语句 scanf( [格式串]，变量名1，...，变量名n)； 输出语句 printf( [格式串]，表达式1，...，表达式n);
8. 在算法描述中可以使用的扩展函数有：
求最大值 max（表达式1，...，表达式n）；这个 函数返回参数表中n个表达式计算结果中的最大值。 求最小值 min（表达式1，...，表达式n）；这个 函数返回参数表中n个表达式计算结果中的最小值。
t
27
## x ## y
正确写法 t=x; x=y; y=z;
##
## z
z=t;
注意：我们在写程序时必须兼顾 时间效率和空间效率。
28
小 结
本章介绍了贯穿全书的基本概念和基本思想
• 程序＝数据结构＋算法 • 数据结构
逻辑结构 物理结构 数据运算
• 算法 • 算法的复杂性分析
29
习题与练习
case 条件2：语句序列2；break；
...
case 条件n：语句序列n；break；
default：语句序列n+1；
}
20
5. 在算法描述中可以使用的循环结构语句形式有：
for循环语句 for （表达式1；循环条件表达式；表 达式2） 语句； while循环语句 while （循环条件表达式） 语句； do-while循环语句 do { 语句序列； } while （循环条件表达式）； 6. 在描述算法中可以使用的结束语句形式有： 函数结束语句 return 表达式； return; case或循环结束语句 break; 异常结束语句 exit；
7
1.数据的存储（物理）结构: 数据的逻辑结构 在计算机存储器中的具体实现。
存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系. 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系.
2.数据的逻辑结构—只抽象反映数据元素的逻辑 关系.
8
存储地址 存储内容
001 002 003 004 …… 高等数学 理论力学 高等数学 线性代数 …… 樊映川 罗远祥 华罗庚 栾汝书 …… S01 L01 S01 S02 ……
6
数据结构的三个方面： 线性结构 数据的逻辑结构 非线性结构 数据的存储结构 顺序存储 链式存储
线性表 栈 队 树形结构 图形结构
数据的运算：检索、排序、插入、删除、修改等
13
如用N-S图来描述从a和b中找大数的问题。 输入a和b a>b maxa maxb 输出max scanf(“%d,%d”,&a,&b); if(a>b) max=a; else max=b;
printf(“%d,%d”,a,b);
3、程序设计语言： 算法最终要用程序设计语言来描述，计算机才能保存、 翻译和执行。如用 C 语言来描述从 a和b中找大数的问题。 常用的算法有：迭代法、枚举法、递归法、递推法等。
一、名词解释
数据 数据项 数据元素 数据结构 数据逻辑结构 数据物理结构 算法 算法的时间复杂性
二、简答
• 1. 算法分析的目的是什么？ • 2. 什么是算法的最坏和平均时间复杂性？
30
三、分析下列算法的时间复杂性:
• 1．sum=0; for (i=1;i<=n;i++) { sum=sum+i; } • 2．i=1; while(i<=n) i=i*10;
1
第 三 章
2
第一讲
举例说明:
数据结构概述
线性表
S01 L01 S01 S02 ……
书目文件
1.1 什么是数据结构
程序=数据结构+算法 书目卡片 001 高等数学 樊映川 002 理论力学 罗远祥 登录号： 003 高等数学 华罗庚 004 书名： 线性代数 栾汝书 …… 作者名： …… ……
else 语句；
开关语句1 switch （表达式） {
case 值1：语句序列1；break； case 值2：语句序列2；break； ... case 值n：语句序列n；break； default：语句序列n+1； }
19
开关语句2 switch {
case 条件1：语句序列1；break；
22
三.
算法的评价(补充了解)
算法的评价标准
(1) 正确性：要求算法能够正确地执行预先规定的功能， 并达到所期望的性能要求。
(2) 可读性：为了便于理解、测试和修改算法，算法应该 具有良好的可读性。
(3) 健壮性：算法中拥有对输入数据、打开文件、读取文 件记录、分配内存空间等操作的结果检测，并通过与用 户对话的形式做出相应的处理选择。 (4) 时间与空间效率：算法的时间与空间效率是指将算法 变换为程序后，该程序在计算机上运行时所花费的时间 及所占据空间的度量。
成组赋值 （变量名1，...，变量名n）=（表达 1，...， 表达式n）；
结构赋值
条件赋值 交换赋值
结构名1 = 结构名2；
结构名 =（值1，值2，...，值n）； 变量名 = 条件表达式 ? 表达式1：表达式2； 变量名1 变量名2；
18
4. 在算法描述中可以使用的选择结构语 句形式有： 条件语句1 if （表达式） 语句； 条件语句2 if （表达式） 语句；
12
二、算法的描述方法
算法是考虑实现某一个问题求解的框架流程，而程序 设计则是根据这一求解的框架流程进行语言细化实现这一 问题求解的具体过程。常用描述算法的工具有： 1、自然语言： 使用人们日常进行交流的语言。 如：从a,b中找出一个大的数给max。 ⑴ 从键盘输入两个数给a和b； ⑵ 如果a比b大，则把a的值传给max， 否则把b的值传给max； ⑶ 输出max的值。 2、专用工具： 借助于有关图形工具或代码符号来描述。常用的工具有 流程图、N-S图等。
一、算法的概念 算法是由一套规则组成的一个过程，算法是对某一特 定问题的求解步骤的一种描述。算法应当具备以下几个方 面的特点： 1、一个算法必须保证执行有限步之后结束； 2、算法的每一个步骤必须具有确切的定义； 3、应对算法给出初始量； 4、算法具有一个或多个输出； 5、算法的每一步都必须是计算机能进行的有效操作。
f ( n) n 3
T n O n

3
24
当T(n)为多项式时,可只取其最高次幂项, 且它的系数也可略去不写。 一般地，对于足够大的n，常用的时间复 杂性存在以下顺序：
O(1)< O(logn)< O(n)< O(n*logn)< O(n2)< O(n3)…<O(2n)<O(3n)<…<O(n!)
其中,O(1)为常数数量级,即算法的 时间复杂性与输入规模n无关。
25
算法的运行时间往往还与具体输入的数据有关,通 常用以下两种方法来确定一个算法的运算时间： 1. 平均时间复杂性：研究同样的n值时各种可能的输 入，取它们运算时间的平均值。 2. 最坏时间复杂性：研究各种输入中运算最慢的一 种情况下的运算时间。
26
算法空间效率的分析：
一个算法的空间效率是指在算法的执行过程中， 所占据的辅助空间数量。 辅助空间就是除算法代码本身和输入输出数据 所占据的空间外，算法临时开辟的存储空间单 元。 在设计算法时，应该注意空间效率。
空间效率分析举例：
Q：某程序中已经定义了三个变量x、y、z，现需要把y 中的原有数据放到x中，z中的原有数据放到y中，x中的 原有数据放到z中。设计一组语句完成该操作。
指针 1400 ∧ ……. 1536 …….
1536
元素3
1346
10