《数据结构复习》PPT课件.ppt

数据结构,主 讲 ：刘仁芬,熟悉各名词、术语的含义，掌握基本概念。,理解算法五个要素的确切含义。,掌握计算语句频度和估算算法时间复杂度的方法。,本章知识点,第一章 绪论,1.1 什么是数据结构,本章目录,1.2 基本概念和术语,1.3 抽象数据类型的表示和实现,第1章 绪论,本节总结,1.4 算法和算法分析,数据（data)对客观事物的符号表示, 指所有能输入到计算机中并被计算机程序处理的符号的集合，计算机操作对象的总称.如整数，实数，字符串，图像，声音是数据。 数据元素（data element）数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。 数据项（data item）数据的不可分割的最小单位. 如一本书的书目信息为一个数据元素，书目信息中的每一项（如书名，作者名，出版日期（组合项）为一个数据项。,1.2 基本概念和术语,数据对象是性质相同的数据元素的集合，是数据的一个子集。如整数数据对象是集合N = 0, 1, 2, ，字母字符数据对象是集合C=A,B,C,，Z。 数据结构（data structure)是相互之间存在一种或多种特定关系的数据元素的集合。,结构（数据元素相互之间的关系）,（集合）数据元素间除“同属于一个集合”外，无其它关系 线性结构一个对一个，如线性表、 栈、队列 树形结构一个对多个，如树 图状结构多个对多个，如图,根据数据元素间关系的不同特性，有四种基本结构,数据结构的形式定义为：数据结构是一个二元组 Data_Structure=(D, S) 其中：D是数据元素的有限集，S是D上关系的有限集,数据的逻辑结构结构定义中的“关系”，描述的是数据元素之间的逻辑关系，因此称为数据的逻辑结构。是对操作对象的一种数学描述，从操作对象抽象出来的数学模型。从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。 数据的存储（物理）结构是数据结构在计算机中的表示（又称映像）。包括数据元素的表示和关系的表示。指数据元素及其关系在计算机存储器内的表示。存储结构是逻辑结构用计算机语言的实现，依赖于计算机语言。,数据元素的表示： 位：二进制数的一位，表示信息的最小单位。 数据元素/结点：由若干位组合起来形成的一个位串，即数据元素在计算机中的映像。 数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。,数据元素之间的关系的表示：关系都可以表示成有序对的集合。, ,数据元素之间的关系的表示即有序对集合的映像。,数据元素之间的关系的表示方法：顺序映像和非顺序映像。对应两种不同的存储结构：顺序存储结构和链式存储结构。 顺序映像特点:是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 中y的存储位置与x相差一个常量C，C是一个隐含值。,非顺序映像特点:是借助附加信息（指示元素存储地址的指针）来表示数据元素之间的逻辑关系。 中附加信息与x存储在一起，指向y的存储地址。,不同的编程环境数据结构的描述不同，比如高级语言就可以用数组来描述顺序存储结构。,数据类型：是一个值的集合和定义在这个集上的一组操作的总称。,数据类型分为两类：一类是非结构的原子类型。原子类型的值是不可分解的。如C语言中的基本类型（整型、实型、字符型和枚举），指针类型和空类型。另一种是结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是结构的，也可以是非结构的。如数组是由若干分量组成，每个分量可以是整数，也可以是数组。 结构类型可以看成由一种数据结构和定义在其上的一组操作组成。,抽象数据类型（ADT）：是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 D+S=数据结构，D+S+P=抽象数据类型。 抽象数据类型的特性： 数据抽象：强调本质特征及所能完成的功能和外部接口。 数据封装：将实体的外部特性和内部实现细节分离，并且隐藏实现细节。,1.4 算法和算法分析 算法（algorithm）对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。,算法着重于思想的描述,可能会省略很多细节,因此,算法需要进行适当修改才能变成程序在机器上实现.,(1)有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。 (2)确定性：算法的每一条指令必须有确切的含义，理解时不会产生二义性,并且在任何条件下都只有一条执行路径。 (3)可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 (4)输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。 (5)输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,算法特性,算法设计的要求衡量算法优劣的标准 正确性：算法应当满足具体问题的需求。4个层次 程序不含语法错误 程序中对于几组输入数据能够满足规格说明要求的结果 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够满足规格说明要求的结果 程序对于一切输入数据都能产生满足规格说明要求的结果 可读性：算法主要是为了人的阅读和交流，其次才是机器执行。,算法设计的要求衡量算法优劣的标准 健壮性：当输入的数据非法时，算法应当恰当地做出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。 效率与低存储量需求：效率指的是算法执行时间。存储量需求指算法执行构成中所需要的最大存储空间。,算法=控制结构+原操作（固有数据类型的操作） 算法的执行时间=原操作（i）执行次数 原操作（i）执行时间 原操作（i）执行次数 对于研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。基本操作重复执行的次数被称为语句频度，是问题规模n的某个函数 f(n)。随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。记作： T (n) = O(f(n),算法的空间复杂度： 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作：S(n) = O(f(n)，输入和程序之外的额外空间。,/ 将 a 中整数序列重新排列成自小至大有序的整数序列。 for (i=n-1, change=TRUE; i1 -i), change = FALSE; / change 为元素进行交换标志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡 S(n) =O(1) 原地工作,线性结构的特点；线性表的相关概念；线性表上定义的基本运算和用基本运算构造出的较复杂的运算。,掌握顺序存储结构和链式存储结构的描述方法，以及各种基本操作的实现。,能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。,本章知识点,第二章 线性表,2.1 线性表的类型定义,本章目录,2.2 线性表的顺序表示和实现,2.3 线性表的链式表示和实现,第2章 线性表,本节总结,2.4 一元多项式的表示及相加,线性结构的特点： 在数据元素的非空有限集中， (1)存在唯一的一个被称为第一个的数据元素； (2)存在唯一的一个被称为最后一个的数据元素； (3)除第一个之外，集合中的每个数据元素均只有一个前驱； (4)除最后一个之外，集合中每个数据元素均只有一个后继。,第2章 线性表,线性表是一种最常用最简单的线性结构。,2.1 线性表的类型定义,线性表是n个数据元素的有限序列。,抽象数据类型线性表的定义,ADT List 数据对象：Dai|aiElemSet,i=1,2,.,n, n0 数据关系：R1|ai-1 ,aiD, i=2,.,n 即数据元素的次序关系。,ai 是第i个数据元素，称i为ai在线性表中的位序。 数据元素可以是字母字符、数、或者更复杂的记录（由多个数据项组成）。,称n为线性表的长度;称n=0时的线性表为空表。,线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。(元素之间的关系隐含在存储地址中),an,ai,a2,a1,b,b+L,b+(i-1)*L,b+（n-1)*L,存储地址,内存状态,图 2.2 线性表的顺序存储结构示意图 设每个元素需占L个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。 b为第一个数据元素的存储位置，称为线性表的起始位置或者基地址,2.2 线性表的顺序表示和实现,Loc(ai)=Loc(a1)+（i-1）*L,每个元素所占用 的存储单元个数,LOC（a1）是线性表的起始地址或基地址。,线性表中第i+1个数据元素的存储位置 Loc（ai+1）和第i个数据元素的存储位置 Loc（ai）之间满足下列关系： Loc(ai+1)=Loc(ai)+L 线性表的第i个数据元素ai的存储位置为：,线性表的这种机内表示称作线性表的顺序存储结构或顺序映象，称这种存储结构的线性表为顺序表。 以元素在计算机内的物理位置相邻来表示线性表中数据元素之间的逻辑关系。每个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。因此，只要确定了线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。,#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量 typedef struct /定义一个SqList这样的类型(结构体类型) ElemType *elem; / 存储空间基址,指示线性表基地址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位) SqList;,/-线性表的动态分配顺序存储结构-,线性表的基本操作在顺序表中的实现,InitList_Sq(&L) / 结构初始化,LocateElem_Sq(L, e, compare() / 查找,ListInsert_Sq(&L, i, e) / 插入元素,ListDelete_Sq(&L, i) / 删除元素,算法2：在线性表中指定位置i前插入一个元素,(a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an), ,表的长度增加,例如：ListInsert_Sq(L, 5, 66),L.length-1,0,87,56,42,66,q = ,*q=e;/ 插入e +L.length;/ 表长增1,一般情况下，设 Pi是在第i (1in)个数据元素之前插入一个元素的概率，在第i个元素之前插入一个元素时，需将第n个元素至第i个元素向后移动一个位置，即移动n-i+1个元素。 在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）为,插入时移动次数的期望值（平均次数）,(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,算法3：在线性表中删除第i个元素,L.length-1,0,87,56,p = ,例如：ListDelete_Sq(L, 5, e),一般情况下，删除第i(1in)个元素时，需将第i+1至第n(共n-i个)元素依次向前移动一个位置。qi是删除第i个元素的概率。 在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均值）为,删除第i个元素的移动次数的期望值（平均值）,例如：顺序表,23 75 41 38 54 62 17,L.length,L.listsize,e =,38,i,1,2,3,4,1,8,50,可见，基本操作是： 将顺序表中的元素逐个和给定值 e 相比较。不相等后移，相等返回。,算法4：在顺序表中查找是否存在和e相同的数据元素,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 i = 1; / i 的初值为第 1 元素的位序 p = L.elem; / p 的初值为第 1 元素的存储位置 while (i = L.length / LocateElem_Sq,时间复杂度O(L.length),2.3 线性表的链式表示和实现,线性表的链式存储结构特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。,为了表示每个数据元素与其直接后继之间的逻辑关系，对数据元素ai来说,除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映象，称为结点。它含有两个域：存储数据元素信息的域称为数据域。存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。,数据域 指针域,结点,2.3.1 线性链表,n个结点链成一个链表，即为线性表（a1,a2,an）的链式存储结构。由于链表的每个结点中只包含一个指针域，又称线性链表或单链表。 整个链表的存取需从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映象）的存储位置。由于最后一个数据元素没有直接后继，则线性表中最后一个结点的指针为空(NULL)。 指针为数据之间逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，这种存储结构为非顺序映像或链式映像。,typedef struct LNode ElemType data； struct Lnode *next； LNode，*LinkList；,线性表的单链表存储结构,L,图2.7 带头结点的单链表,L,(a)非空表,(b)空表,在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针。 单链表的头指针指向头结点。 若线性表为空表，则头结点的指针域为空。,L,单链表操作的实现,GetElem_L(L, i, &e) / 取第i个数据元素,ListInsert_L(&L, i, e) / 插入数据元素,ListDelete_L(&L, i, &e) / 删除数据元素,CreateList_L(&L, n) / 生成含 n 个数据元素的链表,线性表的操作GetElem_L(L, 3, &e) 在单链表中的实现:,j,1,2,3,单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为： 从头到尾根据next指针域移动指针，令指针 p 始终指向线性表中第j个数据元素，比较 j 和 i，当j=i时（p指向第i个数据元素）或者移动到链表尾部时结束。,线性表的操作 ListInsert(&L, i, e) 在单链表中的实现：,有序对 改变为 和,s = (LinkList) malloc ( sizeof (LNode); /生成新结点 s-data = e; s-next = p-next; p-next = s; /插入 return OK;,s,p,线性表的操作ListDelete_L (&L, i, &e)在链表中的实现:,有序对 和 改变为 ,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q = p-next; p-next = q-next; e = q-data; free(q);,p,q,a1 a2 . an,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,循环单链表,特点：最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到其它结点。P35,空表,2.3.2 循环链表,在每个结点中有两个指针域，一个指向直接后继，一个指向直接前驱。,typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList;,线性表的双向链表存储结构,2.3.3 双向链表,双向循环链表,空表,非空表,a1 a2 . an,双向链表有循环表，链表中有两个环，在双向链表中，若d为指向表中某一结点的指针（即d为DuLinkList型变量），则显然有d-next-prior=d-prior-next=d,双向链表的操作特点：,“查询”和单链表相同。,“插入”和“删除”时需要同时修改两个方向上的指针。,s-next = p-next; p-next = s; s-next-prior = s; s-prior = p;,p,s,插入,删除,p-next = p-next-next; p-next-prior = p;,p,删除,p-prior-next = p-next; p-next-prior = p-prior;,p,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3. 综合比较线性表两种存储结构的不同特点及其适用场合。,本章总结,线性表链式存储结构的特点： 优点：空间合理利用，插入和删除不需要移动。 缺点：实现某些操作不如顺序存储结构。 线性表顺序存储结构特点： 优点：关系上相邻的两个元素在物理位置上也相邻，因此可随机存取表中任一元素，存储位置可用一个简单，直观的公式来表示。 缺点：插入或删除操作时，需大量移动元素。 分析讨论： （1）在表很长时，采用顺序方式时插入和删除元素的效率很低，只有在很少进行插入和删除运算的情况下，采用顺序表才是合适的。而线性链表的插入和删除运算效率总是很高，与表长无关。 （2）对线性表的长度或存储规模难以估计时，不宜采用顺序表 （3）顺序表所占存储空间少，但要求是连续的存储单元；线性链表因为有指针域，所占存储空间大，但可以利用非连续 单元。,本章要点, 栈和队列的定义和特点, 熟练掌握栈类型的实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。, 能在相应的应用问题中正确选用它们。,第三章 栈和队列,本章目录,第3章 栈和队列 3.1 栈 3.2栈的应用举例 3.3栈和递归的实现 3.4队列,栈(后进先出的线性表)：是限定仅在表尾进行插入和删除操作的线性表。表尾端为栈顶，表头端为栈底。不含元素的栈为空栈。,3.1 栈,3.1.1抽象数据类型栈的定义,设栈s=（a1，a2，.,ai，.，an），a1是栈底元素，an是栈顶元素。,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,栈的抽象数据类型的定义:,GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。,a1,a2,an, ,Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。,a1,a2,an,e, ,入栈,Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。,a1,a2,an,an-1, ,出栈,栈有两种存储表示方法：顺序栈、链栈。,顺序栈：即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的存储位置。,3.1.2 栈的表示和实现,/- 栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize;/栈的最大容量 SqStack;,a1,a2,top,base,栈的初始化操作为：按设定的初始分配量进行第一次存储分配，base称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base值为NULL，表明栈结构不存在。 称top为栈顶指针，初值指向栈底，即top=base为栈空，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。,top,base,top,base,top,base,top,base,栈中的运算： 1.设置空栈； 2.取栈顶元素; 3.插入一个新的栈顶元素； 4.删除栈顶元素。,Status InitStack (SqStack ,/- 基本操作的算法描述 -,构造一个空栈S,Status GetTop(SqStack S,SElemType ,取栈顶元素,Status Push (SqStack /存储分配失败,入栈,S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; ,Status Pop (SqStack ,出栈,例：设S是一个顺序栈，栈的最大容量stacksize=4 ，初始状态top=base,10,S4,base,*s.top=e top=top+1,top,栈空,10进栈,S4,top,base,top=base,10,25,30,S4,top,base,top=top-1 e=*s.top,40出栈,top-base=stacksize,栈满,10,25,30,40,S4,top,base,由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。,3.2.1 数制转换,3.2 栈的应用举例,3.2.2 括号匹配的检验,3.2.3 行编辑程序,3.2.4 迷宫求解,3.2.5 表达式求值,递归函数：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数。,3.3 栈和递归的实现,递归算法：描述递归定义的函数或求解递归问题的过程称为递归算法。 递归算法的实质，是将解问题规模N的较复杂的处理分解为问题规模小于N的较简单的处理，这些较简单的问题又分解为问题规模更小的更简单的问题处理，直到最简单的处理。然后这些规模小的简单问题的解综合为规模较大的问题的解，直到求到原问题的解。,假设有3个分别命名为x、y和z的塔座，在塔座x上插有n个直径大小各不相同、依小到大编号为l，2，n的圆盘，现要求将x轴上的n个圆盘移至z轴上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则： (1)每次只能移动一个圆盘； (2)圆盘可以插在x、y和z中的任一塔座上； (3)任何时刻都不能将一个较大的圆盘压在较小圆盘之上。,n阶Hanoi塔问题,void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n / 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 if (n=1) 3 move(x, 1, z); / 将编号为的圆盘从x移到z 4 else 5 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 6 move(x, n, z); / 将编号为n的圆盘从x移到z 7 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 8 9 ,介绍的是队列的逻辑结构定义及在两种存储结构(顺序存储结构和链式存储结构)上如何实现队列的基本运算。 本章的重点是掌握队列在两种存储结构上实现的基本运算。 难点是循环队列中对边界条件的处理。,本节内容及重点,3.4 队列,队列：是先进先出（FIFO）的线性表。只允许在表的一端进行插入，而在另一端进行删除元素的线性表。,3.4.1 队列的定义与运算,允许插入的一端叫队尾，允许删除的一端称为队头。 假设队列q=(a1, a2, ,an） a1是队头元素,an队尾元素。,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,基本操作：,InitQueue(&Q),操作结果：构造一个空队列Q。,EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。,a1,a2,an,e, ,DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。,a1,a2,an, , ADT Queue,队列的主要运算： （1）设置一个空队列； （2）读取队头元素; （3）插入一个新的队尾元素，称为入队； （4）删除队头元素，称为出队。,一个链队列显然需要两个分别指示队头和队尾的指针（头指针，尾指针）才能唯一确定。 为了操作方便，给链队列添加一个头结点，并令头指针指向头结点。 空的链队列的判决条件为头指针和尾指针均指向头结点。,3.4.2 链队列队列的链式表示和实现,链队列：用链表表示的队列。,Q.front Q.rear,Q.front Q.rear,空队列,链队列,链队列示意图,队头,队尾,Q.rear-next=S; Q.rear=S;,p=Q.front-next; Q.front-next=p-next; Free(p);?,typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,/-单链队列队列的链式存储结构,/-ADT Queue的表示和实现,Status EnQueue (LinkQueue ,Status DeQueue (LinkQueue ,在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，需附设两个front和rear分别指示队列头元素及队列尾元素的位置。,3.4.3 循环队列队列的顺序表示和实现,为在c语言中描述方便起见，在此约定：初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，尾指针增1；每当删除队列头元素时，头指针增1。,在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。,rear,front,初始状态,rear,front,J4,J5,J6,0,1,2,3,4,5,rear,front,J8,J7,队空,一般情况,解决方案： 少用一个元素空间： 队空：Q.front=Q.rear 队满：(Q.rear+1)%MAXQSIZE=Q.front,队满,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 初始化的动态分配存储空间 int front; / 头指针，若队列不空，指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素的下一个位置 SqQueue;,/-循环队列队列的顺序存储结构,Status InitQueue (SqQueue ,Status EnQueue (SqQueue ,Status DeQueue (SqQueue ,1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。,3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。,4. 理解递归算法执行过程中栈的状态变化过程。,本章总结,本章要点,理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。,熟悉串的基本操作的定义，并能利用基本操作来实现串的其它各种操作的方法。掌握串的三种机内表示方法。,第四章 串,4.1 串类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法,本章目录,第4章 串,串（string）：由零个或多个字符组成的有限序列。记为：s=a1a2a3an(n0) s是串的名，a1a2a3an是串的值。 ai（1in）可以是字母、数字或其它字符。 串的长度：串中字符的数目n。 空串：零个字符的串，它的长度为零。用表示空串。 空格串：由一个或多个空格组成的串。,4.1串类型的定义,串是有限长的字符序列，由一对单引号相括，如: a string,串的抽象数据类型定义：,ADT String ,数据对象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,数据关系：,R1 | ai-1, ai D, i=2,.,n ,串的逻辑结构和线性表极为相似，区别是串的数据对象约束为字符集。,StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。,例如：StrCompare(data, state) 0 比较的实质是ASCII码值,串的比较是一个字符一个字符的比,按照ASCII码比较,不是比较串长度. 串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。,StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数，称为串的长度。,SubString (&Sub, S, pos, len) 初始条件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。 操作结果： 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。,子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 如：A=STUDYING ，B=DYI ，A为主串，B为子串。 位置：字符在序列中的序号。 子串在主串中的位置以子串的第一个字符在主串中的位置来表示。,串的逻辑结构和线性表极为相似，区别是串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；而在串的基本操作中，通常以“串的整体”作为操作对象，,如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,串有3种机内表示方法,顺序,链式,若模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号。否则称匹配不成功，函数值为零。,模式匹配：子串的定位操作 模式串：子串,线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。 数组和广义表可以看成是线性表的扩展：表中的数据元素本身也是一个数据结构。,第5章 数组和广义表,ADT Array 数据对象： ji =0,.,bi -1, i=1,2,n Daj1, ,ji,jn| n是数组的维数，bi第i维的长度，ji第i维下标，aj1, ,ji,jn ElemSet 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, aj1,. ji,. jn , aj1, .ji +1, .jn D，i=2,.,n ,5.1 数组的定义,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW= | 0ib1-1, 0jb2-2 COL = | 0ib1-2, 0jb2-1,两个关系仍是线性关系,特点: 1) 一旦建立数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此采用顺序存储结构表示数组。 2) 数组是多维的结构，而存储空间是一个一维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。,5.2 数组的顺序表示和实现,二维数组有两种存储方式:P92 1)以行序为主序 （低次序优先） 2)以列序为主序 （高次序优先）,例如：,称为基地址或基址,以“行序为主序”的存储映象,二维数组A中任一元素aj1,j2 的存储位置 LOC(j1,j2) = LOC(0,0) + (j1b2j2),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,L,L,(式中：Loc（00）为元素a00的存储位置，即二维数组的起始存储位置，也称基地址，b1为二维数组的行数，b2为列数，aj1,j2代表其中第j1行、第j2列的那个元素,每个数据元素占L个存储单元),压缩存储：为多个值相同的元素只分配一个存储空间；对零元不分配空间。 目的是节省存储空间。,基本概念,特殊矩阵：值相同的元素或零元在矩阵中的分布有一定的规律。(对称矩阵，三角矩阵，对角矩阵). 反之,称为稀疏矩阵.,5.3 矩阵的压缩存储,稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑链接的顺序表,三、十字链表,ADT Glist 数据对象：Dei | i=1,2,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系： LR| ei-1 ,eiD, 2in,5.4 广义表（列表）的定义,广义表是线性表的推广,是递归定义的线性结构。记作LS = ( 1, 2, , n ) 。 LS是广义表的名称，n为表的长度。 i是表元素，它可以是广义表(称为子表)，可以是单个元素(称为原子)。 n = 0 的广义表为空表。,列表 LS = ( 1, 2, , n )是多层次的线性结构：,列表的元素可以是子表，而子表的元素还可以是子表，由此，列表是一个多层次的结构；,例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,c,e,（1）广义表中的数据元素有相对次序； （2）广义表的长度定义为最外层的元素个数； （3）广义表的深度定义为包含括弧的重数：原子的深度为0；空表的深度为1. （4）广义表可以共享; 例如：D=(E, F)，A=(E),E、F是D的子表，不必列子表的值，而是通过子表的名称来应用 （5）列表可以是一个递归的表；递归的深度无穷值，长度是有限值。,列表 LS = ( 1, 2, , n ) 的结构特点：,6）任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为： 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 两部分。 当广义表非空时，表的第一个元素1称为广义表的表头(head)，除此之外，其它元素组成的表（2,3, n）称为广义表的表尾(tail)。,1. 了解数组的存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 2. 掌握对特殊矩阵（对称矩阵和对角矩阵）进行压缩存储时的下标变换公式。 3. 了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,本章总结,4. 掌握广义表的结构特点及其存储表示方法，学会对非空广义表进行分解的分析方法：即可将一个非空广义表分解为表头和表尾两部分。,树是以分支关系定义的层次结构。 树结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可用树来表示。 树在计算机领域中也广泛应用，如在编译程序中，可用树表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一。,树型结构是非线性数据结构。,第6章 树和二叉树,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 哈夫曼树与其应用,树（tree）是n (n0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n1时，其余结点可分为m (m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。,6.1 树的定义和基本术语,根,子树,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm，存在关系，Xi T1 ，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,ADT Tree,基 本 术 语,结点:,结点的度:,树的度:,叶子（终端）结点:,分支(非终端)结点:,数据元素+若干指向子树的分支,结点拥有的子树数,树中所有结点的度的最大值,度为零的结点,度不为零的结点,D,H,I,J,M,子孙:以某结点为根的子树中的任一结点。,A,B,C,D,E,F,G,H,I,J,M,K,L,孩子:结点的子树的根。,双亲:该结点称为孩子的双亲。,兄弟:同一个双亲的孩子之间互称兄弟。,祖先:从根到该结点所经分支上的所有结点,有序树：子树之间存在确定的次序关系，不能互换,无序树：子树之间不存在确定的次序关系,树的深度：树中结点的最大层次,堂兄弟:其双亲在同一层的结点,结点的层次:假设根结点的层次为1，若某结点在第l 层，则其子树的根结点层次为l+1,D,H,I,J,M,任何一棵非空树是一个二元组 Tree =（root，F） 其中：root 被称为根结点 F 被称为m棵子树的森林,森林：,是m（m0）棵互 不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),对比,6.2 二叉树,二叉树:或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,特点： （1）每个结点至多有二棵子树(即不存在度大于2的结点)； （2）二叉树的子树有左、右之分，且其次序不能任意颠倒。,二叉树的五种基本形态：,空树,只含根结点,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,二叉树的性质,性质 1 ：在二叉树的第i 层上至多有2i-1 个结点。 (i1),性质 2 ：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,两类特殊的二叉树：,指的是深度为k且含有2k-1个结点的二叉树。,满二叉树：,树中所含的 n个结点和满二叉树中编号为 1 至 n 的结点一一对应。,完全二叉树：,完全二叉树特点：,（1）叶子结点只可能在层次最大的两层上出现;,（2）对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+1。,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1 (第k层第一个结点的编号） n 2k（第k1层第一个结点的编号） 即 k-1 log2 n k 因为 k 只能是整数,因此, k =log2n + 1 。,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为