数据结构总复习课件.ppt

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 是数据元素集合，是数据

6、元素集合，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, , , 第一章第一章 绪绪 论论结束第 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） 以求解问题的基本操作

8、（原操作）的执行次数作为算法时间的度量结束第 13 页结束第 14 页 常用的数据结构常用的数据结构 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 页2 2线

10、性表的基本操作线性表的基本操作1 1 初始化操作初始化操作 InitListInitList(&L) (&L) 2 2 销毁操作销毁操作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,com

11、pare() (L,e,compare() 8 8 插入操作插入操作 ListInsertListInsert(&L,i,e )(&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 顺序表顺序表用一组连续的内存单元依

12、次存放线性用一组连续的内存单元依次存放线性表的数据元素表的数据元素。2 顺序表的类型定义顺序表的类型定义typedef structtypedef struct ElemType ElemType * *elemelem; /; /线性表存储空间基址线性表存储空间基址 int int length; /length; /当前线性表长度当前线性表长度 int listsizeint listsize; /; /当前分配的存储空间大小当前分配的存储空间大小 SqListSqList; ;结束第 19 页顺序表图示顺序表图示设设 A =A =（a a1 1,a,a2 2 , a, a3 3 , .

13、a, . an n ）是一线性表，是一线性表，L L是是SqList SqList 类型的结构变量，用于存放类型的结构变量，用于存放 A A2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现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( SqListSqL

15、ist &L) &L)2 2 插入插入操作操作算法算法 ListInsert ListInsert_Sq(_Sq(SqListSqList &L, &L,intint i, i,ElemTypeElemType e) e)3 3 删除删除操作操作算法算法 ListDeleteListDelete_Sq(_Sq(SqListSqList &L, &L,intiinti, ,ElemTypeElemType &e) &e)2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现结束第 22 页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现5 5 顺序表顺序表主要操作特点操作特点1

16、 1）可随机存取顺序表的元素）可随机存取顺序表的元素( (用用L.L.elemelemi-1i-1或或L.L.elemelem+(i-1)+(i-1)可直接定位元素可直接定位元素的存储地址的存储地址) )2 2）插入删除操作通过移动元素实现）插入删除操作通过移动元素实现结束第 23 页2 23 3 线性表的链式存储结构和实现线性表的链式存储结构和实现线性表的链式存储结构线性表的链式存储结构 用一组任意的存储单元存储线性表中的数据元素用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存，对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。了相关元素的存储

17、位置。结束第 24 页2.3.1 .3.1 线性链表线性链表一一 线性链表的概念线性链表的概念1 1 线性链表线性链表 用一组任意的存储单元存储线性表中用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储身信息外，还保存了直接后继元素的存储位置。位置。2 23 3 线性表的链式存储结构和实现线性表的链式存储结构和实现结束第 25 页typedef struct Lnode ElemType data; Struct Lnode *next;LNode, *LinkList; 数据域数据域指针域指针域 dat

18、a next L L2 2 线性链表的结点类型定义线性链表的结点类型定义 及指向结点的指针类型定义及指向结点的指针类型定义2. 3. 1 线性链表线性链表ai-1aia1an结束第 26 页2. 3. 1 线性链表线性链表3 3 线性链表存储特点线性链表存储特点1 1）用一组任意的存储单元存储线性表中的数据）用一组任意的存储单元存储线性表中的数据元素；元素；2 2） 通过保存直接后继元素的存储位置来表示数通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；据元素之间的逻辑关系；结束第 27 页 二二 线性链表基本操作算法线性链表基本操作算法1 1 初始化操作初始化操作算法算法InitL

19、istInitList_L (_L (LinkListLinkList &L) &L)2 2 插入操作算法插入操作算法ListInsertListInsert_L(_L(LinkListLinkList &L, &L,intiinti, ,ElemTypeElemType e) e)3 3 删除操作算法删除操作算法ListInsertListInsert_L(_L(LinkListLinkList &L, &L,intiinti, ,ElemTypeElemType &e) &e) 2. 3. 1 线性链表线性链表结束第 28 页2. 3. 1 线性链表线性链表5 5 线性链表操作主要特点线性

20、链表操作主要特点1 1）不能随机存取元素；）不能随机存取元素； 2 2）插入、删除操作通过修改结点的指针实现；）插入、删除操作通过修改结点的指针实现； 结束第 29 页 循环链表循环链表 循环链表的特点是将线性链表的最后一个结循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点点的指针指向链表的第一个结点 aia1ai+1ai-1anaiai+1ai-1anL L2.3.2 2.3.2 循环链表循环链表结束第 30 页 双向链表双向链表 双向链表中，每个结点有两个指针域，一个双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元指向直接后继元素结点，另一

21、个指向直接前趋元素结点。素结点。2.3.3 2.3.3 双向链表双向链表L Lai ia1 1a ai i- -1 1an n结束第 31 页 线性表的其他操作的实现线性表的其他操作的实现1) 1) 通过调用基本操作算法通过调用基本操作算法2) 2) 直接实现直接实现线性表的其他操作的实现线性表的其他操作的实现结束第 32 页第二章练习题第二章练习题； 线性表的逻辑结构：在线性表中，除第一个元线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都素和最后一个元素外，其他元素都有且仅有一有且仅有一个个直接前趋，直接前趋，有且仅有一个有且仅有一个直接后继。直接后继。 顺序表存储特点

22、：顺序表存储特点：1 1）元素存储在）元素存储在一组连续一组连续的内存单元中的内存单元中2 2）通过元素的）通过元素的存储顺序存储顺序反映线性表中数据元素反映线性表中数据元素之的逻辑顺序；之的逻辑顺序；顺序表操作特点：顺序表操作特点：1 1）可随机存取可随机存取顺序表的元素；顺序表的元素；2 2）顺序表的插入删除操作要通过）顺序表的插入删除操作要通过移动元素移动元素实现实现 结束第 33 页第二章练习题第二章练习题线性链表存储特点线性链表存储特点1 1）用用任意一组任意一组的存储单元存储线性表中的数据的存储单元存储线性表中的数据元素；元素；2） 通过保存通过保存直接后继元素的存储位置直接后继元

23、素的存储位置来表示数来表示数据元素之间的逻辑关系；据元素之间的逻辑关系；线性链表操作特点线性链表操作特点1 1）不能随机不能随机存取元素；存取元素； 2 2）插入、删除操作通过）插入、删除操作通过修改结点的指针修改结点的指针实现；实现；顺序表的插入、删除操作平均要移动表的顺序表的插入、删除操作平均要移动表的一半一半元素元素 结束第 34 页第二章练习题第二章练习题顺序表能随机存取元素的原因是：顺序表能通顺序表能随机存取元素的原因是：顺序表能通过过L.L.elemelemi-1i-1或或L.L.elemelem+(i-1)+(i-1)直接直接定位元素的定位元素的存储地址。存储地址。线性链表不能随

24、机存取元素的原因是：线性链表不能随机存取元素的原因是： 需从需从线性链表的线性链表的头指针开始，顺着链指针头指针开始，顺着链指针定位元素的定位元素的存储地址存储地址对于经常要存取元素的应用对于经常要存取元素的应用，线性表应采用线性表应采用顺顺序序存储结构存储结构10 10 对于经常要插入删除元素的应用，线性表应对于经常要插入删除元素的应用，线性表应采用采用链式链式存储结构存储结构结束第 35 页结束第 36 页 栈是限定仅能在表尾进行插入删除操作的线栈是限定仅能在表尾进行插入删除操作的线性表。性表。（a a1 1,a,a2 2.a ai i-1-1, ,a ai i , ,a ai i+1+1

25、, ,a,an n ）栈栈底底栈栈顶顶插入插入删除删除栈的特点栈的特点后进先出后进先出3.1 3.1 栈栈一一. .栈的概念栈的概念1 1 栈的定义栈的定义结束第 37 页 3.1 3.1 栈栈2 2 栈的基本操作栈的基本操作 1 1） 初始化操作初始化操作InitStackInitStack(&S)(&S) 2 2）销毁栈操作销毁栈操作DestroyStackDestroyStack(&S)(&S) 3 3）置空栈操作）置空栈操作ClearStackClearStack(&S)(&S) 4 4）取栈顶元素操作）取栈顶元素操作GetTopGetTop(S, &e)(S, &e) 5 5）进栈操

26、作进栈操作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） 用一组连续的内存单元依次存放自栈底用一组连续的内存单元依次存放自栈底到栈顶的数据元素；到栈顶的数据元素； 2 2） 栈顶元素的位置由栈顶指针指示；栈顶元素的位置由栈顶指针指示； 结束第 39 页typedef structtypedef struct SElemTyp

27、e SElemType * *base; /base; /栈底指针SElemType SElemType * *top /top /栈顶指针栈顶指针int stacksizeint stacksize; /; /当前分配的栈空间大小当前分配的栈空间大小 /( /(以以sizeofsizeof( (SElemTypeSElemType) )为单位）为单位） SqStackSqStack; ;3.1 3.1 栈栈 2 2 顺序栈的类型定义顺序栈的类型定义结束第 40 页3.1 3.1 栈栈S.S.stacksizestacksizeS.topS.topS.baseS.base99999999n n

28、n-1n-1n-2n-21 10 0 a an n a an-1n-1a a2 2a a1 1 顺序栈的图示顺序栈的图示结束第 41 页3 栈操作算法栈操作算法1 1）进栈操作）进栈操作算法算法：在栈顶插入元素：在栈顶插入元素 Push( Push(SqStackSqStack &S, &S, SElemTypeSElemType e) e)2 2）出栈操作）出栈操作算法算法：在栈顶插入元素：在栈顶插入元素 Pop( Pop(SqStackSqStack &S, &S, SElemTypeSElemType &e ) &e )4 4 栈操作主要特点栈操作主要特点进栈、出栈操作要修改进栈、出栈操

29、作要修改栈顶指针栈顶指针3.1 3.1 栈栈结束第 42 页3.1 3.1 栈栈3 3栈的链式存储和实现栈的链式存储和实现 栈的链式存储与线性表的链式存储类似，栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头注意：栈顶指针就是带头结点的线性链表的头指针指针ai+1aiana1S S结束第 43 页四四 栈的应用举例栈的应用举例例例2 2 表达式求值表达式求值算符优先算法：掌握利用算符优先算法：掌握利用操作数栈操作数栈OPNDOPND ，运，运算符栈算符栈OPTROPTR，对，对表达式求值的方法表达式求值的方法3

30、.2 栈栈结束第 44 页第三章练习题第三章练习题栈是限定栈是限定仅能在表尾一端仅能在表尾一端进行插入、删除操进行插入、删除操作的线性表；作的线性表；2 2 表尾称为表尾称为栈顶栈顶，表头称为，表头称为栈底栈底；3 3 栈的具有栈的具有后进先出后进先出的特点；的特点；4 4 栈顶元素的位置栈顶元素的位置由一个栈顶指针指示由一个栈顶指针指示；5 5 进栈、出栈操作要修改进栈、出栈操作要修改栈顶指针栈顶指针；6 6 一个栈的输入序列为一个栈的输入序列为a,b,ca,b,c，则所有可能的出则所有可能的出栈序列为：栈序列为： abcabc, ,acbacb, ,bacbac, ,bcabca, ,cb

31、acba结束第 45 页一一 队列的概念队列的概念 队列的定义队列的定义 队列是限定仅能在表头删除，表尾插入的队列是限定仅能在表头删除，表尾插入的线性表。线性表。入队入队 a a1 1 a a2 2 a an n队队头头队队尾尾出队出队队列的特点队列的特点先进先出先进先出3 34 4 队列队列结束第 46 页2 2 队列的基本操作队列的基本操作1 1）初始化操作）初始化操作InitQueueInitQueue( &Q)( &Q)2 2）销毁操作销毁操作DestroyQueueDestroyQueue( &Q)( &Q)3 3）置空操作置空操作ClearQueueClearQueue(&Q)(&

32、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 循环队列循环队列队列的顺序存贮结构队列的顺序存贮结构（1 1）在队列的顺序存贮结构中用一组连续存储在队列的顺序存贮结构中用一组连续存储单元依

33、次存储队列的数据元素单元依次存储队列的数据元素（2 2）队头、队尾元素的位置分别由队头指针和队头、队尾元素的位置分别由队头指针和队尾指针指示；队尾指针指示；（3 3）将顺序队列设想为首尾相连的环状空间）将顺序队列设想为首尾相连的环状空间3 34 4 队列队列结束第 48 页 2 2 循环队列的类型定义循环队列的类型定义# #define MAXSIZE 100 /define MAXSIZE 100 /最大队列长度最大队列长度typedef structtypedef struct QElemType QElemType * *base; base; 队空间基址队空间基址 intint fro

34、nt; / 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 页第三章练习题第三章练习题队列是限定队列是限定仅能在表尾一端仅能在表尾一端插入，插入，表头一端表头

35、一端删删除操作的线性表；除操作的线性表；2 2 表尾称为表尾称为队头队头，表头称为，表头称为队尾队尾 3 3 队头、队尾元素的位置分别由队头、队尾元素的位置分别由队头指针和队尾队头指针和队尾指针指示；指针指示；4 4 队列具有队列具有先进先出先进先出的特点的特点5 5 入队操作要修改入队操作要修改队尾指针队尾指针，出队操作要修改，出队操作要修改队队头指针；头指针；结束第 51 页结束第 52 页4. 1 4. 1 串的基本概念串的基本概念一、串的概念一、串的概念1 1 什么是串什么是串 串是由零个或多个字符组成的有限序列，串是由零个或多个字符组成的有限序列，一般记作一般记作 s = a1,a2

36、, 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, pos,lenlen) ) 求子串位置

37、操作求子串位置操作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语言的字符数组，语言的字符数组，以一组地址连续的存储单元存放串值字符序列，以一组地址连续的存储单元存放串值字

38、符序列，其类型说明如下：其类型说明如下：# #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; /; /指向存放

39、串值的存储空间基址指向存放串值的存储空间基址 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=abcisastring

40、abcisastring 3 3 请列举两个线性表所没有的串操作请列举两个线性表所没有的串操作: :求子串求子串, ,求求子串位置子串位置，结束第 57 页结束第 58 页5 51 1 数数 组组1 1 数组的逻辑结构数组的逻辑结构 n n 维数组中的每个元素都受维数组中的每个元素都受n n个线性关系的约个线性关系的约束，束， 以二维数组为例：二维数组中的每个元素以二维数组为例：二维数组中的每个元素都受两个线性关系的约束都受两个线性关系的约束 结束第 59 页5 51 1 数数 组组2 2 数组的基本操作数组的基本操作（了解）（了解）1初始化操作 InitArray(&A,n,bound1,b

41、oundn)功能：参数合法，构造数组A，并返回OK；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 数组的顺序存贮结构数组的顺序存贮结构( ( 以二维数组为例以二维数组为例) ) 两种方式：以行为主序的方式，两种方式：以行为主序的方式， 以列序为主序

42、的方式以列序为主序的方式4 数组元素存储地址的计算数组元素存储地址的计算结束第 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 ；二维数组的两种顺序存贮结构为：二维数组的两种顺序存贮结构为：）以）以行

43、为主序行为主序的方式，的方式，） 以以列序为主列序为主序的方式。序的方式。 数组元素存储地址的计算数组元素存储地址的计算 结束第 62 页5 52 2 矩阵的压缩存储矩阵的压缩存储 矩阵压缩存储是指为矩阵压缩存储是指为多个值相同的元素分配多个值相同的元素分配一一个存储空间，对个存储空间，对零元素零元素不分配存储空间不分配存储空间一一 特殊矩阵特殊矩阵1 1 什么是特殊矩阵什么是特殊矩阵 值相同元素或者零元素分布值相同元素或者零元素分布有一定规律有一定规律的矩阵的矩阵称为特殊矩阵称为特殊矩阵2 2 特殊矩阵压缩存储特殊矩阵压缩存储 特殊矩阵的压缩存储是根据元素的分布规律特殊矩阵的压缩存储是根据元

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

45、，对每一非零元，除了要保存非零元素的值外，还要保存非零元，除了要保存非零元素的值外，还要保存非零元素在零元素在矩阵中的位置矩阵中的位置；结束第 64 页5 52 2 矩阵的压缩存储矩阵的压缩存储3 3 稀疏矩阵的（非零元）三元组表稀疏矩阵的（非零元）三元组表 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) )4 4 三元组顺

46、序表三元组顺序表 用顺序表存储三元组表，非零元三元组以行为用顺序表存储三元组表，非零元三元组以行为主序存储主序存储结束第 65 页第五章练习题第五章练习题1 1 矩阵压缩存储是指为矩阵压缩存储是指为多个值相同的元素分配多个值相同的元素分配一个存储空间，对一个存储空间，对零元素零元素不分配存储空间；不分配存储空间；2 2 特殊矩阵的压缩存储是根据元素的分布规律特殊矩阵的压缩存储是根据元素的分布规律，确定元素的，确定元素的存储位置与元素在矩阵中的位置存储位置与元素在矩阵中的位置的的对应关系；对应关系；3 (3 (含零元的含零元的) )稀疏矩阵的压缩存储只存非零元稀疏矩阵的压缩存储只存非零元，对每一

47、非零元，除了要保存零元素的值外，还，对每一非零元，除了要保存零元素的值外，还要保存零元素在要保存零元素在矩阵中的位置矩阵中的位置； 4 4 给出稀疏矩阵，写出对应的（非零元）三元组给出稀疏矩阵，写出对应的（非零元）三元组表表 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 什么是广义表什么是广义表广义表是

48、数据元素的有限序列。广义表是数据元素的有限序列。 记作：记作：LS= LS= (1,2,(1,2, ,n) ,n)。其中其中ii其可以是单个元素其可以是单个元素，也可以是广义表。，也可以是广义表。2 2 广义表的基本操作广义表的基本操作求表头求表头求表尾求表尾表头：广义表的第一个元素表头：广义表的第一个元素表尾：除第一个元素外，起它元素组成的表表尾：除第一个元素外，起它元素组成的表 结束第 67 页53 广义表广义表广义表的存储结构广义表的存储结构（了解）（了解） 广义表通常采用链式存储结构。链表中有两广义表通常采用链式存储结构。链表中有两种的结点：一种是表结点，用以表示广义表；一种的结点：一

49、种是表结点，用以表示广义表；一种是原子结点，用以表示原子；种是原子结点，用以表示原子； 结束第 68 页第五章练习题第五章练习题广义表是数据元素的有限序列。其元素可以是广义表是数据元素的有限序列。其元素可以是单个元素单个元素，也可以是，也可以是广义表。广义表。2 2表头：广义表的表头：广义表的第一个元素第一个元素表尾：除第一个元素外，表尾：除第一个元素外，其它元素组成的表其它元素组成的表结束第 69 页结束第 70 页6.1 6.1 树的有关概念树的有关概念一一 树的概念树的概念1 1 树的逻辑结构树的逻辑结构树：是一种一对多的结构关系或称为分枝结构关树：是一种一对多的结构关系或称为分枝结构关

50、系，除了根之外，每个元素只有一个直接前趋；，系，除了根之外，每个元素只有一个直接前趋；，但每个元素可以有零个或多个直接后继；但每个元素可以有零个或多个直接后继；J JI IH HG GF FE ED 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）ClearTree