第1页，共30页，星期日，2025年，2月5日第1章概述第2页，共30页，星期日，2025年，2月5日§1.1研究内容和地位一、研究内容：研究软件设计中常用的基本技术。二、地位：第3页，共30页，星期日，2025年，2月5日§1.2基本概念和术语数据(data)——能够输入到计算机中并能被计算机处理的符号的集合。（广义）数据元素(dataelement)——构成数据的基本单位（具有完整的独立意义）。在某些场合还被称为元素、记录、结点、顶点等。第4页，共30页，星期日，2025年，2月5日§1.2基本概念和术语数据结构(datastructure)——构成数据元素之间的结构关系。线性结构树形结构图结构（网状结构）集合第5页，共30页，星期日，2025年，2月5日§1.2基本概念和术语通常称这几类结构为逻辑结构，因为只考虑了元素之间的逻辑关系。存储结构（物理结构）——同样的逻辑结构≠同样的存储结构运算（判断存储结构的好坏）第6页，共30页，星期日，2025年，2月5日学习数据结构的方法①逻辑结构②运算定义③存储结构④实现运算⑤分析第7页，共30页，星期日，2025年，2月5日§1.3算法和算法分析第8页，共30页，星期日，2025年，2月5日一、算法的概念算法（目前为止没有统一的说法）：是某类问题的求解方法（粗略）：指令的有限序列满足输入0～n个输出1～n个与输入有特定联系确定性（无二义性）相同的输入只能有相同的输出有穷性可行性算法在有限的时间内结束第9页，共30页，星期日，2025年，2月5日二、衡量算法的度量（一）主要度量：(1)正确性(correctness)(2)可读性(readability)(3)健壮性(robustness)(4)效率（时间和空间）第10页，共30页，星期日，2025年，2月5日二、衡量算法的度量－2（二）时间性能：以时间复杂度来表示运行算法所需的时间计算比较麻烦计算基本语句的执行次数来代替具体的执行时间次数数量级第11页，共30页，星期日，2025年，2月5日二、衡量算法的度量－3for（i=1；i=n；i++）x=x+1；——O(n)如果limf(n)/g(n)=常数（≠0，∞）则f(n)，g(n)为同一数量级O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)例第12页，共30页，星期日，2025年，2月5日三、算法指定的语言1、计算机语言优：易上机实现；缺：死板；2、自然语言优：灵活；缺：不易上机实现；3、伪语言(类语言)类pascal类c类c++第13页，共30页，星期日，2025年，2月5日四、类c语言（一）算法的形式——函数返回类型函数名（参数表）{程序序列；return（返回值）；//当返回类型为void可省}返回类型：int，char，double，void等等第14页，共30页，星期日，2025年，2月5日（二）语句1、赋值和交换：v=表达式；v1=v2；2、if语句：条件S1S2成立ifs1；elses2；条件S1成立或ifs1第15页，共30页，星期日，2025年，2月5日（二）语句－23、switch语句：switch（表达式）{case常量表达式1：语句1[break；]case常量表达式2：语句2[break；]……case常量表达式n：语句n[break；][default：语句n+1]}switch括弧内的表达式可以是任何类型；每一个case后的表达式必须互不相同；case的执行次序无关；第16页，共30页，星期日，2025