[PPT模板]数据结构讲义严蔚敏13章02201517.ppt

复制！数据结构习题集_徐昊郭威_20110220.doc张胜兰 数据结构上机讲义.rar,数 据 结 构,胡东红 QQ:1055908606湖北大学 物理学与电子技术学院,课程教学目的和任务：数据结构是电子信息工程专业的专业课程之一。通过本课程的学习，要求学生掌握数据结构的基本知识和数据结构程序设计的基本方法。教学方法：讲授、自学、课堂讨论、实验等多种形式相结合。先修课程及相关课程：本课程是在学习了一定的计算机基础、计算机语言等课程。总学时及学时分配建议表：总学时54学时。,学时分配建议,1 绪论 42 线性表 83 栈和队列 64 串 65 树和二叉树 86 图 67.复习 28.上机 12,参考文献,数字图像处理与分析（张弘 机械工业出版社）光盘 VC+代码上机讲义习题集,第1章 绪 论,计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。1.1 什么是数据结构首先要从具体问题抽象出一个适当的数据模型,然后设计一个解此数学模型的算法,最后编出程序、进行测试、调整直至得到最终的解答。,例1-1 图书馆的书目检索系统自动化问题最简单的线性关系,1.1 什么是数据结构,图1.1 图书目录文件示范,“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构。,图1.2 井字棋对奕“树”(a)棋盘格局示例；(b)对奕树局部。,例12 计算机和人对弈问题,这类交通、道路问题的数学模型是一种称谓“图”的数据结构。顶点代表通路顶点间的连线代表通路相互矛盾,例1-3 多叉路口交通灯的管理问题,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,数学代数系统,编码理论,算子关系,数据类型,数据表示法,数据的运算,数据结构数据存取机器组织,文件系统组织数据信息检索,软件（计算机程序设计）,存储装置,硬件（计算机系统设计）,图1.4“数据结构”所处的地位,1.2 基本概念和术语数据(Data)数据元素(Data Element)数据对象(Data Object)数据结构(Data Structure)数据元素相互之间的关系称为结构(Structure),1.2 基本概念和术语,四类基本结构:集合线性结构树形结构图状结构或网状结构,1.2 基本概念和术语,数据结构的形式定义为:数据结构是一个二元组 Data_Structure=(D,S)（1-1)其中:D是数据元素的有限集,S是D上关系的有限集。例1-4 复数是一种数据结构 Complex=(C,R)(1-2)其中：C是含两个实数的集合c1,c2；R=P,而P是定义在集合C上的一种关系表示c1是复数的实部，c2是复数的虚部。,1.2 基本概念和术语,例1-5 课题小组：1位教师、13名研究生及16名本科生。教师指导研究生，每位研究生指导12名本科生。定义数据结构：Group=(P,R)(1-3)其中:,1.2 基本概念和术语,逻辑结构物理结构,又称存储结构位(bit)元素(Element)或者结点(Node)数据域(Data Field)顺序映象非顺序映象两种不同的存储结构:顺序结构和链式存储结构指针,1.2 基本概念和术语,0300,0320,0632,0634,0415,0611,0613,图1.6 复数z1=3.0-2.3iz2=-0.7+4.8i存储结构示意图,（a）顺序存储结构；,（b）链式存储结构,数据类型（Data Type)是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型（Abstract Data Type)是指一个数学模型以及定义在该模型上的一组操作。一个含抽象数据类型的软件模块通常应包含定义、表示和实现三个部分。抽象数据类型可用三元组表示(D,S,P)其中D是数据对象,S是D上的关系集,P是对D的基本操作集。,1.2 基本概念和术语,ADT抽象数据类型名 数据对象：（数据对象定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义）ADT抽象数据类型名基本操作名（参数表）初始条件：（初始条件描述）操作结果：（操作结果描述）,ADT Triplet 数据对象:数据关系:基本操作:InitTriplet(&T,v1,v2,v3)DestroyTriplet(&T)Get(T,i,&e)Put(&T,i,e)IsAscending(T)IsDescending(T)Max(T,&e)Min(T,&e)ADT Triplet多形数据类型：是指其值的成分不确定的数据类型。,例1-6 抽象数据类型三元组的定义：,1.3 抽象数据类型的表示和实现,C语言的核心子集若干扩充修改预定义常量和类型#define TRUE 1类型定义 typedef 函数描述赋值语句选择语句循环语句结束语句输入输出语句注释基本函数逻辑运算,例1-7 抽象数据类型Triplet的表示和实现typedef ElemType*Triplet;/由InitTriplet分配三个元素存储空间/-基本操作的函数原型说明-Status InitTriplet(Triplet/初始条件：三元组已经存在，1 i 3。/操作结果：改变T的第i元的值为e。,1.3 抽象数据类型的表示和实现,1.3 抽象数据类型的表示和实现,Status IsAscending(Triplet T);/初始条件：三元组已经存在。/操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。Status IsDescending(Triplet T);/初始条件：三元组已经存在。/操作结果：如果T的3个元素按降序排列，则返回1，否则返回0。Status Max(Triplet T,ElemType/初始条件：三元组已经存在。/操作结果：用e返回T的3个元素中的最小值。,/-基本操作的实现-Status InitTriplet(Triplet/InitTriplet,1.3 抽象数据类型的表示和实现,Status DestroyTriplet(Triplet/DestroyTriplet,1.3 抽象数据类型的表示和实现,1.3 抽象数据类型的表示和实现,Status Get(Triplet/Get,1.3 抽象数据类型的表示和实现,Status Put(Triplet T,int i,ElemType e)/1 i 3,置T的第i元的值为e。if（i3)return ERROR;Ti-1=e;return OK;/Put,1.3 抽象数据类型的表示和实现,Status IsAscending(Triplet T)/如果T的3个元素按升序排列，则返回1,/否则返回0。return(T0=T1)/IsAscending,1.3 抽象数据类型的表示和实现,Status IsDescending(Triplet T);/如果T的3个元素按降序排列，则返回1，/否则返回0。return(T0=T1)/IsDescending,1.3 抽象数据类型的表示和实现,Status Max(Triplet T,ElemType/Max 注释：I=(32?1:0),1.3 抽象数据类型的表示和实现,Status Min(Triplet T,ElemType/Min,1.4.1 算法 算法(Algorithm)是对待定问题求解步骤的一种描述,它是指令的有限序列，其中每一条指令表示一个或多个操作；算法的5个重要特性：有穷性确定性可行性输入输出,1.4 算法和算法分析,正确性可读性健壮性效率与低存储要求,1.4.2 算法设计的要求,度量一个程序的执行时间通常有两种方法：事后统计的方法；事前分析估算的方法：两个NN矩阵相乘的问题for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=1;k=n;k+)ci,j+=ai,k*bk,j;整个算法的执行时间与该基本操作(乘法)重复执行的次数n3成正比，记做T(n)=O(n3),1.4.3 算法效率的度量,图1.7 常见函数的增长率,一般情况下,算法中基本操作重复执行的次数是问题规模 n的某个函数f(n),算法的时间量度记作T(n)=O(f(n)(1-5)它表示随时间规模 n 的增大,算法执行时间的增长率和 f(n)的增长率相同,称作算法的渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。,1.4.3 算法效率的度量,+x;s=0;for(i=1;i=n;+i)+x;s+=x;for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;这三个程序段的时间复杂度分别为O(1),O(n)和O(n2),分别称为常量阶、线性阶和平方阶。,1.4.3 算法效率的度量,空间复杂度（Space Complex)作为算法所需存储空间的度量，记作 S(n)=O(f(n)若额外空间相对于输入数据量来说是常数，则称此算法为原地工作,1.4.4 算法的存储空间需求,第二章 线 性 表,线性结构的特点是：在数据元素的非空有限集中:存在唯一的一个被称做“第一个”的数据元素；存在唯一的一个被称做“最后一个”是数据元素；除第一个之外，集合中的每个数据元素均只有一个前驱；除最后一个之外，集合中每个数据元素均只有一个后继。,2.1 线性表的类型定义,线性表数据项记录文件,图2.1 学生健康情况登记表,将线性表记为直接前驱元素直接后继元素线性表长度空表位序,2.1 线性表的类型定义,抽象数据类型线性表的定义如下：ADT List 数据对象：数据关系：基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。,2.1 线性表的类型定义,2.1 线性表的类型定义,ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,&e)初始条件：线性表L已存在。1i ListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,compare()初始条件：线性表L已存在。compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0.PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。,2.1 线性表的类型定义,NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert(&L,i,e)初始条件：线性表L已存在,1i ListLength(L)+1.操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1.ListDelete(&L,i,&e)初始条件：线性表L已存在且非空,1i ListLength(L).操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1.ListTraverse(L,visit()初始条件：线性表L已存在.操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT List,例2-1 合并两个线性表,void union(List/数据元素，则插入之/union算法2.1的时间复杂度为O(ListLength(LA)*ListLength(LB),例2-2 算法2.2 按值非递减有序排列,void MergeList(List La,List Lb,List/MergeList,例2-2 按值非递减有序排列 算法2.2,void MergeList(List La,List Lb,List/MergeList,2.2 线性表的顺序表示和实现,线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的第i个数据元素ai的存储位置为 式中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。,图2.2 线性表的顺序存储结构示意图,顺序存储结构或顺序印象(Sequential Mapping)线性表的顺序存储结构是一种随机存取的存储结构。,动态分配的一维数组,/线性表的动态分配顺序存储结构#define LIST_INIT_SIZE 100/初始分配量#define LISTINCREMENT 10/分配增量Typedef struct ElemType*elem;/存储空间基址 int length;/当前长度 int listsize;/当前分配的存储容量SqList;,算法2.3 顺序表的初始化操作,Status InitList_Sq(SqList/InitList_Sq,线性表的插入操作,(a1,.,ai-1,ai,.,an)(a1,.,ai-1,b,ai,.,an)图2.3 线性表插入前后的状况插入前n=8插入后n=9,线性表的删除操作,图2.4 线性表删除前后的状况删除前n=8删除后n=9,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,算法2.4 线性表中插入新的元素,Status ListInsert_Sq(SqList/ListInsert_Sq,算法2.5 线性表的删除操作,Status ListDelete_Sq(SqList/ListDelete_Sq,线性表的插入或删除,在顺序存储结构的线性表中插入或删除一个数据元素，平均约移动表中一半元素。,算法2.6 在顺序表查找元素,int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序 i=1;/i的初值为第1个元素的位序 p=L.elem;/p的初始值为第1个元素的存储位置 while(i=L.length/LocateElem Sq,算法2.7 顺序表的合并,Void MergeList_Sq(SqList La,SqList,SqList/MergeList_Sq,2.3 线性表的链式表示和实现,线性表的顺序存储结构：可以随机存取表中的任一元素。但是做插入或删除操作时，需要移动大量元素。因此，提出线性表的链式存储结构。,2.3.1 线性链表,存储单元可以是不连续的结点（Node）：它包括两个域其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。n个节点链结成一个链表，即为线性表(a1,a2,an)的链式存储结构。链表的每个结点中只包含一个指针域，故称为线性链表或单链表。头指针,图 2.5 线性链表示例,图2.6线性链表的逻辑状态,线性表的单链表存储结构,typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;,图2.7 带头结点的单链表,算法 2.8：函数GetElem在单链表中的实现,Status GetElem_L(LinkList L,int i,ElemType/GetElem_L时间复杂度为O(n),图2.8 在单链表中插入结点,s-next=p-next;p-next=s；,算法 2.9 单链表插入元素,Status ListInsert_L(LinkList/ListInsert_L,算法2.10 单链表删除元素,Status ListDelete_L(LinkList/ListDelete_L,算法2.11 逆位序建立单链表,void CreateList_L(LinkList/CreateList_L,算法2.12,void MergeList_L(LinkList/MergeList_L,线性表的静态单链表存储结构,#define MAXSIZE 1000typedef struct ElemType data;Int cur;component,SLinkListMAXSIZE;,图2.10 静态链表示例,(a)修改前的状态;(b)修改后的状态,算法 2.13 在静态单链表中查找第一个值为e的元素,int LocateElem_SL(SLinkList S,ElemType e)/在静态单链表中查找第一个值为e的元素 i=S0.cur;while(i/LocateElem_SL,例 2-3（略）,2.3.2 循环链表,循环链表 是另一种形式的链式存储结构.它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。图2.12 单循环链表(a)非空表;(b)空表。,图2.12 单循环链表,非空表,空表,图2.13 仅设尾指针的循环链表,两个链表,2.3.3 双向链表,双向链表 在双向链表的结点中有两个指针域,其中一指向直接后继,另一指向直接前趋。线性表的双向链表存储结构typedef struct DuLNode ElemType data;struct DuLNode*prior;Struct DuLNode*next;DuLNode,*DuLinkList;,图2.14 双向链表示例,(a)结点结构;(b)空的双向循环链表;(c)非空的双向循环链表。,prior,图2.15 在双向链表中删除结点时指针变化状况,图2.16 在双向链中插入一个结点时指针的变化状况,算法 2.18 双链循环线性表中插入元素e,Status ListInsert_DuL(DuLinkList/ListInsert_DuL,算法2.19 双链循环线性表中删除元,Status ListDelete_DuL(DuLinkList/ListDelete_DuL,一个带头结点的线性链表定义如下:typedef struct Lnode/结点类型 ElemType data;struct Lnode*next;*Link,*Position;typedef struct/链表类型 Link head,tail;/指向头结点和尾结点 int len;/链表中元素个数LinkList;,算法2.20 单链表插入元素,Status ListInsert_L(LinkList/ListInsert_L,算法2.21 合并非递减排列链表,Status MergeList_L(LinkList,第三章 栈和队列,3.1 栈3.1.1 抽象数据类型栈的定义栈（Stack）是限定仅在表尾进行的插入或删除操作的线性表。对栈来说，表尾端称为栈顶，表头端称为栈底假设栈S=（a1,a2,.,an）,则称a1为栈底元素，an为栈顶元素。栈的修改是按后进下出的原则进行的，因此栈又称为后进先出（Last In First Out）的线性表（简称LIFO结构）。,图3.1 栈,(a)栈的示意图(b)用铁路调度站表示栈,栈的抽象数据类型的定义,ADT Stack 数据对象：数据关系：基本操作：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTraverse(S,visit()ADT Stack,3.1.2栈的表示和实现,顺序栈，即栈的顺序存储结构是，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。顺序栈的定义：typedf struct SElemType*base;SElemType*top;int stacksize;SqStack;,图3.2 栈顶指针和战中元素之间的关系,栈的顺序存储表示,#definde STACK_INIT_SIZE 100;/存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量Typedef struct SElemType*base;SElemTYpe*top;int stacksize;SqStack;,基本操作的函数原型说明,Status InitStack(SqStack,基本操作的算法描述,Status InitStack(SqStack,用e返回S的栈顶元素,Status GetTop(SqStack S,SElemType,插入元素e为新的栈顶元素,Status Push(SqStack,删除栈顶元素e,Status Pop(SqStack,图3.3 链栈示意图,3.2 栈的运用举例,3.2.1数制转换N=(N div d)d+N mod d,3.2 栈的运用举例,void conversion()/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(S);scanf(“%d”,N);while(N)Push(S,N%8);N=N/8;While(!StackEmpty(s)Pop(S,e);printf(“%d”,e);/conversion,3.3 栈与递归的实现,例 3-2（n阶Hanoi塔问题）,3.4 队列,3.4.1 抽象数据类型队列的定义队列：是一种先进先出的的线性表,它只允许在表的一端进行插入,而在另一端删除元素。在队列中,允许插入的一端叫队尾,允许删除的一端则称为队头。,图3.8 队列的示意图,列队的抽象数据类型定义,ADT Queue 数据对象:D=ai|ai ElemSet,i=1,2,n,n0数据关系:R1=|ai-1,aiD,i=2,n基本操作:InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e)DeQueue(&Q,&e)QueueTraverse(Q,visit()ADT Queue,图3.9 双端队列示意图,双端队列：是限定插入和删除操作在表的两端进行的线性表。,图3.9 双端队列示意图,3.4.2 链队列队列的链式表示和实现,链队列:用链表表示的队列图 3.10 链队列示意图,图 3.11 队列运算指针变化状况,(a)空队列;(b)元x素入队列;(c)元素y入队列;(d)元素x出队列.,ADT Queue的表示与实现,/-单链队列队列的链式存储结构-typedef struct QNode QElemType data;Struct QNode*next;QNode,*QueuePtr;Typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针LinkQueue;,基本操作的函数原型说明,Status InitQueue(LinkQueue&Q)Status DestroyQueue(LinkQueue&Q)Status ClearQueue(LinkQueue&Q)Status QueueEmpty(LinkQueue&Q)int QueueLength(LinkQueue Q)Status GetHead(LinkQueue Q,QElemType&e)Status EnQueue(LinkQueue&Q,QElemType e)Status DeQueue(LinkQueue&Q,QElemType&e)Status QueueTraverse(LinkQueue Q,visit(),/-基本操作的算法描述（部分）-,Status initQueue(LinkQueue,销毁队列Q,Status Destroy(LinkQueue,插入元素e为Q的新的队尾元素,Status EnQueue(LinkQueue,删除队头元素并用e返回其值,Status DeQueue(LinkQueue,3.4.3 循环队列-队列的顺序表示和实现,图3.12 头、尾指针和队列中元素之间的关系(a)空队列;(b)J1、J2和J3相继入队列;(c)J1和J2相继被删除;(d)J4、J5和J6相继插入队列之后J3及J4被删除.,图3.13 循环队列示意图,图3.14 循环队列的头尾指针,(a)一般情况;(b)队列满时;(c)空队列.,循环队列类型的模块说明:,/-循环队列队列的顺序存储结构-#define MAXQSIZE 100typedef stuct QElemType*base;int front;int rear;SqQueue;,-循环队列的基本操作的算法描述,Status InitQueue(SqQueue,返回Q的元素个数,int QueueLength(SqQueue Q)Return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;,插入元素到队列尾,Status EnQueue(SqQueue,删除队列队头元素,Status DeQueue(SqQueue,