数据结构复习资料ppt课件.ppt

《数据结构复习资料ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构复习资料ppt课件.ppt（146页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、结束第 1 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能题型题型1 1 选择题选择题 2 2 填空题填空题 3 3 解答题解答题 4 4 算法题算法题 结束第 2 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能结束第 3 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第一章第一章绪绪论论计算机的发展计算机的发展硬件硬件 CPU CPU、内、外存储器等、内、外存储器等软件软件：系统软件、应用软件：系

2、统软件、应用软件应用应用 科学计算科学计算 数据处理数据处理 过程控制等过程控制等处理数据的能力和种类处理数据的能力和种类：数值：数值 字符、字符串字符、字符串 具有多个属性对象具有多个属性对象 图形图形 图像图像 声音声音 结束第 4 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能数据结构的研究对象数据结构的研究对象：非数值数据之间的结构关系，如何表示，非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。如何存储，如何处理的问题。本课程讨论的问题：本课程讨论的问题：应用中常用的几种数据结构，以及如何存储应用中常用的几

3、种数据结构，以及如何存储,如何处理它们。如何处理它们。第一章第一章绪绪论论结束第 5 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1 1 数据数据：客观对象的：客观对象的符号表示符号表示。例如：课程名，地名，书名都是数据例如：课程名，地名，书名都是数据2 2 数据结构：数据结构：带有带有结构和操作结构和操作的数据元素集合的数据元素集合 结构：数据元素之间的关系；结构：数据元素之间的关系；操作：对数据的加工处理操作：对数据的加工处理 ；第一章第一章绪绪论论结束第 6 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,

4、贯彻全国教育大会精神,充分发挥中小学图书室育人功能第一章第一章绪绪论论3 3 数据的逻辑结构数据的逻辑结构 ：数据之间的：数据之间的结构关系结构关系，是，是具体关系的抽象。具体关系的抽象。4 4 常用的有下列几类基本结构：常用的有下列几类基本结构：（1 1）集合）集合 （2 2）线性结构）线性结构 （3 3）树结构）树结构 （4 4）图结构）图结构 （5 5）其它复杂结构）其它复杂结构5 5 数据结构的基本操作：数据结构的基本操作：也叫基本运算：是指对也叫基本运算：是指对数据结构的加工处理；数据结构的加工处理；结束第 7 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教

5、育大会精神,充分发挥中小学图书室育人功能第一章第一章绪绪论论6 6 数据的存储结构：数据的存储结构：数据结构在计算机数据结构在计算机内存中的表示内存中的表示。7 7 顺序存储结构顺序存储结构 用一组用一组连续的内存单元连续的内存单元存放数据元素，用元存放数据元素，用元素素相对的存储位置相对的存储位置表示元素之间的结构关系；表示元素之间的结构关系；8 8 链式存储结构链式存储结构 用用任意一组存储单元任意一组存储单元存储数据元素，对每个存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素数据元素除了保存自身信息外，还保存相关元素的的存储位置存储位置。数据结构基本操作的实现：数据结构基本

6、操作的实现：基本操作在计算机基本操作在计算机上的实现（方法）上的实现（方法）结束第 8 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能9 9 数据结构的表示数据结构的表示 1 1 图示表示图示表示 2 2 二元组表示二元组表示图示表示：由顶点和边构成的图，其中图示表示：由顶点和边构成的图，其中顶点顶点表示表示数据数据 ，边边表示数据之间的结构关系；表示数据之间的结构关系；第一章第一章绪绪论论J JI IH HG GF FE ED DB BA AC C结束第 9 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全

7、国教育大会精神,充分发挥中小学图书室育人功能二元组表示二元组表示 用一个二元组（用一个二元组（D D，S S）表示数据结构，其中）表示数据结构，其中 D D 是数据元素集合，是数据元素集合，S S 是是 D D 上关系的集合。上关系的集合。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,第一章第一章绪绪论论结束第 10 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第一章第一章绪绪论论10 10 算法的概念算法的概念 算法是求解问题的操作序列（或操作步骤

8、）算法是求解问题的操作序列（或操作步骤）11 11 时间复杂度时间复杂度T T（n n）以求解问题的基本操作（原操作）的执行次以求解问题的基本操作（原操作）的执行次数作为算法的时间度量数作为算法的时间度量 空间复杂度空间复杂度用执行算法所需的辅助空间的大小作为算法所需用执行算法所需的辅助空间的大小作为算法所需空间的度量空间的度量结束第 11 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第一章练习题第一章练习题1数据结构：带有结构和操作的数据元素集合。2 2 常用的数据结构常用的数据结构3 3数据结构的表示数据结构的表示4 数据

9、的逻辑结构 ：数据之间的结构关系，是具体关系的抽象。5数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理；6数据的存储结构：数据结构在计算机内存中的表示7数据结构基本操作的实现：基本操作在计算机上的实现（方法）8顺序存储结构9链式存储结构10 算法的概念 算法是求解问题的操作序列（或操作步骤）。11 时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法时间的度量结束第 12 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能结束第 13 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育

10、大会精神,充分发挥中小学图书室育人功能 常用的数据结构常用的数据结构 1 1）集合集合 2 2）线性结构线性结构 3 3）树结构树结构 4 4）图结构图结构 5 5）其它复杂结构其它复杂结构第二章线性表第二章线性表对每种数据结构，主要讨论如下两方面的问题对每种数据结构，主要讨论如下两方面的问题1 1 数据的逻辑结构，数据结构的基本操作；数据的逻辑结构，数据结构的基本操作；2 2 数据的存储结构，数据结构基本操作的实现数据的存储结构，数据结构基本操作的实现 结束第 14 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 第二章线性表

11、第二章线性表线性数据结构：线性数据结构：除第一个元素和最后一个元素之外，其他除第一个元素和最后一个元素之外，其他元素都有且仅有一个元素都有且仅有一个直接前趋直接前趋，有且仅有一个，有且仅有一个直直接后继。接后继。结束第 15 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 2.1 2.1 线性表的概念线性表的概念 一一 线性表的逻辑结构线性表的逻辑结构在线性表中，除第一个元素和最后一个元素之外，在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个其他元素都有且仅有一个直接前趋直接前趋，有且仅有一，有且仅有一个个直接

12、后继。直接后继。2.1 2.1 线性表的概念线性表的概念 a a1 1 a a2 2a ai-i-1 a ai ia ai+i+1 a an n结束第 16 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能二二线性表的基本操作线性表的基本操作三三1 1 初始化操作初始化操作 InitList(&L)InitList(&L)2 2 销毁操作销毁操作DetroyList(&L)DetroyList(&L)3 3 置空操作置空操作ClearList(&L)ClearList(&L)4 4 判空操作判空操作ListEmpty(L)List

13、Empty(L)5 5 求表长操作求表长操作 ListLength(L)ListLength(L)6 6 取元素操作：取元素操作：GetElem(L,i,&e)GetElem(L,i,&e)7 7 查找操作查找操作 LocateElem(L,e,compare()LocateElem(L,e,compare()8 8 插入操作插入操作 ListInsert(&L,i,e)ListInsert(&L,i,e)9 9 删除操作删除操作 ListDelete(&L,i,&e)ListDelete(&L,i,&e)10 10 遍历操作遍历操作 ListTraverse(&L,visit()ListTr

14、averse(&L,visit()2.1 2.1 线性表的概念线性表的概念结束第 17 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现一一 线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表1 1 顺序表顺序表用一组连续的内存单元依次存放线性用一组连续的内存单元依次存放线性表的数据元素表的数据元素。2顺序表的类型定义顺序表的类型定义typedef structtypedef struct ElemType *elem;/ElemType *elem;/线性表存储空间基

15、址线性表存储空间基址 int length;/int length;/当前线性表长度当前线性表长度 int listsize;/int listsize;/当前分配的存储空间大小当前分配的存储空间大小SqList;SqList;结束第 18 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能顺序表图示顺序表图示设设 A=A=（a a1 1,a,a2 2,a,a3 3,.a,.an n ）是一线性表，是一线性表，L L是是SqList SqList 类型的结构变量，用于存放类型的结构变量，用于存放 A A2.2 2.2 线性表的顺序存

16、储和实现线性表的顺序存储和实现L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen n9999 a a1 1 a a2 2a ai-1i-1 a ai ia ai+1i+1 a an n0 01 1i-2i-2i-1i-1i in-1n-19999 顺序表保存了哪些信息?结束第 19 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 顺顺序表保存了哪些信息？序表保存了哪些信息？*线性表中的数据元素；线性表中的数据元素；*线性表

17、中数据元素的顺序关系；线性表中数据元素的顺序关系；*表中元素个数（简化算法）表中元素个数（简化算法）*当前分配的存储空间当前分配的存储空间 顺顺序表如何保存这些信息？序表如何保存这些信息？3 3 顺序表存储特点顺序表存储特点元素存储在元素存储在一组连续的内存单元中；一组连续的内存单元中；通过元素存储顺序元素之的逻辑顺序；通过元素存储顺序元素之的逻辑顺序；结束第 20 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能二二 顺序表的基本操作算法顺序表的基本操作算法1 1 初始化算法初始化算法 InitList_Sq(SqList&L)

18、InitList_Sq(SqList&L)2 2 插入操作算法插入操作算法 ListInsert_Sq(SqList&L,int i,ElemType e)ListInsert_Sq(SqList&L,int i,ElemType e)3 3 删除删除操作操作算法算法 ListDelete_Sq(SqList&L,inti,ElemType&e)ListDelete_Sq(SqList&L,inti,ElemType&e)2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现结束第 21 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图

19、书室育人功能2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现5 5 顺序表顺序表主要操作特点操作特点1 1）可随机存取顺序表的元素）可随机存取顺序表的元素(用用L.elemi-1L.elemi-1或或L.elem+(i-1)L.elem+(i-1)可可直直接接定定位位元元素素的存储地址的存储地址)2 2）插入删除操作通过移动元素实现）插入删除操作通过移动元素实现结束第 22 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2 23 3 线性表的链式存储结构和实现线性表的链式存储结构和实现线性表的链式存储结构线性表的链式

20、存储结构用一组任意的存储单元存储线性表中的数据元素，用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。相关元素的存储位置。结束第 23 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.1 .3.1 线性链表线性链表一一 线性链表的概念线性链表的概念1 1 线性链表线性链表用一组任意的存储单元存储线性表中用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自的数据元素，对每个数据元素除了保存自身信息外，还保存了直接

21、后继元素的存储身信息外，还保存了直接后继元素的存储位置。位置。2 23 3 线性表的链式存储结构和实现线性表的链式存储结构和实现结束第 24 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能typedefstructLnodeElemTypedata;StructLnode*next;LNode,*LinkList;数据域数据域指针域指针域 data next L L2 2 线性链表的结点类型定义线性链表的结点类型定义 及指向结点的指针类型定义及指向结点的指针类型定义2.3.1线性链表线性链表ai-1aia1an结束第 25 页为

22、深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3.1线性链表线性链表3 3 线性链表存储特点线性链表存储特点1 1）用用一一组组任任意意的的存存储储单单元元存存储储线线性性表表中中的的数数据据元素；元素；2 2）通通过过保保存存直直接接后后继继元元素素的的存存储储位位置置来来表表示示数数据元素之间的逻辑关系；据元素之间的逻辑关系；结束第 26 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 二二 线性链表基本操作算法线性链表基本操作算法1 1 初始化操作算法初始化

23、操作算法InitList_L(LinkList&L)InitList_L(LinkList&L)2 2 插入操作算法插入操作算法ListInsert_L(LinkList&L,inti,ElemType e)ListInsert_L(LinkList&L,inti,ElemType e)3 3 删除操作算法删除操作算法ListInsert_L(LinkList&L,inti,ElemType&e)ListInsert_L(LinkList&L,inti,ElemType&e)2.3.1线性链表线性链表结束第 27 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精

24、神,充分发挥中小学图书室育人功能2.3.1线性链表线性链表5 5 线性链表操作主要特点线性链表操作主要特点1 1）不能随机存取元素；）不能随机存取元素；2 2）插入、删除操作通过修改结点的指针实现；）插入、删除操作通过修改结点的指针实现；结束第 28 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 循环链表循环链表 循环链表的特点是将线性链表的最后一个结循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点点的指针指向链表的第一个结点 aia1ai+1ai-1anaiai+1ai-1anL L2.3.2 2.3.2

25、循环链表循环链表结束第 29 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 双向链表双向链表双向链表中，每个结点有两个指针域，一个双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元指向直接后继元素结点，另一个指向直接前趋元素结点。素结点。2.3.3 2.3.3 双向链表双向链表L Lai ia1 1a ai i-1 1an n结束第 30 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 线性表的其他操作的实现线性表的其他操作的实现1

26、)1)通过调用基本操作算法通过调用基本操作算法2)2)直接实现直接实现线性表的其他操作的实现线性表的其他操作的实现结束第 31 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第二章练习题第二章练习题；线性表的逻辑结构：在线性表中，除第一个元线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都素和最后一个元素外，其他元素都有且仅有一有且仅有一个个直接前趋，直接前趋，有且仅有一个有且仅有一个直接后继。直接后继。顺序表存储特点：顺序表存储特点：1 1）元素存储在）元素存储在一组连续一组连续的内存单元中的内存单元中2

27、2）通过元素的）通过元素的存储顺序存储顺序反映线性表中数据元素反映线性表中数据元素之的逻辑顺序；之的逻辑顺序；顺序表操作特点：顺序表操作特点：1 1）可随机存取可随机存取顺序表的元素；顺序表的元素；2 2）顺序表的插入删除操作要通过）顺序表的插入删除操作要通过移动元素移动元素实现实现 结束第 32 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第二章练习题第二章练习题线性链表存储特点线性链表存储特点1 1）用用任意一组任意一组的存储单元存储线性表中的数据的存储单元存储线性表中的数据元素；元素；2）通过保存通过保存直接后继元素的存

28、储位置直接后继元素的存储位置来表示数来表示数据元素之间的逻辑关系；据元素之间的逻辑关系；线性链表操作特点线性链表操作特点1 1）不能随机不能随机存取元素；存取元素；2 2）插入、删除操作通过）插入、删除操作通过修改结点的指针修改结点的指针实现；实现；顺序表的插入、删除操作平均要移动表的顺序表的插入、删除操作平均要移动表的一半一半元素元素 结束第 33 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第二章练习题第二章练习题顺序表能随机存取元素的原因是：顺序表能通顺序表能随机存取元素的原因是：顺序表能通过过L.elemi-1L.el

29、emi-1或或L.elem+(i-1)L.elem+(i-1)直接直接定位元素的定位元素的存储地址。存储地址。线性链表不能随机存取元素的原因是：线性链表不能随机存取元素的原因是：需从需从线性链表的线性链表的头指针开始，顺着链指针头指针开始，顺着链指针定位元素的定位元素的存储地址存储地址对于经常要存取元素的应用对于经常要存取元素的应用，线性表应采用线性表应采用顺顺序序存储结构存储结构10 10 对于经常要插入删除元素的应用，线性表应对于经常要插入删除元素的应用，线性表应采用采用链式链式存储结构存储结构结束第 34 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神

30、,充分发挥中小学图书室育人功能结束第 35 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能栈是限定仅能在表尾进行插入删除操作的线栈是限定仅能在表尾进行插入删除操作的线性表。性表。（a a1 1,a,a2 2.a.ai-1i-1,a,ai i,a,ai+1i+1,a,an n ）栈栈底底栈栈顶顶插入插入删除删除栈的特点栈的特点后进先出后进先出3.1 3.1 栈栈一一.栈的概念栈的概念1 1 栈的定义栈的定义结束第 36 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能

31、3.1 3.1 栈栈2 2 栈的基本操作栈的基本操作 1 1）初始化操作初始化操作InitStack(&S)InitStack(&S)2 2）销毁栈操作）销毁栈操作DestroyStack(&S)DestroyStack(&S)3 3）置空栈操作）置空栈操作ClearStack(&S)ClearStack(&S)4 4）取栈顶元素操作）取栈顶元素操作GetTop(S,&e)GetTop(S,&e)5 5）进栈操作进栈操作Push(&S,e)Push(&S,e)6 6）退栈操作退栈操作Pop(&S,&ePop(&S,&e）7 7）判空操作）判空操作StackEmpty(S)StackEmpty(

32、S)结束第 37 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1 3.1 栈栈二二 栈的顺序存储和实现栈的顺序存储和实现1 1 栈的顺序存储结构栈的顺序存储结构 1 1）用一组连续的内存单元依次存放自栈底用一组连续的内存单元依次存放自栈底到栈顶的数据元素；到栈顶的数据元素；2 2）栈顶元素的位置由栈顶指针指示；栈顶元素的位置由栈顶指针指示；结束第 38 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能typedef structtypedef structSE

33、lemType *base;/SElemType *base;/栈底指针SElemType *top /SElemType *top /栈顶指针栈顶指针int stacksize;/int stacksize;/当前分配的栈空间大小当前分配的栈空间大小 /(/(以以sizeof(SElemType)sizeof(SElemType)为单位）为单位）SqStack;SqStack;3.1 3.1 栈栈 2 2 顺序栈的类型定义顺序栈的类型定义结束第 39 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1 3.1 栈栈S.sta

34、cksizeS.stacksizeS.topS.topS.baseS.base99999999n nn-1n-1n-2n-21 10 0 a an n a an-1n-1a a2 2a a1 1 顺序栈的图示顺序栈的图示结束第 40 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3栈操作算法栈操作算法4 41 1）进栈操作）进栈操作算法算法：在栈顶插入元素：在栈顶插入元素 Push(SqStack&S,SElemType e)Push(SqStack&S,SElemType e)2 2）出栈操作）出栈操作算法算法：在栈顶插入元素

35、：在栈顶插入元素 Pop(SqStack&S,SElemType&e)Pop(SqStack&S,SElemType&e)4 4 栈操作主要特点栈操作主要特点进栈、出栈操作要修改进栈、出栈操作要修改栈顶指针栈顶指针3.1 3.1 栈栈结束第 41 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.1 3.1 栈栈三三栈的链式存储和实现栈的链式存储和实现四四 栈的链式存储与线性表的链式存储类似，栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头注意：

36、栈顶指针就是带头结点的线性链表的头指针指针ai+1aiana1S S结束第 42 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能四四 栈的应用举例栈的应用举例例例2 2 表达式求值表达式求值算符优先算法：掌握利用算符优先算法：掌握利用操作数栈操作数栈OPND OPND，运，运算符栈算符栈OPTROPTR，对，对表达式求值的方法表达式求值的方法3.2栈栈结束第 43 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第三章练习题第三章练习题栈是限定栈是限定仅能在表尾一端

37、仅能在表尾一端进行插入、删除操进行插入、删除操作的线性表；作的线性表；2 2 表尾称为表尾称为栈顶栈顶，表头称为，表头称为栈底栈底；3 3 栈的具有栈的具有后进先出后进先出的特点；的特点；4 4 栈顶元素的位置栈顶元素的位置由一个栈顶指针指示由一个栈顶指针指示；5 5 进栈、出栈操作要修改进栈、出栈操作要修改栈顶指针栈顶指针；6 6 一个栈的输入序列为一个栈的输入序列为a,b,ca,b,c，则所有可能的出，则所有可能的出栈序列为：栈序列为：abc,acb,bac,bca,cbaabc,acb,bac,bca,cba结束第 44 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻

38、全国教育大会精神,充分发挥中小学图书室育人功能一一 队列的概念队列的概念 队列的定义队列的定义 队列是限定仅能在表头删除，表尾插入的队列是限定仅能在表头删除，表尾插入的线性表。线性表。入队入队 a a1 1 a a2 2 a an n队队头头队队尾尾出队出队队列的特点队列的特点先进先出先进先出3 34 4 队列队列结束第 45 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2 2 队列的基本操作队列的基本操作1 1）初始化操作）初始化操作InitQueue(&Q)InitQueue(&Q)2 2）销毁操作）销毁操作Destroy

39、Queue(&Q)DestroyQueue(&Q)3 3）置空操作）置空操作ClearQueue(&Q)ClearQueue(&Q)4 4）判空操作）判空操作QueueEmpty(Q)QueueEmpty(Q)5 5）取队头元素操作）取队头元素操作GetHead(Q,&e)GetHead(Q,&e)6 6）入队操作）入队操作EnQueue(&Q,e)EnQueue(&Q,e)7 7）出队操作）出队操作DeQueue(&Q,&e)DeQueue(&Q,&e)3 34 4 队列队列结束第 46 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室

40、育人功能二二 循环队列循环队列队列的顺序存储和实现队列的顺序存储和实现1 1循环队列循环队列队列的顺序存贮结构队列的顺序存贮结构2 2（1 1）在队列的顺序存贮结构中用一组连续存在队列的顺序存贮结构中用一组连续存储单元依次存储队列的数据元素储单元依次存储队列的数据元素3 3（2 2）队头、队尾元素的位置分别由队头指针队头、队尾元素的位置分别由队头指针和队尾指针指示；和队尾指针指示；4 4（3 3）将顺序队列设想为首尾相连的环状空间）将顺序队列设想为首尾相连的环状空间3 34 4 队列队列结束第 47 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中

41、小学图书室育人功能 2 2 循环队列的类型定义循环队列的类型定义#define MAXSIZE 100 /#define MAXSIZE 100 /最大队列长度最大队列长度typedef structtypedef struct QElemType *base;QElemType *base;队空间基址队空间基址 int front;/int front;/队头指针队头指针 int rear;/int rear;/队尾指针队尾指针SqQueue;SqQueue;3 34 4 队列队列结束第 48 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学

42、图书室育人功能3 34 4 队列队列2 2 队列操作算法队列操作算法入队操作：在队尾插入元素；入队操作：在队尾插入元素；出队操作：在队头删除元素；出队操作：在队头删除元素；Q.baseQ.baseQ.frontQ.frontQ.rearQ.rear0 03 30 01 14 43 32 25 5J3J3J2J2J1J1结束第 49 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第三章练习题第三章练习题队列是限定队列是限定仅能在表尾一端仅能在表尾一端插入，插入，表头一端表头一端删删除操作的线性表；除操作的线性表；2 2 表尾称为表

43、尾称为队头队头，表头称为，表头称为队尾队尾 3 3 队头、队尾元素的位置分别由队头、队尾元素的位置分别由队头指针和队尾队头指针和队尾指针指示；指针指示；4 4 队列具有队列具有先进先出先进先出的特点的特点5 5 入队操作要修改入队操作要修改队尾指针队尾指针，出队操作要修改，出队操作要修改队队头指针；头指针；结束第 50 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能结束第 51 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4.1 4.1 串的基本概念串的基本概念

44、一、串的概念一、串的概念1 1 什么是串什么是串 串是由零个或多个字符组成的有限序列，串是由零个或多个字符组成的有限序列，一般记作一般记作 s=a1,a2,a3,.an s=a1,a2,a3,.an结束第 52 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4.1 4.1 串的基本概念串的基本概念2 2 串的基本操作串的基本操作（了解）（了解）串的逻辑结构与线性表一样，都是线性结串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。操作与线性表

45、有很大差别。串连接操作串连接操作 Concat(&T,S1,S2)Concat(&T,S1,S2)求子串操作求子串操作SubString(&Sub,S,pos,len)SubString(&Sub,S,pos,len)求子串位置操作求子串位置操作Index(S,T,pos)Index(S,T,pos)串插入操作串插入操作 StrInsert(&S,pos,T)StrInsert(&S,pos,T)串删除操作串删除操作 StrDelete(&S,pos,len)StrDelete(&S,pos,len)结束第 53 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精

46、神,充分发挥中小学图书室育人功能4.2 4.2 串存储和实现串存储和实现一、串的存储一、串的存储（了解）（了解）1 1 定长顺序存储结构定长顺序存储结构 定长顺序存储结构类似于定长顺序存储结构类似于C C语言的字符数组，语言的字符数组，以一组地址连续的存储单元存放串值字符序列，以一组地址连续的存储单元存放串值字符序列，其类型说明如下：其类型说明如下：#define MAXSTRLEN 255#define MAXSTRLEN 255Typedef unsigned char SStringMAXSTRLEN+1 Typedef unsigned char SStringMAXSTRLEN+1

47、结束第 54 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4.2 4.2 串存储和实现串存储和实现2 2、堆分配存储、堆分配存储堆分配存储类似于线性表的顺序存储结构堆分配存储类似于线性表的顺序存储结构 堆分配存储的类型说明堆分配存储的类型说明Typedef struct Typedef struct char*ch;/char*ch;/指向存放串值的存储空间基址指向存放串值的存储空间基址 int length;/int length;/整型域：存放串长整型域：存放串长Hstring;Hstring;结束第 55 页为深入学习习

48、近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第四章练习题第四章练习题从逻辑结构上看串是从逻辑结构上看串是线性数据结构线性数据结构；S=ababcabcac,S1=abc S=ababcabcac,S1=abc，S2=isastringS2=isastringConcat(Hstring&T,Hstring S1,Hstring S2)Concat(Hstring&T,Hstring S1,Hstring S2)T=abcisastring T=abcisastring 3 3 请列举两个线性表所没有的串操作请列举两个线性表所没有的串操作:求

49、子串求子串,求求子串位置子串位置，结束第 56 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能结束第 57 页为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5 51 1 数数 组组1 1 数组的逻辑结构数组的逻辑结构 n n 维数组中的每个元素都受维数组中的每个元素都受n n个线性关系的约个线性关系的约束，束，以二维数组为例：二维数组中的每个元素以二维数组为例：二维数组中的每个元素都受两个线性关系的约束都受两个线性关系的约束 结束第 58 页为深入学习习近平新时代中

50、国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5 51 1 数数 组组2 2 数组的基本操作数组的基本操作（了解）（了解）1初始化操作 InitArray(&A,n,bound1,boundn)功能：参数合法，构造数组A，并返回OK；2销毁操作 DestroyArray(&A)功能：销毁数组A；3 读元素操作读元素操作 Value(A,&e,index1,indexn)功能：若指定下标不越界，读指定下标的元素，用e返回，并返回OK；4 4写元素操作写元素操作 Assign(A,e,index1,indexn)功能：若指定下标不越界，将e赋值给A指定的下标