数据结构(12.1)串结构的定义
数据结构(12.1)串结构的定义
前⾔
串是⼀种⽐较特殊的数据结构,它是计算机上⾮数值处理的主要对象。
事实上在C语⾔中,是没有“字符串”这个变量类型的,虽然可以通过字符指针 char *p 这样来记录⼀个字符串,p本质上仍是⼀个字符指针,保存的是⼀个字符的地址。因此,C语⾔中的保存⼀个字符串,只是保存它⾸个字符的地址。但是到了诸如Java这样的语⾔⾥,提供了⼀种String类,可以直接⽤String s 来记录字符串,String和int、char⼀样是⼀种数据类型(只不过不是基本的数据类型,⽽是属于引⽤类型)。并且Java提供了很多操作函数,可以直接实现对字符串的相关操作。当然,C语⾔中虽然没有明确的字符串类型,但是同样存在字符串操作函数。
串的定义
定义:串(或字符串)是由零个或多个字符组成的有限序列,⼀般记为:s = ‘a1a2…an’(n>=0)
串的名称:s
画公主
串的值:⽤单引号(有些书中也⽤双引号)括起来的字符序列,可以是数字、字母或者其他字符。但是单引号本⾝不属于串,它的作⽤是避免与变量名或数的常量混淆。
串的长度:n
有关概念
空串:零个字符的串称为空串,其长度为零。例如 s = ‘’。
⼦串:串中任意个连续的字符组成的⼦序列称为该串的⼦串,例如 s = ‘abcde’,t = ‘abc’,则 t 是 s 的⼦串
主串:包含⼦串的串相应地称为主串,例如 s = ‘abcde’,t = ‘abc’,那么 s 就是 t 的主串
串的位置:字符在序列中的序号称为该字符在串中的位置,例如s = ‘abcde’,字符’ b '在 s 中的位置就是2(在实际应⽤中为了⽅便数组操作,也可以从零开始数,则此处就为1)。
⽽⼦串在主串中的位置,则⽤⼦串的第⼀个字符在主串中的位置来表⽰。例如 s = ‘abcde’,t = ‘cd’,⼦串 t 在 s 中的位置为3。
串相等:只有两个串的长度相等,并且各个对应位置的字符都相等时才称为串相等。例如 s = ‘abc’,t = ‘ab c’,此时 s 和 t 并不相等(空格也属于字符集合中的⼀个元素)。
空格串:由⼀个或者多个空格组成的串,称为空格串。例如 s = ’ ',此时 s 串是空格串,但不是空串,其长度为空格的数量。
南张北周串的存储结构
回顾线性表的概念:由n(n>=0)个数据特性相同的元素构成的有限序列。
可以发现,同样是有限序列,串的逻辑结构和线性表是很相似的,区别仅在于串的约束对象是字符集。也就是说,假如字符串中存储的
是’123456’这么⼀串,实际上它保存的类型是char,⽽不是int。
布丁仓鼠
那么,把线性表的存储类型改为char不也能表⽰串吗?按理来说是这样,但是串与线性表的主要区别是在操作上。在线性表的基本操作中,多以”单个元素“作为操作的对象,例如插⼊、删除等,多是对某个元素进⾏操作;⽽在线性表中,多以“串的整体”作为操作的对象,⽐如插⼊,多是插⼊另⼀个串,⽽不是单个字符。因此,串的操作和线性表有很⼤不同,需要把串当成与线性表不同的逻辑结构来看待。
从存储结构上来说,串也有两种基本的存储结构:顺序存储和链式存储。
顺序存储
有些资料中说,串有三种机内表⽰⽅法,分别是定长顺序表⽰、堆分配存储表⽰和块链存储表⽰。实际上,定长顺序表⽰和堆分配表⽰都属于顺序存储。
顺序存储的特点是,使⽤⼀组地址连续的存储单元来进⾏存储。我们使⽤顺序存储结构时,往往需要在⼀开始去申请⼀整块的内存空间,然后在我们所申请好的这块内存空间内来插⼊、删除元素;这样就会出现⼀个问题:如果这块空间满了,⼜有新元素需要存⼊,应该怎么办呢?
在我们以往的实现中,有两种做法:第⼀种是逻辑上我的这个存储空间已经满了,就不允许再存⼊了,它的内存是静态的,能存多少元素已经在⼀开始确定了。⽽第⼆种则会在空间满的时候去重新申请⼀块更⼤的空间,只有当物理内存真正满了,空间申请失败的时候,才不允许再存⼊,它的内存是动态分配的。
我们把采⽤第⼀种处理⽅法称为定长顺序表⽰,定长即串空间的⼤⼩在编译的时候就确定了,不允许再更改,顺序则意味着它的地址空间是连续的。⽽第⼆种处理⽅法称为堆分配表⽰,因为C语⾔的内存分为五⼤分区,其中⼀个区叫做堆(heap)区,这个区的空间可以让程序员来进⾏分配释放,我们
调⽤malloc和free函数,就是在对堆区的内存进⾏操作。在堆分配表⽰中,串的空间可以动态分配,意味着串长可以任意(只要不超过实际的内存),但是它的地址空间仍然是连续的。
定长顺序表⽰
在定长顺序表⽰⾥,需要规定⼀个最⼤串长,在串创建时就按照预定义的⼤⼩为每个串分配固定的存储区,串的实际长度可以在预定义的范围之内,超过预定义长度的部分将会被舍去,称为”截断“。
堆分配表⽰
在堆分配表⽰中,存储空间是在程序执⾏过程中动态分配⽽来的,所占的空间由串的实际长度决定。需要注意的是,即使是动态分配,它的空间也是连续的⼀整块,可以去查⼀下malloc、relloc和calloc函数的细节。
顺序存储中串结构的设计
雨后小故事图
⽆论是顺序存储还是链式存储,都⾸先需要考虑⼀个问题:怎样确定串已经结束了?实际上它也可以转换成另⼀个问题:怎样确定串的实际长度?针对这两个问题的不同回答,决定了对串结构的不同设计。在这⾥先说顺序存储中的情况。
假设我们从串长的⾓度来考虑,只需要额外使⽤⼀个变量来保存串的长度,并且实时更新就可以了。这样,我们可以设计出来⼀个结构体,它包括⼀个存储串的空间,和⼀个保存串当前长度的整型变量
定长顺序表⽰:
#define MAXSTRLEN 255 //最⼤串长
typedef struct SString{
char ch[MAXSTRLEN];//存储串的⼀维数组
int length;//串的当前长度
}SString;
堆分配表⽰:
typedef struct HString{
char*ch;//串的存储空间
int length;//串的当前长度
}HString;
在定长顺序串中,还可以直接把当前长度存到数组中的0号单元⾥,让串从1下标开始,这样⼀开始要开辟的就是最⼤串长+1的空间,并且也不需要结构体了。
#define MAXSTRLEN 255 //最⼤串长
typedef unsigned char SString[MAXSTRLEN+1];//0号单元存放串的当前长度
需要注意,这个时候使⽤ unsigned char 型来保存数值,最⼤串长只能到255。
假如从串结束的问题来考虑,可以和C语⾔的做法⼀样,在串的最后加上⼀个不计⼊串长的字符来标记,⽐如’\0’,这样要开辟的也是最⼤串长+1的空间。由于这个时候的串长是⽆法直接得到的,在有些操作上可能不太⽅便。
定长顺序表⽰:
#define MAXSTRLEN 255 //最⼤串长
通讯录同步助手typedef unsigned char SString[MAXSTRLEN+1];//多出来⼀位⽤于在串满时在末尾加上'\0'
堆分配表⽰:
(初始化时需要记得多申请⼀个位置⽤于存放’\0’,并且在每次串变动后都需要注意’\0’的设置。)
typedef unsigned char* HString;
链式存储
⼀般⽽⾔,链式存储的设计包括两个部分:第⼀是结点的设计,包括结点要保存的内容和后续结点的
指针。第⼆则是针对整个链式结构的设计,⽐如设置头指针尾指针、结点数量等,⽤于对整个结构进⾏管理,并且⽅便⼀些操作。
额外提⼀下,这个“结点要保存的内容”可以很简单,我们平时学习的时候为了简便常常只是设置⼀个int型,得到的只是⼀些数值,感觉似乎没什么⽤;但是它也可以⽐较复杂,例如⼀个学⽣的信息,那么就需要char来记录名字,int来记录年龄、编号等等等等,需要根据实际情况来设置这个结构体,它的应⽤其实是很⼴泛的。
⾔归正传,对结点的设计很重要。按照往常的思路,我们⼀个结点⽤于保存⼀个字符,那么就是这样的:
//结点
typedef struct Node{
char c;//保存字符
struct Node * next;//下⼀个结点
}Node;
这虽然可⾏,但是我们⼀个结点只保存⼀个字符的话,每保存⼀个字符,就要花⼀个额外的空间来保存下⼀个结点的指针,造成⽐较⼤的浪费,由于串的特性,我们也可以考虑⼀个结点保存多个字符。
⼀个结点保存多个字符,⾸先需要设置结点可保存的最⼤字符量,假如我们⽤数组来存储,这实际上就是定长顺序串和链式存储的结合。
#define CHUNCKSIZE 3 //⼀个结点保存三个字符
//结点
typedef struct Chunk{
char ch[CHUNKSIZE];//存储串的⼀维数组
struct Chunk *next;//下⼀个结点
}Chunk;
这⾥可以通过判断next结点是否为空来确定串是否结束,所以不像顺序存储中那么⿇烦。
如图所⽰,假如我们使⽤数组来存储的话,最后⼀个结点它不⼀定会被占满,此时常补上“#”或者其他的⾮串值字符(通常不把“#”包括在串的字符集中,⽽是当做⼀个特殊符号。)
如果不想造成这样的浪费的话,也可以考虑不⽤数组来存储,⽽是动态开辟空间,假如要存储的字符串长度⼤于等于设定的结点长度,就按照设定长度来开辟;假如⼩于,则按照字符串实际的长度来开辟(怎样确定要存储的字符串长度,⼜是⼀个问题)。
#define CHUNCKSIZE 3 //⼀个结点保存三个字符
//结点
扣子手工制作
typedef struct Chunk{
char*ch;//实际空间->按照情况来分配
电脑如何设置自动关机struct Chunk *next;//下⼀个结点
}Chunk;
为了⽅便串的操作,除了头指针外还可以附设⼀个尾指针,并且给出当前串的长度,称这样定义的串存储结构为块链结构,因为单个结点它不是只保存⼀个数据,⽽是⼀“块”数据。
//整个串
typedef struct LString{
Chunk *first;//头指针
Chunk *last;//尾指针
述职报告格式int length;//串长
}LString;
串的链式存储结构在除了某些操作,⽐如连接两个串时,有⼀定的⽅便之处,但是总体⽽⾔没有顺序存储结构灵活,性能也不⾼,因此⽐较少⽤。