第1章 数据结构与算法基础,内容简介 教学目标 1.1 算法的基本概念 1.2 数据结构的基本概念 1.3 线性表及其顺序存储结构 1.4 栈和队列 1.5 线性链表 1.6 树和二叉树 1.7 查找技术 1.8 排序技术 本章小结 习题一,Access数据库程序设计,2,内容简介,数据结构是计算机科学中最基本、最重要的一门知识。 基本任务是讨论现实世界中数据的各种逻辑结构在计算机中的存储结构以及实现各种操作的算法问题。 基本目的是掌握如何组织数据、存储数据和处理数据的基本方法。,3,教学目标,理解算法和数据结构的基本概念 掌握线性表的定义、存储及其基本运算 理解栈和队列的基本概念 理解线性链表基本概念 掌握树、二叉树的基本概念和基本运算 掌握查找的基本方法 掌握最基本的排序方法,4,1.1 算法的基本概念,1.1.1 算法的基本概念 1.1.2 算法的时间复杂度和空间复杂度 1.1.3 经典例题解析,5,1.1.1 算法的基本概念,1算法的定义 算法是一个有限的指令集，是对特定问题求解步骤描述的计算机指令的有限序列，其中每一条指令表示一个或多个操作。 简单解释：算法是解决问题的方法和步骤。,6,2算法的基本特性,输入性： 输出性： 有穷性： 确定性： 可行性：,7,3算法设计目标,正确性； 可读性； 健壮性； 高效性； 低存储性。,8,4算法的描述工具,流程图描述； 自然语言描述； 其他方式描述。,9,1.1.2 算法的时间复杂度和空间复杂度,1算法的时间复杂度 平均时间复杂度 最坏时间复杂度 最优时间复杂度,10,2算法的空间复杂度,与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。 但一般所讨论的是除正常占用内存开销外的辅助存储单元规模。 注意： 空间复杂度指执行时占用内存的空间，而不是存储时占用外存的空间。,11,1.1.3 经典例题解析,【例3.1.1】下列叙述中正确的是（ ）。 A）算法的效率只与问题的规模有关，而与数据的存储结构无关 B）算法的时间复杂度是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关。,12,解 析：,算法的复杂度主要包括时间复杂度和空间复杂度。通常用时间复杂度和空间复杂度来衡量算法效率，算法的时间复杂度就是执行该算法所需要的计算工作量，算法所执行的基本运算次数与问题的规模有关。而一个算法的空间复杂度，就是执行该算法所需要的内存空间。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。 【答 案】B,13,【例3.1.2】,下列叙述中正确的是（ ）。 A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对,14,解 析：,算法在运行过程中所需要的辅助存储空间的大小称为算法空间复杂度；算法的时间复杂度是执行该算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，与所使用的计算机、程序设计语言以及程序编制者无关，而且还与算法实现过程中的许多细节无关。但可以用算法在执行过程所需基本运算的执行次数来度量算法的工作量。 【答 案】D,15,【例3.1.3】,算法复杂度主要包括时间复杂度和（ ）复杂度。 【答 案】空间,16,【例3.1.4】,对某个问题处理方案的正确而完整的描述称为（ ）。 解 析：算法是指为解决某个特定问题而采取的确定且有限的步骤的一种描述。 【答 案】算法,17,1.2 数据结构的基本概念,1.2.1 数据结构的定义 1.2.2 线性结构与非线性结构 1.2.3 经典例题解析,18,1.2.1 数据结构的定义,1数据、数据元素、数据项和数据对象的概念 （1）数据 （2）数据元素 （3）数据项 （4）数据对象,19,2数据结构的概念,数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。 数据结构主要研究和讨论逻辑结构、存储结构和数据的运算3个方面的内容。,20,3数据的逻辑结构,数据的逻辑结构是对数据元素之间的逻辑关系的描述，它是数据的组织形式。 数据元素间有4种基本逻辑结构，包括：集合、线性结构、树型结构和图形结构。,21,（1）集合,集合中任意两个数据元素间都没有逻辑关系，组织形式松散。 如下图所示。,22,（2）线性结构,数据元素间构成一种顺序的线性关系。 如下图所示。,23,（3）树型结构,树型结构具有分支、层次特性，数据元素间形成一种树型的关系。如下图所示。,24,（4）图形结构,图形结构是最复杂的一种，结构中数据元素之间存在多对多的关系。如下图所示。,25,4数据的存储结构,即数据的物理结构，是指数据按逻辑结构规定的关系在计算机存储器中的存放方式。 存储结构主要有顺序存储结构、链式存储结构、索引存储结构和散列存储结构等。,26,（1）顺序存储结构,每个存储结点只含有一个数据元素。所有存储结点连续地存放在存储器中，从而逻辑相邻的两个结点必物理相邻。,27,（2）链式存储结构,结点在存储器中随意存放，结点之间的物理关系与逻辑关系无关，逻辑关系用附加的指针域来表示。,28,（3）索引存储结构,每个结点仅含一个数据元素，所有结点连续存放。 此外增设一个索引表，索引表中的索引指示各存储结点的存储位置。,29,（4）散列存储结构,每个结点仅含一个数据元素，各结点均匀分布于存储区中，用散列函数指示各个结点的存储位置。,30,1.2.2 线性结构与非线性结构,根据数据结构中各元素之间前趋后继关系的不同，一般将数据结构分为线性结构与非线性结构两大类。 在一个数据结构中，数据元素之间为一对一的线性关系，第一个元素无直接前趋，最后一个元素无直接后继，其余元素都有且只有惟一的一个直接前趋和惟一的一个直接后继。则称这种数据结构为线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。,31,注意：,线性结构与非线性结构都可以是空的数据结构。对于空的数据结构究竟是属于线性结构还是非线性结构，这要根据具体情况来确定，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。,32,1.2.3 经典例题解析,【例3.1.5】下列叙述中正确的是（ ）。 A）程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量 D）以上三种说法都不对,33,解 析：,在计算机中处理数据时，数据的存储结构对程序的执行效率有很大影响。例如，在有序存储的表中查找某个数值比在无序存储的表中查找的效率高很多。 【答 案】A,34,【例3.1.6】,下列叙述中正确的是（ ）。 A）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机在存储空间上是向量式的存储结构，因此，利用数组只能处理线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构 D）以上说法都不对,35,解 析：,一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。数组是数据的逻辑结构，可以用多种存储结构来表示，因此选项B、C错误。 【答 案】 D,36,【例3.1.7】,下列叙述中正确的是（ ）。 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率,37,解 析：,一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。 【答 案】D,38,【例3.1.8】,数据的存储结构是指（ ）。 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示,39,解 析：,数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 【答 案】D,40,【例3.1.9】,数据结构分为逻辑结构和存储结构，循环队列属于（ ）结构。 解 析：数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。而数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。而所谓循环队列，就是将队列存储 空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。所以循环队列不需要存放元素之间的前后关系，故它属于逻辑结构。 【答 案】逻辑,41,1.3 线性表及其顺序存储结构,1.3.1 线性表的定义 1.3.2 线性表的顺序存储结构 1.3.3 顺序表的插入与删除运算 1.3.4 经典例题解析,42,1.3.1 线性表的定义,1数据结构与线性表 线性结构是n（n0）个数据结点的有穷序列。,43,2线性表的定义,线性表是n（n0）个数据元素构成的有限序列（a1，a2，an）。当n0时，a1称为表的始结点，an称为表的终结点；a1是a2的直接前驱节点，a2是a1的直接后继节点。依此类推。 非空线性表的结构特征如下： 有且只有一个始结点，没有直接前趋结点，只有一个直接后继结点； 有且只有一个终结点，没有直接后继结点，只有一个直接前趋结点； 除始结点和终结点外的其他结点有且只有一个前趋结点，也有且只有一个后继结点。,44,1.3.2 线性表的顺序存储结构,顺序表是线性表的顺序存储结构，即用一组地址连续的存储单元依次存储线性表的数据元素。,45,1顺序表的基本特征,线性表中的元素所占据的存储空间是连续的； 线性表中的各个元素按逻辑顺序依次存放在存储空间里。 由于一维数组是采用顺序存储结构，因此可以用数组来表示线性表的顺序存储结构。 数组an存放线性表的n个结点（a1，a2，an），每个结点在内存中占据d个连续字节，用loc（ak）表示ak的首地址，1kn，则：loc（ak）=log（a1）k*d。,46,2线性表的基本运算,（1）随机存储 （2）插入 （3）删除 （4）查找 （5）计数,47,1.3.3 顺序表的插入与删除运算,1插入运算,48,2删除运算,线性表的删除运算是指将表的第i（1in）个结点删去，使长度为n的线性表（a1，a2，an）变成长度为n-1的线性表（a1，a2，ai-1，ai+1， ，an）。在顺序表中要实现删除运算必须移动结点才能反映出结点间逻辑关系的变化。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。”,49,1.3.4 经典例题分析,【例3.1.10】在一个长度为n的顺序表中，向第i个元素（1in+1）位置插入一个新元素时，需要从后向前依次移动（ ）个元素。 A）n-1 B）i C）n-i-1 D）n-i+1 解 析：根据顺序表的插入运算的定义知道，在第i个位置入插入x，从ai到an都要向后移动一个位置，共需要移动n-i+1个元素。 【答 案】 D,50,1.4 栈和队列,1.4.1 栈 1.4.2 队列 1.4.3 经典例题解析,51,1.4.1 栈与栈的运算,1栈的定义 栈实际也是线性表，只不过是一种特殊的线性表。栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种“后进先出”或“先进后出”的线性表，简称为LIFO表。,52,2栈的运算,初始化栈：将栈S置为一个空栈（不含任何元素）。