1、2022-8-19数据结构1数据结构数据结构 2022-8-19数据结构2讲课安排：讲课安排：串讲全书内容串讲全书内容典型习题分析典型习题分析前年、去年考题分析前年、去年考题分析 2022-8-19数据结构3数据结构及其概念 如何评价一个算法2022-8-19数据结构4一、术语一、术语 是信息的载体，能被计算机识别、存储、加工处理。是信息的载体，能被计算机识别、存储、加工处理。数据的基本单位数据的基本单位,即数据集合中的一个个体。也称即数据集合中的一个个体。也称元素、元素、结点、顶点、记录结点、顶点、记录是具有独立含义的最小标识单位是具有独立含义的最小标识单位唯一能识别一个数据元素的数据项。唯
2、一能识别一个数据元素的数据项。数据元素由数据元素由组成组成2022-8-19数据结构5 是具有相同性质的计算机数据的集合及在这个是具有相同性质的计算机数据的集合及在这个集合上的一组操作集合上的一组操作。数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：既对数据施加的操作数据的运算：既对数据施加的操作2022-8-19数据结构6逻辑结构：逻辑结构：(有时直接称为数据结构）有时直接称为数据结构）线性结构：线性表、栈、队列、串线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继最多只有一个直接前趋和一个直接后继)非线性结构：树非线性结构：树、图、多维数组、广义表、
3、图、多维数组、广义表说明：说明：1、逻辑结构与数据元素本身的形式、内容无关、逻辑结构与数据元素本身的形式、内容无关2、逻辑结构与数据元素的相对位置无关、逻辑结构与数据元素的相对位置无关3、逻辑结构与所含结点个数无关、逻辑结构与所含结点个数无关2022-8-19数据结构7存储结构：存储结构：顺序存储方法：顺序存储方法：数据元素在内存中按序连续存储，数据元素在内存中按序连续存储，结点间的逻辑关系由存储单元的邻接关系来体现结点间的逻辑关系由存储单元的邻接关系来体现链接存储方法：链接存储方法：用指针指出其直接后继结点的存储位置，用指针指出其直接后继结点的存储位置，结点间的逻辑关系由存储单元的邻接关系来
4、体现结点间的逻辑关系由存储单元的邻接关系来体现索引存储方法：索引存储方法：数据元素连续存放，再设一个索引表（有数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成序），索引表由索引项组成，每个索引项由关键字和地址构成 分为稠密索引和稀疏索引分为稠密索引和稀疏索引散列存储方法：散列存储方法：确定散列函数后，根据结点的关键字直接确定散列函数后，根据结点的关键字直接 计算出该结点的存储地址。计算出该结点的存储地址。2022-8-19数据结构8关系：关系：逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于计算机
5、的。计算机的。逻辑结构是从具体问题抽象出来的数学模型逻辑结构是从具体问题抽象出来的数学模型存储结构是逻辑结构用计算机语言的实现（亦称映象）存储结构是逻辑结构用计算机语言的实现（亦称映象）数据的运算是定义在数据的逻辑结构上的一个运算的集合数据的运算是定义在数据的逻辑结构上的一个运算的集合运算的实现与存储结构密切相关运算的实现与存储结构密切相关逻辑结构与存储结构是多对多的关系逻辑结构与存储结构是多对多的关系2022-8-19数据结构9例：一个学生成绩表：例：一个学生成绩表：是一个数据结构是一个数据结构每行是一个结点（或记录），由学号、姓名、各科成绩每行是一个结点（或记录），由学号、姓名、各科成绩
6、及平均成绩等数据项组成。及平均成绩等数据项组成。逻辑关系：线性结构逻辑关系：线性结构存储结构：存储结构：表的运算：表的运算：2022-8-19数据结构10 逻辑结构上定义的定义的基本运算在存储结构上的实现是通过算法来描述的。一、算法定义一、算法定义 算法算法是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。2022-8-19数据结构11 二、算法应具有的五个特性：二、算法应具有的五个特性：（1）输入输入 一个算法有零个或多个的输入，它们是算法开始前给出的最初量（2）输出输出 一个算法至少有一个输出，它们是同输入 有某种关系的量（3）有穷性有穷性 每一条指令
7、的执行次数必须是有限的（4）确定性确定性 每一条指令必须有确切的含义，无二义性（5）可行性可行性 每条指令的执行时间都是有限的。2022-8-19数据结构12一、算法评价五要素一、算法评价五要素 2022-8-19数据结构13二、算法的时间复杂度二、算法的时间复杂度 一个算法所耗费的时间一个算法所耗费的时间:该算法中每条语句的执行时间之和。该算法中每条语句的执行时间之和。每条语句的执行时间每条语句的执行时间：该语句的执行次数乘以该语句执行一次：该语句的执行次数乘以该语句执行一次所需时间。所需时间。频度频度：语句重复执行的次数：语句重复执行的次数算法的时间耗费算法的时间耗费T(n)=每条语句的执
8、行的时间每条语句的执行的时间=（语句频度（语句频度语句执行一次所需时间）语句执行一次所需时间）=语句频度语句频度算法的时间复杂度：算法的时间复杂度：就是算法的时间耗费就是算法的时间耗费T(n)2022-8-19数据结构14三、（渐进）时间复杂度三、（渐进）时间复杂度(O(f(n)当问题的规模当问题的规模n趋向无穷大时，时间复杂度趋向无穷大时，时间复杂度T(n)的数量的数量级（阶）称为算法的级（阶）称为算法的渐近时间复杂度渐近时间复杂度，简称简称时间复杂度时间复杂度四、最坏时间复杂度四、最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度
9、称为最坏时间复杂度。称为最坏时间复杂度。五、平均时间复杂度五、平均时间复杂度在假设数据集的分布是等概率的条件下，估算出的时间在假设数据集的分布是等概率的条件下，估算出的时间复杂度称为平均时间复杂度。复杂度称为平均时间复杂度。例：顺序查找例：顺序查找2022-8-19数据结构15五、空间复杂度五、空间复杂度S(n)：算法所耗费的存储空间，仍是问题规模算法所耗费的存储空间，仍是问题规模n的函数。的函数。2022-8-19数据结构161、掌握数据、数据元素、数据结构等基本概念。、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。、掌握数据逻辑结构和物理结构的分类。3、学会
10、算法分析的基本方法。、学会算法分析的基本方法。2022-8-19数据结构17本章要学习的主要内容本章要学习的主要内容1、线性表的逻辑结构及基本运算、线性表的逻辑结构及基本运算2、线性表的顺序存储结构、线性表的顺序存储结构3、线性表的链式存储结构：单链表、循环链表、双、线性表的链式存储结构：单链表、循环链表、双链表、静态链表链表、静态链表4、顺序表和链表的比较、顺序表和链表的比较2022-8-19数据结构18 线性表是由线性表是由n(n=0)个数据元素个数据元素(点点)a1,a2,.,ai,.,an组成的有限序列。其中，数据元素的个数组成的有限序列。其中，数据元素的个数n定义为表长。定义为表长。
11、当当n=0时称为空表，非空的线性表时称为空表，非空的线性表(n0)记为：记为：(a1,a2,.,ai,.,an)1.数据元素数据元素ai是一个抽象的符号是一个抽象的符号 2.ai可取各种数据类型可取各种数据类型 3.一般情况下一般情况下,同一线性表中的元素具有相同的数据类型同一线性表中的元素具有相同的数据类型 4.i是元素的序号是元素的序号(1=i=n)：仅有一个开始结点和一个终端结点，并且所有结仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继点都最多只有一个直接前趋和一个直接后继2022-8-19数据结构19线性表的常见基本运算包括：线性表的常见基本运算包括：
12、（1）置空表）置空表SETNULL(L)（2）建表）建表CREATLIST(L)（4）取结点）取结点GET(L,i)（5）定位）定位LOCATE(L,x)（6）插入）插入INSERT(L,x,i)（7）删除）删除DELETE(L,i)（3）求表长）求表长LENGTH(L)复杂的运算可以由这些基本运算组合来实现复杂的运算可以由这些基本运算组合来实现2022-8-19数据结构201、顺序存储：将线性表的结点按逻辑次序依次存放在一组地、顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。址连续的存储单元里。3 3、存储地址的计算：、存储地址的计算：LOC(aiLOC(ai)=LOC
13、(a1)+(i-1)=LOC(a1)+(i-1)*c 1=i=nc 1=idata=ch;s-next=head;head=s;ch=getchar();return head;2022-8-19数据结构29尾插法建表：尾插法建表：将新结点插入到当前链表的表尾（需引入将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr不带头结点的尾插法：不带头结点的尾插法：插入时插入时，第一个结点的处理与其，第一个结点的处理与其它结点的处理有区别。它结点的处理有区别。结束时结束时，空表和非空表的处理有区别。，空表和非空表的处理有区别。2022-8-19数据结构30Linklist*CREATLIST
14、R()char ch;linklist*head,*s,*r;head=NULL;r=NULL;ch=getchar();while(ch!=$)s=malloc(sizeof(linklist);s-data=ch;if(head=NULL)head=s else r-next=s;r=s;ch=getchar();if(r!=NULL)r-next=NULL;return head;2022-8-19数据结构31尾插法建表：将新结点插入到当前链表的表尾（需引入尾插法建表：将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr不带头结点的尾插法：不带头结点的尾插法：插入时插入时，第一
15、个结点的处理与其，第一个结点的处理与其它结点的处理有区别。它结点的处理有区别。结束时结束时，空表和非空表的处理有区别。，空表和非空表的处理有区别。带头结点的尾插法：带头结点的尾插法：1）链表第一个位置上的操作与其）链表第一个位置上的操作与其它位置上的操作相一致。它位置上的操作相一致。2）空表和非空表的处理相一致。）空表和非空表的处理相一致。2022-8-19数据结构32Linklist*CREATLISTR1()char ch;linklist*head,*s,*r;head=malloc(sizeof(linklist);r=head;ch=getchar();while(ch!=“$”)s
16、=malloc(sizeof(linklist);s-data=ch;r-next=s;r=s;ch=getchar();r-next=NULL;return head;dsrcHeadr2022-8-19数据结构33（1）按序号查找）按序号查找 GET（L，i）给定一个序号，在单链表中查找该序号对应的结点，给定一个序号，在单链表中查找该序号对应的结点，若结点存在，则返回该结点的指针，否则返回空指针。若结点存在，则返回该结点的指针，否则返回空指针。：非随机存储结构非随机存储结构的链表，决定了上述查找运算只能通过扫描单链表来完成。设置一个计数器设置一个计数器j一个一个p，初始指向头结点，初始指向
17、头结点P向后每移动一个位置向后每移动一个位置j+当当j=i时返回时返回2022-8-19数据结构34按值查找即在链表中查找是否有值等于给定值按值查找即在链表中查找是否有值等于给定值key的的结点。若有则返回首次找到的其值为结点。若有则返回首次找到的其值为key的结点的指的结点的指针，否则返回针，否则返回NULL。算法描述如下：算法描述如下：linklist*locate(head,key)linklist*head;datatye key;linklist*p;p=head next;在等概率的情况下，该算法的平均时间复杂度亦为在等概率的情况下，该算法的平均时间复杂度亦为O(n)（2）按值查找
18、）按值查找 LOCATE（head，key）while(p!=NULL)if(p data!=key)p=p next;else break;return p;2022-8-19数据结构35 （1）后插操作）后插操作:在指针在指针p所指结点之后插入所指结点之后插入xs（2）前插操作）前插操作:在指针在指针p所指结点之前插入所指结点之前插入Headp时间复杂度度时间复杂度度O(1)O(1)xs平均时间复杂度平均时间复杂度 O(n)O(n)先从头指针起先从头指针起,顺链找到顺链找到*p的前趋结点的前趋结点*q.Headpq2022-8-19数据结构36Headpax将前插操作转变为后插操作将前插操
19、作转变为后插操作xsxsaINSERTBEFORE(p,x)linklist*p;datatype x;linklist*s;s=malloc(sizeof(linklist);s-data=p-data;s-next=p-next;p-data=x;p-next=s;时间复杂度时间复杂度 O O(1)(1)2022-8-19数据结构37时间复杂度时间复杂度 O O(1)(1)删除指定结点的直接后继删除指定结点的直接后继Headprr=p-next;p-next=r-next;free(r);删除指定结点删除指定结点时间复杂度时间复杂度O(n)O(n)链表的优点链表的优点:在链表上实现插入、删
20、除运算无须移动结点，在链表上实现插入、删除运算无须移动结点，仅须修改指针仅须修改指针改进改进?2022-8-19数据结构382.单循环链表的特点：链表尾结点的单循环链表的特点：链表尾结点的next域不为空，而是指向域不为空，而是指向头结点或开始结点。（头结点或开始结点。（优点：优点：从任一结点从任一结点开始，均可找到其前趋和后继结点。）开始，均可找到其前趋和后继结点。）3、引入单循环链表的目的在于方便一些运算的实现。、引入单循环链表的目的在于方便一些运算的实现。实用中常采用实用中常采用尾指针单循环链表尾指针单循环链表,而不是头指针单循环链表。而不是头指针单循环链表。4、单循环链表上的操作与单链
21、表基本一致、单循环链表上的操作与单链表基本一致 差别差别仅在于：循环控制条件不是判空，而是判断是否等于仅在于：循环控制条件不是判空，而是判断是否等于头指针或尾指针。头指针或尾指针。1.循环链表循环链表:是一种首尾相接的链表是一种首尾相接的链表单循环链表单循环链表双循环链表双循环链表2022-8-19数据结构39 1.双链表的特点：每个结点有两个指针域，分别指向其直接双链表的特点：每个结点有两个指针域，分别指向其直接 前趋和后继。前趋和后继。2.双链表存储结构描述如下双链表存储结构描述如下：typedef struct dnode datatype data;struct dnode*prior
22、,*next;dlinklist;dlinklist*head;对于双向链表，当将头、尾结点链起来时，便成了对于双向链表，当将头、尾结点链起来时，便成了双向循环双向循环链表。链表。2.3.4 2.3.4 双链表双链表 priornextdata为了指示双链表，也须引入一为了指示双链表，也须引入一个头指针个头指针head，指指向其开向其开始结点始结点。2022-8-19数据结构403.双向链表基本运算的实现：双向链表基本运算的实现：（1）删除运算）删除运算（2）插入运算）插入运算插入和删除都非常方便插入和删除都非常方便p-prior-next=p=p-next-prior删除运算删除运算DELE
23、TENODE（p）/*删除双链表结点删除双链表结点*p*/dlinklist*p;p-prior-next=p-next;p-next-prior=p-prior;free(p);Headp2022-8-19数据结构41插入运算插入运算DINSERTBEFORE(p,x)dlinklist*p;datatype x;dlinklist*s;Pxss=malloc(sizeof(dlinklist);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;2022-8-19数据结构42 实现方法实现方法 存储空间存储空间 分配和释放分
24、配和释放 静态链表静态链表 游游 标标 预分配的一预分配的一个连续空间个连续空间 用户定义用户定义 动态链表动态链表 指指 针针 内存所有可内存所有可用空间用空间 系统提供系统提供 静态链表与动态链表的区别静态链表与动态链表的区别2022-8-19数据结构43 2、静态链表存储结构描述如下：、静态链表存储结构描述如下：define maxsize 1024typedef int datatype;typedef int cursor;typedef struct datatype data;数据域数据域 cursor next;游标游标 node;node nodepoolmaxsize;存储
25、池存储池 cursor av;游标变量游标变量 1、用数组和、用数组和“游标游标”实现链式存储的方法是实现链式存储的方法是：事先定义一个规模较大的结构数组作为备用结点空间事先定义一个规模较大的结构数组作为备用结点空间（即存储池），当申请结点空间时，从存储池中取出结点，（即存储池），当申请结点空间时，从存储池中取出结点，当释放结点空间时，将其归还于存储池内。采用这种方法实当释放结点空间时，将其归还于存储池内。采用这种方法实现的链表称为现的链表称为静态链表静态链表。12Maxsize-13NULL012Maxsize-1av0nodepoolmaxsize2022-8-19数据结构44说明说明:静
26、态链表也可以用头指针静态链表也可以用头指针L唯一指示唯一指示,L为为cursor类型类型 3、可用空间表、可用空间表:将存储池中所有空闲结点链成一个将存储池中所有空闲结点链成一个头指针为头指针为av的单链表的单链表,构成一个可用空间表构成一个可用空间表2022-8-19数据结构4512Maxsize-13NULL012Maxsize-1av1nodepoolmaxsize初始化：初始化：INITALIZE()int i;for(i=0;idata=x;p-next=top;return p;2022-8-19数据结构57Linkstack *POPLSTACK(top,datap)linkst
27、ack *top;datatype *datap;linkstack *p;if(top=NULL)printf(“underflow”);return NULL;else *datap=top-data;p=top;top=top-next;free(p);return top;2）退栈退栈 *POPLSTACK(top,datap)2022-8-19数据结构583.2 栈的应用举例栈的应用举例1.文字编辑器文字编辑器 2022-8-19数据结构593.3 队队 列列1定义：定义：队列队列 是一端进行删除另一端进行插入的线性表。允许插入的一端称为队尾队尾()，允许删除的一端称为队头队头()。
28、2特点：特点：先入队(即插入队尾）的元素必将被先删除(即出队）。因此，队列是一种先进先出(First In First Out)的线性表。3.3.1 队列的概念及运算队列的概念及运算出队出队入队入队队头队头队尾队尾a1 a2 an2022-8-19数据结构60 3队列的基本运算：队列的基本运算：（1）SETNULL（Q）置队空）置队空（2）EMPTY（Q）判队空）判队空（3）FRONT（Q）取队头元素）取队头元素,队中元素保持不变队中元素保持不变（4）ENQUEUE（Q,x)将元素将元素x入队入队（5）DEQUEUE（Q）出队）出队,函数返回原队头元素函数返回原队头元素2022-8-19数据结
29、构613.3.2 顺顺 序序 队队 列列1 定义：定义：采用采用的队列称为的队列称为顺序队列顺序队列。rear指向当前队尾元素的位置指向当前队尾元素的位置2 顺序队列存储结构描述如下：顺序队列存储结构描述如下：typedef struct datatype datamaxsize;int front,rear;sequeue;sequeue *sq;2022-8-19数据结构624 3 2 1 0sq-rearsq-front sq-rear4 3 2 1 0DCBA4 3 2 1 0DC 空队列空队列 ABCD入队入队 AB出栈出栈sq-front sq-front sq-rear3 顺序队
30、列指针图示顺序队列指针图示4 顺序队列基本运算顺序队列基本运算初始时，初始时，sqrear=sq front=-1,在不考虑溢出的情况下，在不考虑溢出的情况下，入队和出队的运算如下：入队和出队的运算如下：入队：入队：sq rear+;sq datasq rear=x;出队：出队：sq front+;2022-8-19数据结构63队空：队空：sq rear=sq front队满：队满：sq rear sq front=maxsize下溢：下溢：队空时，若要进行出队操作时发生队空时，若要进行出队操作时发生上溢：上溢：队满时，进行入队操作时出现。队满时，进行入队操作时出现。“假上溢假上溢”：当当 s
31、q-rear=maxsize-1但队列并不但队列并不满满时进行入队操作时进行入队操作.sqrear=4sqfront=143210edcba这种情况（即这种情况（即sq-rear=maxsize-1)下若要进行入队运算下若要进行入队运算,sqrear的值的值将超出下标范围，故不能进行这将超出下标范围，故不能进行这种运算，但此时整个队列空间并种运算，但此时整个队列空间并没用完。没用完。4 几种特殊情况几种特殊情况2022-8-19数据结构64v解决解决“假上溢假上溢”的方法有两种：的方法有两种：（1）当元素出队或出现假上溢时，移动队列元素。）当元素出队或出现假上溢时，移动队列元素。sqrear=
32、4sqfront=143210edcbaedc43210sqrear=2sqfront=-1移动元素后移动元素后（2）采用循环队列：即）采用循环队列：即sq-data0 接在接在sq-datamaxsize-1之后之后循环队列循环队列的示意图的示意图054321sqrear=0sqfront=42022-8-19数据结构65采用循环队列采用循环队列后，进行入队和出队运算时，头、尾指针后，进行入队和出队运算时，头、尾指针加加1操作应如下进行：操作应如下进行：出队：出队：sq front=(sq front+1)%maxsize;入队：入队：sq rear=(sq rear+1)%maxsize;
33、循环队列如何判断队空和队满循环队列如何判断队空和队满?方法一：引入标志方法一：引入标志flag 若若(sq front=sq rear)&(flag=0),则队空则队空,不能出栈。不能出栈。若若(sq front=sq rear)&(flag=1),则队满则队满,不能入栈。不能入栈。054321sqrear=5sqfront=5054321sqfront=5sqrear=42022-8-19数据结构66 方法二：牺牲一个元素的空间（方法二：牺牲一个元素的空间（sq-datasq-front)，避免队满时头、尾指针指向同一位置。避免队满时头、尾指针指向同一位置。若若 sq front=sq re
34、ar，则队空。，则队空。若若(sq rear+1)%maxsize=sq front，则队满。，则队满。054321sqrear=1sqfront=1054321sqfront=5sqrear=42022-8-19数据结构673.3.3 链链 队队 列列1、定义：采用链式存储结构的队列称为、定义：采用链式存储结构的队列称为链队列。链队列。（是限（是限制在表头删除在表尾插入的单链表）制在表头删除在表尾插入的单链表）2 2、链队列存储结构描述链队列存储结构描述 typedef struct linklist *front,*rear;linkqueue;linkqueue *q;为了运算实现的方便
35、，在队头结点前引入一个头结为了运算实现的方便，在队头结点前引入一个头结点。初始时（即队空）链队的头、尾指针均指向头结点。点。初始时（即队空）链队的头、尾指针均指向头结点。front rear q头结点头结点qrearfront rear q头结点头结点 q front队头结点队头结点q-front=q-rear2022-8-19数据结构681）入队）入队ENQUEUE（q,x)类似于单链表的尾插法类似于单链表的尾插法2022-8-19数据结构692）出队）出队qrearfront rear q头结点头结点 q front队头结点队头结点*sfront rear q头结点头结点a1*s fron
36、t rear q头结点头结点S=q-front-next;q-front-next=s-next;free(s);S=q-front-next;q-front-next=s-next;free(s);队列长度等于队列长度等于1时，不但修改头结点的指针域，还需尾指针。时，不但修改头结点的指针域，还需尾指针。队列长度大于队列长度大于1时，只需修改头结点的指针域，尾指针不变。时，只需修改头结点的指针域，尾指针不变。2022-8-19数据结构70解决方法解决方法：出队时只修改头指针，删除头结点，使链队列：出队时只修改头指针，删除头结点，使链队列上的队头结点成为新的链表的头结点，队列上的第上的队头结点成
37、为新的链表的头结点，队列上的第2个结个结点成为队头结点。即物理上删除头结点，逻辑上删除对头点成为队头结点。即物理上删除头结点，逻辑上删除对头结点。即使当前队列长度为结点。即使当前队列长度为1，也不用修改尾指针。，也不用修改尾指针。qrearfront rear q头结点头结点 队头结点队头结点*s2022-8-19数据结构71串串(即字符串）是一种特殊的线性表，其每个结点仅由一即字符串）是一种特殊的线性表，其每个结点仅由一个字符组成。个字符组成。4.1 串及其运算串及其运算4.1.1 串的基本概念串的基本概念 1.串串(string):是由是由零个或多个字符零个或多个字符组成的组成的有限有限序
38、列。序列。一般记为一般记为S=“a1a2.an”,其中：其中：S为串名，为串名，a1a2an为串值；为串值；ai(1=i=n)可可 以是字母、数字和其它字符；以是字母、数字和其它字符；注意：注意：仅含一个空格的串（仅含一个空格的串（“”）和空串（和空串（“”）是不是不同的两个串。同的两个串。2.串长度：串长度：串中所含的字符个数串中所含的字符个数 空串：空串：长度为零的串（不含任何字符，和空格串严格区分长度为零的串（不含任何字符，和空格串严格区分）第四章第四章 串串2022-8-19数据结构724.子串在主串中的序号：子串在主串中的序号：子串在主串中第一次出现时其第子串在主串中第一次出现时其第
39、一个字符在主串中的序号。一个字符在主串中的序号。S1=“I am a student.”S2=“student”S2在在S1中的序号为中的序号为83.子串：子串：串中任意个串中任意个连续的连续的字符组成的子序列字符组成的子序列,该串相应称该串相应称为为主串主串。空串为任意串的子串，任意串为其自身的子串空串为任意串的子串，任意串为其自身的子串。两串相等两串相等当且仅当两串长度相等且对应位置上的字符相同。当且仅当两串长度相等且对应位置上的字符相同。5.在程序中使用的串可分为在程序中使用的串可分为串常量串常量和和串变量串变量S2=“student”将串常量命名为将串常量命名为S2char objec
40、t=“data structure”第四章第四章 串串2022-8-19数据结构734.1.2 串的基本运算串的基本运算 串的基本运算有九种，具体如下串的基本运算有九种，具体如下（p61）（1）赋值：）赋值：=（2）联接：）联接：strcat(ST1,ST2)（3）求串长：）求串长：strlen(S)（4）求子串：）求子串：substr(S,i,j)（5）比较串的大小：）比较串的大小：strcmp(S,T)（6）插入：）插入：insert(S1,i,S2)（7）删除：）删除：delete(S,i,j)（9）置换：）置换：replace(S1,i,j,S2)，repl(S,T,V)2022-8-
41、19数据结构744.2 串的存储结构串的存储结构 串可以分别采用顺序顺序、链式链式和索引索引存储结构实现存储。1）用字符数组描述）用字符数组描述1、顺序存储、顺序存储 串中的字符被顺序地存储在内存中相邻的存储单元中。串中的字符被顺序地存储在内存中相邻的存储单元中。采用顺序存储结构的串称为采用顺序存储结构的串称为顺序串顺序串。H o w a r e y o u?.串串S的顺序存储示意图的顺序存储示意图S=“How are you?”#define maxsize 32char smaxsize;2022-8-19数据结构75 ）顺序串存储结构描述：顺序串存储结构描述：#define maxsiz
42、e 128;typedef struct char chmaxsize;int curlen;seqstring;串字符存串字符存储空间储空间串长度串长度 缺点：缺点：顺序串上插入、删除运算不方便。顺序串上插入、删除运算不方便。2022-8-19数据结构76 2.链式存储链式存储 采用链式存储结构的串称为采用链式存储结构的串称为链串链串，链串中结点的数据，链串中结点的数据域既可存储单个字符，也可存储多个字符，结点数据域域既可存储单个字符，也可存储多个字符，结点数据域存储字符的个数称为存储字符的个数称为结点的大小结点的大小。显然，结点大小大于显然，结点大小大于1的链串，其结点的存储密度提高的链串
43、，其结点的存储密度提高了，但同时也带来了了，但同时也带来了问题问题：(1)如何处理链串的最后一个结点，因为串所含字符如何处理链串的最后一个结点，因为串所含字符数不一定是结点大小的整数倍。数不一定是结点大小的整数倍。(2)插入、删除运算实现起来不方便。插入、删除运算实现起来不方便。(p64)2022-8-19数据结构77 typedef struct linknode char data;struct linknode *next;linkstring;linkstring *s;如果结点大小不为如果结点大小不为1，则此处应说明一个字则此处应说明一个字符数组。符数组。链串存储结构描述如下：链串存
44、储结构描述如下：2022-8-19数据结构78 1）带长度的名字表）带长度的名字表 2）带末指针的名字表）带末指针的名字表 3）带特征位的名字表）带特征位的名字表 4）带位移量的名字表）带位移量的名字表 3.索引存储索引存储特点：特点：将串的串名作为关键字组织将串的串名作为关键字组织名字表名字表(即即索引表索引表)，名，名字表中的每一项记录了字表中的每一项记录了串名串名和串值存放单元的起址及确定和串值存放单元的起址及确定串长的有关数据。串长的有关数据。名字表名字表一般采用顺序存储方式存储。其组织形式主要一般采用顺序存储方式存储。其组织形式主要有如下几种：有如下几种：(p65)2022-8-19
45、数据结构79 本节讨论子串定位运算本节讨论子串定位运算(也称模式匹配也称模式匹配)在顺序串上的实在顺序串上的实现现,及在链串上的实现及在链串上的实现子串定位运算的含意：子串定位运算的含意：4.3 串运算的实现串运算的实现设有两个顺序串设有两个顺序串S和和T，且：，且：S=“s0s1s2.sn-1”目标目标 T=“t0t1t2.tm-1”模式模式 匹配有两种结果：匹配有两种结果：若在若在S中找到了模式为中找到了模式为T的子串（若有的子串（若有多个模式为多个模式为T的子串，只需找出第一个）时，则返回该子的子串，只需找出第一个）时，则返回该子串在串在S中的位置，这种情况称为匹配成功；否则称为匹配中的
46、位置，这种情况称为匹配成功；否则称为匹配失败。失败。2022-8-19数据结构80 1.朴素的匹配算法朴素的匹配算法基本思想：基本思想：初始时，从初始时，从S的第一个字符开始将的第一个字符开始将T的第一个字的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如符与其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在匹配成功，则返回子串在S中的位置，否则，将中的位置，否则，将T向右移动向右移动一个字符位置，从一个字符位置，从T的第一个字符开始与的第一个字符开始与S中第二个字符进中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二行比较，并在相等的情况下逐个比较后
47、续字符，进行第二趟匹配，成功则返回子串在趟匹配，成功则返回子串在S中的位置，否则，中的位置，否则，T再向右移再向右移动一个字符位置，进行第三趟匹配，如此反复，或匹配成动一个字符位置，进行第三趟匹配，如此反复，或匹配成功，或当功，或当T右移到无法与右移到无法与S继续进行比较时，匹配失败。继续进行比较时，匹配失败。a b a b c a b c a c b a b a b c a c2022-8-19数据结构81 1.朴素的匹配算法朴素的匹配算法基本思想：基本思想：初始时，从初始时，从S的第一个字符开始将的第一个字符开始将T的第一个字的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如符与
48、其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在匹配成功，则返回子串在S中的位置，否则，将中的位置，否则，将T向右移动向右移动一个字符位置，从一个字符位置，从T的第一个字符开始与的第一个字符开始与S中第二个字符进中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二行比较，并在相等的情况下逐个比较后续字符，进行第二趟匹配，成功则返回子串在趟匹配，成功则返回子串在S中的位置，否则，中的位置，否则，T再向右移再向右移动一个字符位置，进行第三趟匹配，如此反复，或匹配成动一个字符位置，进行第三趟匹配，如此反复，或匹配成功，或当功，或当T右移到无法与右移到无法与S继续进行比
49、较时，匹配失败。继续进行比较时，匹配失败。a b a b c a b c a c b a b a b c a c2022-8-19数据结构82 a b a b c a b c a c b a b 设设S=“ababcabcacbab”T=“abcac”a b c a ci=0j=0i=1j=1i=2j=2i指针回溯的位置为：指针回溯的位置为：i=i-j+1（i的值为的值为1）1.朴素的匹配算法朴素的匹配算法2022-8-19数据结构83 a b a b c a b c a c b a b 设设S=“ababcabcacbab”T=“abcac”a b c a ci=1j=0i指针回溯的位置为：
50、指针回溯的位置为：i=i-j+1（i的值为的值为2）2022-8-19数据结构84设设S=“ababcabcacbab”T=“abcac”a b a b c a b c a c b a b a b c a ci=2j=0i=3j=1i=4j=2i=5j=3i=6j=4i指针回溯的位置为：指针回溯的位置为：i=i-j+1（i的值为的值为3）2022-8-19数据结构85 a b a b c a b c a c b a b 设设S=“ababcabcacbab”T=“abcac”a b c a ci=3j=0i指针回溯的位置为：指针回溯的位置为：i=i-j+1（i的值为的值为4）2022-8-19
