以图明志

数据结构

题外话:谈谈malloc()和free()

malloc()和free()里的学问
对于串的顺序存储,有些需要补充说明。串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区,叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。那么今天就来点题外话,谈谈malloc()和free()。

数据结构

字符串中的子串替换

串的替换
在很多编程语言中,都封装了字符串替换的操作,那么我们这里自己用C语言来实现一个字符串替换的函数。具体需求为:Replace(String S,String T,String V),用V替换主串S中出现的所有与T相等的不重叠的子串。字符串替换这个操作,需要结合我们前面讲到的几个函数。

数据结构

如何在串中删除特定长度的子串

串的删除
昨天我们写了如何在串中插入另外一个串,那么今天我们来看看对应的操作:如何在串中删除指定长度的子串。也就是,从串S1中删除第pos个字符起长度为len的子串。其实就是数组操作啦,把第pos个元素起的len个元素去掉即可。具体怎么去掉呢?把S[pos+len]赋值给S[pos],把S[pos+len+1]赋值给S[pos+1]……以此类推就OK了。

数据结构

如何在串中插入串

串的插入
继续完成一些常见的操作。比如有两个串s1,s2,现在需要把s2安插到s1的特定位置,我们今天来解决这个问题。还是要根据截断分为两种情况。如果没有截断的话,就可以将s2完全插入到s1里。首先从s1的末尾,将从pos位置到末尾的元素复制过去。比如nowamagic.net需要在第4个位置插入lol,则从第四个位置起,将整个s1拷过去,即nownowamagic.net

数据结构

寻找子串在主串中的位置

匹配主串与子串的过程
我们先来看这么一个需求。比如主串是 nowamagic.net,子串是 magic,那么如何知道 magic 在主串的第几个字符后的位置呢?设i用于主串s1中当前位置下标值,j用于子串sub中当前位置下标值。首先我们比较s1[1]与sub[1],如果相同的话,可能子串就开始了。如果不相等,那么子串仍然是从sub[1]开始,而主串s1则以s1[2]与其比较。

数据结构

串最基本的5个操作的C实现

串的最小操作子集
前面谈到串的最小操作子集:串赋值StrAssign,串比较StrCompare,求串长StrLength,串联接Concat,求子串SubString。这5种操作不可能利用其他串操作来实现,但其他串操作均可在这个最小操作子集上实现。这里我们写程序实现上面的操作吧。

数据结构

串的顺序存储结构

串在内存中如何存储?
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。既然是定长数组,就存在一个预定义的最大串长度,一般可以将实际的串长度值保存在数组的0下标位置,有的书中也会定义存储在数组的最后一个下标位置。

数据结构

串的抽象数据类型ADT

定义串的一些操作
串的逻辑结构和线性表很相似,不同之处在于串针对的是字符集,也就是串中的元素都是字符,哪怕串中的字符是“123”这样的数字组成,或者“2010-10-1CT这 样的日期组成,它们都只能理解为长度为3和长度为10的字符串,每个元素都是字符而已。

数据结构

如何比较串的大小

其实就是比较串的内部编码
两个数字,很容易比较大小。2比1大,这完全正确,可是两个字符串如何比较呢?事实上,串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。计算机中的常用字符是使用标准的ASCII编码,更准确一点,由7位二进制数表示一个字符,总共可以表示128个字符。

数据结构

数据结构里的串是什么东西?

就是字符串啦
早先的计算机在被发明时,主要作用是做一些科学和工程的计算工作,也就是现在我们理解的计算器,只不过它比小小计算器功能更强大、速度更快一些。后来发现,在计算机上作非数值处理的工作越来越多,使得我们不得不需要引入对字符的处理。于是就有了字符串的概念。
1 / 1 首页 < Prev 1 Next > 尾页 页码: