数据结构 串
- 格式：ppt
- 大小：612.00 KB
- 文档页数：52
下载文档原格式
合集下载
数据结构串串的基本概念串的存储结构与实现串的模式匹配
t.ch[i]=s1.ch[i]; for(i=s1.length;i<t.length;i++)
t.ch[i]=s2.ch[i-s1.length]; }
串删除
void strdelete(Hstring &s,int pos,int len) {
if(pos<1||pos>s.length-len+1||len<0||len>s.length){ cout<<"删除位置不合法"<<endl; return;
int flag=0; int i=0,j=1; if(s1[0]+s2[0]<=MAXSTRLEN) {
for(i=1;i<=s1[0];i++) t[i]=s1[i];
for(i=s1[0]+1;i<=s1[0]+s2[0];i++) t[i]=s2[j++];
t[0]=s1[0]+s2[0]; flag=1; //未截断 }
strempty(s) 初始条件：s为一个串 操作结果：若s为空串，则返回1
strcopy(&t,s) 初始条件：s为一个串 操作结果：把串s复制给t
strncpy(&sub,s,pos,len) 初始条件：s为一个串，pos为起始位置， 1≤pos≤strlength(s)-1,len≥0 操作结果：用sub返回串s的第pos个字符开⑩长度为len的子串
例：模式串t=“abcac”和主串s=“ababcabcaccabbc”匹配过程
第三二一 趟 a b a b c a b c a c c a b b c i=112734568901
t.ch[i]=s2.ch[i-s1.length]; }
串删除
void strdelete(Hstring &s,int pos,int len) {
if(pos<1||pos>s.length-len+1||len<0||len>s.length){ cout<<"删除位置不合法"<<endl; return;
int flag=0; int i=0,j=1; if(s1[0]+s2[0]<=MAXSTRLEN) {
for(i=1;i<=s1[0];i++) t[i]=s1[i];
for(i=s1[0]+1;i<=s1[0]+s2[0];i++) t[i]=s2[j++];
t[0]=s1[0]+s2[0]; flag=1; //未截断 }
strempty(s) 初始条件：s为一个串 操作结果：若s为空串，则返回1
strcopy(&t,s) 初始条件：s为一个串 操作结果：把串s复制给t
strncpy(&sub,s,pos,len) 初始条件：s为一个串，pos为起始位置， 1≤pos≤strlength(s)-1,len≥0 操作结果：用sub返回串s的第pos个字符开⑩长度为len的子串
例：模式串t=“abcac”和主串s=“ababcabcaccabbc”匹配过程
第三二一 趟 a b a b c a b c a c c a b b c i=112734568901
数据结构中的串
next[j] = max { k | 0<k<j 且使得 1…tk-1=tj-k+1…tj-1} 当集合不空 且使得t 1
首页
其他情况
上页 下页 退出
第四章
§4.4 串的应用
一、文本编辑 二、建立索引表
思考题： 思考题： 试写出判串S是否是回文的算法。 1、试写出判串S是否是回文的算法。 若串S= S=‘ STRING’以块链存储， 2、若串S=‘THIS IS A STRING’以块链存储，结点大小 链指针占4个字节， 32位 问存储密度是多少？ 为4，链指针占4个字节，即32位，问存储密度是多少？ 是两个但单链表存储的串，试设计一个算法， 3、若X和Y是两个但单链表存储的串，试设计一个算法， 找出X中第一个不在Y中出现的字符来。 找出X中第一个不在Y中出现的字符来。
首页
上页
下页
退出
第四章
§4.1 串类型的定义
三、C语言常用的字符串处理的标准函数： 语言常用的字符串处理的标准函数：
int strlen(char s); int strcmp(chars1,char s2); char strcpy(char to,char from); char strcat(char to,char from) 但在抽象数据类型定义的13种操作中， 13种操作中 但在抽象数据类型定义的13种操作中，串赋值 StrAssign、串复制StrCopy、串比较StrCompare、求串 StrAssign、串复制StrCopy、串比较StrCompare、 StrCopy StrCompare StrLength、串联接Concat以及求子串SubString Concat以及求子串SubString等 长StrLength、串联接Concat以及求子串SubString等6 种操作构成串类型的最小操作子集。 种操作构成串类型的最小操作子集。 例如，可利用判等、 例如，可利用判等、求串长和求子串等操作实现串 的定位函数 Index(S,T,pos) 和串的置换操作 Replace(S,T,V)。 。 换句话说，如果在高级程序设计语言中设有"串类 换句话说，如果在高级程序设计语言中设有 串类 的话， 种操作， 型"的话，提供的基本操作不能没有这 种操作，因为它 的话 提供的基本操作不能没有这6种操作 首页 上页 下页 退出 们不能通过其它串操作实现。 们不能通过其它串操作实现。
数据结构第5章 串和广义表
5.1 串的定义和基本运算
• （4）串的连接StrCat(S,T)。 • 初始条件：串S和T存在。 • 操作结果：将串T的值连接在串S的后面。 • （5）求子串SubString(Sub,S,pos,len)。 • 初始条件：串S存在，1≤pos≤StrLength(S)且
1≤len≤StrLength(S)-pos+1。 • 操作结果：用Sub返回串S的第pos个字符起长度为len的
1≤len≤StrLength(S)-pos+1。 • 操作结果：从串S中删除第pos个字符起长度为len的子串。 • （9）串的替换StrReplace(S,T,V)。 • 初始条件：串S，T和V存在，且T是非空串。 • 操作结果：用V替换串S中出现的所有与T相等的不重叠子
串。 • （10）判断串空StrEmpty(S)。 • 初始条件：串S存在。 • 操作结果：若串S为空串，则返回1；否则返回0。
• （1）非紧凑存储。设串S="Hello boy"，计算机字长为32 位（4个Byte），用非紧凑格式一个地址只能存一个字符， 如图5-2所示。其优点是运算处理简单，但缺点是存储空 间十分浪费。
• （2）紧凑存储。同样存储S="Hello boy"，用紧凑格式一 个地址能存四个字符，如图5-3所示。紧凑存储的优点是 空间利用率高，缺点是对串中字符处理的效率低。
•}
5.3 串的基本运算的实现
• （3）求子串操作。求串S从第pos位置开始，长度为len的 子串，并将其存入到串Sub中。操作成功返回1，不成功 返回0。其算法描述如下：
• int SubString(String *S,String *Sub,int pos,int len)
数据结构——第4章 串(C#)
将当前链串的所有结点?nstr将q结点插入到尾部将q结点插入到尾部将链串t的所有结点?nstr将q结点插入到尾部尾结点的next置为null返回新建的链串5求子串substrij返回当前串中从第i个字符开始的连续j个字符组成的子串ຫໍສະໝຸດ 第4章 串4.1 串的基本概念
4.1.1 什么是串 串（或字符串）是由零个或多个字符组成的有限序列。 记作str="a1a2…an"（n≥0），其中str是串名，用双引号括 起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一 个任意字符（字母、数字或其他字符），它称为串的元素， 是构成串的基本单位，串中所包含的字符个数n称为串的 长度，当n=0时，称为空串。
4.2 串的存储结构
4.2.1 串的顺序存储结构－顺序串
和顺序表一样，用一个data数组（大小为MaxSize）和 一个整型变量length来表示一个顺序串，length表示data数 组中实际字符的个数。 定义顺序串类SqStringClass如下：
class SqStringClass { const int MaxSize=100; public char[] data; //存放串中字符 public int length; //存放串长 public SqStringClass() //构造函数,用于顺序串的初始化 { data=new char[MaxSize]; length=0; } //顺序串的基本运算 }
（9）串输出DispStr() 将当前串s的所有字符构成一个字符串并输出。对应的算 法如下：
public string DispStr() { int i; string mystr=""; if (length==0) mystr = "空串"; else { for (i=0;i<length;i++) mystr+=data[i].ToString(); } return mystr; }
4.1.1 什么是串 串（或字符串）是由零个或多个字符组成的有限序列。 记作str="a1a2…an"（n≥0），其中str是串名，用双引号括 起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一 个任意字符（字母、数字或其他字符），它称为串的元素， 是构成串的基本单位，串中所包含的字符个数n称为串的 长度，当n=0时，称为空串。
4.2 串的存储结构
4.2.1 串的顺序存储结构－顺序串
和顺序表一样，用一个data数组（大小为MaxSize）和 一个整型变量length来表示一个顺序串，length表示data数 组中实际字符的个数。 定义顺序串类SqStringClass如下：
class SqStringClass { const int MaxSize=100; public char[] data; //存放串中字符 public int length; //存放串长 public SqStringClass() //构造函数,用于顺序串的初始化 { data=new char[MaxSize]; length=0; } //顺序串的基本运算 }
（9）串输出DispStr() 将当前串s的所有字符构成一个字符串并输出。对应的算 法如下：
public string DispStr() { int i; string mystr=""; if (length==0) mystr = "空串"; else { for (i=0;i<length;i++) mystr+=data[i].ToString(); } return mystr; }
数据结构 串 实验报告
实验报告实验名称：串实验目的：（1）、熟悉C语言的上机环境，进一步掌握C语言的结构特点；（2）、掌握串的定义及C语言实现；（3）、掌握串的模式匹配及C语言实现；（4）、掌握串的各种基本操作；实验步骤：（1）、建立链串类型（2）、实现匹配过程中需考虑的链表的特征。
实验内容：4.一个字符串中的任意一个子序列，若子序列中各字符值均相同，则成为字符平台。
写一算法，输入任意以字符串S，输出S中长度最大的所有字符平台的起始位置及所含字符。
注意，最大字符平台有可能不止一个。
实验数据记录：（源代码及执行过程）#include<stdio.h>#include<stdlib.h>#define Maxsize 20#define n 100typedef struct Node{int element[Maxsize];int front;int rear;}Queue;int EnterQueue(Queue *Q,int x){if((Q->rear+1)%Maxsize == Q->front){printf("队列已满!\n");return 0;}Q->element[Q->rear] = x;Q->rear = (Q->rear+1)%Maxsize;return 1;}int DeleQueue(Queue *Q,int *x){if(Q->front == Q->rear){printf("队列为空!\n");return 0;}*x = Q->element[Q->front];Q->front = (Q->front+1)%Maxsize;return 1;}int Donull(Queue *Q){while(Q->front != Q->rear){Q->element[Q->front] = 0;Q->front = (Q->front+1)%Maxsize;}Q->front = Q->rear = 0;if(Q->front == Q->rear){return 1;}else{return 0;}}int main(void){char str[n];int i=0,j=1,k=1,ch,p=1,flag=1;Queue *Q;Q = (Queue *)malloc(sizeof(Queue));Q->front = Q->rear = 0;printf("请输入字符串：");gets(str);while('\0' != *(str+i)){ while(*(str+i+1) == *(str+i)){if(flag){p = i;flag = 0;}i++;j++;}if(flag){p = i;}if(j >= k){if(j > k){Donull(Q);k = j;}if(EnterQueue(Q ,j) == 0)break;if(EnterQueue(Q,p+1) == 0)break;if(EnterQueue(Q,*(str+i)) == 0)break;}j=1;i++;flag = 1;} while(Q->front < Q->rear){DeleQueue(Q,&j);DeleQueue(Q,&k);DeleQueue(Q,&ch);printf("%-10d",k);for(i = 0; i < j; i++){printf("%c",ch);}printf("\n");}printf("\n");system("pause");}。
数据结构第4章 串
ring s, SString t)
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;
数据结构-第4章 串
真子串是指不包含自身的所有子串。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。
数据结构中的串
if(pos>=0) { n=StrLength(S); m=StrLength(T); i=pos; while ( i<=n-m ) { SubString( sub,S,i,m );//返回S中从i起长度为m的子串 if( SubCompare (sub,T)!= 0 ) i++; else return i; } // while
StrCompare(S, T) : 若S>T 返回>0;若S=T 返回=0;若
S<T 返回<0;
StrLength( S ) :串S存在，返回S中元素的个数，称为串
的长度
more
串的基本操作
Concat( &T, S1,S2 ) : 用T返回S1和S2联接而成的新串 SubString( &Sub,S,pos,len ) : 用Sub返回串S的第pos个
▪ 两个串之间可以进行比较。 ▪ 称两个串相等，当且仅当这两个串的值相等，包括
两个串的长度相等，并且各个对应位置的字符都相 等。
▪ 当两个串不相等时，可按“字典顺序”分大小。令
s= “s0s1…sm-1” (m>0) t= “t0t1…tn-1” (n>0) ▪ 假设，两者最大有前k个子序列相等（最大相等前缀子
▪ 串中任意个连续的字符组成的子序列称为该串的子串。包含 子串的的串相应地称为主串。通常称字符在序列中的序列号 为该字符在串中的位置。子串在主串中的位置则以子串第0 个字符在主串的位置来表示。
4.1 串的定义和操作
▪ 例如：下面a，b，c，d都是串
▪ a=“BEI”
长度为3
▪ b=“JING”
长度为4
44
第4章 串
StrCompare(S, T) : 若S>T 返回>0;若S=T 返回=0;若
S<T 返回<0;
StrLength( S ) :串S存在，返回S中元素的个数，称为串
的长度
more
串的基本操作
Concat( &T, S1,S2 ) : 用T返回S1和S2联接而成的新串 SubString( &Sub,S,pos,len ) : 用Sub返回串S的第pos个
▪ 两个串之间可以进行比较。 ▪ 称两个串相等，当且仅当这两个串的值相等，包括
两个串的长度相等，并且各个对应位置的字符都相 等。
▪ 当两个串不相等时，可按“字典顺序”分大小。令
s= “s0s1…sm-1” (m>0) t= “t0t1…tn-1” (n>0) ▪ 假设，两者最大有前k个子序列相等（最大相等前缀子
▪ 串中任意个连续的字符组成的子序列称为该串的子串。包含 子串的的串相应地称为主串。通常称字符在序列中的序列号 为该字符在串中的位置。子串在主串中的位置则以子串第0 个字符在主串的位置来表示。
4.1 串的定义和操作
▪ 例如：下面a，b，c，d都是串
▪ a=“BEI”
长度为3
▪ b=“JING”
长度为4
44
第4章 串
数据结构的串操作
数据结构的串操作数据结构的串操作
⒈概述
⑴串的定义
⑵串的基本操作
⒉串的存储结构
⑴顺序存储结构
⑵链式存储结构
⒊串的基本操作
⑴串的长度
⑵串的比较
⑶串的连接
⑷串的截取
⑸串的插入
⑹串的删除
⑺串的替换
⒋字符串匹配算法
⑴朴素模式匹配算法
⑵ KMP 算法
⑶ Boyer-Moore 算法
⑷ Rabin-Karp 算法
附件：
⒈示例代码
⒉数据集
法律名词及注释：
⒈串：在计算机科学中，串（String）是由零个或多个字符组成的有限序列。
⒉顺序存储结构：串的顺序存储结构是将串的字符按线性次序逐个存储在一组地址连续的存储单元里。
⒊链式存储结构：串的链式存储结构是通过定义一个节点类型来存储串的字符，每个节点包含一个字符和一个指向下一个节点的指针。
⒋朴素模式匹配算法：朴素模式匹配算法是最简单的字符串匹
配算法之一，通过对目标串的每个字符依次与模式串进行比较，直
到找到匹配的位置或遍历完所有字符。
⒌ KMP 算法：KMP 算法是一种高效的字符串匹配算法，通过利
用模式串的前缀和后缀信息，在匹配失败时将模式串移动比朴素算
法更远的位置，减少比较次数。
⒍ Boyer-Moore 算法：Boyer-Moore 算法是一种基于多种规则
的字符串匹配算法，通过从右到左比较模式串和目标串的字符，根
据不匹配字符在模式串中的位置和字符表进行移动，提高匹配效率。
⒎ Rabin-Karp 算法：Rabin-Karp 算法是一种利用哈希函数的
字符串匹配算法，通过计算目标串和模式串的哈希值，并逐个比较，减少比较次数。
数据结构——串
7
三、串的基本操作 C语言中常用的串运算 定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result;
(1) 求串长(length) int strlen(char s); //求串的长度
例如：printf(“%d”,strlen(s1)); 输出13
char strcat(char s1 , char s2)
该函数将串s2复制到串s1的末尾，并且返回一 个指向串s1的开始处的指针。
例如：strcat(a3,”/”)
strcat(a3,a2);
2020//4//a143=“dirtreeformat/file.mem”
9
(4)串比较（compare)
A=“This is a string” B=“is” B在A中出现了两次，其中首次出现所对应的主串
位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子
串。
2020/4/14
5
二、串的抽象数据定义
• ADT String { • 数据对象:D={ai| ai
16
顺序串的类型定义和顺序表类似： typedef char ElemType;
typedef struct { ElemType ch[maxstrlen]; int length;
}sstring; //其优点是涉及到串长操作时速度快。
2020/4/14
17
4.2.2 堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存 放字符串序列，但它们的存储空间是在程序执行过程中动态 分配而得。所以也称为动态存储分配的顺序表。在C语言中， 利用malloc和realloc,free等动态存储管理函数，来根据实 际需要动态分配和释放字符数组空间。这样定义的顺序串类
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑵ 堆存储结构
数据结构C语言描述
这种存储方法仍然以一组地址连续的存储单元存放串的字符 序列，但它们的存储空间是在程序执行过程中动态分配的。系统 序列，但它们的存储空间是在程序执行过程中动态分配的。 将一个地址连续、容量很大的存储空间作为字符串的可用空间， 将一个地址连续、容量很大的存储空间作为字符串的可用空间， 每当建立一个新串时，系统就从这个空间中分配一个大小和字符 每当建立一个新串时， 串长度相同的空间存储新串的串值。 串长度相同的空间存储新串的串值。 在C语言中，存在一个称之为“堆”的自由存储区，并由C语 语言中，存在一个称之为“ 的自由存储区，并由C 言的动态分配函数malloc() free()来管理 利用函数malloc() malloc()和 来管理。 言的动态分配函数malloc()和free()来管理。利用函数malloc() 为每个新产生的串分配一块实际串长所需的存储空间， 为每个新产生的串分配一块实际串长所需的存储空间，若分配成 则返回一个指向起始地址的指针，作为串的基址，同时， 功，则返回一个指向起始地址的指针，作为串的基址，同时，为 了以后处理方便，约定串长也作为存储结构的一部分。 了以后处理方便，约定串长也作为存储结构的一部分。
出版社
MAXLEN
256
<最大串长> 最大串长>
typedef struct
/*串的实际长度* /*串的实际长度*/ 串的实际长度
串的存储结构（ 4.1.2 串的存储结构（续）
数据结构C语言描述
串的实际长度可在这预定义长度的范围内随意， 串的实际长度可在这预定义长度的范围内随意， 超过预定义长度的串值则被舍去，称之为“截断” 超过预定义长度的串值则被舍去，称之为“截断”。 对串长有两种表示方法： 对串长有两种表示方法：一是如上述定义描述的那 以分量存放串的实际长度； 样，以分量存放串的实际长度；二是在串值后面加 一个不计入串长的结束标记字符， 如在有的 C 语言 一个不计入串长的结束标记字符 ， 如在有的C 中以〞 表示串值的终结。此时的串长为隐含值, 中以〞\0〞表示串值的终结 。此时的串长为隐含值, 显然不便于进行某些串操作。 显然不便于进行某些串操作。这时数据类型可以定 义如下： 义如下： typedef char *Sstring1;
出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑴ 串的顺序存储结构
数据结构C语言描述
串的顺序存储就是把串设计成一种静态结构类型， 串的顺序存储就是把串设计成一种静态结构类型，串的存储分 配是在编译时完成的， 配是在编译时完成的，串中的字符依次存放在一组连续的存 储空间中，也就是用向量来存储串。 储空间中，也就是用向量来存储串。 串的顺序存储结构如下： 串的顺序存储结构如下： #define { ch[MAXLEN+1 char ch[MAXLEN+1]； length； int length； }SString;
(4) StrCompare(S,T)：串的比较。已知串S和T,若S>T，则返回值1；若S=T， ：串的比较。已知串 和 若 ，则返回值 ； ， 数据结构C语言描述 则返回值=0； 则返回值 ；若S<T，则返回值 。 ，则返回值-1。 (5) StrLength(S)求串 的长度。已知串 ，函数返回 串的长度。 求串S的长度 串的长度。 求串 的长度。已知串S，函数返回S串的长度 (6) StrClear(*S)：串S存在，将S清为空串。 存在， 清为空串。 ： 存在 清为空串 (7) Concat(*T,S1,S2)：已知串 和S2，用T返回由 和S2联接而成的新串。 返回由S1和 联接而成的新串 联接而成的新串。 ：已知串S1和 ， 返回由 (8) SubString(*Sub,S,pos,len)：求子串。已知串 ，1≤pos≤StrLength(S)且 ：求子串。已知串S， 且 0≤len≤StrLength(S)-pos+1。用Sub返回串 的第 个字符起长度为 的子串。 返回串S的第 个字符起长度为len的子串 。 返回串 的第pos个字符起长度为 的子串。 (9) StrIndex(S,T,pos)：串的定位。已知串 和T（非空）， ：串的定位。已知串S和 （非空）， 1≤pos≤StrLength(S)。若串 中存在和串 相同的子串，则返回它在主串 中第 中存在和串T相同的子串 。若串S中存在和串 相同的子串，则返回它在主串S中第 pos个字符之后第一次出现的位置；否则函数值返回 。 个字符之后第一次出现的位置； 个字符之后第一次出现的位置 否则函数值返回0。 (10) Replace(*S,T,V)：串的置换。已知串S，T和V，T是非空串，用V替换主 ：串的置换。已知串 ， 和 ， 是非空串， 替换主 是非空串 中出现的所有与T相等的不重叠的子串 串S中出现的所有与 相等的不重叠的子串。 中出现的所有与 相等的不重叠的子串。 (11) StrInsert(*S,pos,T)：串的插入。已知串 和T，1≤pos≤StrLength(S)+1。 ：串的插入。已知串S和 ， 。 在串S的第 个字符之前插入串T。 的第pos个字符之前插入串 在串 的第 个字符之前插入串 。 (12) StrDelete(*S,pos,len)串的删除。已知串 ，1≤pos≤StrLength(S)-len+1，在 串的删除。 串的删除 已知串S， ， 中删除第pos个字符起长度为 的子串。 串S中删除第 个字符起长度为 的子串。 中删除第 个字符起长度为len的子串 (13) StrDestroy (*S)已知串 ，将S销毁释放内存空间。 已知串S， 销毁释放内存空间。 已知串 销毁释放内存空间 }ADT String 出版社
出版社
串的存储结构（ 4.1.2 串的存储结构（续） typedef struct { char int
数据结构C语言描述
*ch；/*若是非空串 则按串长分配存储区，否则ch 若是非空串， ch为 *ch；/*若是非空串，则按串长分配存储区，否则ch为NULL length； length； /* 串长度 */
*/
}HString； }HString； 这种存储结构表示时的串操作仍是基于“ 这种存储结构表示时的串操作仍是基于“字符 序列的复制”进行的。 序列的复制”进行的。
出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑶ 串的块链存储表示
数据结构C语言描述
由于串也是一种线性表，因此也可以采用链式存储。 由于串也是一种线性表，因此也可以采用链式存储。由 于串的特殊性(每个元素只有一个字符) 在具体实现时， 于串的特殊性(每个元素只有一个字符)，在具体实现时，每 个结点既可以存放一个字符，也可以存放多个字符。 个结点既可以存放一个字符，也可以存放多个字符。每个结 点称为块，整个链表称为块链结构，为了便于操作， 点称为块，整个链表称为块链结构，为了便于操作，再增加 一个尾指针。结点大小为数据域中存放字符的个数。 一个尾指针。结点大小为数据域中存放字符的个数。 例如， 4.1(a)是结点大小为4(即每个结点存放4 例如，图4.1(a)是结点大小为4(即每个结点存放4个字 是结点大小为4(即每个结点存放 的链表， 4.1(b)是结点大小为 的链表。 是结点大小为1 符)的链表，图4.1(b)是结点大小为1的链表。当结点大小大 由于串长不一定是结点大小的整倍数， 于1时，由于串长不一定是结点大小的整倍数，则链表中的 最后一个结点不一定全被串值占满，此时通常补上〞 最后一个结点不一定全被串值占满，此时通常补上〞#〞或 其他的非串值字符(通常“ 不属于串的字符集 不属于串的字符集， 其他的非串值字符(通常“#”不属于串的字符集，是一个特 殊的符号) 殊的符号)。
出版社
串的基本概念（ 4.1.1 串的基本概念（续）
数据结构C语言描述
当两个串的长度相等，并且各个对应位置的字符都相同时，称这两个串相等。 当两个串的长度相等， 并且各个对应位置的字符都相同时，称这两个串相等。 串的数据对象是字符集合，一系列连续的字符就组成一个串。学习线性表后， 串的数据对象是字符集合，一系列连续的字符就组成一个串。学习线性表后， 也许你会觉得串也是一种线性表，串的逻辑结构和线性表极为相似， 也许你会觉得串也是一种线性表，串的逻辑结构和线性表极为相似，但由 于串有某些特征而不同线性表（ 于串有某些特征而不同线性表（操作的对象不是单个数据元素而是若干个 元素—既子串 既子串） 故独立讨论。 元素 既子串），故独立讨论。 串的抽象数据类型定义如下： 串的抽象数据类型定义如下： ADT String{ 数据对象： 数据对象：D={ai|ai∈CharacterSet,i=1,2,...,n, n≥0} ∈ 数据关系： 数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n} ∈ 基本操作： 基本操作： (1) StrAssign(*T,charconstant)：串赋值。charconstant是字符串常量， 是字符串常量， ：串赋值。 是字符串常量 生成一个其值等于charconstant的串 。 的串T。 生成一个其值等于 的串 (2) StrCopy(*T,S)：串复制。已知串 ，将串 的内容复制到串 中。 的内容复制到串T中 ：串复制。已知串S，将串S的内容复制到串 (3) StrEmpty(S)：判断串 是否为空，若S为空，则返回真 是否为空， 为空， ：判断串S是否为空 为空 则返回真TRUE，否则 ， 返回 FALSE。 。 出版社
4.1.2 串的存储结构
数据结构C语言描述
线性表有顺序和链式存储结构、对于串都是适 用的。但任何一种存储结构对于串的不同运算并非 都是十分有效的。对于串的插入和删除操作，顺序 存储结构是不方便的，而链式存储结构则显得方便 些。如果访问串中单个字符。对链表来说是不困难 的；当要访问一组连续的字符时，则用链式存储结 构要比用顺序存储结构麻烦。所以应针对不同的应 用来选择串的存储结构。另外，串的存储结构和具 体的计算机的编址方式也有密切的关系。因此，选 用串的存储方式要考虑的因素是较多的，下面作一 些大致的分析。
串的存储结构（ 4.1.2 串的存储结构（续）
⑵ 堆存储结构
数据结构C语言描述
这种存储方法仍然以一组地址连续的存储单元存放串的字符 序列，但它们的存储空间是在程序执行过程中动态分配的。系统 序列，但它们的存储空间是在程序执行过程中动态分配的。 将一个地址连续、容量很大的存储空间作为字符串的可用空间， 将一个地址连续、容量很大的存储空间作为字符串的可用空间， 每当建立一个新串时，系统就从这个空间中分配一个大小和字符 每当建立一个新串时， 串长度相同的空间存储新串的串值。 串长度相同的空间存储新串的串值。 在C语言中，存在一个称之为“堆”的自由存储区，并由C语 语言中，存在一个称之为“ 的自由存储区，并由C 言的动态分配函数malloc() free()来管理 利用函数malloc() malloc()和 来管理。 言的动态分配函数malloc()和free()来管理。利用函数malloc() 为每个新产生的串分配一块实际串长所需的存储空间， 为每个新产生的串分配一块实际串长所需的存储空间，若分配成 则返回一个指向起始地址的指针，作为串的基址，同时， 功，则返回一个指向起始地址的指针，作为串的基址，同时，为 了以后处理方便，约定串长也作为存储结构的一部分。 了以后处理方便，约定串长也作为存储结构的一部分。
出版社
MAXLEN
256
<最大串长> 最大串长>
typedef struct
/*串的实际长度* /*串的实际长度*/ 串的实际长度
串的存储结构（ 4.1.2 串的存储结构（续）
数据结构C语言描述
串的实际长度可在这预定义长度的范围内随意， 串的实际长度可在这预定义长度的范围内随意， 超过预定义长度的串值则被舍去，称之为“截断” 超过预定义长度的串值则被舍去，称之为“截断”。 对串长有两种表示方法： 对串长有两种表示方法：一是如上述定义描述的那 以分量存放串的实际长度； 样，以分量存放串的实际长度；二是在串值后面加 一个不计入串长的结束标记字符， 如在有的 C 语言 一个不计入串长的结束标记字符 ， 如在有的C 中以〞 表示串值的终结。此时的串长为隐含值, 中以〞\0〞表示串值的终结 。此时的串长为隐含值, 显然不便于进行某些串操作。 显然不便于进行某些串操作。这时数据类型可以定 义如下： 义如下： typedef char *Sstring1;
出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑴ 串的顺序存储结构
数据结构C语言描述
串的顺序存储就是把串设计成一种静态结构类型， 串的顺序存储就是把串设计成一种静态结构类型，串的存储分 配是在编译时完成的， 配是在编译时完成的，串中的字符依次存放在一组连续的存 储空间中，也就是用向量来存储串。 储空间中，也就是用向量来存储串。 串的顺序存储结构如下： 串的顺序存储结构如下： #define { ch[MAXLEN+1 char ch[MAXLEN+1]； length； int length； }SString;
(4) StrCompare(S,T)：串的比较。已知串S和T,若S>T，则返回值1；若S=T， ：串的比较。已知串 和 若 ，则返回值 ； ， 数据结构C语言描述 则返回值=0； 则返回值 ；若S<T，则返回值 。 ，则返回值-1。 (5) StrLength(S)求串 的长度。已知串 ，函数返回 串的长度。 求串S的长度 串的长度。 求串 的长度。已知串S，函数返回S串的长度 (6) StrClear(*S)：串S存在，将S清为空串。 存在， 清为空串。 ： 存在 清为空串 (7) Concat(*T,S1,S2)：已知串 和S2，用T返回由 和S2联接而成的新串。 返回由S1和 联接而成的新串 联接而成的新串。 ：已知串S1和 ， 返回由 (8) SubString(*Sub,S,pos,len)：求子串。已知串 ，1≤pos≤StrLength(S)且 ：求子串。已知串S， 且 0≤len≤StrLength(S)-pos+1。用Sub返回串 的第 个字符起长度为 的子串。 返回串S的第 个字符起长度为len的子串 。 返回串 的第pos个字符起长度为 的子串。 (9) StrIndex(S,T,pos)：串的定位。已知串 和T（非空）， ：串的定位。已知串S和 （非空）， 1≤pos≤StrLength(S)。若串 中存在和串 相同的子串，则返回它在主串 中第 中存在和串T相同的子串 。若串S中存在和串 相同的子串，则返回它在主串S中第 pos个字符之后第一次出现的位置；否则函数值返回 。 个字符之后第一次出现的位置； 个字符之后第一次出现的位置 否则函数值返回0。 (10) Replace(*S,T,V)：串的置换。已知串S，T和V，T是非空串，用V替换主 ：串的置换。已知串 ， 和 ， 是非空串， 替换主 是非空串 中出现的所有与T相等的不重叠的子串 串S中出现的所有与 相等的不重叠的子串。 中出现的所有与 相等的不重叠的子串。 (11) StrInsert(*S,pos,T)：串的插入。已知串 和T，1≤pos≤StrLength(S)+1。 ：串的插入。已知串S和 ， 。 在串S的第 个字符之前插入串T。 的第pos个字符之前插入串 在串 的第 个字符之前插入串 。 (12) StrDelete(*S,pos,len)串的删除。已知串 ，1≤pos≤StrLength(S)-len+1，在 串的删除。 串的删除 已知串S， ， 中删除第pos个字符起长度为 的子串。 串S中删除第 个字符起长度为 的子串。 中删除第 个字符起长度为len的子串 (13) StrDestroy (*S)已知串 ，将S销毁释放内存空间。 已知串S， 销毁释放内存空间。 已知串 销毁释放内存空间 }ADT String 出版社
出版社
串的存储结构（ 4.1.2 串的存储结构（续） typedef struct { char int
数据结构C语言描述
*ch；/*若是非空串 则按串长分配存储区，否则ch 若是非空串， ch为 *ch；/*若是非空串，则按串长分配存储区，否则ch为NULL length； length； /* 串长度 */
*/
}HString； }HString； 这种存储结构表示时的串操作仍是基于“ 这种存储结构表示时的串操作仍是基于“字符 序列的复制”进行的。 序列的复制”进行的。
出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑶ 串的块链存储表示
数据结构C语言描述
由于串也是一种线性表，因此也可以采用链式存储。 由于串也是一种线性表，因此也可以采用链式存储。由 于串的特殊性(每个元素只有一个字符) 在具体实现时， 于串的特殊性(每个元素只有一个字符)，在具体实现时，每 个结点既可以存放一个字符，也可以存放多个字符。 个结点既可以存放一个字符，也可以存放多个字符。每个结 点称为块，整个链表称为块链结构，为了便于操作， 点称为块，整个链表称为块链结构，为了便于操作，再增加 一个尾指针。结点大小为数据域中存放字符的个数。 一个尾指针。结点大小为数据域中存放字符的个数。 例如， 4.1(a)是结点大小为4(即每个结点存放4 例如，图4.1(a)是结点大小为4(即每个结点存放4个字 是结点大小为4(即每个结点存放 的链表， 4.1(b)是结点大小为 的链表。 是结点大小为1 符)的链表，图4.1(b)是结点大小为1的链表。当结点大小大 由于串长不一定是结点大小的整倍数， 于1时，由于串长不一定是结点大小的整倍数，则链表中的 最后一个结点不一定全被串值占满，此时通常补上〞 最后一个结点不一定全被串值占满，此时通常补上〞#〞或 其他的非串值字符(通常“ 不属于串的字符集 不属于串的字符集， 其他的非串值字符(通常“#”不属于串的字符集，是一个特 殊的符号) 殊的符号)。
出版社
串的基本概念（ 4.1.1 串的基本概念（续）
数据结构C语言描述
当两个串的长度相等，并且各个对应位置的字符都相同时，称这两个串相等。 当两个串的长度相等， 并且各个对应位置的字符都相同时，称这两个串相等。 串的数据对象是字符集合，一系列连续的字符就组成一个串。学习线性表后， 串的数据对象是字符集合，一系列连续的字符就组成一个串。学习线性表后， 也许你会觉得串也是一种线性表，串的逻辑结构和线性表极为相似， 也许你会觉得串也是一种线性表，串的逻辑结构和线性表极为相似，但由 于串有某些特征而不同线性表（ 于串有某些特征而不同线性表（操作的对象不是单个数据元素而是若干个 元素—既子串 既子串） 故独立讨论。 元素 既子串），故独立讨论。 串的抽象数据类型定义如下： 串的抽象数据类型定义如下： ADT String{ 数据对象： 数据对象：D={ai|ai∈CharacterSet,i=1,2,...,n, n≥0} ∈ 数据关系： 数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n} ∈ 基本操作： 基本操作： (1) StrAssign(*T,charconstant)：串赋值。charconstant是字符串常量， 是字符串常量， ：串赋值。 是字符串常量 生成一个其值等于charconstant的串 。 的串T。 生成一个其值等于 的串 (2) StrCopy(*T,S)：串复制。已知串 ，将串 的内容复制到串 中。 的内容复制到串T中 ：串复制。已知串S，将串S的内容复制到串 (3) StrEmpty(S)：判断串 是否为空，若S为空，则返回真 是否为空， 为空， ：判断串S是否为空 为空 则返回真TRUE，否则 ， 返回 FALSE。 。 出版社
4.1.2 串的存储结构
数据结构C语言描述
线性表有顺序和链式存储结构、对于串都是适 用的。但任何一种存储结构对于串的不同运算并非 都是十分有效的。对于串的插入和删除操作，顺序 存储结构是不方便的，而链式存储结构则显得方便 些。如果访问串中单个字符。对链表来说是不困难 的；当要访问一组连续的字符时，则用链式存储结 构要比用顺序存储结构麻烦。所以应针对不同的应 用来选择串的存储结构。另外，串的存储结构和具 体的计算机的编址方式也有密切的关系。因此，选 用串的存储方式要考虑的因素是较多的，下面作一 些大致的分析。