串的链式存储结构Ⅱ

  • A+

上一篇的链式存储结构中,结点中的数据域都是要求能装满就装满的,这样虽然减少了对空间的浪费,但是在发生插入或删除的时候,有可能造成大量的移动,这就像顺序存储结构那样了。这次我们改一下,每个结点都可以不存满,余下的空间存'\0',新增一个结点长度,来表示结点真实存储的数据大小。


 

可以看出只有结点那里不一样了,新增加了一个结点真实长度域,ValueTo方法也没有怎么变

 

没什么好说的,只有数组的指标直接使用了结点真实长度,方便快捷了,最后一个结点的空闲位置用'\0'填充

 


上面出现了个ToChar方法

①判断串是否为空

②新建对应串长度的字符数组

③遍历每一个结点,将每个结点应的不同或相同长度的字符,按顺序赋值的对应位置的字符数组

④最后就返回字符数组的引用

 


①检查索引的合法性

②找到对应的结点

③取出对应结点对应位置的数据

串的链式存储结构Ⅱ

 


链接字符数组在串的后面,这里跟上次的也差不多,跟ValueTo方法也很相同。这里直接向最后一个结点赋值数据,若最后结点已满,则更改最后一个结点为新的结点,继续赋值填充数据,最后修改长度就好。

 


①检查字符串,字符数组和索引的合法性

②找到插入位置的结点和它的前一个结点,并找出插入位置结点的插入位置下标

③同上次,将插入结点分为插入位置前和后。当sub == 0 时,表示直接在其前结点或增加结点填充,sub != 0 时,表示插入结点有数据需要先保存

④先填充原插入结点的数据,再填充插入的字符数组,再填充插入结点插入位置和其后的数据

⑤注意结点的链接,注意抛弃插入结点后的情况

这里的步骤就不详细说了,可以参照上一篇,这里少了移动,只是将空闲的位置保留着

 


①判断索引和串的合法性

②找到删除位置的结点,和下标,考虑特殊情况,删除下标后面的所有子串

③若不是特殊情况,找到需要保留的结点和下标位置,考虑保留结点的结点数据长度小于或等于删除结点的删除数据。(保留下标>=删除下标),将保留结点的数据填充到删除结点中,节省空间,然后抛弃保留结点,链接删除结点和保留节点的下一个结点

④如果删除结点的删除空间不足填充保留结点的数据,那么修改删除结点的长度为相应长度(sub),填充空闲位置为'\0',然后将保留结点的数据前移到最前面,修改长度

⑤对应长度减少


KMP匹配算法,这个也不说了哈


替换子串为其他串,这个也不说了哈

 


测试

 

结果

串的链式存储结构Ⅱ

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: