[入门必看]数据结构4.1:串的定义和实现
- 第四章 串
- 4.1 串的定义和实现
- 知识总览
- 4.1.1_串的定义和基本操作
- 4.1.2_串的存储结构
- 4.1.1_串的定义和基本操作
- 串的定义
- 串 V.S 线性表
- 串的基本操作
- 串的比较操作
- 字符集编码
- 4.1.2_串的存储结构
- 串的顺序存储
- 串的链式存储
- 基本操作的实现
- 求子串
- 比较两个串大小
- 定位子串
- 知识回顾与重要考点
- 4.1.1_串的定义和基本操作
- 4.1.2_串的存储结构
第四章 串
小题考频:2
大题考频:0
4.1 串的定义和实现
难度:☆☆
知识总览
4.1.1_串的定义和基本操作
4.1.2_串的存储结构
4.1.1_串的定义和基本操作
注:数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构)
存储结构不同,运算的实现方式不同
串的定义
串,即字符串(String)是由零个或多个字符组成的有限序列。一般记为
S = ‘a1a2······an’ (n ≥0)
其中,S是串名,单引号括起来的字符序列是串的值;ai可以是字母、数字或其他字符;串
中字符的个数n称为串的长度。n = 0时的串称为空串(用∅表示)。
例:
S=”HelloWorld!”
T=‘iPhone 11 Pro Max?’
注:有的地方用双引号(如Java、C)
有的地方用单引号(如Python)
引号是边界符
子串:串中任意个连续的字符组成的子序列。
Eg:’iPhone’,’Pro M’是串T的子串
主串:包含子串的串。
Eg:T是子串’iPhone’的主串
字符在主串中的位置:字符在串中的序号。
Eg:’1’在T中的位置是8(第一次出现)
子串在主串中的位置:子串的第一个字符在主串中的位置。
Eg:’11 Pro’在T中的位置为8
空串V.S空格串:
M=‘’
M是空串
N=‘ ’
N是由三个空格字符组成的空格串,每个空格字符占1B - 8bit
串 V.S 线性表
串是一种特殊的线性表,数据元素之间呈线性关系
串的数据对象限定为字符集(如中文字符、英文字符、数字字符、标点字符等)
串的基本操作,如增删改查等通常以子串为操作对象
串的基本操作
假设有串T=“”,S=”iPhone 11 Pro Max?”,W=“Pro”
StrAssign(&T,chars):赋值操作。把串T赋值为chars。
StrCopy(&T,S):复制操作。由串S复制得到串T。
StrEmpty(S):判空操作。若S为空串,则返回TRUE,否则返回FALSE。
StrLength(S):求串长。返回串S的元素个数。
ClearString(&S):清空操作。将S清为空串。
DestroyString(&S):销毁串。将串S销毁(回收存储空间)。
Concat(&T,S1,S2):串联接。用T返回由S1和S2联接而成的新串
Eg:执行基本操作Concat(&T, S, W)后,T=“iPhone 11 Pro Max?Pro”
存储空间扩展?
SubString(&Sub,S,pos,len):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Eg:执行基本操作SubString(&T ,S, 4, 6)后,T=“one 11”
Index(S,T)=:定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的位置;否则函数值为0。
执行基本操作Index(S, W)后,返回值为11
StrCompare(S,T):比较操作。若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0。
串的比较操作
StrCompare(S,T):比较操作。若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0。
正序词汇表,就对字符串进行了比较操作
“abandon” < “aboard”
从第一个字符开始往后依次对比,先出现更大字符的串就更大
“abstract” < “abstraction”
“abstract”<“abstrast ” (多了空格)
长串的前缀与短串相同时,长串更大
“academic”>“abuse”
“academic”=“academic”
只有两个串完全相同时,才相等
字符集编码
任何数据存到计算机中一定是二进制数。
需要确定一个字符和二进制数的对应规则这就是“编码”
空格对应的二进制数是00100000,每个空格会占一个字节,1B - 8bit
“字符集”:
英文字符——ASCII字符集
中英文——Unicode字符集
基于同一个字符集,可以有多种编码方案,如:UTF-8,UTF-16
从函数的角度来理解字符集编码:
y = f(x)
字符集:函数f(x)的定义域
编码:函数映射规则f
y:对应的二进制数
注:采用不同的编码方式,每个字符所占空间不同,做题中只需默认每个字符占1B即可
拓展:乱码问题
解码方式错误:
在你的文件中,原本采用某一套编码规则y=f(x),如: ‘码’↔0001010100010101010010
打开文件时,你的软件以为你采用的是另一套编码规则y=g(x),如:0001010100010101010010↔鑹
4.1.2_串的存储结构
串的顺序存储
- 静态数组实现:
长度不可改变,用完系统自动回收
- 动态数组实现:
使用malloc函数,用完需要手动free
优缺点:
——结合顺序表优缺点
- 优点:随机存取
- 缺点:插入删除(空间的拓展收缩)不方便
实现方案:
方案一:专门用一个int型变量来记录长度Length
方案二:用char[0]来充当Length
优点:字符的位序和数组下标一一对应(1、2、3、4……)
缺点:char[0]也只有1B大小,能表示的数字范围∈[0,255],字符串长度更大的话,无法表示
方案三:没有Length变量,在字符串末尾处插入"\0"(对应ASCII码的0)
缺点:想知道字符串长度,需要从头到尾遍历找到"\0",需要经常使用数组长度,会不方便
方案四(默认使用):结合方案一和方案二。舍弃char[0]不用,专门用一个int型变量来记录长度Length
当我们访问字符串时,从char[1]开始访问
串的链式存储
char ch; 1个字符,大小为1B
但是指针struct StringNode *next大小为4B
用1B空间存储信息,还要用4B空间存储辅助信息,有用的信息占比小
——存储密度低:每个字符1B,每个指针4B
解决方案:
每个结点存储更多字符,存储密度就会提高
如果最后一个结点中存不满,可以用特别的字符(如"#“,”\0")填充进去
优缺点:
——结合链表优缺点
- 优点:增加删除方便
- 缺点:不具备随机存取特性
基本操作的实现
StrAssign(&T,chars):赋值操作。把串T赋值为chars。
StrCopy(&T,S):复制操作。由串S复制得到串T。
StrEmpty(S):判空操作。若S为空串,则返回TRUE,否则返回FALSE。
StrLength(S):求串长。返回串S的元素个数。
ClearString(&S):清空操作。将S清为空串。
DestroyString(&S):销毁串。将串S销毁(回收存储空间)。
Concat(&T,S1,S2):串联接。用T返回由S1和S2联接而成的新串
求子串
SubString(&Sub,S,pos,len):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
串S,长度为7
传入串Sub,for循环把特定范围内的各个字符依次复制到Sub的char ch[MAXLEN]数组里,并把Sub.length设为子串长度len
if用来判断子串长度是否越界
比较两个串大小
StrCompare(S,T):比较操作。若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0。
逐个字符比较,如果相同的话比较下一个字符,字符不相同则比较字符大小,先出现更大的字符的字符串,则为实际更大的字符串;
如果对比结束全部相同,则长度更长的串更大
先出现更大字符的字符串,实际更大:
1)当S.ch[i] - T.ch[i] < 0时,直接返回一个小于0的值是符合逻辑的;
2)当S.ch[i] - T.ch[i] > 0时,直接返回一个大于0的值是符合逻辑的
当循环结束,扫描过的所有字符都相同,那么长度长的串更大:
1)当S.length > T.length时,S.length - T.length > 0,返回大于0的值,符合逻辑;
2)当S.length < T.length时,S.length - T.length < 0,返回小于0的值,符合逻辑;
3)当扫描过的所有字符都相同,且S.length = T.length时,S.length - T.length = 0,返回0,则两字符串相等
定位子串
Index(S,T):定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的位置;否则函数值为0,即没有该子串。
(1)用取子串的基本操作:取S中长度为3的子串,如’wan’;
(2)用比较两个串大小的基本操作:相等时,即找到该子串,返回该子串第一个值的位序;
(3)不相等时,循环(1)(2),继续取后一位长度为3的子串,并进行比较,直到找到该子串;
(4)全部扫描完后没有找到相同的子串,则没有该子串
求出S的长度和T的长度,直到T的长度,就能知道要取的子串有多长;
以此作为参数,然后调用取子串基本操作;
每取一个子串,都使用比较两个串大小的基本操作来对比子串大小;
找到相等的子串则返回,否则继续向后寻找;
找不到相同的子串,返回0
知识回顾与重要考点
4.1.1_串的定义和基本操作
4.1.2_串的存储结构
- 默认使用方案是:静态数组,并且浪费ch[0]位置,用单独的变量length来记录字符串的长度
- 该小节中,用别的基本操作来实现求串在主串中的位置(index),接下来将探讨不使用基本操作,而是直接操作数组来实现index函数