文档介绍：1 全国计算机等级考试(NCRE) 二级 C第 10 讲全国计算机二级公共基础知识 C C语言程序设计知识结构语言程序设计知识结构 2C语言程序设计知识结构 3主要内容?1、数据结构与算法?2、程序设计基础?3、软件工程基础?4、数据库设计基础 4第4页算法的定义??对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是程序设计的核心算法是程序设计的核心算法的基本概念算法的基本概念 P1 P1 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程(计算的方法)。在这个过程中,无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法),都是在实施某种算法。例: n个数从大到小进行排序。有多种排序方法,常用的有冒泡排序、选择排序等。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。常考点 5第5页算法的基本特征 P1 一个算法应该具有以下五个重要的特征: ?有穷性?确定性?输入?输出?可行性一个算法必须保证执行有限步之后结束; 算法的每一步骤必须有确切的定义; 一个算法有 0个或多个输入,以刻画运算对象的初始情况,所谓 0个输入是指算法本身定出了初始条件; 一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的; 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成拥有足够的情报常考点 6第6页?算法与计算机程序算法____ 是一组逻辑步骤程序——用计算机语言描述的算法算法的表示算法的表示 INPUT r S= * r*r PTINT S 开始输入 R S= *R*R输出 S结束问题: 输入园的半径, 计算园的面积一个算法的表示需要使用一些语言形式。传统的算法------- 图形法,如“流程图”和 N-S 图目前常用的方法------- 使用伪码描述算法。算法好坏的描述: 时间复杂度空间复杂度一般考点 7算法的复杂度??是是算法效率算法效率的度量:时间复杂度和空间复杂度。的度量:时间复杂度和空间复杂度。??表示: 表示: O(1)\ O(n)\ O(n^2) O(1)\ O(n)\ O(n^2) ??算法算法时间时间复杂度:指复杂度:指执行算法所需要的计算工作量执行算法所需要的计算工作量。通常, 。通常, 一个算法所用的时间包括编译时间和运行时间。一个算法所用的时间包括编译时间和运行时间。??算法算法空间空间复杂度:指执行这个算法所复杂度:指执行这个算法所需要的内存空间需要的内存空间。包括。包括算法程序所占的空间,输入的初始数据所占的空间,算法执算法程序所占的空间,输入的初始数据所占的空间,算法执行过程中所需的额外空间。行过程中所需的额外空间。??空间复杂度和时间复杂度并不相关空间复杂度和时间复杂度并不相关??常用算法常用算法的时间复杂度: 的时间复杂度: ??顺查找线性表的时间复杂度顺查找线性表的时间复杂度 O(n O(n ) ) ??二分法查找有序线性表时间复杂度二分法查找有序线性表时间复杂度 O(log O(log 2 2 (n)) (n)) ??冒泡排序算法的时间复杂度冒泡排序算法的时间复杂度 O(n^2) O(n^2) ??堆排序算法的时间复杂度堆排序算法的时间复杂度 O(nlog O(nlog 2 2 (n)) (n)) 8数据结构与算法 P3 1 1、数据:计算机需要处理( 、数据:计算机需要处理( 存贮存贮、计算、、计算、检索检索)的对象,如文档、声音、视频。)的对象,如文档、声音、视频。 2 2、数据结构:是相互有关联的数据的集合,包括数据的、数据结构:是相互有关联的数据的集合,包括数据的逻辑结构逻辑结构、、存贮结构存贮结构(即物理结构) (即物理结构) 。。尽量尽量节约空间、节省时间节约空间、节省时间。。 3 3、数据结构的内容: 、数据结构的内容: ( (1 1)数据集合中各数据元素之间所固有的逻辑关系,即数据的)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构逻辑结构。含: 。含: 表示数据元素的信息;表示各数据元素之间的前后件关系表示数据元素的信息;表示各数据元素之间的前后件关系( (2 2)在对数据进行处理时,各数据元素在计算机中的存储关系,即)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储数据的存储结构结构。。顺序存储顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。这种存储表示称为顺序存储结构。的逻辑关系由存储单元的邻接关系来体现。这种存储