文档详情

公共基础知识(程序设计基本概念).doc

发布:2019-01-16约1.03万字共15页下载文档
文本预览下载声明
- PAGE \* MERGEFORMAT 1 - 程序设计基本概念 计算机工作原理: 程序的定义: 指令的结合(解释指令); 通过硬件控制系统自动完成某一功能; 通过一系列代码实现; 程序的执行与编写程序: 计算机本身仅能识别二进制代码; 编程最直接、最低级的就是机器语言; 未解决机器语言难理解、难记忆等问题,出现符号语言(汇编语言); 为使编程接近自然语言,出现高级语言,如C、PASCAL、FORTRAN等; 为配合高级语言编程,出现开发工具,提高效率、减轻劳动量,如VB、VC、PB、DELPHI、VFP(不是编程语言!)等; 不管什么形式编写代码,最终都应将代码翻译成机器语言,不同语言有不同的编译器; 程序控制是一种逻辑控制; 程序的特殊性决定了程序的复杂性,且与实现功能的复杂性成正比; 程序的最终目标是程序最终完成的功能稳定、可靠、实用、易维护和安全; 程序设计语言或工具: 程序设计的语言可分为高级语言和低级语言,区别在于接近于自然语言的程度; 高级语言一般与计算机硬件无关,比较接近于自然语言的语法习惯和数学表达形式; 高级语言编写的源程序不能被机器直接执行,需通过编译才能被机器执行; 数据结构与算法 算法: 算法的基本概念: 是对特定问题求解步骤的一种描述; 是指令的有限序列,其中每条指令表示一个或多个操作; 是一组严谨地定义运算顺序的规则,每一个规则都必须是明确有效的,顺序将在有限次数下终止; 算法的五个特征: 有穷性:算法必须在有限的时间内结束; 确定性:算法中的每个步骤都必须有确定的含义,对于确定的要有一个确定的输出; 可行性:算法中的操作可以通过现有的基本运算经过有限次的执行而实现; 输入:算法中可以没有输入,也可以有多个输入; 输出:任何一个算法必须有一个或多个输出,输出表示数据加工的结果; 算法的基本要素: 对数据对象的运算和操作:算术运算、逻辑运算、关系运算、数据传输; 算法的控制结构: ①算法中各操作的执行顺序; ②描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等; ③一个算法一般可以用顺序、选择、循环三种基本结构组合而成; 算法设计的基本方法:列举法、归纳法、递推、递归、减半递归技术、回溯法; 算法的复杂度: 时间的复杂度: ①依据算法编制的程序在计算机上运行时所消耗的时间来度量; ②通常分为事后统计法、事前分析估计法; ③算法由控制结构(顺序、选择、循环)和原操作构成,算法时间取决于两者综合效果; ④算法中基本操作重复执行次数n和算法执行时间同步增长,称为算法的时间复杂度; 空间复杂度: ①是指执行算法所需的内存空间; ②存储空间包括算法程序所占用的空间、算法初始数据所占用存储空间和某种数据结构所需附加存储空间; ③上机执行程序除了需要存储空间寄存本身所用指令、常数、变量和输入数据外,也需要对数据进行操作的工作单元和存储为实现计算所需信息的辅助空间; 数据结构: 数据结构的概念: 研究数据组织、存储和运算的一般方法; 其中的数据包括整数、实数、字符串、图形和声音; 存储是指数据元素在计算机中的表示,目的不同则最佳存储方法不同; 运算是指对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序); 数据结构包括数据的逻辑结构、数据的物理结构(存储结构)和对数据的操作运算; 数据的逻辑结构与所使用的计算机无关; 数据的存储结构是指数据的逻辑结构在计算机中的表示; 数据元素: 数据的基本单位,即数据集合中的个体; 有时一个数据元素可由若干个数据项(数据的最小单位)组成; 亦称节点或记录; 数据结构可描述为: Group=(D,R)(D:有限个数据元素的集合;R:有限个节点关系的集合); 当今计算机应用的特点: 1、所处理的数据数量大且具有一定的相关性; 2、对其的操作不光是单纯的数值计算,还包括对其进行组织、管理和检索; 3、对数据的讨论不单是数据本身,还包括数据之间的关系; 4、应用举例:学籍档案管理(线性结构)、家庭血缘关系(树形结构)、定制教学计划(图形结构); 数据的逻辑结构: 线性结构(有且只有一个根节点,每个节点最多有一个前件,也最多有一个后件): 线性表、栈、队; 非线性结构(线性以外的数据结构): 树形结构(节点间具有分层次的连接关系)、图形结构(节点间的连结任意); 线性表: 线性表的定义: 具有线性结构的n个元素的有限序列,它们之间的关系可以排成一个线性序列: a1,a2,a3,…,ai,…an(n称作表的长度,n=0时称作空表); 数据在线性表中的位置只取决于它们自己的序号,数据之间的相对位置是线性的; 节点间以线性关系连结; 线性表的特点: 线性表中所有元素性质相同;
显示全部
相似文档