数据结构课堂笔记(di第一~三章)(完整版).doc

一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。 二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。 四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常有下列4类基本结构：（1）集合------------数据元素仅有同属一个关系的关系（2）线性结构----------结构中数据元素之间存在一个对一个的关系（3）树形结构------------结构中的数据元素之间存在一个对多个的关系（4）图状结构或网状结构-----------结构中的数据元素之间存在多个对多个的关系 五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。（2）逻辑结构 六、位bit：在计算机中表示信息的最小单位是二进制的一位 七、元素element/节点node：位串 八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串 九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。 类C语言语句： （1）预定义常量和类型： #define TRUE 1 FALSE 0 #define OK 1 ERROR 0 #define INFEASIBLE -1 OVERFLOW -2 (2)数据元素类型ElemType (3)赋值语句： 简单赋值 变量名=表达式； 串联赋值 变量名1=变量名2=…=变量名k=表达式； 成组赋值 （变量名1，…，变量名k）=（表达式1，…，表达式k）； 结构名=结构名； 结构名=（值1，…，值k）； 变量名[]=表达式； 变量名[起始下标..终止下标]= 变量名[起始下标..终止下标]； 交换赋值：变量名-变量名； 条件赋值：变量名=条件表达式？表达式T：表达式F； （4）选择语句有 条件语句1 if（表达式）语句； 条件语句2 if（表达式）语句； else语句； 开关语句1 switch(表达式){ case值1：语句序列1；break; … case值n：语句序列n；break; default:语句序列n+1; } 开关语句2 switch(表达式){ case条件1：语句序列1；break; … case条件n：语句序列n；break; default:语句序列n+1; } (6)循环语句有： for语句 for（赋初值表达式序列；条件；修改表达式序列）语句； while语句 while（条件）语句； do-while语句 do{ 语句序列； }while（条件）； （7）结束语句有 函数结束语句 return表达式； return； case结束语句 break； 异常结束语句 exit（异常代码）； （8）输入和输出语句有： 输入语句 scanf（[格式串]，变量1，…，变量n）； 输出语句 printf（[格式串]，表达式1，…，表达式n）； 通常省略格式串。 （9）注释 单行注释//文字序列 （10）基本函数有： 求最大值 max（表达式1，…，表达式n） 求最小值 min（表达式1，…，表达式n） 求绝对值 abs（表达式） 求不足整数值 floor（表达式） 求进位整数值 ceil（表达式） 判定文件结束 eof（文件变量）或eof 判定行结束 eoln（文件变量）或eoln （11）逻辑运算约定 与运算：对于AB，当A的值为0时，不再对B求值。 或运算||：对于A||B，当A的值为非0时，不再对B求值。 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。 （1）有穷性（2）确定性（3）可行性（4）输入（5）输出 算法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求 线性表：是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。 在复杂的线性表中，一个数据元素可以由若干个数据项item组成。在这种情况下，常把数据元素称为