基本数据结构和算法.ppt

《基本数据结构和算法.ppt》由会员分享，可在线阅读，更多相关《基本数据结构和算法.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识公共基础知识（二级）基本数据结构和算法主讲人：张炎欣主讲人：张炎欣全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识笔试考试题型一、选择题（每小题2分，共70分）二、填空题（每小题2分，共30分）公共基础知识 占10道选择题，5道填空题，共占30分.全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识数据结构概论考核知识点数据结构的基本概念算法的基本概念线性表的定义栈和队列线性链表循环链表树的基本概念查找技术排序技术全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识数

2、据结构概论重要考点提示数据结构的基本概念；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构算法的基本概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）线性表的定义；线性表的顺序存储结构及其插入与删除运算栈和队列的定义；栈和队列的顺序存储结构及其基本运算线性链表、双向链表与循环链表的结构及其基本运算树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序、后序遍历顺序查找与二分法查找算法基本排序算法(交换类排序、选择类排序、插入类排序)全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识一、数据结构概论1.数据、数据元素和数据项的概念2.数据结构的概念定

3、义：由逻辑结构S、基本运算集 和存储实现D所构成的整体（S，D）。构成：包括逻辑结构和基本运算两部分。3.数据的逻辑结构定义：是指数据元素之间逻辑关系的整体。是数据的组织形式。四类基本逻辑结构:集合、线性结构、树型结构、图状结构（逻辑结构的图形表示）非线性结构全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识一、数据结构概论4.数据的存储结构定义：数据按逻辑结构规定的关系在计算机存储器中的存放方式（也称物理结构）。存储结构的三个主要部分：存储结点：每个结点存储一个数据元素数据元素间关联方式的表示，即逻辑结构的计算机内部表示。附加设施，如为便于运算实现而设置的“哑结点”等。存

4、储结点之间可以有四种关联方式（称为基本存储方式）顺序存储/链式存储/索引存储/散列存储全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识二、算法及其描述重点提示算法的基本概念算法设计的要求算法复杂度的概念和意义（时间复杂度和空间复杂度）全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识二、算法及其描述1.算法的基本概念定义：求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能通过有限的指令序列、在有限的时间内被求解。算法的5个特性：1)有穷性2)确定性3)可行性4)输入5)输出全国计算机等级考试培训全国计算机等级考试培训-公共基础

5、知识公共基础知识二、算法及其描述2.算法设计的要求1)正确性2)可读性3)健壮性4)效率与低存储量需求3.算法的描述可以用自然语言，也可用计算机程序设计语言全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识二、算法及其描述4.算法的时间复杂度和空间复杂度时间复杂度：是指执行算法所需要的计算工作量。但有时使用这种绝对时间单位来衡量算法的效率是不合适的，所以又采用最坏情况复杂度和平均时间复杂度。最坏情况时间复杂度：是指在规模为n时，算法所执行的基本运算次数。平均时间复杂度：各种特定输入下的基本运算次数的加权平均值空间复杂度：指执行这个算法所需要占用存储空间的大小。算法好坏比较：

6、当问题规模n趋于无穷大时所需时间小的算法好（P5例）。全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识三、线性表重点提示线性结构的定义与特征线性表的定义线性表的顺序存储实现顺序表顺序表上插入与删除元素的运算全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识三、线性表1.线性结构与线性表的概念1)线性结构：定义：是n(n=0)个数据元素（结点）的有穷序列。说明：同一线性结构中的元素必定具有相同特性，相邻数据元素之间存在着序偶关系。描述：将含n(n0)个结点的线性结构表示成(a1,ai-1,ai,ai+1,an）。）。其中其中ai(0i=n)代表一个结点，

7、a1 称为起始结点,an称为终端结点。“i”称为ai在线性表中的序号或位置。对任意一对相邻结点，ai称为ai+1的直接前趋元素，ai+1称为ai的直接后断元素。全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识三、线性表1.线性结构与线性表的概念2)线性结构的基本特征存在惟一的一个被称为“第一个”的数据元素存在惟一的一个被称为“最后一个”的数据元素除起始结点外，其他结点有且仅有一个直接前趋；除终端结点外，其他结点有且仅有一个直接后继；3)线性表的概念定义：线性表的逻辑结构是线性结构线性表的长度：指所含结点的个数。表长为0的表称为空表。全国计算机等级考试培训全国计算机等级考试

8、培训-公共基础知识公共基础知识三、线性表2.线性表的顺序存储结构顺序表顺序表：即用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的特点：逻辑结构中相邻的结点在存储结构中仍相邻。顺序表的容量：指线性表实际达到的最大长度；表长指当前表的长度，表长小于或等于表的容量。3.插入、删除运算在顺序表上的实现1)插入2)删除全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识四、线性单链表、双向链表与循环链表的结构及其基本运算重点提示线性表的链式存储结构单链表，在单链表上插入与删除结点的操作双向链表与循环链表的结构在双向链表中插入与删除结点的基本操作全国计算机等级考试培训全国计算机

9、等级考试培训-公共基础知识公共基础知识1.线性表的链式存储结构单链表单链表表示法的基本思想是用指针表示结点间的逻辑关系。结点形式为：所有结点通过指针的链接而组织成单链表。2.插入、册除运算在单链表上的实现1)插入:INSERT(L,x,i)在单链表上找到插入位置生成一个值为X的新结点将新结点链入C语言描述：s-next=p-next;p-next=s;四、线性单链表、双向链表与循环链表next(指针域)data(数据域)a1a2an Lb插入前abax插入后pps本结点的指针是p-next全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识四、线性单链表、双向链表与循环链表2

10、.插入、册除运算在单链表上的实现2)删除的实现DELETE(L,i):找到第i个结点从单链表上摘除该结点（即改变指针域的指向）bacC语言的描述：p-next=q-next;Free(q);pq本结点的指针是q-next全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识四、线性单链表、双向链表与循环链表3.循环链表和双链表1)循环链表:与单链表的差别仅仅在于其尾结点指向与单链表的差别仅仅在于其尾结点指向头结点。头结点。判断循环链表是否为空表的条件是它们是否等于头指针。即 L-next=La1a2anL2)双链表:双链表的结点中有一个数据域和两个指针域特点：容易查找前趋与后继

11、data(数据域)prior(指向前驱)prior(指向后继)空单循环链表全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识四、线性单链表、双向链表与循环链表3.循环链表和双链表2)双链表:双向链表的结构：a1a2anL双链表的插入与删除：baxbca ppqs-next=p-next p-next-prior=ss-next=p-next p-next-prior=sp-next=s s-prior=pp-next=s s-prior=p s q-next=p-next q-next=p-next p-next-prior=qp-next-prior=q本结点的指针是p-

12、next，即结点p的后继域指针p-next，所以本结点的前趋指针为：p-next-prior请注意指针修改先后次序。全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识五、栈和队列q栈和队列都是线性表，从数据结构角度看，也是线性表，是操作受限的线性表，也称限定性数据结构。1.栈的定义v定义：栈是种“特殊的”线性表，其插入和删除操作限定在表的某一端进行。v几个名词：栈顶、栈底、进栈、退栈v运算原则：“先进后出”（或“后进先出”）2.栈的顺序实现1)顺序栈的定义：栈的顺序存储结构称为顺序栈。v“上溢”：当顺序栈的状态为栈满时，再有进栈v“下溢”：顺序栈为空时，如果做退栈运算。a1

13、a2an出栈进栈栈顶栈底一般由一维数组和记录栈项位置变量组成全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识五、栈和队列2.栈的顺序实现2)顺序栈的进栈和退栈运算v进栈：栈顶下标加1 将入栈元素放到新的栈顶下标所指位置v退栈：退栈先要将栈顶元素取出，由参数返回，并将栈顶下标减13.队列的定义v定义：队列（简称队）是只允许在一端删除，在另一端插入的顺序表。允许插入的一端称队尾，允许删除的一端称队头。v队列又称先进先出线性表a1 a2 a3 an出队列入队列全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识五、栈和队列4.队列的顺序实现1)顺序队的组织方法

14、，顺序队上的“假溢出”及其原因v队列的顺序实现称为顺序队，它由一个一维数组及两个分别指示队头和队尾的变量组成。v当前尾指针等于数组的上界，即使队列不满，再做入队操作也会导致溢出，这种现象称“假溢出”4 3 2 1 0队尾队头4 3 2 1 0队尾abc队头4 3 2 1 0队尾c队头4 3 2 1 0队尾队头de空队 a,b,c相继入队 删除a,b d,e入队后又删除c全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识五、栈和队列4.队列的顺序实现2)循环队列的组织方法及其基本运算v所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。这样只要

15、数组的低下标端有空闲空间，仍可做入队操作。此时只需令sq.rear=0v入队、出队操作3)循环队列的判断队满、队空的方法4)队满:当队尾指针“绕一圈”后赶上队头指针时视为队满，即：(sq.rear+1)%maxsize=sq.frontv队空:首尾指针相等。即：sq.rear=sq.front 2 1 队尾:sq.rear队头:sq.frontm入队：sq.rear=(sq.rear+1)%maxsize;Sq.datasq.rear=x;出队：Sq.front=(sq.front+1)%maxsize;注：%为取余运算x全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识六

16、、树重点提示树的基本概念二叉树的定义及其性质、满二叉树与完全二叉树二叉树的存储结构顺序存储与链式存储的实现二叉树的遍历前序（先根）、中序（中根）和后序（后根）遍历全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识六、树1.树型结构的基本概念1)树的定义：树是n(n=0)个结点的有限集合。n=0称为空树，n0称为非空树：2)有且仅有一个称为根的结点3)当n1时，除根结点外的其余结点可以划分为m个互不相交的有限个集合，每一个集合又是一棵树，称为子树，每棵子树的根结点有且仅有一个直接前驱，0个或多个后继。2)树型结构的有关术语3)结点的度/叶子或终端结点/树的度/父结点/兄弟/根

17、的子孙/祖先/树的高度或深度全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识2.二叉树的定义1)二叉树的逻辑结构、特点和5种基本形态v二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件：有且仅有一个称为根的结点根结点外的其余结点分为两个互不相交的集合T1、T2，且T1、T2都是二叉树，并且有序（T1在T2之前），它们分别称为根的左右子树。v二叉树的5种基本形态：A空树只有根结点同时有非空左右子树全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识2.二叉树的定义2)满二叉树和完全二叉树的概念v满二叉树是指：除最后一层外，每一层上的所有结点都有

18、两个子结点。深度为k的二叉树具有2k-1个结点。在第i(i=1)层上最多有2i-1个结点。v完全二叉树是指：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。满二叉树也是完全二叉树。k-1结点的排列遵循从上到下，从左到右，左为空时不能将结点放入右边3)二叉树的基本性质:p18全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识3.二叉树的顺序存储结构1)二叉树存储的基本思想（按层编号）按层编号是指将一棵树中的所有结点按从第一层到最大层、每层从左到右顺序依次标记为1,2,n。对于完全二叉树，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一

19、维数组。对于非完全二叉树，则通过在非完全二叉树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。二叉树的顺序存储结构图全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识3.二叉树的顺序存储结构2)二叉树的链式存储结构二叉链表的结点形式如右：data域称为数据域；lchild称为左孩子指针域；rchild称为右孩子指针域。用于指向本结点的指针（左或右指针）二叉链表中所有存储结点通过它们的左、右指针的链接而形成整体每个二叉链表还必须有一个指向根结点的指针，即根指针。对二叉链表的访问只能从根结点开始。每个指针域必须有一个值，为空指针NULLlchildrchilddata123

20、4567root全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识4.二叉树的遍历含义：就是按某种次序系统的“访问”二叉树上的所有结点，使得每个结点均被访问一次，而且仅被访问一次。二叉树由三个基本单元组成：根结点、左子树和右子树先左后右遍历二叉树的三种情况：DLR,LDR,LRD1)先根（序）遍历：若二叉树为空，执行空操作，否则访问根结点先根遍历左子树先根遍历右子树2)中根（序）遍历：若二叉树为空，执行空操作，否则中根遍历左子树访问根结点中根遍历右子树3)后根（序）遍历：若二叉树为空，执行空操作，否则后根遍历左子树后根遍历右子树访问根结点全国计算机等级考试培训全国计算机等级

21、考试培训-公共基础知识公共基础知识七、查找表重点提示静态查找表的定义顺序查找的基本思路与算法二分查找的基本思路与算法。全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识七、查找表1.查找表的基本特点：查找表的逻辑结构是集合：它的基本运算包括查找、读表元、插入和删除元素等。静态查找表：查找表一经生成后，便只对其进行检索而不进行修改；或者在进行了一段时间的检索后集中地修改。即检索与修改不交叉进行。动态查找表：适用于检索与修改交叉进行、无法分成两个不相交的阶段的场合。2.静态查找表的实现以顺序表作为存储结构，然后在这个存储结构上实现表态查找表的基本运算。全国计算机等级考试培训全国

22、计算机等级考试培训-公共基础知识公共基础知识七、查找表3.顺序查找算法查找过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若比较相等则查找成功，找到所查记录。反之若直至第一条记录比较都不相等，则查找失败。平均查找长度：需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。长度为n的顺序表，在等概率情况下查找成功的平均查找长度为(n+1)/2,考虑到查找不成功的情形，则为3(n+1)/4。全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识七、查找表4.静态查找表的有序表表示方法及二分查找（折半查找）的算法有序表：所有结点的关键值都按某

23、种次序排列的顺序表。如整数按大小次序关系等二分查找的基本思路：每次将处于查找区间中间位置上的数据元素的键值X与给定值K比较，若不等则缩小查找区间（如K比中间值大则舍弃下半部分），并在新区间内重复上述过程，直到查找成功或查找区间长度为0（即查找不成功）为止。举例：P22全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识八、基本排序算法重点提示排序的基本概念，包括：排序的定义、内部排序与外部排序、排序算法时间复杂性的度量交换类排序冒泡排序和快速排序选择类排序直接插入排序常用排序方法的性能比较全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识1.排序的基本概念

24、1)排序的含义：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。2)内部排序与外部排序的概念1.内部排序：指在排序的整个过程中，数据全部存放在计算机的内存储器中，并且在内存储器中调整记录间的相对位置。2.外部排序：指排序过程中，数据的主要部分存放在外存储器中，借助内存储器逐步调整记录之间的相对位置。3)内部排序算法时间复杂性的度量方法1.通常只考虑键值的比较次数和记录的移动次数。2.当键值是字符串时，比较要占用较多的时间，当记录很大时，为了交换记录的位置，移动记录也要占用较多的时间。这是影响时间复杂性的两个主要因素。全国计算机等级考试培训全国计算机等级考试培训-公共基础知

25、识公共基础知识2.插入排序基本思想：P23插入排序包括直接插入排序和希尔排序两种直接插入排序：依次将每个记录插入到一个有序的子序中去希尔排序：先将整个待排元素序列分割成若干子序列,并分别进行插入排序，最后再整体进行一次插入排序。直接插入排序算法的时、空性能：1.初始状态若各记录已排好序的情况下，关键字比较次数为n-1,记录移动次数为0，此时的时间复杂度为O(n);2.初始状态若各记录是逆序排列时，关键字比较次数为(n+2)(n-1)/2,记录移动次数为(n-1)(n+4)/2，此时的时间复杂度为O(n2);3.直接排序是稳定的排序，其平均时间复杂度为O(n2)，空间复杂度为O(1)。全国计算机

26、等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识3.交换排序指在排序过程中，若两个记录A和B的相对位置不符合排好序的要求，则交换A和B的位置。交换排序可分为冒泡排序和快速排序两种。1)冒泡排序基本思想：P24冒泡排序是稳定的排序，其平均时间复杂度为O(n2)，空间复杂度为O(1)。2)快速排序基本思想：P25快速排序是不稳定的。全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识4.选择排序从待排序的记录中选择出一个关键字最小（按升序时）的记录，放在已排好序的记录序列之后。选择排序包括直接选择排序和堆排序1)直接选择排序2)直接选择排序算法的时、空性能无论记录初始

27、序列如何，都要进行n(n-1)/2次关键字比较。有序序列记录移动0次，逆序序列则要做3(n-1)次记录移动。直接选择排序是不稳定的排序，其平均时间复杂度为O(n2)，空间复杂度为O(1)。5.各种排序方法比较：P26全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识例题分析与练习例题分析：P26课后练习：P44全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识数据的逻辑结构集合：任何两个元素间都没有逻辑关系，组织形式松散。线性结构：数据元素间存在一对一的关系。树型结构：具有分支、层次特性，其形态有点像自然界中的树。元素间存在一对多的关系。图状结构：数据元

28、素间存在一多对多的关系。全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识插入、删除运算在顺序表上的实现插入前：(a1,ai-1,ai,ai+1,an）在第i个位置插入这个元素x插入后：(a1,ai-1,x,ai+1,ai+2,an+1）删除前：(a1,ai-1,x,ai+1,an）删除第i个位置的元素x删除后：(a1,ai-1,ai,an-1）全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识满二叉树与完全二叉树498151110612237a.完全二叉树4981511106237a.满二叉树13121514全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识二叉树的顺序存储结构图4981511106122374157623a.完全二叉树b.非完全二叉树000001 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 0 0 0 0 6 7 0全国计算机等级考试培训全国计算机等级考试培训-公共基础知识公共基础知识 二叉树的遍历498151110612237498151110612237498151110612237先根（序）中根（序）后根（序）