资源描述
数据结构与算法,第1章 数据结构与算法 1.1 算法 1 算法的基本概念 2 算法复杂度 1.2 数据结构的基本概念 1 什么是数据结构 2 数据结构的图形表示 3 线性结构与非线性结构 1.3 线性表及其顺序存储结构 1 线性表的基本概念 2 线性表的顺序存储结构 3 顺序表的插入运算 4 顺序表的删除运算 1.4 栈和队列 1 栈及其基本运算 2 队列及其基本运算 1.5 线性链表 1 线性链表的基本概念 2 线性链表的基本运算 3 循环链表及其基本运算 1.6 树与二叉树 1 树的基本概念 2 二叉树及其基本性质 3 二叉树的存储结构 4 二叉树的遍历 1.7 查找技术 1 顺序查找 2 二分法查找 1.8 排序技术 1 交换类排序法 2 插入类排序法 3 选择类排序法,1、 算法,算法 算法是指为解决某个特定问题而采取的确定且有限的步骤的一种描述，它是有限的指令序列，在有限的时间内被求解。 算法的复杂度 可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。 时间复杂度：是指执行算法所需要的计算工作量。 常见时间复杂度有： 空间复杂度：一般是指执行此算法所需要的内存空间量。,有穷性：一个算法应包含有限个操作步骤。 确定性：算法中每一条指令必须有确切的含义。 有效性（可行性） ：算法中的每一步骤都应当能有效地执行，并得到结果。 有输入：执行算法时从外界取得的信息，有零个或多个输入。 有输出：算法得到的结果就是算法的输出，有一个或多个输出。,算法的基本特性,算法中对数据的运算和操作：对于所有算法都是按照要求从环境能够运行的所有操作中选择合适的操作所组成的一组指令序列。共四类 算术运算：主要包括加、减、乘、除等运算。 逻辑运算：主要包括“与”、“或”、“非”等运算。 关系运算：主要包括“大于”、“小于”、“等于”、和“不等于”等运算。 数据传输：主要包括赋值、输入和输出等操作。 算法的控制结构：算法中各操作之间的执行顺序。（顺序、选择、循环）,算法的基本要素,算法的描述方法 用自然语言表示 用传统流程图表示 用N-S流程图表示 用伪代码表示 算法设计的方法： 列举法 归纳法 递推 递归 回溯,正确性（Correctness）：算法应满足具体问题的需求。 可读性（Readability）：算法主要是为了人的阅读与交流，其次才是及其执行，可读性好有助于人对算法的理解。 健壮性（Robustness）：当输入非法是，算法应能适当的作出反应或进行处理。 高效性：有效使用存储空间和有较高的时间效率。,算法设计的要求,举例,计算机算法指的是_。 A.计算方法 B.调度方法 C.排序方法 D.解决某一问题的有限运算序列 算法的时间复杂度取决于_。 A.问题的规模 B.待处理的数据的初始状态 C.问题的困难度 D.A和B 算法的空间复杂度是指_。 A.算法程序中的指令条数。 B.算法执行过程中所需要的存储空间。 C.算法程序的长度。 D.算法程序所占有的存储空间。 描述算法的常用方法有_。自然语言、传统流程图、N-S流程图、伪代码描述语言,数据（Data）的概念 是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机程序处理的符号的总称。 数据元素（Data Element） 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。,2 数据结构,数据对象（Data Object） 是性质相同的数据元素的集合，是数据的一个子集。 数据结构（Data Structure） 是相互之间存在一种或多种特定关系的数据元素的集合，即带有结构的数据元素之间的前后件关系。,2 数据结构,数据结构（问题的数据模型）作为计算机的一门学科，它主要研究和讨论3个方面的问题： 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； 对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。 对各种数据结构进行的运算。,数据结构研究的问题,数据的逻辑结构是指数据元素之间的逻辑关系，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示。 数据的逻辑结构是从逻辑关系上描述数据，它与数据在计算机中的存储位置无关，是独立于计算机的。,数据的逻辑结构,数据逻辑结构有四类： 集合结构：数据元素之间的关系是“属于同一个集合”，集合是元素关系极为松散的一种。 线性结构：该结构数据元素之间存在一对一的关系。 树形结构：元素之间存在一对多的关系。 图形结构：数据元素之间存在多对多的关系。,数据的存储结构是数据元素及其关系在计算机存储空间中的表示。存储结构的主要内容是指在存储空间中使用一个存储结构点来存储一个数据元素；在存储空间中建立各存储结构点之间的关联，以表示数据元素之间的逻辑关系。 常用数据的存储结构有如下4种： 顺序存储方式。 链式存储方式。 索引存储方式。 散列存储式。,数据的存储结构,用二元关系表示：B=(D,R) 其中B表示数据结构， D表示数据元素的集合， R反映数据元素之间的前后件关系。例如 家庭成员数据结构可表示成： B=(D,R) D=父亲，儿子，女儿 R=（父亲，儿子）,(父亲，女儿) 用图形表示：对关系R中的每个二元组，用一条有向线段从前件结点指向后件结点，上述结构可表示如下：,数据结构的表示,线性结构与非线性结构,根据结构中各数据元素之间前后件关系的复杂程度，将数据结构分为两个类型：线性结构和非线性结构。 线性结构：在数据元素的非空有限集中，线性结构有如下特征： 存在唯一的一个被称作“第一个”的数据元素。 存在唯一的一个被称作“最后一个”的数据元素。 除第一个之外，集合中的每个数据元素均只有一个前驱。 除最后一个之外，集合中的每个数据元素均只有一个后继。 非线性结构：其特征是一个结点可能有多个直接前驱和直接后继，例如，树和图都是非线性结构。,举例,数据在计算机内存中的表示是指_。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系 数据的_包括集合、线性结构、树形结构和图形结构四种基本类型。 A 算法描述 B 基本运算 C 逻辑结构 D 存储结构 在数据结构中，从逻辑上可以把数据结构分成_。 线性结构和非线性结构 数据的存储结构包括顺序、_、索引和散列四种基本类型。 链式 _中任何两个结点之间都没有逻辑关系。 集合,线性表（Linear_List）的概念 线性表是n个具有相同数据类型的数据元素的有限序列。数据元素可以是一个数，一个符号，一页书，或是其他更复杂的信息。n为表长。 线性表的顺序存储结构 是指在内存中用一组地址连续的存储单元依次存储线性表中的数据元素，也称为顺序表。 顺序表的基本运算 插入运算是指在表中的某指定位置上增加一个新结点；而删除运算是指将表中某个结点从线性表中去掉。,3 线性表及其顺序存储结构,栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。对栈来说，表尾端有其特殊的含义，称为栈顶（top），表头端称为栈底（bottom）。栈顶元素总是被最后插入的元素，也是最先能被删除的元素；栈底元素总是最先被插入的元素，也是最后能被删除的元素。（LIFO） 栈的顺序存储结构 栈的基本运算,4 栈和队列,栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，存时附设指针指示栈顶元素在顺序栈中的位置。 如下图所示。,栈的顺序存储结构,a1,a2,an,栈的顺序存储结构示意图,其中，a1为栈底元素， an为栈顶元素。栈中的元素按照a1， a2，an为次序进栈，退栈的第一个元素为栈顶元素an。,进栈,出栈,栈顶,栈底,栈的基本运算有3种：入栈、退栈和读栈顶元素。 入栈运算：是指在栈顶插入一个新元素。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不能再进行插入栈的操作。上溢 退栈运算：是指取出栈顶元素并赋给一个指定的变量。当栈顶为0时，说明栈空，不可能进行退栈操作。下溢 读栈顶元素：是指将栈顶元素赋给一个指定的变量。此处要注意，此运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。,栈的基本运算,队列是限定仅在表的一端进行插入，而在表的另一端删除数据元素的线性表。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端称为队头（front）。（FIFO） 队列的顺序存储结构 队列的基本运算,4 栈和队列,在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需要附设两个指针，分别指示队头元素和队尾元素的位置。 队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。,队列的顺序存储结构,循环队列： Q.front=Q.rear=0表示队列空 (Q.rear+1)%maxqsize=Q.front表示队列满,一般情况,对满,对空,循环队列的基本运算有2种：入队和退队。假设循环队列的初始状态为空，即s=0,且front=rear=m 入队运算：是指在循环队列的队尾加一个新元素。这个运算有两个本操作，首先将队尾指针增一（rear=rear+1），并当rear=m+1时置rear=1；然后将新元素插入到队尾指针指向的位置。 退队运算：是指在队列的队头位置退出一个元素并赋值给指定的变量。这个运算有两个基本操作，首先将队头指针增一（front=front+1），并当front=m+1时置front=1；然后将队头指针指向的元素赋给指定的变量。,循环队列基本运算,举例,在一个长度为n的顺序表中，向第i个元素(1=i=n+1)位置插入一个新元素时，需要从后向前依次后移_个元素。 A n-i B i C n-i-1 D n-i+1 从一个长度为n的顺序表中，删除第i个元素 (1=i=n+1)时，需要从前向后依次向前移_个元素。 A i B n-i C n-i-1 D n-i+1 线性表中_称为表的长度。 数据元素的个数 栈又称为_表，队列又称为_表。 后进先出；先进先出 栈的插入和删除操作在_进行。 A 栈底 B 栈顶 C 指定位置 D 任意位置 假定一个栈的输入序列为A,B,C,D,E，则下列序列中不可能是栈的输出序列是_。 A B,C,D,A,E B E,D,A,C,B C B,C,A,D,E D B,E,D,C,A 在一个用一位数组an表示的顺序栈中，该栈所含元素的个数最少为_个，最多为_个。 0；n-1,线性单链表 线性表的链式存储结构的特点是用一组任意的存储单元（结点）存储线性表的数据元素。这组存储单元可以是连续的，也可以是不连续的。 基本运算 1、插入运算：p指向单链表中某结点，s指向待插结点。 前插：q=L; while(q-next!=p) q=q-next;/*找p的直接前驱*/ s-next=q-next;q-next=s;时间复杂度o(n) 后插：s-next=p-next; p-next=s; 时间复杂度o(1),5 线性链表,2、删除运算：设p指向单链表中某结点，删除p。 q为p的前驱结点 q-next=p-next; free(p); 循环链表 循环链表的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任一结点出发均可找到表中其他结点。 循环链表和单链表的差别仅在于判断链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。 基本运算 同非循环链表相似,在双向链表的结点中，有两个指针域，其一指向直接后继，另一个指向直接前驱。 基本操作 1、插入结点：设p指向双向链表中某结点，s指向待插入的值x的新结点，将s插入到 p的前面。 s-prior=p-prior;p-prior-next=s; s-next=p;p-prior=s; 2、删除结点：设p指向双向链表中某结点，删除p。 p-prior-next=p-next; p-next-prior=p-prior; free(p);,双向链表,举例,单链表要求内存中可用存储单元的地址_。 A.必须是连续的 B.一定不是连续的 C.部分地址必须是连续的 D.可以连续也可以是不连续 采用链接方式存储线性表的优点是_。 A.便于随机存取 B.花费的存储空间较顺序存储少 C.数据元素的物理顺序和逻辑顺序不同 D.便于插入和删除 在单链表中，头指针的作用是_。 A.方便运算的实现。 B.用于标识单链表。 C.使单链表至少有一个结点。 D.用于标识首结点位置。 在双向链表中，每个结点有两个指针域，一个指向_另一个指向_ 。前驱结点、后继结点,树的基本概念 树是一种简单的非线性结构。在树数据结构中，所有数据元素之间的关系具有明显的层次性。树是n（n0）个结点的有限集。n=0的树称为空树；在任意一棵非空树（n0）中： 有且仅有一个特定的结点称为根。 当n0时，其实结点可分为m（m0）个互不相交的有限集T1，T2，Tm。其中，每个有限集本身又是一棵树，并且称为根的子树。,6 树与二叉树,在任何一棵树中，除根结点外，其他任何一个结点又且仅有一个双亲，有0个或多个子女，且它的子女恰好为其子树的根结点。 一个结点拥有的子女数称为该结点的度，树中所有结点度的最大值称为树的度。 称度为0的结点为终端结点或叶子结点，称度不为0的结点为非终端结点或分支结点。 树中结点的层次：从树根开始定义，根结点为第一层，根的子女结点构成第二层，依次类推。称树中结点的最大层次数为树的深度或高度。,二叉树：二叉树是另一种树形结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能颠倒。 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左至右的顺序编号，如果编号为i(1=i=n)的结点与满二叉树中编号为i的结点在二叉树中位置相同，则称为完全二叉树。,二叉树主要性质： 性质1：一棵非空二叉树的第i层上的结点数目最多为2i-1(i1)。 性质2：一棵深度为k的二叉树中，最多有2k-1个结点(k1)。 性质3：在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。 性质4：具有n个结点的完全二叉树的深度k为log2n+1。,二叉树的存储结构 顺序存储结构：是指用一组连续的存储单元存放二叉树中的结点。 链式存储结构：是指用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。,二叉树的遍历 指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。 先序遍历：根-左子树-右子树 中序遍历：左子树-根-右子树 后序遍历：左子树-右子树-根 前序遍历序列：abdefgc 中序遍历序列：debgfac 后序遍历序列：edgfbca,举例,树最适合于表示_。 A.有序数据元素 B.元素之间无联系的数据 C.无序数据元素 D.元素之间具有分支层次关系的数据 在深度为4的满二叉树中，结点的个数为_。 A.20 B.35 C.30 D.15 已知某二叉树的前序遍历序列是ABDGCFK,中序遍历序列是DGBAFCK，则它的后序遍历序列是_。 A.ACFKDBG B.GDBFKCA C.KCFAGDB D.ABCDFKG 设二叉树根节点的层次为0，对含有100个结点的二叉树，可能的最大树深度和最小树深度分别是_。 99和6,顺序查找 顺序查找又称顺序搜索，是指在线性表中查找指定的元素，其基本查找过程如下： 从表中第一个记录开始，逐个进行记录的关键字和给定值的比较。 若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；若直至最后一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。,7 基本查找技术,二分法查找（折半查找） 二分法查找只适用于顺序存储的有序表，即要求线性表中的结点必须按关键字值的递增或递减顺序排列。,排序 排序是计算机内经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列。 插入类排序 将待排序文件中的记录，逐个的按其排序码值的大小插入到目前已排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。分为直接插入排序和希尔排序。,8 基本排序方法,1、直接插入排序： 初始可认为文件中的第一个记录已排好序，然后将第2个到第n个记录依次插入到已排序的记录组成的文件中。时间复杂度o(n2)。 时效分析： 开始有序，比较次数n-1，移动次数0次。 开始逆序，比较次数n(n-1)/2，移动次数n(n-1)/2次。,2、希尔排序： 首先选择一个增量序列t1,t2,tk,其中t1t2，tk=1；然后按增量序列个数k，对序列进行k趟排序；每趟排序根据对应的增量ti，将待排序分割成若干长度为m的子序列，分别对各子表进行直接插入排序。（不稳定的排序方法）,交换类排序： 对待排序记录两量进行排序码比较，若不满足排序顺序则交换这对记录，直到任何两个记录的排序码都满足排序要求为止。有冒泡法排序和快速排序法。,1、冒泡排序：首先对所有记录从左到右每相邻两个记录的排序码进行比较，如果这两个记录的排序码不符合排序要求，则进行交换，这样做完一趟，将排序码最大或最小者放在最后一个位置；然后对剩下的n-1个待排序记录重复上述过程，反复进行n-1趟排序结束，即为有序序列。 效率分析： 若记录初始状态已经排好序，则关键字的比较次数是n-1，交换次数是0，时间复杂度是o(n)。若初始状态为逆序，则关键字比较次数是(n+2)(n-1)/2,交换次数是3n(n-1)/2,时间复杂度是o(n2)。冒泡法是稳定的排序。,2、快速排序：从n个待排序的记录中任取一个记录k，将k后小于k的记录移到k前，而k前大于k的记录放置于k后，这样就以k为分界线，把记录分成两个子表。然后对前后两部分待排序记录重复上述过程，直到所有子表为空，排序即成。 效率分析：快速排序是不稳定的排序。 其平均时间效率最佳，为o(nlog2n)。 最坏情况下，时间效率为o(n2)。 若初始序列按关键马有序或基本有序时，快速排序蜕化为冒泡法排序。, 选择类排序 每次从待排序的文件中选出排序码最小的记录，将该记录放入已排序文件的最后一个位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。分为直接选择排序和堆排序。,1、直接选择排序： 首先从所有n个待排序记录中选择排序码最小的记录，将该记录与第一个记录交换，再从剩下的n-1个记录中选出排序码最小的记录与第2个记录交换。重复这样的操作直到剩下2个记录时，再从中选出排序码最小的记录与第n-1个记录交换，排序即告完成。 效率分析：关键字比较次数n(n-1)/2次，直接选择排序是不稳定的排序，时间复杂度是o(n2)，空间复杂度是o(1)。,2、堆排序： 设有n个元素的序列k1、k2、k3、kn，当且仅当满足下述关系之一时称之为堆： kik2i、 kik2i+1或者kik2i、 ki k2i+1 首先将n个元素按关键码建成堆复的操作直到剩下2个记录时，再从中选出排序码最小的记录与第n-1个记录交换，排序即告完成。,举例,对于长度为20的顺序表，若采用二分法查找，则查找第八个元素的查找长度为_。 A.2 B.3 C.5 D.4 顺序查找适合于存储结构为_的线性表。 A.散列存储 B.索引存储 C.压缩存储 D.1顺序存储或链式存储 在对n个元素进行冒泡排序的过程中，第一趟至多需要进行_对相邻元素之间的比较。 A.n/2 B.n-1 C.n D.n+1 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换他们的位置，此种方法称为_排序。 快速排序,
展开阅读全文