第1章 绪论
第1章 绪论
程序设计就是使用计算机解决现实世界中的实际问题。对于给定的一个实际问题，在进行程序设计时，首先要把实际问题中用到的信息抽象为能够用计算机表示的数据；第二要把抽象出来的这些数据建立一个数据模型，这个数据模型也称为逻辑结构，即建立数据的逻辑结构；第三要把逻辑结构中的数据及数据之间的关系存放到计算机中，即建立数据的存储结构；最后在所建立的存储结构上实现对数据元素的各种操作，即算法的实现。
本章就是要使大家了解计算机中的数据表示，理解数据元素、逻辑结构、存储结构和算法的有关概念；掌握基本逻辑结构和常用的存储方法，能够选择合适的数据的逻辑结构和存储结构；掌握算法及算法的五个重要特性，能够对算法进行时间复杂度分析，从而选择一个好的算法，为后面的学习打下良好的基础。
1.1基本概念和术语
1.数据(data)：
是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。
2.数据元素(data element): 是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项（data item）组成，数据项是数据不可分割的最小单位。
3.数据结构(data structure):
是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组，记为:
data_structure=(D,S).其中D为数据元素的集合，S是D上关系的集合。 数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性，通常由下列四类基本结构：
（1）集合:数据元素间的关系是同属一个集合。（图1） （2）线性结构:数据元素间存在一对一的关系。（图2） （3）树形结构：结构中的元素间的关系是一对多的关系。（图3） （4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）
图1 图2
第1章 绪论
图3 图4
1.2 数据的逻辑结构和物理结构
1.逻辑结构：数据元素之间存在的关系（逻辑关系）叫数据的逻辑结构。即上面给出的四种结构。
2.物理结构：数据结构在计算机中的表示（映象）叫数据的物理结构，又称存储结构。
一种逻辑结构可映象成不同的存储结构：顺序存储结构和非顺序存储结构（链式存储结构和散列结构）。
1.3算法及算法分析
1. 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。
2. 算法的重要特性
①输入：一个算法应该有零个或多个输入。
②有穷性：一个算法必须在执行有穷步骤后正常结束，而不能形成无穷循环。 ③确定性：算法中的每一条指令必须有确切的含义，不能产生多义性。 ④可行性：算法中的每一条指令必须是切实可执行的，即原则上可以通过已经实现的基本运算执行有限次来实现。
⑤输出：一个算法应该有一个或多个输出，这些输出是同输入有某个特定关系的量。
3. 算法的时间复杂度
①定义：设问题的规模为n，把一个算法的时间耗费T(n)称为该算法的时间复杂度，它是问题规模为n的函数。
②算法的渐进时间复杂度
设T(n)为一个算法的时间复杂度，如果当n趋向无穷大时T(n)与函数f(n)的比值的极限是一个非零常数M，即记作T(n)=O(f(n))，则称O(f(n))为算法的渐进时间复杂度，简称时间复杂度，也称T(n)与f(n)的数量级相同，通常，f(n)应该是算法中频度最大的语句的频度。
③常用的算法的时间复杂度的顺序
第1章 绪论
O(1) ④算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 例如：在数组A[0...n-1]中查找给定值K的算法如下： (1)i=n-1; (2)while(i>=0&&(A[i]!=k)) (3) i--; (4)return i; 此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关： 若A中没有与K相等的元素，则语句(3)的频度f(n)=n； 若A的最后一个元素等于K，则语句(3)的频度f(n)是常数0。 ⑤最坏时间复杂度和平均时间复杂度 最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况下更长。 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 例1 求下列交换两个变量i和j的值的算法的时间复杂度。 (1) i=10; (2) j=20; (3) t=i; (4) i=j; (5) j=t; 解：各行语句的执行次数均为1，所以该算法的时间耗费T(n)= 1+1+1+1+1=5，该算法的时间耗费T(n)与问题的规模n无关，因此，该算法的时间复杂度T(n)=O(1)。 例2 求两个n阶方阵的乘积C=A×B，其算法如下，计算该时间复杂度。 程序段： (1) for(i=0; i (4) for(k=0; k (5) c[i][j]+=a[i][k]*b[k][j]; 第1章 绪论 } 解：解法1 计算程序段中的每一行的执行次数。 第(1)行for(i=0; i 第(2)行for(j=0; j 第(3)行c[i][j]=0;在表达式i 第(5)行c[i][j]+=a[i][k]*b[k][j]; 在表达式i 因此，各行执行次数分别为：n+1，n（n+1），n2，n2（n+1），n3。 如果用T(n)表示该算法的时间耗费，则 T(n)= n+1+n（n+1）+n2+n2（n+1）+n3=2n3+3n2+2n+1 由此可知，该算法的时间耗费T(n)是矩阵阶数n的函数，T(n)=O(n3)。 解法2 只计算执行频度最高的行。 显然，在该程序段中，执行频度最高的行为c[i][j]+=a[i][k]*b[k][j]; 在表达式i 【课堂实践】分析并计算下面程序段执行的时间复杂度。 i=1; k=0; while(i<=n-1) { k+=10*i; i++; } 第2章 线性表 第2章 线性表 线性表是最常用且最简单的一种数据结构，一个线性表是n个数据元素的有序系列，每个数据元素可以是一个数或一个符号，也可以使一页书，甚至其他更复杂的信息。如26个字母的字母表：（A,B,C,D…..,Z）在复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为一个记录，含有大量记录的线性表又称文件。如图 综合上述例子，可以将线性表描述为： 线性表是由n个数据元素的有限序列(a1,a2,…,an)组成的，其中每一个数据元素ai的具体含义可以按不同的情况和要求定义具体的内容，它可以是一个数、一个符号、一串文字，甚至是其他更复杂的信息。线性表中数据元素的个数n称为线性表的长度。 2.1 线性表的逻辑结构及基本运算 1.线性表简单的定义 n个数据元素的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。线性表中的数据元素不仅可以进行访问，还可进行插入和删除。 若n=0，则表示一个空表，即没有任何数据元素的线性表；若n>0，则除a1和an外，有且仅有一个直接前驱和一个直接后继，即ai(其中1< i （1）线性表初始化 格式：InitList(L) 初始条件：线性表L不存在。 操作结果：构造一个空的线性表L。 （2）求线性表的长度 格式：LengthList(L)