数据结构课件第2章

数据结构课件第2章目录线性表栈和队列串数组和广义表01线性表线性表是具有n个数据元素的有限序列。定义包括初始化、插入、删除、查找、遍历等。基本操作线性表的定义和基本操作用一段地址连续的存储单元依次存储线性表的数据元素。存储方式特点优缺点逻辑上相邻的元素在物理位置上也相邻，可随机存取任一元素。存储密度大，空间利用率高；但插入和删除操作需要移动大量元素。030201线性表的顺序存储结构用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。存储方式数据元素的逻辑顺序是通过链表中的指针链接次序实现的。特点插入和删除操作不需要移动元素，只需修改指针；但存储密度小，空间利用率低，且查找操作需要遍历链表。优缺点线性表的链式存储结构02栈和队列栈的定义栈（Stack）是一种特殊的线性数据结构，其操作只能在一端（称为栈顶）进行，遵循后进先出（LIFO）的原则。基本操作栈的基本操作包括入栈（push）、出栈（pop）、查看栈顶元素（top）和判断栈是否为空（empty）。栈的定义和基本操作栈的顺序存储结构采用一维数组来表示，栈底对应数组的起始位置，栈顶对应数组的结束位置。顺序栈具有空间利用率高、存取速度快等优点，但需要预先分配存储空间，且存在栈溢出和栈下溢的风险。栈的顺序存储结构特点存储方式存储方式栈的链式存储结构采用链表来实现，链表中的节点包含数据域和指针域，指针域指向下一个节点。特点链式栈无需预先分配存储空间，可以动态地分配和释放内存空间，但存取速度相对较慢。栈的链式存储结构队列（Queue）是一种特殊的线性数据结构，其操作在两端进行，遵循先进先出（FIFO）的原则。队列的定义队列的基本操作包括入队（enqueue）、出队（dequeue）、查看队头元素（front）和查看队尾元素（rear）。基本操作队列的定义和基本操作存储方式队列的顺序存储结构采用一维数组来表示，队头对应数组的起始位置，队尾对应数组的结束位置。特点顺序队列具有空间利用率高、存取速度快等优点，但需要预先分配存储空间，且存在队列溢出和队列下溢的风险。同时，在出队操作中需要移动大量元素，时间复杂度较高。队列的顺序存储结构队列的链式存储结构采用链表来实现，链表中的节点包含数据域和指针域，指针域指向下一个节点。队头和队尾分别用两个指针来标识。存储方式链式队列无需预先分配存储空间，可以动态地分配和释放内存空间。在出队操作中无需移动大量元素，时间复杂度较低。但链式队列的存取速度相对较慢，且需要额外的空间来存储指针信息。特点队列的链式存储结构03串串的定义和基本操作串的定义串是由零个或多个字符组成的有限序列，又名字符串。串的基本操作包括串的赋值、串的比较、求串长、串的连接、串的复制、子串的查找、插入子串和删除子串等操作。VS用一组地址连续的存储单元来存储串中的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，通常是定长顺序存储表示。顺序存储结构优缺点优点是存储密度大、空间利用率高；缺点是存在空间浪费，且串的长度受到限制。顺序存储定义串的顺序存储结构链式存储结构对串的分配存储空间是动态的，用单链表或双向链表来存储一个字符串。链表中每个结点可以存放一个字符，也可以存放多个字符。如果链表中的每个结点存放一个字符，则结点中的数据域为字符型，每个结点占用一个字节；如果结点存放多个字符，数据域则为字符数组。优点是存储空间动态分配、灵活方便；缺点是存储密度小，空间利用率低。链式存储定义链式存储结构优缺点串的链式存储结构朴素模式匹配算法又称简单匹配算法或暴力匹配算法，是一种最基本的模式匹配算法。其主要思想是将主串S的第一个字符与模式T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。KMP模式匹配算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。串的模式匹配算法04数组和广义表数组的定义和基本操作数组是一种线性表数据结构，它用一组连续的内存空间来存储具有相同类型的数据元素。数组的定义包括创建数组、销毁数组、访问数组元素、修改数组元素、插入和删除数组元素等。数组的基本操作数组采用顺序存储方式，即所有元素在内存中占有一块连续的存储空间。存储方式可以随机访问任意元素，时间复杂度为O(1)。优点插入和删除操作需要移动大量元素，时间复杂度较高。缺点数组的顺序存储结构矩阵的压缩存储定义为了节省存储空间，可以对矩阵进行压缩存储，即只存储矩阵中的非零元素或特殊元素。要点一要点二特殊矩阵的压缩存储对于具有特殊性质的矩阵（如对称矩阵、三角矩阵等），可以采用特殊的压缩存储方式，进一步节省存储空间。矩阵的压缩存储广义表的定义广义表是一种扩展了线性表的数据结构，它允许列表的元素可以是其他列表。广义表的基本操作包括创建广义表、销毁广义表、访问广义表元素、修改广义表元素、插入和删除广义表元素等。广义表的定义和基本操作

广义表的存储结构头尾链表存储结构使用