数据结构第四章

数据结构第四章第1页，共42页。第2页，共42页。4.1 串的抽象数据类型的定义串的抽象数据类型的定义4.2 串的表示和实现串的表示和实现第3页，共42页。4.1 串的抽象数据类型的定义串的抽象数据类型的定义串：是由零个或多个字符组成的有限序列。串：是由零个或多个字符组成的有限序列。s=a1a2 an空串：零个字符的串。空串：零个字符的串。长度：串中字符的数目。长度：串中字符的数目。子串：串中任意个连续的字符组成的子序列。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。主串：包含子串的串。位置：通常称字符在序列中的序号为位置：通常称字符在序列中的序号为 该字符在串中的位置。该字符在串中的位置。第4页，共42页。4.1 串的抽象数据类型的定义如下串的抽象数据类型的定义如下：ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,ai D,i=2,.,n 串是有限长的字符序串是有限长的字符序列，由一对单引号相列，由一对单引号相括，如括，如:a string 第5页，共42页。根本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,S2)第6页，共42页。SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)ADT String第7页，共42页。StrEmpty(S)初始条件：串S存在。操作结果：假设 S 为空串，那么返回 true，否那么返回 false。表示空串，空串的长度为零。第8页，共42页。StrCompare(S,T)初始条件：串 S 和 T 存在。操作结果：假设S T，那么返回值 0；假设S T，那么返回值 0；假设S T，那么返回值 0。例如：例如：StrCompare(data,state)0第9页，共42页。Concat(&T,S1,S2)初始条件：串 S1 和 S2 存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。例如例如：Concat(T,man,kind)求得 T=mankind 第10页，共42页。SubString(&Sub,S,pos,len)初始条件：操作结果：用 Sub 返回串 S 的第 pos 个 字符起长度为 len 的子串。串 S 存在，1posStrLength(S)且 0lenStrLength(S)-pos+1。第11页，共42页。例如：例如：SubString(sub,commander,4,3)子串为子串为“串中的一个字符子序列串中的一个字符子序列求得 sub=man ;SubString(sub,commander,1,9)SubString(sub,commander,9,1)求得 sub=r 求得 sub=commander 第12页，共42页。SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系起始位置和子串长度之间存在约束关系长度为长度为 0 的子串为的子串为“合法串合法串第13页，共42页。Index(S,T,pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：假设主串 S 中存在和串 T 值一样 的子串,那么返回它在主串 S 中第pos 个字符之后第一次出现的位置;否那么 函数值为0。第14页，共42页。假设 S=abcaabcaaabc,T=bca Index(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;“子串在主串中的位置意指子串中的第一个字符在主串中的位序。第15页，共42页。Replace(&S,T,V)初始条件：串S,T和 V 均已存在，且 T 是非空串。操作结果：用 V 替换主串 S 中出 现的所有与模式串T 相等的不重叠的子串。第16页，共42页。例如：假设 S=abcaabcaaabca,T=bca 假设 V=x,那么经置换后得到 S=axaxaax 假设 V=bc,那么经置换后得到 S=abcabcaabc bcabcabca第17页，共42页。StrInsert(&S,pos,T)初始条件：串S和T存在，1posStrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。例如：例如：S=chater ，T=rac ，那么执行那么执行 StrInsert(S,4,T)之后得到之后得到 S=character 第18页，共42页。StrDelete(&S,pos,len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符 起长度为len的子串。第19页，共42页。对于串的根本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供以下串处理函数：第20页，共42页。串赋值串赋值StrAssign、串复制、串复制Strcopy、串比较串比较StrCompare、求串长、求串长StrLength、串联接串联接Concat以及求子串以及求子串SubString 等六种操作构成串类型的最小操作子集。等六种操作构成串类型的最小操作子集。在上述抽象数据类型定义的13种操作中，即：这些操作不可能利用其他串操作来实现，反之，其他串操作除串去除ClearString和串销毁DestroyString外可在这个最小操作子 集上实现。第21页，共42页。串的逻辑构造和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的根本操作和线性表有很大差异。在线性表的根本操作中，大多以“单个元素作为操作对象；在串的根本操作中，通常以“串的整体作为操作对象。第22页，共42页。在程序设计语言中，串只是作为在程序设计语言中，串只是作为 输入或输出的常量出现，那么只需存储输入或输出的常量出现，那么只需存储 此串的串值，即字符序列即可。但在此串的串值，即字符序列即可。但在 多数非数值处理的程序中，串也以变多数非数值处理的程序中，串也以变 量的形式出现。量的形式出现。4.2 串的表示和实现串的表示和实现第23页，共42页。一、串的定长顺序存储表示一、串的定长顺序存储表示二、串的堆分配存储表示二、串的堆分配存储表示三、串的块链存储表示三、串的块链存储表示第24页，共42页。#define MAXSTRLEN 255 /用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN+1;/0号单元存放串的长度一、串的定长顺序存储表示一、串的定长顺序存储表示第25页，共42页。按这种串的表示方法实现的串的运算时，其根本操作为“字符序列的复制 串的实际长度可在这个预定义长度的串的实际长度可在这个预定义长度的范围内随意设定，超过予定义长度的串范围内随意设定，超过予定义长度的串值那么被舍去，称之为值那么被舍去，称之为“截断截断 特点特点:第26页，共42页。Status Concat(SString S1,SString S2,SString&T)/用用T返回由返回由S1和和S2联接而成的新串。假设未截断联接而成的新串。假设未截断,那么返回那么返回TRUE，否那么，否那么FALSE。return uncut;/Concat例如：例如：串的联接算法中需分三种情况处理：T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断 else if(S10 MAXSTRSIZE)/截断 else /截断(仅取S1)T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLEN uncut=FALSE;第27页，共42页。typedef struct char*ch;/假设是非空串，那么按串长分配假设是非空串，那么按串长分配 /存储区，否那么存储区，否那么 ch 为为NULL int length;/串长度串长度 HString;二、串的堆分配存储表示二、串的堆分配存储表示第28页，共42页。通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和 free()进展串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆。C语言中的串以一个空字符为完毕符，串长是一个隐含值。这类串操作实现的算法为:先为新生成的串分配一个存储空间，然后 进展串值的复制。第29页，共42页。三、串的块链存储表示三、串的块链存储表示也可用链表来存储串值，由于串的数据元也可用链表来存储串值，由于串的数据元素是一个字符，因此用链表存储时，通常素是一个字符，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一一个结点中存放的不是一个字符，而是一个子串。个子串。存储密度存储密度=数据元素所占存储位实际分配的存储位第30页，共42页。#define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk /结点构造 char chCHUNKSIZE;struct Chunk *next;Chunk;typedef struct /串的链表构造 Chunk*head,*tail;/串的头和尾指针 int curlen;/串的当前长度 LString;第31页，共42页。例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长构造(80个字符),行和行之间用指针相联接。实际应用时，可以根据问题所需来设置结点的大小。第32页，共42页。本章作业本章作业1.1.两个串相等的充分必要条件是两个串相等的充分必要条件是什么？什么？2.2.空串与空格串是一样的吗？为空串与空格串是一样的吗？为什么？什么？第33页，共42页。习题一习题一1.for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;On32.for(i=1;i=n;i=2*i)+x;Olog2n 3.s=0;for(i=0;i=n;i+)for(j=0;j=n;j+)for(k=0;knext=p-next ;2p-next=s;3t=p-data;4p-data=s-data ;5s-data=t ;9.在一个单链表中删除在一个单链表中删除p所指结点时，应执行以下操作：所指结点时，应执行以下操作：q=p-next;p-data=p-next-data;p-next=p-next-next ;free(q);第36页，共42页。习题一习题一10.从顺序表中删除所有值为从顺序表中删除所有值为x的元素。的元素。void delall(Sqlist&L)int i=0,j;while(iL.len&L.datai!=x)i+;for(j=i+1;jnext;While(p-cost next;If (p-cost=h&p!=null)p-num=p-num+m;Else t=(LNode*)malloc(sizeof(LNode);t-cost=h;t-num=m;q-next=t;t-next=p;第38页，共42页。习题一习题一12假设一个栈的输入序列是假设一个栈的输入序列是1，2，3，n，输出序列的第一个元素是，输出序列的第一个元素是n，那么第，那么第i个个输出元素是输出元素是 D 。A 不确定不确定 B n-i C n-i-1 D n-i+113设栈设栈S和队列和队列Q的初始状态为空，元素的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈依次通过栈S，一，一个元素出栈后即进入队列个元素出栈后即进入队列Q，假设，假设6个元素出队的顺序是个元素出队的顺序是e2、e4、e3、e6、e5、e1，那，那么栈么栈S的容量至少应该是的容量至少应该是 C 。A 6 B 4 C 3 D 214一个栈的入栈序列是一个栈的入栈序列是1，2，3，4，5，那么栈的不可能的输出序列是，那么栈的不可能的输出序列是 C 。A 54321 B 45321 C 43512 D 12345 15在操作序列在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？之后，栈顶元素和栈底元素分别是什么？push(k)表示整数表示整数k入栈，入栈，pop表示栈顶元素出栈。表示栈顶元素出栈。【解答】栈顶元素为【解答】栈顶元素为6，栈底元素为，栈底元素为1。第39页，共42页。习题一习题一16栈和队列是两种特殊的线性表，栈的操作特性是栈和队列是两种特殊的线性表，栈的操作特性是，队列的操，队列的操作特性是作特性是，栈和队列的主要区别在于，栈和队列的主要区别在于。【解答】后进先出，先进先出，对插入和删除操作限定的位置不同【解答】后进先出，先进先出，对插入和删除操作限定的位置不同17循环队列的引入是为了抑制循环队列的引入是为了抑制。【解答】假溢出【解答】假溢出18数组数组Qn用来表示一个循环队列，用来表示一个循环队列，front为队头元素的前一个位置，为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为为队尾元素的位置，计算队列中元素个数的公式为。【解答】【解答】rear-front+n%n19用循环链表表示的队列长度为用循环链表表示的队列长度为n，假设只设头指针，假设只设头指针，那么出队和入队的时间复杂度分别是那么出队和入队的时间复杂度分别是 和和。【解答】【解答】(1)，(n)第40页，共42页。谢谢！第41页，共42页。谢谢大家！第42页，共42页。