北京师范大学数据结构教学资料 第4章-数组、串与广义表

数据结构第4章数组、串与广义表北京师范大学教学资料Contents本章目录01串的定义、存储与模式匹配02数组的定义与矩阵压缩存储03广义表的定义、性质与操作CHAPTER01串的定义、存储与模式匹配从基本概念到BF与KMP算法的完整认知路径DATASTRUCTURE·STRING串的基本定义与核心术语串（String）是由零个或多个字符组成的有限序列，是线性表在字符集上的特化形式。理解空串与空格串的区别、子串与主串的关系、字符位置与子串位置的差异，是掌握后续串操作和模式匹配算法的前提。01串的定义由零个或多个字符组成的有限序列，记为S='a₁a₂...aₙ'，其中S为串名，引号内为串值，n为串长。有限序列02空串与空格串的区别空串长度n=0，不含任何字符；空格串含有一个或多个空格字符，长度不为零，二者在判等操作中结果不同。n=0vsn≠003子串与主串若串a是串c的连续子序列，则a为c的子串；子串位置用其首字符在主串中的序号表示，如'BEI'在'BEIJING'中位置为1。首字符序号04串相等判定两个串长度相等且对应位置字符完全相同才判定为相等，这是串比较操作StrCompare的核心逻辑。逐位比较DataStructure串的逻辑结构：受限的线性表串是数据元素限定为字符集的线性表，其逻辑结构与线性表一致——元素之间存在一对一的前驱后继关系。但串的操作特点与一般线性表存在显著差异：操作对象通常从单个字符转变为字符序列（子串），并衍生出模式匹配等串特有的核心操作。01数据对象限定：D={aᵢ|aᵢ∈CharacterSet,i=1,2,...,n,n≥0}，元素类型固定为字符集成员，区别于线性表可存储任意类型CharacterSet02数据关系一致：R₁={<aᵢ₋₁,aᵢ>|aᵢ₋₁,aᵢ∈D,i=2,...,n}，相邻字符间存在前驱后继的线性关系，逻辑结构与线性表完全相同R₁03操作粒度差异：线性表侧重单个元素的插入删除查找，串侧重子串的定位、替换、插入等操作，催生了Index、Replace等特有运算Index04模式匹配是串的核心应用：在主串中查找子串出现的位置，是文本编辑、信息检索、基因序列分析等领域的基础操作PatternSTRINGADT串的抽象数据类型（ADT）定义串的ADT定义了12个基本操作，涵盖赋值、比较、连接、子串提取、模式定位、替换、插入和删除等功能，是后续算法实现的接口规范。BASICOPERATIONS基础操作StrAssign(&T,chars)—将字符序列赋值给串T，是串创建和初始化的基础StrCompare(S,T)—比较两个串的大小，返回正数、零或负数，用于排序和判等StrLength(S)—返回串S的长度，时间复杂度O(1)（定长）或O(n)（动态）Concat(&T,S1,S2)—将S1和S2连接为新串T，需注意结果串长度溢出问题ADVANCEDOPERATIONS高级操作SubString(&Sub,S,pos,len)—提取S中从pos起长度为len的子串，是模式匹配的基础Index(S,T,pos)—返回子串T在主串S中pos之后的首次出现位置，即模式匹配核心Replace(&S,T,V)—将S中所有不重叠的T替换为V，是文本编辑器的基本功能StrInsert/StrDelete—在指定位置插入或删除子串，改变原串结构DATASTRUCTURE串的顺序存储结构串的顺序存储分为定长存储和堆分配存储两种方式，均支持O(1)随机访问，但插入删除需移动大量元素。定长顺序存储预定义MAXSTRLEN常量，超过长度的串值被截断（截尾法），用数组S[0]或额外变量记录串长。堆分配存储利用malloc/free动态分配连续空间，串长度不受编译期限制，适合长度变化大的应用场景。随机访问优势顺序存储可通过下标直接定位任意字符，时间复杂度O(1)，便于模式匹配算法的逐字符比较。插入删除的代价在位置pos插入或删除子串时，需移动后续所有字符，平均移动n/2个元素，时间复杂度O(n)。DataStructure·StringStorage串的链式存储：块链结构串的链式存储采用块链结构，每个链表节点存放多个字符（块大小>1），通过调整块大小在存储密度和操作灵活性之间取得平衡。01块链结构设计每个节点包含data域（存放chunk_size个字符）和next指针，块大小根据应用场景选定。chunk02存储密度权衡块越大存储密度越高（接近1），但末尾节点可能浪费空间；块大小为1时密度约50%。≈50%03操作灵活性优势插入删除只需修改指针和少量字符移动，在文本编辑器等频繁修改场景下效率显著高于顺序存储。O(1)04随机访问劣势无法通过下标直接定位，需从头遍历链表，不适合BF等需要大量随机访问的模式匹配算法。O(n)ALGORITHMBF模式匹配算法（暴力匹配）BF算法通过逐字符比较和失配回退实现子串定位，最好情况O(m)，最坏退化至O(m×n)，长文本匹配中效率低下。CORELOGIC算法核心逻辑设置主串指针i和模式串指针j，逐字符比较，匹配则双指针前进，失配则i回退到起始位置+1，j归零S[i]=T[j]BESTCASE最好情况分析第一次尝试即匹配成功，比较次数为模式串长度m，时间复杂度O(m)，如主串ABCDEFG匹配ABCO(m)WORSTCASE最坏情况分析每次在模式串末尾失配，需n-m+1趟比较，每趟m次，总比较约m×(n-m+1)O(m×n)ROOTCAUSE回退低效的根源失配后主串指针i大幅回退，已匹配的字符信息被完全丢弃，未利用已有匹配结果优化下一轮比较i回退ALGORITHMKMP模式匹配算法KMP算法的核心创新在于利用已匹配的部分信息避免主串指针回退。通过预计算模式串的next数组（部分匹配表），记录每个位置之前子串的最长公共前后缀长度，在失配时将模式串智能滑动而非暴力回退，将时间复杂度从O(m×n)优化至O(m+n)。01核心改进：失配时主串指针i不回退，模式串指针j根据next数组跳转到合适位置，利用已匹配信息减少重复比较。O(m×n)→O(m+n)02next数组含义：next[j]表示模式串T[0..j−1]的最长公共前后缀长度，即前缀和后缀相同的最大长度（不包括整个子串本身）。next[j]03next数组计算：通过双指针递推求解，当T[j]=T[k]时next[j+1]=k+1，否则k回退到next[k]继续比较，计算过程时间复杂度O(m)。O(m)04整体复杂度分析：预处理next数组O(m)加上匹配过程O(n)，总时间复杂度O(m+n)，相比BF在最坏情况下有质的飞跃。O(m+n)Algorithm·KMPKMP算法next数组计算实例next数组的计算是KMP算法的核心难点。通过分析模式串每个位置之前子串的最长公共前后缀，可以确定失配时模式串的最优滑动距离。以'ABABC'为例，next值为[-1,0,0,1,2]，直观展示了模式串内部的自相似结构如何指导匹配优化。ABABCi=0-1i=10i=20i=31i=4201基础约定：以模式串'ABABC'为例，next[0]=-1（约定值），next[1]=0（单字符无公共前后缀），next[2]=0（'AB'无公共前后缀）。02next[3]=1：子串'ABA'的最长公共前后缀为'A'（前缀A=后缀A），长度为1，失配时j回退到位置1。03next[4]=2：子串'ABAB'的最长公共前后缀为'AB'（前缀AB=后缀AB），长度为2，失配时j回退到位置2继续比较。04本质理解：next数组记录模式串中每个位置之前子串的"自相似程度"，自相似度越高，失配时可跳过的比较越多。ALGORITHMCOMPARISONBF与KMP算法对比总结BF算法以简单直观取胜，适合短串和小规模匹配；KMP通过next数组消除主串回退，大规模场景性能优势显著。BF算法与KMP算法核心特征对比对比维度BF算法（暴力匹配）KMP算法核心思想逐字符比较，失配后主串和模式串均回退利用next数组避免主串回退，模式串智能滑动最好时间复杂度O(m)，首次即匹配成功O(m+n)，含预处理最坏时间复杂度O(m×n)，每次末尾失配O(m+n)，主串仅遍历一次空间复杂度O(1)，无需额外空间O(m)，需存储next数组实现难度简单直观，代码量约15行需理解next数组递推，代码量约30行适用场景短文本匹配、教学演示大规模文本搜索、基因序列比对Summary—KMP在时间效率上有质的提升，代价是需要额外空间存储next数组CHAPTER02数组的定义与矩阵压缩存储从多维数组的地址计算到特殊矩阵的空间优化策略DataStructure·Array数组的定义与基本特性数组是线性表向多维方向的推广，维数与维界一旦定义即固定不变，天然适合顺序存储并支持O(1)随机访问。多维推广n维数组是"元素为(n-1)维数组"的线性表，如二维数组可视为元素为一维数组的一维数组，形成递归定义结构。n维递归结构固定数组创建后维数和各维大小不可变，不存在插入和删除操作，基本操作仅有Value（取值）和Assign（赋值）。不可变ADT操作InitArray初始化、DestroyArray销毁、Value获取指定下标元素值、Assign修改指定下标元素值，共四项基本操作。4项操作随机访问元素按规则顺序存储，可通过地址计算公式直接定位任意元素，访问时间O(1)，这是数组最核心的优势。O(1)DATASTRUCTURE数组的顺序存储与地址计算数组的顺序存储将多维结构映射到一维连续内存，分为行优先和列优先两种方式，通过地址公式在O(1)时间内定位任意元素。01行优先存储按行号从小到大、同行内按列号从小到大的顺序存放Loc(i,j)=Loc(0,0)+(i×n+j)×L02列优先存储按列号从小到大、同列内按行号从小到大的顺序存放，FORTRAN默认采用Loc(i,j)=Loc(0,0)+(j×m+i)×L03三维数组地址计算按页/行/列顺序存放，n₂、n₃为后两维的大小Loc(i,j,k)=Loc(0,0,0)+(i·n₂·n₃+j·n₃+k)×L04公式参数含义L为每个元素占用的存储单元大小（字节数），Loc(0,0)为数组起始地址（基地址），计算结果为元素的实际物理地址Practice地址计算实例演练通过具体例题掌握数组地址计算的完整过程：确定存储方式（行优先/列优先）、代入地址公式、注意元素大小和基地址。地址计算是数据结构考试的高频考点，也是理解编译器如何实现数组访问的基础。Example01二维数组行优先寻址A[6][8]，每元素6字节，基址1000A[3][5]=1000+(3×8+5)×6=1174Example02总存储量与末元素地址总量=6×8×6=288字节A[5][7]=1000+(5×8+7)×6=1282Example03三维数组页优先寻址B[2][3][4]，每元素4字节，基址2000B[1][2][3]=2000+(1×3×4+2×4+3)×4=2076Warning易错提醒下标起始值影响计算结果。若下标从1开始（如A[1..6][1..8]），公式中i和j需分别减1后再代入。i→i−1，j→j−1DATASTRUCTURE·COMPRESSION对称矩阵的压缩存储对称矩阵满足a[i][j]=a[j][i]的特性，只需存储下三角（含对角线）的n(n+1)/2个元素即可完整表示n×n矩阵。通过一维数组sa[n(n+1)/2]按行序存储下三角元素，可将存储空间从n²降至约一半，同时通过地址公式仍可O(1)访问任意元素。01存储策略仅存储下三角区域（i≥j的元素）和对角线元素，共n(n+1)/2个值，以一维数组sa[n(n+1)/2]按行序依次存放i≥j02下标映射公式i≥j时位置k=i×(i+1)/2+j；i<j时利用对称性a[i][j]=a[j][i]间接访问O(1)03空间节省效果n阶对称矩阵从n²个存储单元降至n(n+1)/2个，n=100时从10000降至5050~50%04应用实例图的邻接矩阵、距离矩阵等天然是对称矩阵，采用压缩存储可显著减少内存占用n=100SpecialMatrices三角矩阵与对角矩阵的压缩存储三角矩阵的非常数区域呈三角形分布，只需存储三角区域的n(n+1)/2个元素加一个常数C，共n(n+1)/2+1个存储单元。对角矩阵的非零元素集中在主对角线附近的带状区域，可按对角线顺序存储。两类矩阵的压缩存储均保持O(1)随机访问能力。01三角矩阵存储上三角矩阵中i>j的元素均为常数C，仅需存储上三角区域的n(n+1)/2个元素和1个常数C。n(n+1)/2+1存储单元02上三角地址公式i≤j时，k=i×(2n−i+1)/2+(j−i)，即前i行元素个数加本行偏移；常数C存放在sa[n(n+1)/2]的位置。k=i·(2n−i+1)/2+(j−i)03对角矩阵（带状矩阵）非零元素集中在以主对角线为中心、宽度为2d+1的带状区域，其余元素全为零。带宽2d+104带状矩阵存储方案将带状区域按行序展开到一维数组，或按对角线顺序——主对角线、上次对角线、下次对角线——依次存储。行序/对角线序DATASTRUCTURE稀疏矩阵的压缩存储稀疏矩阵中非零元素远少于零元素且分布无规律，常规存储造成大量空间浪费。三元组顺序表通过记录每个非零元素的行号、列号和值实现压缩，适合静态场景；十字链表通过行列双链结构支持高效的动态插入删除，适合矩阵运算频繁修改的场景。01稀疏矩阵定义非零元素个数远小于矩阵总元素个数（通常t≪m×n），且分布无明显规律，无法用简单公式压缩02三元组顺序表每个非零元素用(行号,列号,值)三元组表示，按行序排列成一维表，另存矩阵行数、列数和非零元个数03三元组的局限顺序存储支持按行序遍历，但不支持随机查取，需从头遍历查找；插入删除非零元素需大量移动操作04十字链表每个非零元素节点含right和down两个指针，分别链接同行与同列下一个非零元，插入删除仅需修改指针DATASTRUCTURE稀疏矩阵三元组存储实例以5×6稀疏矩阵为例，30个元素中仅有5个非零元素，使用三元组表存储只需5组(行,列,值)加3个辅助量，存储效率从30单元降至约8单元。稀疏矩阵三元组顺序表示例序号行号i列号j值v00251103224733124459附加维度信息：(5,6,5)—5行×6列×5个非零元存储压缩30→8原始矩阵需30个存储单元，三元组表示仅需5组(行,列,值)加3个辅助量，压缩至约8单元。访问特性三元组按行序排列便于顺序遍历，但查找特定位置元素需线性扫描，不适合高频随机访问场景。DataStructure稀疏矩阵的十字链表存储十字链表是稀疏矩阵的动态链式存储结构，每个非零元素节点同时属于行链表和列链表，通过right和down双指针实现行列双向链接。节点结构每个非零元素节点包含(row,col,value)数据域和(right,down)两个指针域，right指向同行下一个非零元，down指向同列下一个非零元。row·col·val头指针管理设置行头指针数组rhead[0..m-1]和列头指针数组chead[0..n-1]，分别指向各行和各列第一个非零元素节点。rhead+chead插入优势新增非零元素时，只需在对应行链表和列链表中按序插入节点并修改指针，无需移动其他元素，时间复杂度O(k)。O(k)应用场景矩阵加法、矩阵乘法、矩阵转置等运算中非零元素频繁增删，十字链表比三元组顺序表更适合此类动态场景。加法·乘法·转置DATASTRUCTURES特殊矩阵压缩存储方法总结四种特殊矩阵的压缩存储各有适用场景：对称矩阵和三角矩阵利用元素重复性实现约50%的空间节省，对角矩阵利用带状分布特性大幅压缩，稀疏矩阵通过记录非零元素位置避免零元素的空间浪费。选择存储方式时需综合考虑矩阵特征、访问频率和修改需求。四类特殊矩阵压缩存储方案对比矩阵类型核心特征压缩方法存储量对称矩阵a[i][j]=a[j][i]存下三角到一维数组n(n+1)/2三角矩阵三角区为常数C存三角区+1个常数n(n+1)/2+1对角矩阵非零元集中在对角带按行/对角线存带状区约n(2d+1)稀疏矩阵非零元少且无规律三元组表或十字链表3t（t为非零元数）摘要：前三种矩阵利用元素分布规律压缩，稀疏矩阵通过记录位置信息压缩CHAPTER03广义表的定义、性质与操作从线性表到递归结构的自然延伸与表达能力拓展DATASTRUCTURE广义表的基本定义广义表（Lists）是线性表的推广，其元素既可以是原子（不可再分的数据），也可以是另一个广义表，形成递归嵌套结构。这种灵活性使得广义表能够兼容线性表、数组、树和有向图等多种数据结构，成为表达能力最强的线性结构之一。01广义表LS=(a₁,a₂,...,aₙ)，其中每个aᵢ可以是原子（单个数据元素），也可以是广义表（子表），元素类型不必相同。LS=(aᵢ)02习惯上用大写字母表示广义表（如A、B、C），用小写字母表示原子（如a、b、c），便于区分层次关系。Avsa03当广义表所有元素都是原子时，它退化为普通线性表；因此线性表是广义表的特例，广义表是线性表的推广。线性表⊂广义表04A=(a,b,c)纯原子表；B=(a,(b,c))含子表；C=(a,C)递归表，展现广义表的递归能力。C=(a,C)GENERALIZEDLIST广义表的重要性质长度取最外层元素数，深度取括号最大嵌套层数，表头取首元素，表尾取其余元素构成的表，区分四者是掌握操作的前提。长度（Length）最外层元素个数。如LS=(a,(b,c),d)的长度为3，子表(b,c)整体只算1个元素。最外层计数深度（Depth）括号的最大重数。空表深度为1，原子深度为0；LS=(a,(b,(c,d)))深度为3。最大嵌套层数表头（Head）第一个元素，可为原子或子表。GetHead((a,b,c))=a；GetHead(((a,b),c))=(a,b)。首元素表尾（Tail）除表头外其余元素构成的广义表，表尾一定是表。GetTail((a,b,c))=(b,c)；GetTail((a))=()。其余元素构成的表广义表基本运算GetHead与GetTail操作详解GetHead取首元素，GetTail取剩余表（结果一定带括号）——嵌套计算时从外向内逐层展开，最易出错也最常考。基础操作示例LS=(a,(b,c),d)GetHead→a（原子）GetTail→((b,c),d)外层括号保留HEAD·TAIL嵌套GetHeadHead(Tail(LS))=Head(((b,c),d))=(b,c)先取表尾再取表头(b,c)嵌套GetTailTail(Tail(LS))=Tail(((b,c),d))=(d)连续取表尾逐步缩减最终得到单元素子表(d)深度嵌套取出取出c的路径：H(T(H(T(LS))))从子表(b,c)取尾再取头四层嵌套操作→cDataStructure广义表的链式存储结构广义表因元素类型多样且大小不一，通常采用链式存储。头尾表示法递归分解，扩展线性链表法线性串联，两种方案均天然支持递归操作。Method01头尾表示法节点分类—表节点（tag=1）含hp、tp指针域，分别指向表头与表尾；原子节点（tag=0）含data数据域递归结构—hp、tp分别指向子广义表，形成递归嵌套的树形结构，便于实现GetHead和GetTail空间开销—每个非空表分解为表头与表尾两个子表，节点数较多，但逻辑关系与ADT定义一一对应Head-TailRepresentationtag1hp→tp→表节点tag0datavalue原子节点hp·tp递归分解ExtendedLinearListtag1hp↓子表tp→兄弟表节点tag0datavaluetp→兄弟原子节点hp↓·tp→线性串联DATASTRUCTURE广义表的表达能力与应用广义表是表达能力最强的线性结构：通过限制嵌套和递归条件，它可以退化为线性表、树或有向图。LINEARLIST退化为线性表所有元素均为原子（深度=1）时，广义表等价于普通线性表，如(a,b,c