第1章 绪论 第2章 线性表 第3章 栈 第4章 队列 第5章 树和二叉树 第6章 图 第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 图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)应该是算法中频度最大的语句的频度。 ③常用的算法的时间复杂度的顺序 O(1)=0&&(A[i]!=k)) (3)?i--; (4)return i; 此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
