第2讲_线性数据结构(一)顺序表_线性链表_.ppt

第2单元线性数据结构（一）学习要求涉及的章节数据结构问题的由来问题模型一、基本概念P22数据结构分类1.数据的逻辑结构举例2.数据的存储结构逻辑结构和物理结构的关系数据存储结构分类顺序存储结构链式存储结构散列存储结构3.数据运算4、算法与算法分析算法的特性算法的设计要求
(1)算法中对数据的运算和操作
①算术运算：加减乘除
②逻辑运算：与或非
③关系运算：大于、小于、等于、不等于
④数据传输：赋值、输入、输出等

(2)算法的控制结构1.符号与表达式
loop：i＝i＋1
“设x是A中的最大项”（其中A是一个数组）
“将x插入到L之中”（其中L是某个表）

算法描述语言中，关系运算符用＝、≠、＜、＞、≤、≥
逻辑运算符用and(与)、or(或)、not(非)2.赋值语句
a＝ea←→ba＝b＝e3.控制转移语句无条件转移语句GOTO标号
条件转移语句IFCTHENS或IFCTHENS1ELSES24.循环语句WHILE语句WHILECDOS
功能等价于如下的IF语句：loop：IFCTHEN{SGOTOloop}FORi＝initTOlimitBYstepDOSFORi＝initTOlimitDOS
当step＞0时，功能等价于如下的IF语句：i＝initloop：IFi≤limitTHEN{Si＝i＋stepGOTOloop}当step＜0时，功能等价于如下的IF语句：i＝initloop：IFi≥limitTHEN{Si＝i＋stepGOTOloop}5.其他语句
EXIT
RETURN
READ（或INPUT）
WRITE（或PRINT，或OUTPUT）（1）算法中的注释用【】括起来；
（2）几个短的语句可以写在同一行上，但彼此之间要用分号隔开；
（3）复合语句总是用一对花括号{}括起来作为语句组。
（4）有时为了叙述方便，对算法中的每一行可加上行号。1.列举法
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。例
设每只母鸡值3元，每只公鸡值2元，两只小鸡值1
元。现要用100元钱买100只鸡，设计买鸡方案。

假设买母鸡I只，公鸡J只，小鸡K只。FORI＝0TO100DO
FORJ＝0TO100DO
FORK＝0TO100DO
{M＝I＋J＋K
N＝3I＋2J＋0.5K
IF((M＝100)and(N＝100))THEN
OUTPUTI，J，K
}
RETURN
总循环次数为1013FORI＝0TO33DO
FORJ＝0TO50－1.5IDO
{K＝100－I－J
IF(3I＋2J＋0.5K＝100)THEN
OUTPUTI，J，K
}
RETURN
总循环次数为首先，考虑到母鸡为3元一只，因此，最多只能买33只母鸡，即算法1中的外循环只需要从0到33就可以了，没有必要从0到100。其次，考虑到公鸡为2元一只，因此，最多只能买50只公鸡。又考虑到对公鸡的列举是在算法的第二层循环中，且买一只母鸡的价钱相当于买1.5只公鸡。因此在第一层循环中已确定买I只母鸡的情况下，公鸡最多只能买50-1.5I只，即第二层中对J的循环只要从0到50-1.5I就可以了。最后，考虑到总共买100只鸡，因此，在第一层循环中已确定买I只母鸡，且第二层已确定买J只鸡的情况下，买小鸡的数量只能是K=100-I-J，即第三层的循环已没有必要了。并且，在这种情况下，条件I+J+K=100自然已经满足。#include"stdio.h"
main()
{inti，j，k；
for(i＝0；i＜＝33；i＋＋)
for(j＝0；j＜＝50－1.5*i；j＋＋)
{k＝100－i－j；
if(3*i＋2*j＋0.5*k＝＝100.0)
printf("%5d%5d%5d\n"，i，j，k)；
}
}运行结果如下：
23068
52570
82072
111574
141076
17578
20080
2.归纳法
通过列举少量的特殊情况，经过分析，最后找出一般的关系。

3.递推
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。例4.递归
将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。

注意：这种逐层分解实际上并没有对问题进行求解，而只是当解决了最简单的问题后，再沿着原来逆分解的过程逐步进行综合，这就是递归的基本思想。编写一个过程，对于输入的参数n，依次打印输出自然数1到n。
PROCEDUREWRT(n)
FORk＝1TOnDOOUTPUTk
RETURN

#include"stdio.h"
wrt(intn)
{int