数据结构-华东理工大学计算机科学与工程系.pptVIP

1 1 《数据结构》的研究内容 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面： P167 1.名词解释：算法、流程图、数据结构 2.填空题：（1）～（10） 3.选择题：（1）～（10） 5.算法设计题：（5）、（6）、（7） 1.编写一个程序，输入m、n，打印最小公倍数和最大公约 数。用五种方法写出其算法的描述。 2.试用递归的方法写一下计算菲波那契数列的通项f（n）， 已知f1=1，f2=1，以后每项都是前两项的和。 3.用折半查找1，2，3，4，5，6，7，8，9，10，11，12， 13，14，15怎么找到10，请画图表示查找过程。 4.用三种方法对下列数字排序：12，3，4，5，8，7，15， 9，10，1，11，14，6，13，2，请画出排序过程。 5.算法的灵魂是什么？ 6.用C语言写出选择排序、冒泡排序、插入排序、顺序查找 和折半查找的程序（选做）。 1.write a program that prompt the user to specify the size of a t-shirt: S for small,M for medium,L for large and X for extra large.The prices are $10,$20,$30 and $40,respectively.Display the price of a chosen size. Eg. PromptString.java 2.write a program that displays even integer values from 1 to 20. Eg. DisplayEven.java 3.输入一个华氏温度，要求输出摄氏温度。公式为c=5(F-32)/9，输出要求有文字说明，取2位小数。 Eg. DisplayTemperature.java 4.编写一个程序，输入a、b、c、d，输出其中最大者。 Eg. DisplayMax.java 5.有一函数 y= x (x1) y= 2x-1 (1≤x10) y= 3x-11 (x≥10) 写一程序输入输出值。 9.3 算法的表示 1.为什么要设计算法表示 2.带序号的自然语言描述 易懂却不直观，不严格 【例题】计算1到100的和 1. 0=s单元 2. 1 = n单元 3. s+n =s 4. n+1 =n 5.判断n?100？是，转3；否则转6 6.输出s的值 3.流程图－UML 灵活、自由、形象、直观，可表示任何算法 流程线 输入/输出 处理 判断 起止 连接点 【例题】计算1到100的和 开始 结束 0=s 1=n s+n =s 输出s n+1=n n?100? T F A B P T F A A P A P 循环 4.N-S图（盒图） 特点：完全去掉了带箭头的流程线，算法所有处 理步骤都写在一个大矩形框（表示简单、符合结 构化思想） 处理 判断 【例题】计算1到100的和 0=s 1=n n?100? s+n =s n+1=n 输出s的值 5.伪代码 用介于自然语言与计算机语言之间的文字及符号来 描述算法 方便、易懂、便于向计算机语言过渡 0=s 1=n if n?100 s+n =s n+1=n print s 【例题】计算1到100的和 b 选择结构 d 循环结构 c 多选择结构 a 顺序结构 P1 P2 C P1 P2 Pn L1 L2 X=… Ln P A 或 while c until c P1 P2 输入输出 重复 子算法 定义 选择 语句标号 处理 6.PAD图 【例题】输入年份，判断该年是否为闰年 算法开始 算法结束 x {输入年份} x是400的倍数 或者 x是4的倍数但不是100的倍数 “x是闰年” “x不是闰年” 1.求和 9.4 基本的算法 【例题】1到100的奇数之和 #include stdio.h int main() { int i,sum=0; for (i=1;i=100;i++) { sum=sum+i; i=i+2; } printf(sum= %d \n,sum); } 这个程序对吗？ oddNumber.c #include stdio.h int main() { int a=1,b=99,sum=0; for (;a=b;) {