数据结构耿国华第1章.ppt

3. 算法设计的要求 １） 算法的正确性 (1) 所设计的程序没有语法错误；  (2) 所设计的程序对于几组输入数据能够得出满足要求的结果； (3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。  (4) 程序对于一切合法的输入数据都能产生满足要求的结果。 例如： 要求n个数的最大值问题， 给出示意算法如下：  max:=0;  for（i=1； i=n; i++）  { scanf(″%f″, x);  if (xmax) max=x;  } 2） 可读性 3） 健壮性 4） 高效率和低存储量 1.4 算法描述的工具 1. 算法、 语言和程序的关系 (1) 算法： 描述了数据对象的元素之间的关系（包括数据逻辑关系、 存储关系描述）。 (2) 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。 自然语言简单但易于产生二义，框图直观但不擅长表达数据的组织结构， 而高级程序语言则较为准确但又比较严谨。 (3) 程序是算法在计算机中的实现（与所用计算机及所用语言有关）。 2. 设计实现算法过程的步骤 · 找出与求解有关的数据元素之间的关系（建立结构关系）。 · 确定在某一数据对象上所施加的运算。 · 考虑数据元素的存储表示。 · 选择描述算法的语言。 · 设计实现求解的算法， 并用程序语言加以描述。 3. 类描述算法的语言选择 (1) 预定义常量和类型。 本书中用到以下常量符号，如True、 False、MAXSIZE等，约定用如下宏定义预先定义：  ＃ define TRUE 1 ＃ define FALSE 0 ＃ define MAXSIZE 100 ＃ define OK 1 ＃ define ERROR 0 (2) 本书中所有的算法都以如下的函数形式加以表示， 其中的结构类型使用前面已有的定义。  ［数据类型］ 函数名（［形式参数及说明］） { 内部数据说明；  执行语句组；  } /*函数名*/ 函数的定义主要由函数名和函数体组成，函数体用花括号“{”和“}”括起来。 函数中用方括号括起来的部分如“［形式参数］”为可选项， 函数名之后的圆括号不可省略。 (3) 赋值语句。 ■简单赋值; （1）〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；  （2）〈变量〉++， 它表示变量加1后赋值给变量；  （3）〈变量〉--， 它表示变量减1后赋值给变量。 ■串联赋值#; 〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉； ■成组赋值#; （〈变量1〉，〈变量2〉，〈变量3〉， …, 〈变量k〉)=（〈表达式1〉，〈表达式2〉， 〈表达式3〉， …, 〈表达式k〉）； 〈数组名1〉［下标1］［下标2］=〈数组名2〉［下标1］［下标2］；  ■ 条件赋值; 〈变量名〉=〈条件表达式〉？〈表达式1〉: 〈表达式2〉； (4) 条件选择语句。 ■if （〈表达式〉） 语句；  ■if （〈表达式〉） 语句1；  else 语句2； switch (表达式） {case 判断值1:  语句组 1；  break;  case 判断值2:  语句组 2；  break;  ... case 判断值n:  语句组n;  break;  ［default:  语句组； 