c语言数据结构第五章课件清华出版社

sum=sum+i i++
当i<=10 (直到i>10) 输出sum
#include "stdio.h" int main() {
int i,sum; i=1; sum=0; do { sum=sum+i; i++; }while(i<=10);
至少执 行一次
循环体语句
真 表达式 假
说明
printf("sum=%5d\n",sum); return 0;
7
举例
例5.2 设s=1×2×3×……×n，求s不大于400000时 最大的n。
#include <stdio.h>
int main( )
{ int n=1; long int s=1;
前n项的乘积
Ｐ81
while(s<=400000)
{
n=n+1;
s=s*n;
}
printf("不大于400000时的最大n为：%d\ns值为：%ld\n",n-1,s/n);
输入：1 输出：sum=55 输入：11 输出：sum=0
sum=55 sum=11
什么情况下两 者结果相同？
11
§5.3 for语句
P87
格式 for (表达式1；表达式2；表达式3) 语句
for (循环变量赋初值；循环条件；循环变量增值) 语句
执行 过程
求解表达式1
假 表达式2
真 循环体语句
求解表达式3
一、实现循环结构的控制语句 二、循环嵌套 三、循环结构程序举例
1
• while语句 • do-while语句 • for语句 • break、continue语句 • 几种循环的比较

第5章 数组和广义表
5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储
5.3.1 三角矩阵 5.3.2 带状矩阵 5.3.3 稀疏矩阵 5.4 广义表 5.5 总结与提高
5.1 数组的定义和运算
数组是一种数据类型。从逻辑结构上看，数组可以 看成是一般线性表的扩充。二维数组可以看成是线 性表的线性表。例如：
Am×n=
a12 a12 ┅
a1j
┅ a1n
a21 a22 ┅
a2j
┅ a2n
┇┇
ai1 ai2 ┅
aij
┇┇
┅ ain
am1 am2 ┅
amj
┅ amn
矩阵Am×n看成n个列向量的线性表,即j=(a1j,a2j, …,amj)
我们还可以将数组Am×n看成另外一个线性表: B=(1，,2,，… ，m)，其中i（1≤i ≤m）本身也是一个线性表， 称为行向量，即： I= （ai1，ai2， …，aij ，…，ain）。
Loc[j1,j2,j3]=Loc[c1,c2,c3]+ α1*(j1-c1)+ α2*(j2-c2)+ α3(j3-c3)
=Loc[c1,c2,c3]+ Σαi*(ji-ci) （1≤i≤3）
由公式可知Loc[j1,j2,j3]与j1,j2,j3呈线性关系。 对于ｎ维数组A(c1:d1,c2:d2，…,cn,dn)，我们只要把上式推 广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存储 地址的计算公式。
疏矩阵。
0 12 9 0 0 0 0
0 0 3 0 0 15
0 0 0 00 0 0
12 0 0 0 18 0
M6×7= -3 0 0 0 0 14 0

第16页/共23页
【例6.6】把数316分为两个数之和，其 中一个为13的倍数，一个为11的倍数。
main() { int i=0; for(;;i++)
if(!((316-i*13)%11))break; printf("13*%d+11*%d=316\n",i,(316-13*i)/11); }
i=1,p=1 输入 n 当 i<=n
p p*2 i i+1 输出 p
main() { int i=1,n; long int p=1; scanf("%d",&n); while(i<=n)
图6_3
{ p*=2; i++; }
5
第5页/共p23r页i n t f ( " % d \ n " , p ) ;
• 从多层循环体的内层循环跳到外层循环。
只有不得已(如能大大提高效率)时才能使用goto！
20
第20页/共23页
【例6.8】用if和goto语句构成循环， 求100 n 。
main()
n 1
{
int i=1,sum=0;
loop: if(i<=100)
{
sum=sum+i;
i++;
goto loop;
• 三种循环都可以用来处理同一问题，一般情况下它们可以互相代替。 • 用while和do …while循环时，循环变量初始化的操作在while 和do …
while语句前完成；for语句可以在表达式1中完成。
10
第10页/共23页
三种循环的比较(续)：
• while和do …while循环只在while后面指定循环条件，且在循环体中应包 含使循环趋于结束的语句；for循环可以在表达式3中包含使循环趋于结束的 操作，甚至可以将循环体中的操作全部放到表达式3中，功能更强。

▪ 非闰年的判别：
• !((year%4==0 && year%100!=0)||year%400==0)或者：
• (year%4!=0 )||( year%100==0 && year%400!=0)
C语言程序设计
第五章 选择结构程序设计
5.3 if语句（条件选择语句）
• if语句的三种形式 ▪ 形式一： • 格式：
语句2
=0
表达式3 非0
语句3
=0 语句4
C语言程序设计
第五章 选择结构程序设计
• 例：
if (salary>1000) else if (salary>800) else if (salary>600) else if (salary>400) else index=0;
index=0.4; index=0.3; index=0.2; index=0.1;
if (x>0) printf(“%f”,x) ;
else printf(“%f”,-x);
(3)在if 和else 后面可以只含一个内嵌的语句，也可以有 多个操作语句，此时用花括号将几个语句括起来成为一 个复合语句。如：
if (x>y)
{ t=x ; x=y ; y=t ; }
C语言程序设计
第五章 选择结构程序设计
a=4;b=5;
!a
//值为0
a&&b //值为1
a||b
//值为1
!a||b
//值为1
4&&0||2 //值为1
5>3&&2||8<4－!0 //(5>3)&&2||(8<(4-(!0))) 值为1

if(StrE按mpty行(S))*优ls = N先UL的L; 顺序存放元素，因此，数组元素地址的计算公式为
OLink *hl; Head（B）＝e Tail（B）＝（） 4．求广义表的深度
h广p义), s表ub的); 定q=义p;并没有限制元L素O的递C归(，)=即广L义O表也C可(以a是11其1自)+身d的2子d表3。(i1-1)+d3(i2-1)+(i3-1)
5.3 矩阵压缩存储 18
5.3.1 对称矩阵
对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中 1≤i,j≤n。对称矩阵关于主对角线对称，比如，我们只存储下三 角中的元素aij，其特点是中j≤i且1≤i≤n，对于上三角中的元素 aij，它和对应的aji相等，因此当访问的元素在上三角时，直接 去访问和它对应的下三角元素即可，这样，原来需要n*n个存 储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个 存储单元，当n较大时，这是可观的一部分存储资源。
第5章 数组和广义表
1
5.1 数组类型定义 5.2 数组顺序存储和实现 5.3 矩阵压缩存储 5.4 稀疏矩阵 5.5 广义表
5.1 数组类型的定义 2
1．一维数组 一维数组可以看成是一个线性表或一个向量（第2章已经介 绍），它在计算机内是存放在一块连续的存储单元中，适合于 随机查找。这在第2章的线性表的顺序存储结构中已经介绍。 2．二维数组 二维数组中的每一个元素最多可有两个直接前驱和两个直接 后继（边界除外），故是一种典型的非线性结构。例如，设A 是一个有m行n列的二维数组，则A可以表示为：
LOC(bij)=LOC(b11)+(d2-c2+1)(i-1)+(j-1) 公式中第2项是i-1个整行元素，每行d2-c2+1个元素。也可以解 释为第1维下标减1乘上后面第2维下标区间。

M
1 1 2 3 3 4
1 5 3 1 2 4
3 7 -1 -1 -2 2
N
1 1 2 3 4 5
1 3 3 2 4 1
3 -1 -2 -1 2 7
行列下 标调换
1 5 3 1 2 4
1 1 2 3 3 4
3 7 -1 -1 -2 2
按行下 标排序
法1：
按照矩阵M的列序进行转置，即按三元组A的 第二个字段值（列下标）由小到大的顺序进行转置。 为了找到M中每一列中所有的非零元素，需要对其 三元组表a.data从第一行起整个扫描一遍，由于 a.data是以M的行序为主序来存放每个非零元素 的，对于M中具有相同列下标的非零元来讲，先扫 描到的非零元的行下标一定小于后扫描到的非零元 的行下标，由此得到的恰是b.data应有的顺序。
• 压缩的含义
– 为多个值相同的元素只分配一个存贮空间； – 零元素不分配或少分配存贮空间。
• 特殊矩阵：元素值相同或零元素分布有 一定规律的矩阵。 • 稀疏矩阵：元素值相同或零元素分布没 有规律的矩阵。 • 特殊矩阵的压缩存贮实际是将二维数组 的数据元素压缩到一维数组上。
特殊矩阵的压缩存储
特殊矩阵: 非零元在矩阵中的分布有一定规则
常用的稀疏矩阵的存储方法
三元组表示法 顺序存储 行逻辑联接的顺序表 带辅助行向量的二元组表示法 伪地址表示法 带行指针向量的单链表示法 链接存储 散列存储 行列表示法（十字链表） 多链表示法（正交表）
顺序存储
1、三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个 结点对应稀疏矩阵的一个非零元素。其中包括三个 域，分别为该元素的行下标、列下标和值。结点间 的先后顺序按矩阵的行优先顺序排列（跳过零元 素），将线性表用顺序的方法存储在连续的存储区 里。

格式：while (条件1)
3. 用for 语句实现循环 4. 循环的嵌套
5. break语句和continue语句 6. 几种循环的比较 7. 程 序 举 例
第2页/共63页
一、循环概述
3
第3页/共63页
在很多实际问题中会遇到有规律性的重复运算，因 此在程序中就需要将某些语句重复执行。 • 一组被重复执行的语句称为循环体； • 每重复一次，都必须作出是继续还是停止循环的决 定，这个决定所依据的条件称为循环条件；
do {
......
for(;;) { ......
}while();
}
47
第47页/共63页
例7. 打印乘法“九九表”
1 2 3 4 56 7 89 11 22 4 33 6 9 4 4 8 12 16 5 5 10 15 20 25 6 6 12 18 24 30 36 7 7 14 21 28 35 42 49 8 8 16 24 32 40 48 56 64 9 9 18 27 36 45 54 63 72 81
循环的概念 用while语句和do-while语句实现循环
用for 语句实现循环 循环的嵌套
break语句和continue语句 几种循环的比较 程序举例
第44页/共63页
循环的嵌环中还可以嵌套循环，这就是多重循环。
循环1
循环2
28
第28页/共63页
29
第29页/共63页
（2）：从高位到低位求每一位。
30
第30页/共63页
（3）：从低位到高位求每一位。
31
第31页/共63页
循环结构程序设计
1. 循环的概念 2. 用while语句和do-while语句实现循环

（
从
概
念
E
F
G
E
C
到 实
现
）
树的根结点没有兄弟
清
华
大
F
D
学 出
版
社
G
二叉树根结点的右子树必为空
森林转换为二叉树
将一个森林转换为二叉树的方法是
（1）将森林中的每棵树转换为二叉树
数
（2）将每棵树的根结点视为兄弟，在所有根结点之间加上连线
据 结 构
（
从
（3）按照二叉树结点之间的关系进行层次调整
概 念
到
实
后序遍历序列：B A D E F C H J I G
第五章 v树和二叉树
5-6-2 树、森林与二叉树的转换
讲什么？
树转换为二叉树 森林转换为二叉树 二叉树转换为树（森林）
数 据 结 构 （ 从 概 念 到 实 现 ） 清 华 大 学 出 版 社
Page 01
树与二叉树的对应关系
A
B
A∧
B
∧E
∧C
现
）
A
C
G
清 华
大
学
出
版
DEF H
I
社
B
J
森林转换为二叉树
A
C
DEF B
A B
C D
E F
G
H
I
J G
H
I
J
A
B
C
数
据
结
构
（
D
G
从 概 念
到
实
现
）
EH
清
华
大
学
出
FI
版 社

假设以一维数组sa[0..n(n+1)/2-1]作为n阶对称矩阵A的
存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系。
0
1
2
3
4
5
6
7
8
……
n(n+1)/2-1
sa a00 a10 a11 a20 a21 a22 a30 a31 a32
an-1n-1
27
若i≥j，则aij在下三角形中。aij之前的i行（从第0 行到第i-1行）共有1+2+…+i=i*(i+1)/2个元素，在第i行 上，aij之前恰有j个元素（即ai0,ai1,…,ai,j-1 ），因此aij之 前共有k个元素：
=2000+(3*4+2)*4 =2056
21
例2：二维数组A中，每个元素的长度为3个字节，行下标i 从0到7，列下标j从0到9，从首地址SA开始存放在存储 器内，该数组按列存放时，元素A[4][7]的起始地址 为 。
A. SA+141 C. SA+222 B. SA+180 D. SA+225
解：LOC(a47)=LOC(a00)+(j *m+ i)*L = SA+(7*8+4)*3

以行序为主序（行优先顺序） 以列序为主序（列优先顺序）
13
一、以行序为主序：
1．存放规则 行优先顺序也称为低下标优先或右边下标优先于左 边下标。具体实现时，按行号从小到大的顺序，先将第 一行中元素全部存放好，再存放第二行元素，第三行元 素，依次类推……
BASIC语言、PASCAL语言、C/C++语言都是按行优先

第五章 v树和二叉树
5-5-1 二叉树的顺序存储结构
二叉树的顺序存储结构
顺序存储结构的要求是什么？
用一组连续的存储单元依次存储数据元素，由存储位置表示元素之间的逻辑关系
数
据
结
构
二叉树的顺序存储结构是用一维数组存储二叉树的结点，结点的
（ 从 概
念
存储位置（下标）应能体现结点之间的逻辑关系——父子关系
对于普通的二叉树，如何顺序存储呢？
A1
将二叉树按完全二叉树编号： （1）根结点的编号为 1 （2）若某结点 i 有左孩子，则其左孩子 的编号为 2i （3）若某结点 i 有右孩子，则其右孩子 的编号为 2i+1
B2
C3
数
据
结
构
D5
F6
（ 从 概
念
10 E
到
实
G 13
现 ）
清
华
大
以编号
学 出
版
为下标
社
BiTree( ){root = Creat(root);}
~BiTree( ){Release(root);}
数 据
结
void PreOrder( ){PreOrder(root);}
构 （
void InOrder( ){InOrder(root);}
从 概
念
void PostOrder( ){PostOrder(root);}
BiNode
数
{
据 结
构
DataType data;
（ 从
概
BiNode< DataType > *lchild, *rchild;
念 到
实