数据结构总复习ppt课件.ppt

《数据结构总复习ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构总复习ppt课件.ppt（147页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数数 据据 结结 构构西南民院计算机系西南民院计算机系 TEL TEL 1361809782613618097826EmEmailliu-li-ailliu-li- 结束第 2 页题型题型1 1 选择题选择题 2 2 填空题填空题 3 3 解答题解答题 4 4 算法题算法题 结束第 3 页结束第 4 页第一章第一章绪绪论论计算机的发展计算机的发展硬件硬件 CPUCPU、内、外存储器等内、外存储器等软件软件：系统软件、应用软件：系统软件、应用软件应用应用 科学计算科学计算 数据处理数据处理 过程控制等过程控制等处理数据的能力和种类处理数据的能力和种类：数值：数值 字符、字符串字符、字符串 具有多

2、个属性对象具有多个属性对象 图形图形 图像图像 声音声音 结束第 5 页数据结构数据结构的研究对象的研究对象：非数值数据之间的结构关系，如何表示，非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。如何存储，如何处理的问题。本课程讨论的问题：本课程讨论的问题：应用中常用的几种数据结构，以及如何存储应用中常用的几种数据结构，以及如何存储,如何处理它们。如何处理它们。第一章第一章绪绪论论结束第 6 页1 1 数据数据：客观对象的：客观对象的符号表示符号表示。例如：课程名，地名，书名都是数据例如：课程名，地名，书名都是数据2 2 数据结构：数据结构：带有带有结构和操作结构和操作的数据元素集

3、合的数据元素集合 结构：数据元素之间的关系；结构：数据元素之间的关系；操作：对数据的加工处理操作：对数据的加工处理 ；第一章第一章绪绪论论结束第 7 页第一章第一章绪绪论论3 3 数据的逻辑结构数据的逻辑结构 ：数据之间的：数据之间的结构关系结构关系，是，是具体关系的抽象。具体关系的抽象。4 4 常用的有下列几类基本结构：常用的有下列几类基本结构：（1 1）集合）集合 （2 2）线性结构）线性结构 （3 3）树结构）树结构 （4 4）图结构）图结构 （5 5）其它复杂结构）其它复杂结构5 5 数据结构的基本操作：数据结构的基本操作：也叫基本运算：是指对也叫基本运算：是指对数据结构的加工处理；数

4、据结构的加工处理；结束第 8 页第一章第一章绪绪论论6 6 数据的存储结构：数据的存储结构：数据结构在计算机数据结构在计算机内存中的表示内存中的表示。7 7 顺序顺序存储结构存储结构 用一组用一组连续的内存单元连续的内存单元存放数据元素，用元存放数据元素，用元素素相对的存储位置相对的存储位置表示元素之间的结构关系；表示元素之间的结构关系；8 8 链式存储结构链式存储结构 用用任意一组存储单元任意一组存储单元存储数据元素，对每个存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素数据元素除了保存自身信息外，还保存相关元素的的存储位置存储位置。数据结构基本操作的实现：数据结构基本操作的实

5、现：基本操作在计算机基本操作在计算机上的实现（方法）上的实现（方法）结束第 9 页9 9 数据结构的表示数据结构的表示 1 1 图示表示图示表示 2 2 二元组表示二元组表示图示表示：由顶点和边构成的图，其中图示表示：由顶点和边构成的图，其中顶点顶点表示表示数据数据 ，边边表示数据之间的结构关系；表示数据之间的结构关系；第一章第一章绪绪论论J JI IH HG GF FE ED DB BA AC C结束第 10 页二元组表示二元组表示 用一个二元组（用一个二元组（D D，S S）表示数据结构，其中表示数据结构，其中 D D 是数据元素集合，是数据元素集合，S S 是是 D D 上关系的集合。上

6、关系的集合。D=AD=A，B B，C C，D D，E E，F F，G G，H H，I I，JJ S=R S=R R=R=A,B,A,B,第一章第一章绪绪论论结束第 11 页第一章第一章绪绪论论10 10 算法的概念算法的概念 算法是求解问题的操作序列（或操作步骤）算法是求解问题的操作序列（或操作步骤）11 11 时间复杂度时间复杂度T T（n n）以求解问题的基本操作（原操作）的执行次以求解问题的基本操作（原操作）的执行次数作为算法的时间度量数作为算法的时间度量 空间复杂度空间复杂度用执行算法所需的辅助空间的大小作为算法所需用执行算法所需的辅助空间的大小作为算法所需空间的度量空间的度量结束第

7、12 页第一章练习题第一章练习题1数据结构：带有结构和操作的数据元素集合。2 2 常用的数据结构常用的数据结构3 3数据结构的表示数据结构的表示4 数据的逻辑结构 ：数据之间的结构关系，是具体关系的抽象。5数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理；6数据的存储结构：数据结构在计算机内存中的表示7数据结构基本操作的实现：基本操作在计算机上的实现（方法）8顺序存储结构9链式存储结构10 算法的概念 算法是求解问题的操作序列（或操作步骤）。11 时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法时间的度量结束第 13 页结束第 14 页 常用的数据结构常用的数据结构

8、 1 1）集合集合 2 2）线性结构线性结构 3 3）树结构树结构 4 4）图结构图结构 5 5）其它复杂结构其它复杂结构第二章线性表第二章线性表对每种数据结构，主要讨论如下两方面的问题对每种数据结构，主要讨论如下两方面的问题1 1 数据的逻辑结构，数据结构的基本操作；数据的逻辑结构，数据结构的基本操作；2 2 数据的存储结构，数据结构基本操作的实现数据的存储结构，数据结构基本操作的实现 结束第 15 页 第二章线性表第二章线性表线性数据结构：线性数据结构：除第一个元素和最后一个元素之外，其他除第一个元素和最后一个元素之外，其他元素都有且仅有一个元素都有且仅有一个直接前趋直接前趋，有且仅有一个

9、，有且仅有一个直直接后继。接后继。结束第 16 页 2.1 2.1 线性表的概念线性表的概念 一一 线性表的逻辑结构线性表的逻辑结构在线性表中，除第一个元素和最后一个元素之外，在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个其他元素都有且仅有一个直接前趋直接前趋，有且仅有一，有且仅有一个个直接后继。直接后继。2.1 2.1 线性表的概念线性表的概念 a a1 1 a a2 2a ai i-1 a ai ia ai i+1 a an n结束第 17 页二二线性表的基本操作线性表的基本操作三三1 1 初始化操作初始化操作 InitListInitList(&L)(&L)2 2 销

10、毁操作销毁操作DetroyListDetroyList(&L)(&L)3 3 置空操作置空操作ClearListClearList(&L)(&L)4 4 判空操作判空操作ListEmptyListEmpty(L)(L)5 5 求表长操作求表长操作 ListLengthListLength(L)(L)6 6 取元素操作：取元素操作：GetElemGetElem(L,i,&e)(L,i,&e)7 7 查找操作查找操作 LocateElemLocateElem(L,e,compare()(L,e,compare()8 8 插入操作插入操作 ListInsertListInsert(&L,i,e)(&

11、L,i,e)9 9 删除操作删除操作 ListDeleteListDelete(&L,i,&e)(&L,i,&e)10 10 遍历操作遍历操作 ListTraverseListTraverse(&L,visit()(&L,visit()2.1 2.1 线性表的概念线性表的概念结束第 18 页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现一一 线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表1 1 顺序表顺序表用一组连续的内存单元依次存放线性用一组连续的内存单元依次存放线性表的数据元素表的数据元素。2顺序表的类型定义顺序表的类型定义typedef structtypedef s

12、truct ElemType ElemType *elemelem;/;/线性表存储空间基址线性表存储空间基址 int int length;/length;/当前线性表长度当前线性表长度 int listsizeint listsize;/;/当前分配的存储空间大小当前分配的存储空间大小 SqListSqList;结束第 19 页顺序表图示顺序表图示设设 A=A=（a a1 1,a,a2 2,a,a3 3,.a,.an n ）是一线性表，是一线性表，L L是是SqList SqList 类型的结构变量，用于存放类型的结构变量，用于存放 A A2.2 2.2 线性表的顺序存储和实现线性表的顺序

13、存储和实现L.L.elemelemL.L.lenghtlenghtL.L.listsizelistsizen n9999 a a1 1 a a2 2a ai i-1-1 a ai ia ai i+1+1 a an n0 01 1i-2i-2i-1i-1i in-1n-19999 顺序表保存了哪些信息?结束第 20 页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺顺序表序表保存了哪些信息？保存了哪些信息？*线性表中的数据元素；线性表中的数据元素；*线性表中数据元素的顺序关系；线性表中数据元素的顺序关系；*表中元素个数（简化算法）表中元素个数（简化算法）*当前分配的存储空间当前分

14、配的存储空间 顺顺序表序表如何保存这些信息？如何保存这些信息？3 3 顺序表存储特点顺序表存储特点元素存储在元素存储在一组连续的内存单元中；一组连续的内存单元中；通过元素通过元素存储顺序存储顺序元素之的逻辑顺序；元素之的逻辑顺序；结束第 21 页二二 顺序表的基本操作算法顺序表的基本操作算法1 1 初始化算法初始化算法 InitListInitList_Sq(_Sq(SqListSqList&L)&L)2 2 插入插入操作操作算法算法 ListInsert ListInsert_Sq(_Sq(SqListSqList&L,&L,intint i,i,ElemTypeElemType e)e)3

15、 3 删除删除操作操作算法算法 ListDeleteListDelete_Sq(_Sq(SqListSqList&L,&L,intiinti,ElemTypeElemType&e)&e)2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现结束第 22 页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现5 5 顺序表顺序表主要操作特点操作特点1 1）可随机存取顺序表的元素）可随机存取顺序表的元素(用用L.L.elemelemi-1i-1或或L.L.elemelem+(i-1)+(i-1)可可直直接接定定位位元元素素的存储地址的存储地址)2 2）插入删除操作通过移动元素实现）插

16、入删除操作通过移动元素实现结束第 23 页2 23 3 线性表的链式存储结构和实现线性表的链式存储结构和实现线性表的链式存储结构线性表的链式存储结构用一组任意的存储单元存储线性表中的数据元素，用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。相关元素的存储位置。结束第 24 页2.3.1 .3.1 线性链表线性链表一一 线性链表的概念线性链表的概念1 1 线性链表线性链表用一组任意的存储单元存储线性表中用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自的数据元素，对每个数据元素除

17、了保存自身信息外，还保存了直接后继元素的存储身信息外，还保存了直接后继元素的存储位置。位置。2 23 3 线性表的链式存储结构和实现线性表的链式存储结构和实现结束第 25 页typedefstructLnodeElemTypedata;StructLnode*next;LNode,*LinkList;数据域数据域指针域指针域 data next L L2 2 线性链表的结点类型定义线性链表的结点类型定义 及指向结点的指针类型定义及指向结点的指针类型定义2.3.1线性链表线性链表ai-1aia1an结束第 26 页2.3.1线性链表线性链表3 3 线性链表存储特点线性链表存储特点1 1）用用一一

18、组组任任意意的的存存储储单单元元存存储储线线性性表表中中的的数数据据元素；元素；2 2）通通过过保保存存直直接接后后继继元元素素的的存存储储位位置置来来表表示示数数据元素之间的逻辑关系；据元素之间的逻辑关系；结束第 27 页 二二 线性链表基本操作算法线性链表基本操作算法1 1 初始化操作初始化操作算法算法InitListInitList_L(_L(LinkListLinkList&L)&L)2 2 插入操作插入操作算法算法ListInsertListInsert_L(_L(LinkListLinkList&L,&L,intiinti,ElemTypeElemType e)e)3 3 删除操作

19、算法删除操作算法ListInsertListInsert_L(_L(LinkListLinkList&L,&L,intiinti,ElemTypeElemType&e)&e)2.3.1线性链表线性链表结束第 28 页2.3.1线性链表线性链表5 5 线性链表操作主要特点线性链表操作主要特点1 1）不能随机存取元素；）不能随机存取元素；2 2）插入、删除操作通过修改结点的指针实现；）插入、删除操作通过修改结点的指针实现；结束第 29 页 循环链表循环链表 循环链表的特点是将线性链表的最后一个结循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点点的指针指向链表的第一个结点 aia1

20、ai+1ai-1anaiai+1ai-1anL L2.3.2 2.3.2 循环链表循环链表结束第 30 页 双向链表双向链表双向链表中，每个结点有两个指针域，一个双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元指向直接后继元素结点，另一个指向直接前趋元素结点。素结点。2.3.3 2.3.3 双向链表双向链表L Lai ia1 1a ai i-1 1an n结束第 31 页 线性表的其他操作的实现线性表的其他操作的实现1)1)通过调用基本操作算法通过调用基本操作算法2)2)直接实现直接实现线性表的其他操作的实现线性表的其他操作的实现结束第 32 页第二章练习题第二

21、章练习题；线性表的逻辑结构：在线性表中，除第一个元线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都素和最后一个元素外，其他元素都有且仅有一有且仅有一个个直接前趋，直接前趋，有且仅有一个有且仅有一个直接后继。直接后继。顺序表存储特点：顺序表存储特点：1 1）元素存储在）元素存储在一组连续一组连续的内存单元中的内存单元中2 2）通过元素的）通过元素的存储顺序存储顺序反映线性表中数据元素反映线性表中数据元素之的逻辑顺序；之的逻辑顺序；顺序表操作特点：顺序表操作特点：1 1）可随机存取可随机存取顺序表的元素；顺序表的元素；2 2）顺序表的插入删除操作要通过）顺序表的插入删除操作要

22、通过移动元素移动元素实现实现 结束第 33 页第二章练习题第二章练习题线性链表存储特点线性链表存储特点1 1）用用任意一组任意一组的存储单元存储线性表中的数据的存储单元存储线性表中的数据元素；元素；2）通过保存通过保存直接后继元素的存储位置直接后继元素的存储位置来表示数来表示数据元素之间的逻辑关系；据元素之间的逻辑关系；线性链表操作特点线性链表操作特点1 1）不能随机不能随机存取元素；存取元素；2 2）插入、删除操作通过）插入、删除操作通过修改结点的指针修改结点的指针实现；实现；顺序表的插入、删除操作平均要移动表的顺序表的插入、删除操作平均要移动表的一半一半元素元素 结束第 34 页第二章练习

23、题第二章练习题顺序表能随机存取元素的原因是：顺序表能通顺序表能随机存取元素的原因是：顺序表能通过过L.L.elemelemi-1i-1或或L.L.elemelem+(i-1)+(i-1)直接直接定位元素的定位元素的存储地址。存储地址。线性链表不能随机存取元素的原因是：线性链表不能随机存取元素的原因是：需从需从线性链表的线性链表的头指针开始，顺着链指针头指针开始，顺着链指针定位元素的定位元素的存储地址存储地址对于经常要存取元素的应用对于经常要存取元素的应用，线性表应采用线性表应采用顺顺序序存储结构存储结构10 10 对于经常要插入删除元素的应用，线性表应对于经常要插入删除元素的应用，线性表应采用

24、采用链式链式存储结构存储结构结束第 35 页结束第 36 页栈是限定仅能在表尾进行插入删除操作的线栈是限定仅能在表尾进行插入删除操作的线性表。性表。（a a1 1,a,a2 2.a ai i-1-1,a ai i,a ai i+1+1,a,an n ）栈栈底底栈栈顶顶插入插入删除删除栈的特点栈的特点后进先出后进先出3.1 3.1 栈栈一一.栈的概念栈的概念1 1 栈的定义栈的定义结束第 37 页3.1 3.1 栈栈2 2 栈的基本操作栈的基本操作 1 1）初始化操作初始化操作InitStackInitStack(&S)(&S)2 2）销毁栈操作销毁栈操作DestroyStackDestroyS

25、tack(&S)(&S)3 3）置空栈操作）置空栈操作ClearStackClearStack(&S)(&S)4 4）取栈顶元素操作）取栈顶元素操作GetTopGetTop(S,&e)(S,&e)5 5）进栈操作进栈操作Push(&S,e)Push(&S,e)6 6）退栈操作退栈操作Pop(&S,&ePop(&S,&e）7 7）判空操作）判空操作StackEmptyStackEmpty(S)(S)结束第 38 页3.1 3.1 栈栈二二 栈的顺序存储和实现栈的顺序存储和实现1 1 栈的顺序存储结构栈的顺序存储结构 1 1）用一组连续的内存单元依次存放自栈底用一组连续的内存单元依次存放自栈底到栈

26、顶的数据元素；到栈顶的数据元素；2 2）栈顶元素的位置由栈顶指针指示；栈顶元素的位置由栈顶指针指示；结束第 39 页typedef structtypedef struct SElemType SElemType *base;/*base;/栈底指针SElemType SElemType *top /*top /栈顶指针栈顶指针int stacksizeint stacksize;/;/当前分配的栈空间大小当前分配的栈空间大小 /(/(以以sizeofsizeof(SElemTypeSElemType)为单位）为单位）SqStackSqStack;3.1 3.1 栈栈 2 2 顺序栈的类型定义

27、顺序栈的类型定义结束第 40 页3.1 3.1 栈栈S.S.stacksizestacksizeS.topS.topS.baseS.base99999999n nn-1n-1n-2n-21 10 0 a an n a an-1n-1a a2 2a a1 1 顺序栈的图示顺序栈的图示结束第 41 页3栈操作算法栈操作算法4 41 1）进栈操作）进栈操作算法算法：在栈顶插入元素：在栈顶插入元素 Push(Push(SqStackSqStack&S,&S,SElemTypeSElemType e)e)2 2）出栈操作）出栈操作算法算法：在栈顶插入元素：在栈顶插入元素 Pop(Pop(SqStackS

28、qStack&S,&S,SElemTypeSElemType&e)&e)4 4 栈操作主要特点栈操作主要特点进栈、出栈操作要修改进栈、出栈操作要修改栈顶指针栈顶指针3.1 3.1 栈栈结束第 42 页3.1 3.1 栈栈三三栈的链式存储和实现栈的链式存储和实现四四 栈的链式存储与线性表的链式存储类似，栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头注意：栈顶指针就是带头结点的线性链表的头指针指针ai+1aiana1S S结束第 43 页四四 栈的应用举例栈的应用举例例例2 2 表达式求值表达式求值算符优先算法：

29、掌握利用算符优先算法：掌握利用操作数栈操作数栈OPNDOPND ，运，运算符栈算符栈OPTROPTR，对，对表达式求值的方法表达式求值的方法3.2栈栈结束第 44 页第三章练习题第三章练习题栈是限定栈是限定仅能在表尾一端仅能在表尾一端进行插入、删除操进行插入、删除操作的线性表；作的线性表；2 2 表尾称为表尾称为栈顶栈顶，表头称为，表头称为栈底栈底；3 3 栈的具有栈的具有后进先出后进先出的特点；的特点；4 4 栈顶元素的位置栈顶元素的位置由一个栈顶指针指示由一个栈顶指针指示；5 5 进栈、出栈操作要修改进栈、出栈操作要修改栈顶指针栈顶指针；6 6 一个栈的输入序列为一个栈的输入序列为a,b,

30、ca,b,c，则所有可能的出则所有可能的出栈序列为：栈序列为：abcabc,acbacb,bacbac,bcabca,cbacba结束第 45 页一一 队列的概念队列的概念 队列的定义队列的定义 队列是限定仅能在表头删除，表尾插入的队列是限定仅能在表头删除，表尾插入的线性表。线性表。入队入队 a a1 1 a a2 2 a an n队队头头队队尾尾出队出队队列的特点队列的特点先进先出先进先出3 34 4 队列队列结束第 46 页2 2 队列的基本操作队列的基本操作1 1）初始化操作）初始化操作InitQueueInitQueue(&Q)(&Q)2 2）销毁操作销毁操作DestroyQueueD

31、estroyQueue(&Q)(&Q)3 3）置空操作置空操作ClearQueueClearQueue(&Q)(&Q)4 4）判空操作）判空操作QueueEmptyQueueEmpty(Q)(Q)5 5）取队头元素操作取队头元素操作GetHeadGetHead(Q,&e)(Q,&e)6 6）入队操作入队操作EnQueueEnQueue(&Q,e)(&Q,e)7 7）出队操作）出队操作DeQueueDeQueue(&Q,&e)(&Q,&e)3 34 4 队列队列结束第 47 页二二 循环队列循环队列队列的顺序存储和实现队列的顺序存储和实现1 1循环队列循环队列队列的顺序存贮结构队列的顺序存贮结构

32、2 2（1 1）在队列的顺序存贮结构中用一组连续存在队列的顺序存贮结构中用一组连续存储单元依次存储队列的数据元素储单元依次存储队列的数据元素3 3（2 2）队头、队尾元素的位置分别由队头指针队头、队尾元素的位置分别由队头指针和队尾指针指示；和队尾指针指示；4 4（3 3）将顺序队列设想为首尾相连的环状空间）将顺序队列设想为首尾相连的环状空间3 34 4 队列队列结束第 48 页 2 2 循环队列的类型定义循环队列的类型定义#define MAXSIZE 100 /define MAXSIZE 100 /最大队列长度最大队列长度typedef structtypedef struct QElem

33、Type QElemType *base;*base;队空间基址队空间基址 intint front;/front;/队头指针队头指针 intint rear;/rear;/队尾指针队尾指针 SqQueueSqQueue;3 34 4 队列队列结束第 49 页3 34 4 队列队列2 2 队列操作算法队列操作算法入队操作：在队尾插入元素；入队操作：在队尾插入元素；出队操作：在队头删除元素；出队操作：在队头删除元素；Q.baseQ.baseQ.frontQ.frontQ.rearQ.rear0 03 30 01 14 43 32 25 5J3J3J2J2J1J1结束第 50 页第三章练习题第三章

34、练习题队列是限定队列是限定仅能在表尾一端仅能在表尾一端插入，插入，表头一端表头一端删删除操作的线性表；除操作的线性表；2 2 表尾称为表尾称为队头队头，表头称为，表头称为队尾队尾 3 3 队头、队尾元素的位置分别由队头、队尾元素的位置分别由队头指针和队尾队头指针和队尾指针指示；指针指示；4 4 队列具有队列具有先进先出先进先出的特点的特点5 5 入队操作要修改入队操作要修改队尾指针队尾指针，出队操作要修改，出队操作要修改队队头指针；头指针；结束第 51 页结束第 52 页4.1 4.1 串的基本概念串的基本概念一、串的概念一、串的概念1 1 什么是串什么是串 串是由零个或多个字符组成的有限序列

35、，串是由零个或多个字符组成的有限序列，一般记作一般记作 s=a1,a2,a3,.ans=a1,a2,a3,.an结束第 53 页4.1 4.1 串的基本概念串的基本概念2 2 串的基本操作串的基本操作（了解）（了解）串的逻辑结构与线性表一样，都是线性结串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。操作与线性表有很大差别。串连接操作串连接操作 ConcatConcat(&T,S1,S2)(&T,S1,S2)求子串操作求子串操作SubStringSubString(&Sub,S,pos,(&Sub,S,p

36、os,lenlen)求子串位置操作求子串位置操作Index(S,T,pos)Index(S,T,pos)串插入操作串插入操作 StrInsertStrInsert(&S,pos,T)(&S,pos,T)串删除操作串删除操作 StrDeleteStrDelete(&S,pos,(&S,pos,lenlen)结束第 54 页4.2 4.2 串存储和实现串存储和实现一、串的存储一、串的存储（了解）（了解）1 1 定长顺序存储结构定长顺序存储结构 定长顺序存储结构类似于定长顺序存储结构类似于C C语言的字符数组，语言的字符数组，以一组地址连续的存储单元存放串值字符序列，以一组地址连续的存储单元存放串值

37、字符序列，其类型说明如下：其类型说明如下：#define MAXSTRLEN 255define MAXSTRLEN 255TypedefTypedef unsigned char unsigned char SStringSStringMAXSTRLEN+1MAXSTRLEN+1 结束第 55 页4.2 4.2 串存储和实现串存储和实现2 2、堆分配存储、堆分配存储堆分配存储类似于线性表的顺序存储结构堆分配存储类似于线性表的顺序存储结构 堆分配存储的类型说明堆分配存储的类型说明Typedef struct Typedef struct char*char*chch;/;/指向存放串值的存储空

38、间基址指向存放串值的存储空间基址 int int length;/length;/整型域：存放串长整型域：存放串长 HstringHstring;结束第 56 页第四章练习题第四章练习题从逻辑结构上看串是从逻辑结构上看串是线性数据结构线性数据结构；S=S=ababcabcacababcabcac,S1=,S1=abcabc，S2=S2=isastringisastringConcatConcat(HstringHstring&T,&T,HstringHstring S1,S1,Hstring Hstring S2)S2)T=T=abcisastringabcisastring 3 3 请列举两

39、个线性表所没有的串操作请列举两个线性表所没有的串操作:求子串求子串,求求子串位置子串位置，结束第 57 页结束第 58 页5 51 1 数数 组组1 1 数组的逻辑结构数组的逻辑结构 n n 维数组中的每个元素都受维数组中的每个元素都受n n个线性关系的约个线性关系的约束，束，以二维数组为例：二维数组中的每个元素以二维数组为例：二维数组中的每个元素都受两个线性关系的约束都受两个线性关系的约束 结束第 59 页5 51 1 数数 组组2 2 数组的基本操作数组的基本操作（了解）（了解）1初始化操作 InitArray(&A,n,bound1,boundn)功能：参数合法，构造数组A，并返回OK；

40、2销毁操作 DestroyArray(&A)功能：销毁数组A；3 读元素操作读元素操作 Value(A,&e,index1,indexn)功能：若指定下标不越界，读指定下标的元素，用e返回，并返回OK；4 4写元素操作写元素操作 Assign(A,e,index1,indexn)功能：若指定下标不越界，将e赋值给A指定的下标元素，并返回OK；结束第 60 页5 51 1 数数 组组3 3 数组的顺序存贮结构数组的顺序存贮结构(以二维数组为例以二维数组为例)两种方式：以行为主序的方式，两种方式：以行为主序的方式，以列序为主序的方式以列序为主序的方式4数组元素存储地址的计算数组元素存储地址的计算结

41、束第 61 页第五章练习题第五章练习题1 1 从逻辑结构来看，二维数组中的每个元素都受从逻辑结构来看，二维数组中的每个元素都受两个线性关系两个线性关系的约束的约束在行关系中在行关系中 a aijij直接前趋是直接前趋是 a aijij-1-1，a aijij直接直接后继是后继是 a aijij+1+1 ；在列关系中在列关系中 a aijij直接前趋是直接前趋是 a ai i-1j-1j a aijij直接后直接后继是继是 a ai i+1j+1j ；二维数组的两种顺序存贮结构为：二维数组的两种顺序存贮结构为：）以）以行为主序行为主序的方式，的方式，）以以列序为主列序为主序的方式。序的方式。数组

42、元素存储地址的计算数组元素存储地址的计算 结束第 62 页5 52 2 矩阵的压缩存储矩阵的压缩存储 矩阵压缩存储是指为矩阵压缩存储是指为多个值相同的元素分配多个值相同的元素分配一一个存储空间，对个存储空间，对零元素零元素不分配存储空间不分配存储空间一一 特殊矩阵特殊矩阵1 1 什么是特殊矩阵什么是特殊矩阵 值值相相同同元元素素或或者者零零元元素素分分布布有有一一定定规规律律的的矩矩阵阵称为特殊矩阵称为特殊矩阵2 2 特殊矩阵压缩存储特殊矩阵压缩存储 特特殊殊矩矩阵阵的的压压缩缩存存储储是是根根据据元元素素的的分分布布规规律律，确确定定元元素素的的存存储储位位置置与与元元素素在在矩矩阵阵中中的

43、的位位置置的的对对应关系；应关系；结束第 63 页5 52 2 矩阵的压缩存储矩阵的压缩存储二二 稀疏矩阵稀疏矩阵 1 1 什么是稀疏矩阵什么是稀疏矩阵 有有较较多多值值相相同同元元素素或或较较多多零零元元素素，且且值值相相同同元元素素或或者者零零元元素素分分布布没没有有一一定定规规律律的的矩矩阵阵称称为为稀稀疏疏矩阵。矩阵。2 2 稀稀疏疏矩矩阵阵的的压压缩缩存存储储（只只讨讨论论有有较较多多零零元元素素矩阵的压缩存储）矩阵的压缩存储）稀稀疏疏矩矩阵阵的的压压缩缩存存储储只只存存非非零零元元，对对每每一一非非零零元元，除除了了要要保保存存非非零零元元素素的的值值外外，还还要要保保存存非非零元

44、素在零元素在矩阵中的位置矩阵中的位置；结束第 64 页5 52 2 矩阵的压缩存储矩阵的压缩存储3 3 稀疏矩阵的（非零元）三元组表稀疏矩阵的（非零元）三元组表 A=(1,2,12),A=(1,2,12),(1,3,9),(1,3,9),(3,1,-3),(3,1,-3),(3,6,14),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)(4,3,24),(5,2,18),(6,1,15),(6,4,-7)4 4 三元组顺序表三元组顺序表 用顺序表存储三元组表，非零元三元组以行为用顺序表存储三元组表，非零元三元组以行为主序存储主序存储结束第 65 页第五

45、章练习题第五章练习题1 1 矩阵压缩存储是指为矩阵压缩存储是指为多个值相同的元素分配多个值相同的元素分配一个存储空间，对一个存储空间，对零元素零元素不分配存储空间；不分配存储空间；2 2 特特殊殊矩矩阵阵的的压压缩缩存存储储是是根根据据元元素素的的分分布布规规律律，确确定定元元素素的的存存储储位位置置与与元元素素在在矩矩阵阵中中的的位位置置的的对对应关系；应关系；3 3 (含含零零元元的的)稀稀疏疏矩矩阵阵的的压压缩缩存存储储只只存存非非零零元元，对对每每一一非非零零元元，除除了了要要保保存存零零元元素素的的值值外外，还还要要保存零元素在保存零元素在矩阵中的位置矩阵中的位置；4 4 给出稀疏矩

46、阵，写出对应的（非零元）三元组给出稀疏矩阵，写出对应的（非零元）三元组表表 A=(1,2,12),(1,3,9),(3,1,-3),(3,6,14),A=(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)(4,3,24),(5,2,18),(6,1,15),(6,4,-7)结束第 66 页53广义表广义表1 1 什么是广义表什么是广义表广广义义表表是是数数据据元元素素的的有有限限序序列列。记记作作：LS=LS=(1,2,(1,2,n),n)。其其中中ii其其可可以以是是单单个个元元素素，也可以是广义表。也

47、可以是广义表。2 2 广义表的基本操作广义表的基本操作求表头求表头求表尾求表尾表头：广义表的第一个元素表头：广义表的第一个元素表尾：除第一个元素外，起它元素组成的表表尾：除第一个元素外，起它元素组成的表结束第 67 页53广义表广义表广义表的存储结构广义表的存储结构（了解）（了解）广广义义表表通通常常采采用用链链式式存存储储结结构构。链链表表中中有有两两种种的的结结点点：一一种种是是表表结结点点，用用以以表表示示广广义义表表；一一种是原子结点，用以表示原子；种是原子结点，用以表示原子；结束第 68 页第五章练习题第五章练习题广义表是数据元素的有限序列。其元素可以是广义表是数据元素的有限序列。其

48、元素可以是单个元素单个元素，也可以是，也可以是广义表。广义表。2 2表头：广义表的表头：广义表的第一个元素第一个元素表尾：除第一个元素外，表尾：除第一个元素外，其它元素组成的表其它元素组成的表结束第 69 页结束第 70 页6.1 6.1 树的有关概念树的有关概念一一 树的概念树的概念1 1 树的逻辑结构树的逻辑结构树：是一种一对多的结构关系或称为分枝结构关树：是一种一对多的结构关系或称为分枝结构关系，除了根之外，每个元素只有一个直接前趋；，系，除了根之外，每个元素只有一个直接前趋；，但每个元素可以有零个或多个直接后继；但每个元素可以有零个或多个直接后继；J JI IH HG GF FE ED

49、 DB BA AC C结束第 71 页6.1 6.1 树的有关概念树的有关概念 2 2 树的基本操作树的基本操作（了解）（了解）1 1）InitTreeInitTree(&T);(&T);2 2）DestroyTreeDestroyTree(&T);(&T);3 3）CreateTreeCreateTree(&T,definition);(&T,definition);4 4）ClearTreeClearTree(&T);(&T);5 5）TreeEmptyTreeEmpty(T);(T);6 6）TreeDepthTreeDepth(T);(T);结束第 72 页6.1 6.1 树的有关概念

50、树的有关概念Root(T);Root(T);Value(T,cur_e);Value(T,cur_e);Assign(T,cur_e,value);Assign(T,cur_e,value);ParetParet(T,cur_e);(T,cur_e);LeftChildLeftChild(T,cur_e);(T,cur_e);RightSiblingRightSibling(T,cur_e);(T,cur_e);InsertChildInsertChild(&T,&p,i,c);(&T,&p,i,c);DeleteChildDeleteChild(&T,&p,i);(&T,&p,i);Trav