第1章 公共基础知识ok.ppt

二级 ACCESS 讲义二级公共基础知识二级 ACCESS 讲义 2二级公共基础知识第一章算法与数据结构第二章程序设计基础第三章软件工程基础第四章数据库设计基础二级 ACCESS 讲义 3 第一章算法与数据结构本章要求?算法的基本概念、算法复杂度的概念和意义(时间复杂度与空间复杂度)。?数据结构的定义、数据的逻辑结构与存储结构、数据结构的图形表示、线性结构与非线性结构的概念。?线性表的定义、线性表的顺序存储结构及其插入与删除运算。?栈和队列的定义、栈和队列的顺序存储结构及其基本运算。?线性单链表、双向链表与循环链表的结构及其基本运算。?树的基本概念,二叉树的定义及其存储结构,二叉树的前序、中序和后序遍历。?顺序查找与二分法查找算法、基本排序算法(交换类排序、选择类排序与插入类)。二级 ACCESS 讲义 4 第一章算法与数据结构一、算法二、数据结构三、线性表四、栈五、队列六、线性链表七、树与二叉树八、查找技术九、排序技术二级 ACCESS 讲义 5 一、算法 ?算法是指为了解决某类问题而规定的一个有限长度的操作(指令)序列。(1)算法的特点: 可行性、确定性、有穷性、拥有足够的情报。(2)算法的两个基本要素: 一是对数据对象的运算和操作二是算法的控制结构,具体包括顺序结构、选择结构和循环结构。二级 ACCESS 讲义 6 ?算法的复杂度(代价)是衡量算法好坏的量度,具体可分为两种:时间复杂度和空间复杂度。(1)时间复杂度是指执行算法所需要的计算工作量,即算法执行过程中所需要的基本运算次数。通常记作: 常见的时间复杂度有: (2)空间复杂度是指执行该算法所需要的内存空间。))(()(nfOnT?)2() 3() 2()2 log ()()2 (log )1( nOnOnOnnOnOnOO??????二级 ACCESS 讲义 7 二、数据结构 ?数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。?数据结构有三个方面的内容:数据的逻辑结构、数据的存储结构、数据的运算。二级 ACCESS 讲义 8 ?数据的逻辑结构是指数据元素之间的逻辑关系,从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。?数据的逻辑结构一般分为两种:线性结构和非线性结构。线性结构: 有且只有一个根结点;每一个结点最多有一个前件,也最多有一个后件。如:一年四季。非线性结构: 线性以外的数据结构。如:反映家庭成员间辈分关系的数据结构。二级 ACCESS 讲义 9 A. 线性结构①线性表例:英文字母表(A , B , C , ······· , X ,Y , Z) 例:学生成绩表②栈——后进先出③队列——先进先出 86 胡孝臣 9861103 95 刘忠赏 9861107 100 张卓 9861109 成绩姓名学号二级 ACCESS 讲义 10 B. 非线性结构①树形结构例:全校学生档案管理的组织方式例:计算机文件管理系统也是典型的树形结构