第4章 数据结构与算法本章介绍数据结构与算法，内容包括算法和数据结构的基本概念、栈及线性链表、树与二叉树、排序技术、查找技术。
●了解数据结构与算法的基本概念。
●了解栈与线性链表的操作。
●了解树与二叉树。
●了解数据结构中的排序技术和查找技术。
4.1 算法的概念4.1.1 算法的基本概念程序是算法用某种程序设计语言的具体实现。
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度和时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。
一个状态到另一个状态的转移不一定是确定的。
随机化算法在内的一些算法包含了一些随机输入。
算法具有的一些重要特性：（1）有限性。
算法在执行有限步之后必须终止。
（2）确定性。
算法的每一个步骤都是有精确的定义的。
执行的每一步都是清晰的、无二义的。
大学计算机基础84（3）输入。
一个算法具有任意个输入，它是由外部提供的，作为算法执行前的初始状态。
（4）输出。
算法一定有输出结果。
（5）可行性。
算法中的运算都必须是可以实现的。
4.1.2 算法的复杂度1．时间复杂度算法的时间复杂度采用算法执行过程中其基本操作的执行次数，即计算量来度量。
算法中基本操作的执行次数一般是与问题的规模有关的，对于节点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数。
当比较不同算法的时间性能时，主要标准是看不同算法时间复杂度所处的数量级如何。
例如：以上算法中，循环体中的代码执行了n次，因此算法的时间复杂度为O(n)。
