二级C语言公基础知识总结.doc

二级C语言公共基础知识总结 数据结构与算法 1.1算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限次数下完成。 其特征包括：（1）可行性；（2）确定性；（3）有穷性；（4）拥有足够的情报。 算法的基本要素：（1）对数据对象的运算和操作；（2）算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：（1）算数运算；（2）逻辑运算；（3）关系运算；（4）数据传输。 算法的控制结构：（1）顺序结构；（2）选择结构；（3）循环结构。 算法设计的基本方法：（1）列举法；（2）归纳法;（3）递推；（4）递归；（5）减斗递推技术；（6）回溯法。 算法的复杂度：（1）算法的时间复杂度；（2）算法的空间复杂度。 算法的时间复杂度：是指在执行算法所需要的计算工作量。 算法的空间复杂度：是指执行这个算法所需的内存空间。 1.2数据结构的基本概念 数据结构研究的三个方面： 数据集合中各数据元素之间所有的逻辑关系，即数据的逻辑结构。 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据结构的存储结构。 对各种数据结构进行的运算。 数据的逻辑结构包括： 表示数据元素的信息。 表示各数据元素之间的前后件关系。 数据的存储结构包括：顺序、链接索引等。 线性结构条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。