数据结构复习资料

结束第1页题型1选择题2填空题3解答题4算法题结束第2页结束第3页第一章绪论计算机的发展硬件CPU、内、外存储器等软件：系统软件、应用软件应用科学计算数据处理过程控制等处理数据的能力和种类：数值字符、字符串具有多个属性对象图形图像声音结束第4页数据结构的研究对象：非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。本课程讨论的问题：应用中常用的几种数据结构，以及如何存储,如何处理它们。第一章绪论结束第5页1数据：客观对象的符号表示。例如：课程名，地名，书名都是数据2数据结构：带有结构和操作的数据元素集合结构：数据元素之间的关系；操作：对数据的加工处理；第一章绪论结束第6页第一章绪论3数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。4常用的有下列几类基本结构：（1）集合（2）线性结构（3）树结构（4）图结构（5）其它复杂结构5数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理；结束第7页第一章绪论6数据的存储结构：数据结构在计算机内存中的表示。7顺序存储结构用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系；8链式存储结构用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。数据结构基本操作的实现：基本操作在计算机上的实现（方法）结束第8页9数据结构的表示1图示表示2二元组表示图示表示：由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；第一章绪论JIHGFEDBAC结束第9页二元组表示用一个二元组（D，S）表示数据结构，其中D是数据元素集合，S是D上关系的集合。D={A，B，C，D，E，F，G，H，I，J}S={R}R={〈A,B,B,C,C,DD,E,E,F,F,G,G,H,H,I,I,J}第一章绪论结束第10页第一章绪论10算法的概念算法是求解问题的操作序列（或操作步骤）11时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法的时间度量空间复杂度用执行算法所需的辅助空间的大小作为算法所需空间的度量结束第11页第一章练习题1数据结构：带有结构和操作的数据元素集合。2常用的数据结构3数据结构的表示4数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。5数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理；6数据的存储结构：数据结构在计算机内存中的表示7数据结构基本操作的实现：基本操作在计算机上的实现（方法）8顺序存储结构9链式存储结构10算法的概念算法是求解问题的操作序列（或操作步骤）。11时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法时间的度量结束第12页结束第13页常用的数据结构1）集合2）线性结构3）树结构4）图结构5）其它复杂结构第二章线性表对每种数据结构，主要讨论如下两方面的问题1数据的逻辑结构，数据结构的基本操作；2数据的存储结构，数据结构基本操作的实现结束第14页第二章线性表线性数据结构：除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。结束第15页2.1线性表的概念一线性表的逻辑结构在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。2.1线性表的概念a1a2ai-1aiai+1an结束第16页二线性表的基本操作1初始化操作InitList(&L)2销毁操作DetroyList(&L)3置空操作ClearList(&L)4判空操作ListEmpty(L)5求表长操作ListLength(L)6取元素操作：GetElem(L,i,&e)7查找操作LocateElem(L,e,compare())8插入操作ListInsert(&L,i,e)9删除操作ListDelete(&L,i,&e)10遍历操作ListTraverse(&L,visit())2.1线性表的概念结束第17页2.2线性表的顺序存储和实现一线性表的顺序存储结构——顺序表1顺序表用一组连续的内存单元依次存放线性表的数据元素。2顺序表的类型定义typedefstruct{ElemType*elem;//线性表存储空间基址intlength;//当前线性表长度intlistsize;//当前分配的存储空间大小}SqList;结束第18页顺序表图示设A=（a1,a2,a3,...an）是一线性表，L是SqList类型的结构变量，用于存放A2.2线性表的顺序存储和实现L.elemL.lenghtL.listsizen99a1a2ai-1aiai+1an01i-2i-1in-199顺序表保存了哪些信息?结束第19页2.2线性表的顺序存储和实现顺序表保存了哪些信息？*线性表中的数据元素；*线性表中数据元素的顺序关系；*表中元素个数（简化算法）*当前分配的存储空间顺序表如何保存这些信息？3顺序表存储特点元素存储在一组连续的内存单元中；通过元素存储顺序元素之的逻辑顺序；结束第20页二顺序表的基本操作算法1初始化算法InitList_Sq(SqList&L)2插入操作算法ListInsert_Sq(SqList&L,inti,ElemTypee)3删除操作算法ListDelete_Sq(SqList&L,inti,ElemType&e)2.2线性表的顺序存储和实现结束第21页2.2线性表的顺序存储和实现5顺序表主要操作特点1）可随机存取顺序表的元素(用L.elem[i-1]或L.elem+(i-1)可直接定位元素的存储地址)2）插入删除操作通过移动元素实现结束第22页2．3线性表的链式存储结构和实现线性表的链式存储结构用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。结束第23页2.3.1线性链表一线性链表的概念1线性链表用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。2．3线性表的链式存储结构和实现结束第24页typedefstructLnode{ElemTypedata;StructLnode*next;}LNode,*LinkList;数据域指针域datanextL2线性链表的结点类型定义及指向结点的指针类型定义2.3.1线性链表ai-1aia1an结束第25页2.3.1线性链表3线性链表存储特点1）用一组任意的存储单元存储线性表中的数据元素；2）通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；结束第26页二线性链表基本操作算法1初始化操作算法InitList_L(LinkList&L)2插入操作算法ListInsert_L(LinkList&L,inti,ElemTypee)3删除操作算法ListInsert_L(LinkList&L,inti,ElemType&e)2.3.1线性链表结束第27页2.3.1线性链表5线性链表操作主要特点1）不能随机存取元素；2）插入、删除操作通过修改结点的指针实现；结束第28页循环链表循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点aia1ai+1ai-1anaiai+1ai-1anL2.3.2循环链表结束第29页双向链表双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。2.3.3双向链表Laia1ai-1an结束第30页线性表的其他操作的实现1)通过调用基本操作算法2)直接实现线性表的其他操作的实现结束第31页第二章练习题；１线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。２顺序表存储特点：1）元素存储在一组连续的内存单元中2）通过元素的存储顺序反映线性表中数据元素之的逻辑顺序；３顺序表操作特点：1）可随机存取顺序表的元素；2）顺序表的插入删除操作要通过移动元素实现结束第32页第二章练习题４线性链表存储特点1）用任意一组的存储单元存储线性表中的数据元素；2）通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；５线性链表操作特点1）不能随机存取元素；2）插入、删除操作通过修改结点的指针实现；６顺序表的插入、删除操作平均要移动表的一半元素结束第33页第二章练习题７顺序表能随机存取元素的原因是：顺序表能通过L.elem[i-1]或L.elem+(i-1)直接定位元素的存储地址。８线性链表不能随机存取元素的原因是：需从线性链表的头指针开始，顺着链指针定位元素的存储地址９对于经常要存取元素的应用，线性表应采用顺序存储结构10对于经常要插入删除元素的应用，线性表应采用链式存储结构结束第34页结束第35页栈是限定仅能在表尾进行插入删除操作的线性表。（a1,a2...ai-1,ai,ai+1,…,an）栈底栈顶插入删除栈的特点后进先出3.1栈一.栈的概念1栈的定义结束第36页3.1栈2栈的基本操作1）初始化操作InitStack((&S)2）销毁栈操作DestroyStack(&S)3）置空栈操作ClearStack(&S)4）取栈顶元素操作GetTop(S,&e)5）进栈操作Push(&S,e)6）退栈操作Pop(&S,&e）7）判空操作StackEmpty(S)结束第37页3.1栈二栈的顺序存储和实现1栈的顺序存储结构1）用一组连续的内存单元依次存放自栈底到栈顶的数据元素；2）栈顶元素的位置由栈顶指针指示；结束第38页typedefstruct{SElemType*base;//栈底指针SElemType*top//栈顶指针intstacksize;//当前分配的栈空间大小//(以sizeof(SElemType)为单位）}SqStack;3.1栈2顺序栈的类型定义结束第39页3.1栈S.stacksizeS.topS.base9999nn-1n-210anan-1a2a1顺序栈的图示结束第40页3栈操作算法1）进栈操作算法：在栈顶插入元素Push(SqStack&S,SElemTypee)2）出栈操作算法：在栈顶插入元素Pop(SqStack&S,SElemType&e)4栈操作主要特点进栈、出栈操作要修改栈顶指针3.1栈结束第41页3.1栈三栈的链式存储和实现栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头指针ai+1aiana1S结束第42页四栈的应用举例例2表达式求值算符优先算法：掌握利用操作数栈OPND，运算符栈OPTR，对表达式求值的方法3.2栈结束第43页第三章练习题１栈是限定仅能在表尾一端进行插入、删除操作的线性表；2表尾称为栈顶，表头称为栈底；3栈的具有后进先出的特点；4栈顶元素的位置由一个栈顶指针指示；5进栈、出栈操作要修改栈顶指针；6一个栈的输入序列为a,b,c，则所有可能的出栈序列为：abc,acb,bac,bca,cba结束第44页一队列的概念１队列的定义队列是限定仅能在表头删除，表尾插入的线性表。入队a1a2an队头队尾出队队列的特点先进先出3．4队列结束第45页2队列的基本操作1）初始化操作InitQueue(&Q)2）销毁操作DestroyQueue(&Q)3）置空操作ClearQueue(&Q)4）判空操作QueueEmpty(Q)5）取队头元素操作GetHead(Q,&e)6）入队操作EnQueue(&Q,e)7）出队操作DeQueue(&Q,&e)3．4队列结束第46页二循环队列——队列的顺序存储和实现1循环队列——队列的顺序存贮结构（1）在队列的顺序存贮结构中用一组连续存储单元依次存储队列的数据元素（2）队头、队尾元素的位置分别由队头指针和队尾指针指示；（3）将顺序队列设想为首尾相连的环状空间3．4队列结束第47页2循环队列的类型定义#defineMAXSIZE100//最大队列长度typedefstruct{QElemType*base;队空间基址intfront;//队头指针intrear;//队尾指针}SqQu