首页计算机计算机基础数据结构与算法 04 第4章 串.pptx

04 第4章 串.pptx

页数：39页文件大小：155.4 KB来源： 数据结构与算法ppt课件

本课件讲解串的基本概念与有关术语，给出串的抽象数据类型定义与子串定位算法，随后展开定长顺序存储、堆分配存储与块链存储三种表示方式，并以文本编辑中的页表行表说明串操作的实际应用。

第四章串章节封面页，标示本章讲串类型定义、串的三种表示与实现、串操作应用举例与本章重点
串的概述页，说明计算机非数值处理的对象多为字符串，姓名地址、货物产地等都以字符串形式出现
内容提要页，列出掌握串的基本概念、基本运算、静态与动态存储结构及串连接、求子串与模式匹配的目标
查看本课件的文字版（共 39 页，供检索与复制）

第1页：第四章串

第四章串

第2页：串的概述

有关串的概述

  • 计算机非数值处理的对象是字符串
  • 字符串是计算机语言需要考虑的一种变量类型
  • 在计算机事务处理程序中，许多操作对象都是以字符串形式出现，如顾客的姓名和地址、货物的名称和产地
  • 在文字处理系统、人机交互系统等系统都需要以字符串作为处理对象
  • 不同应用目的对串的要求也不一样，因而必须根据具体情况使用适当的存储结构

第3页：第四章内容提要

内容提要:

  • 本章目的：掌握串的基本概念和串的基本运算、掌握串的静态存储结构和串的动态存储结构，串的连接、求子串和简单串的模式配匹等算法的实现
  • 第一节串类型的定义
  • 第二节串的表示与实现
  • 第三节串的应用操作举例
  • 本章重点

第4页：第一节串类型的定义

第一节串类型的定义

第5页：串的定义与长度

东华理工学院程朋根

  • 串(String)(或字符串)是由零个或多个字符组成的有限序列，一般记为：s=‘a1a2…an’(n0)
  • 其中s是串名，用单引号或双引号括起来的字符系列是串的值ai可以是字母、数字或其他字符
  • 串必须用一队单引号括起来，但单引号不属于串
  • 串中字符的数目n称为串的长度s=‘Cheng’,n=5
  • 零个字符的串称为空串，它的长度为零，例如：s=‘’，n=0(1)有关术语

第6页：子串、主串与串相等

串中任意连续的字符组成的子序称为串的子串，相应地包含子串的串称为主串

  • 例如：str=‘BEIJING’str1=‘BEI’str2=‘JING’
  • 字符在串系列中的序号叫做该字符在串中的位置
  • 子串在主串中的位置：则以子串的第一个字符在主串中的位置来表示
  • 字符相等：当且仅当两个字符的长度相等，并且各个对应位置的字符都相等时(1)有关术语(续)

第7页：串变量名与空格串

注意串变量名与串值的区别：tsing=‘TSING’中tsing为串变量名，字符系列TSING为串值

  • 空格常常是串的字符集中的一个元素，例如s=‘Wearestudent’中包含空格
  • 由一个或多个空格组成的串称为空格串，例如a=‘’,b=‘’(1)有关术语(续)

第8页：串与线性表的区别

串与线性表的区别

  • 串的逻辑结构与线性表极为相似，区别仅在于串的数据对象约束为字符集
  • 但基本操作有较大的差别，操作对象也不同(1)有关术语(续)操作操作对象数据对象插入、删除单个元素任意结构线性表求子串、插入或删除子串串的整体字符集串

第9页：ADTString的定义

(2)串的抽象数据类型定义

  • ADTString{
  • 数据对象：D={ai|aiCharacterset, i=1,2,…,n,n0}
  • 数据关系：R={< ai-1,ai>|ai-1,aiD,i=2,…,n}
  • 基本操作：StrAssign(&T,chars)//生成值为chars的串TStrCopy(&T,S)//由串S复制得串TStrCompare(S,T)//比较两串的大小StrLength(S)//求c串的长度

第10页：串的基本操作

Concat(&T,S1,S2)//将S1,S2连接成新串TSubString(&Sub,S,pos,len)//用Sub返回串S的子串Index(S,T,pos)//若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置StrDelete(&S,pos,len)//从串S中删除第pos个字符起长度为len的子串…………

  • }ADTString

第11页：子串定位算法Index

(3)求子串在主串中第一次出现的位置

  • intIndex(StringS,StringT,intpos){
  • if(pos>0){Dn=StrLength(S);m= StrLength(T);i =pos;Dwhile(i<=n-m+1){SubString(sub,S, i,m);//从S串中的第i位置起顺序提取m个字符串赋给subif(StrCompare(sub,T)!=0)++i;elsereturni;D}//while
  • }//if
  • return0;
  • }nmposn-m+1

第12页：第二节串的表示和实现

第二节串的表示和实现

第13页：串的三种存储结构

串的存储结构有三种

  • 静态存储结构（顺序存储结构）charSString[100];
  • 动态存储结构（堆分配存储结构）用C语言的动态分配函数malloc,free来管理
  • 块链存储结构DCBAHGFE###Ihead

第14页：2.1定长顺序存储表示

2.1定长顺序存储表示

  • 与线性表的顺序存储结构相似，用一组地址连续的存储单元存储串值的字符序列
  • 可以用定长数组描述：＃defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1]//０号单元存放串的长度或定义为：typedefstructqString{ch[MAXSTRLEN+1];intlen;}SEQSTRING;

第15页：串长的两种表示方法

如果一个串的长度超过予定义长度，则超过部分被舍去

  • 串的长度有两种表示方法：
  • 以下标为０的数组存放串的实际长度,如Pascal语言
  • 以特殊字符结束，串长隐含，如C的字符串结束标志是‘\０’

第16页：串连接算法Concat

东华理工学院程朋根(1)串联接算法

  • //用T返回由S1和S2连接而成的新串，
  • StatusConcat(SString&T,SStringS1,SStringS2){
  • if(S1[0]+S2[0]<=MAXSTRLEN){//未截断，s1[0],s2[0]为S1,S2的长度T[1…S1[0]]=S1[1…S1[0]];T[(S1[0]+1)…(S1[0]+S2[0])]=S2[1…S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;
  • }
  • elseif(S1[0]<MAXSTRLEN){//截断S2T[1…S1[0]]=S1[1…S1[0]];T[S1[0]+1…MAXSTRLEN]=S2[1…MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;
  • }

第17页：串连接算法的截断处理

else{//截断S1,仅取S1T[1…MAXSTRLEN]=S1[1…MAXSTRLEN];uncut=FALSE;

  • }
  • returnuncut;
  • }//未截断，返回TRUE；截断，返回FALSE

第18页：求子串算法SubString

(2)求子串算法

  • StatusSubString(SString&Sub,SStringS,intpos,intlen){
  • if(pos<1||pos>s[0]||len<0||len>S[0]-pos+1)returnERROR;
  • Sub[1…len]=S[pos…pos+len-1]
  • Sub[0]=len;
  • returnOK;
  • }S[0]poslen

第19页：顺序存储结构的讨论

(3)讨论

  • 顺序存储结构中，串操作的原操作为“字符序列的复制”
  • 操作时间的复杂度与复制的字符序列的长度有关
  • 串的长度超过上界时，会出现截尾现象
  • 克服办法是不限定字符串长度，即动态分配串值的存储空间

第20页：串的堆分配存储表示

思想：仍以一组地址连续的存储单元存放串值字符系列，但它们的存储空间是在程序执行过程中动态分配而得

  • 用C语言的动态分配函数malloc,free来管理
  • 串的堆分配存储表示结构为Typedefstruct{Char*ch;／／若为空，ch =NULLintlength;//串长度}HString
  • 基本操作有：生成字符串、求串长度、串比较、串连接、求子串等
  • 操作仍是基于“字符序列的复制”进行2.2堆分配存储表示

第21页：生成串算法StrAssign

基本操作算法描述StatusStrAssign(HString&T,char*chars){ if(T.ch)free(T.ch)//释放T原有空间 for(i=0,c=chars; c; ++i,++c)//求chars长度 if( !i){ T.ch=NULL,T.length= 0}else{ if(!(T.ch= (char *)malloc(i *sizeof(char))))exit(OVERFLOW); T.ch[0…i-1]=chars[0…i-1]; T.length=i; } returnOK; }

第22页：串比较算法StrCompare

基本操作算法描述(续)

  • //比较两字符串，S>T,返回值>0;S=T,返回值=0;S<T,返回值<0;
  • intStrCompare(HStringS,HStringH){for(i=0;i<S.length&&i<T.length;++i)if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;//为0
  • }
  • 例如：S=‘ABCDE’，T=‘ABAB’,则S>T则S<TS=‘ABCDE’,T=‘ABGH’,S=‘ABCDE’,T=‘ABCDE’,则S=T

第23页：串连接算法Concat（堆分配）

//连接两个字符串成新串 StatusConcat(HString&T,HStringS1,HStringS2){ if(T.ch)free(T.ch);if(!(T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))exit(OVERFLOW); T.ch[0…S1.length-1]=S1.ch[0…S1.length-1]; T.length=S1.length+S2.length; T.ch[S1.length…T.length-1]=S2.ch[0…S2.length-1]; returnOK; } S1.length-1S１S２0

第24页：求串长算法StrLength

基本操作算法描述(续)

  • //返回字符串的长度
  • intStrLength(HStringS){returnS.length;
  • }

第25页：求子串算法SubString（堆分配）

//用Sub返回S第pos个字符起长度为len的子串 StatusSubString(HString&Sub,HstringS,intpos,intlen){ if(pos<1||pos>S.length||len<0||len>S.length–pos+1)returnERROR; if(Sub.ch)free(Sub.ch); if(!len){ Sub.ch=NULL; Sub.length=0; }else{ Sub.ch=(char*)malloc(len*sizeof(char)); Sub.ch[0…len-1]=S[pos-1…pos+len-2]; } returnOK; } pos-10pos

第26页：2.3串的块链存储表示

2.3串的块链存储表示

  • 思想：与线性表的链式存储相类似，但每个结点可以存放一个字符或多个字符，例如DCBAHGFE###IheadBAChead
  • 当串长不一定结点的整数倍，最后一个结点不一定会被大串值填满，可补上特殊的字符，如“#”

第27页：块链存储结构设计

(1)存储结构设计

  • ＃defineCHUNKSIZE80//块大小
  • TypedefstructChunk{Charch[CHUNKSIZE];structChunk*next;
  • }Chunk;
  • Typedefstruct{Chunk*head,*tail;//串的头指针和尾指针intcurlen;//串当前长度
  • }

第28页：块链存储结构的特点

(2)特点

  • 串操方法：从头到尾顺序扫描，无需建立双向链
  • 尾指针目的：为了便于串的联接操作，但要处理前串尾部的无效字符
  • 结点大小：影响对串的处理速度
  • 存储密度：=串值所占的存储位/实际分配的存储位
  • 存储密度小(如为1),运算处理方便,但存储占用量大
  • 方便字符串的联接操作，但其它操作复杂
  • 操作方法的实现:类似于线性表的链表存储结构

第29页：链式串基本操作应用程序

链式串基本操作应用程序

第30页：第四节串操作应用举例

第四节串操作应用举例

第31页：文本编辑的文本结构

文本编辑

  • 文字编辑应用：书刊编辑排版、公文信函、源程序编辑等
  • 文字编辑的实质：修改字符的形式或格式
  • 基本操作：查找、插入和删除
  • 文本结构：树型结构，串与子串的关系
  • 为编辑方便，文本可以设计成由页表和行表组成，相应地设立页指针，行指针
  • 页表：页号、起始行号
  • 行表：行号、起始地址、长度文件页1页2…页m行1行2…行n

第32页：文本编辑的插入与删除思路

插入、删除插入思路

  • 在行中插入或删除若干字符
  • 如果该行长度没有超分配给它的存储空间，则修改行表中该行的长度
  • 否则，为该行重新分配存储空间，同时修改该行的起始地址
  • 在页中插入或删除一行，涉及行表的操作
  • 如果被删除的是所在页的起始行，则修改页表中相应页的起始行号
  • 否则，只需在行表中插入或删除改行，为查找方便，行表按行号的递增顺序存储
  • 在页表中插入或删除一页，只涉及页表记录的顺序维护

第33页：页表与行表示例

……202531676……起始行页号285->286长度起始地址行号40120228540120228523->481242->144528628->201265287321293288321293288………页表行表

第34页：本章重点

本章重点

  • 串定义的有关术语
  • 串的三种表示方法
  • 及基本操作算法

第35页：习题（一）

习题：

  • 1、空串与空格（白）串是相同的，这种说法是不对的。
  • 2、串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。
  • 3、S1=‘ABCDEFG’，s2=‘PQRST’，假设con(x,y)为连接两字符串函数，subs(s,i,j)返回串s中从第i个位置起的j个字符，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串为：BCDEFEF
  • 4、串的两种最基本的存储方式是顺序存储方式和链式存储方式。
  • 5、采用顺序结构存储字符串s，编写一个函数删除s中第i个字符开始的j个字符。

第36页：字符串拷贝算法assign

//将字符串t拷贝到字符串s中，它们的结构不同，串的内容一致

  • voidassign(HString*s,chart[]){inti=0;while(t[i]!='\0'){s->ch[i]=t[i];i++;}s->ch[i] ='\0';s->len=i;
  • }

第37页：字符串连接算法concat

voidconcat(HString&r,HStrings1,HStrings2) { inti,j; if(r.ch)free(r.ch);if(!r.ch){ *****; exit; }i<s1.len; i++)r.ch[i]=s1.ch[i]; for(j=0; j<=s2.len; j++)r.ch[s.len+j]=s2.ch[j]; r.len=i+j; return; }

第38页：求子串算法substr

strtypesubstr(strtypes,inti,intk)

  • {strtypet;intj;for(j=i;j<i+k;j++)t.str[j-i]=s.str[j];t.len=k;t.str[t.len]='\0';return(t);
  • }

第39页：

《数据结构与算法》课件目录

内容类似资源

顶部目录