《级公共基础》PPT课件.ppt

《《级公共基础》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二级公共基础（30′）第一章数据结构与算法一、概述1、基本概念及术语1)数据结构:反映数据元素之间关系的数据元素集合的表示。2)数据:描述事物的符号记录；是信息的载体。3）数据元素：数据的基本单位（元组、记录、结点、顶点）4）数据项：是具有独立含义的最小单位，不能分割；（属性、字段）2.数据结构（研究三方面的内容）(1)数据的逻辑结构:反映数据元素之间的所固有的逻辑关系（是在现实世界中的描述）;(2)数据的存储结构:数据的逻辑结构在计算机中的存储关系（反映在JSJ世界中）;(3)对数据结构的加工运算;注意：1)数据的逻辑结构与存储结构、计算机无关；2)数据的逻辑结构分为线性结构(线性表、栈、队

2、列)与非线性结构（树、图）；3.数据的存储结构:数据的逻辑结构在计算机中的存储关系.(1)顺序存储结构:逻辑上相邻的结点，物理上仍相邻，结点之间的关系由存储单元的连接关系体现的;(例如：数组采用此种存储结构)特点：①存储密度大、空间的利用率高；②支持直接访问，知一地址能访问所有元素；③插入、删除时可能引起大量结点的移动(2)链式存储结构：至少含有一个指针（地址）域，用指针体现数据元素之间的逻辑关系特点:①存储密度小、空间的利用率低；②不支持直接访问；③插入、删除时不移动结点（链式存储不仅存储数据元素而且还存储地址）(3)散列存储(4)索引存储4.算法及其特点1）定义：解决问题准确而又完整性的描

3、述；2）特点：确定性（无二义性）、可行性、有穷性（在有限的时间内完成）、拥有足够的情报3）算法设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法5.算法的时间复杂度和空间复杂度最坏时间复杂度及平均时间复杂度①算法的时间复杂度:执行算法所需要的计算工作量。（执行算法的次数）与使用的计算机、程序设计语言及程序编程者无关，但与问题规模有关；算法的工作量=f(n)n为问题的规模②算法的空间复杂度:执行这个算法所需要的内存空间。二、线性表1.线性表的逻辑结构1）定义：n个元素（结点）的有穷序列；n称表长。2）特点：除表头无直接前驱，表尾无直接后继，其余的结点有且仅有一个前驱（前件），一个后继（后

4、件);【表头没前驱，表尾没有后继】2.线性表分类1）顺序表顺序存储结构的线性表。是一种随机存取结构Loc(ai)=Loc(a1)+(i-1)*k①计算第i个位置的存储地址：ADR(ai)=ADR（a1）+(i-1)*k②第i个位置之前插入时:移动n-i+1个结点平均移动n/2个结点量级Ｏ(n)③删除第i个位置时:移动n-i个平均移动(n-1)/2个结点量级O(n)2）链表（运算的实现容易、空表与非空表处理一致）链式存储结构的线性表。(1)单链表设头结点（查找效率低）(2)循环链表设尾结点(3)双向循环链表从任一结点可迅速确定前趋和后继(查找效率高，但存储利用率低）…a1a2a3an^He

5、ad//a1a2an…Head补充循环链表的四个优点:1)在循环链表中增加一个表头结点，使得循环链表对空表与非空表的操作实现了统一；2）循环链表中最后一个结点的指针域不是为空，而是指向表头结点；3）判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点；4）在循环链表中，从任意一个结点都可以访问到表中其他所有的结点。三.栈与队列(运算受限【插入与删除】的线性表)1.栈(后进先出的线性表)（1）特点：1)LIFO（FILO）2)只允许在一端（栈顶）插入与删除；3）具有记忆功能(2)基本操作：入栈、出（退）栈、取栈顶元素、判栈空（入栈判满、出栈判空）(3)分类：顺序

6、栈和链栈(4)应用：栈是内存的一片区域；函数调用（子程序调用）；计算机中断过程注：若入栈的顺序A、B、C，问有几种出栈可能？熟练出栈的顺序，准确判断哪些能出栈哪些不能出栈.CBADbottomtop入栈ABCD出栈DCBA2.队列(一端插入，另一端删除)先进先出的线性表(1）特点：1)FIFO(LILO)2)插入、删除时指针均向后移（向右）3)有”假溢出”现象(2)基本操作:入队、出队（退队）(3)分类:顺序队列和链式队列(4)有假溢出现象循环队列ABCDfrontrear入队出队四、树1.定义：若干个结点的有序集（Tree）.当T为空时，称为空树（T=Φ）；要么满足：1)有且仅有一个结点为根

7、结点；（位于第一层）2）其余的若干个结点为互不相交的子集，每个子结点为子树。(子树：树中以某结点的一个子结点为根构成的树。)2.术语及基本概念层：（深度或高度）、度：包括树度和结点度、根结点：无前件的结点；子结点：某结点的的后件；叶子结点：（0度结点）、父结点：只有一个前件3.二叉树（1）定义：除第一层、最后一层外，其余的结点有且仅有一个前件、有一个或两个后件的树；(2)五种基本形态：Φo注意：二