串的链式存储结构

  • A+

最近比较忙,一堆论文要写,还要做各种毕业设计和课程设计,继续努力!!串的链式存储结构,其实与线性结构中的链式结构一样,它存储的元素是char元素,所以实现再实现这样的结构就没什么意义了,一个结点存放一个char,是乎也很浪费结点。我实现一下一个结点存放不同个元素,就是每个结点用一个字符数组来存储元素,不废话了,实现吧

 


定义一个抽象数据结点,这里的数据域为char数组,它的大小由_nodeLength定义,其他的变量就不用讲了,下面看看构造函数(构造串)。

 

新建一个头结点,自定义结点的字符长度,为串初始化为,下面看ValueTo方法

 

赋值串为字符数组

 

①清空串

②遍历整个字符数组,填充到结点数组中,i%this._nodeLength==0表示当前结点的字符数组被填充满了,所以要新建结点,在赋值,链接上个结点,用最后_lastNode指向新加结点,再向它填充数据

③赋值长度

 

第一个ValueTo方法有个ToChars方法

同样的遍历所有的结点,取出每个结点的字符数组的元素,用j指标表示当前结点数据元素的位置,取完后就到下一个结点,并让指标j从头来过,返回总的字符数组

 


获取指定位置的字符

①判断索引的合法性

②得出某个结点的具体位置(数组的下标)

串的链式存储结构

这里(5-1)%2 = 0

③再通过数据下标来判断结点位置是否需要+1。由上图5/2 = 2.5 = 2,由数据下标0可知不是结点最后一个元素,所以结点位置需要+1 ,2+1 = 3。表示在第三个结点,其实这里想表达的是向上取整,获得正确的结点位置。

④遍历结点找到刚刚第(刚刚得到位置)的结点

⑤再取出得到结点的对应数据下标元素

 


这里实现的是插入字符数组

①首先判断索引和字符数组等的合法性

②找出index位置对应的第几个结点(目标结点),和对应这个结点的数组元素位置(下标)

③找到目标结点的前一个结点,用于链接,并用一个临时引用保存目标结点。(等下会割断前一结点和目标结点的关系)

④新建一个结点,先保存目标结点,被插位置前面的数据元素

串的链式存储结构

⑤初始化指标为被插结点数据数组的下标,遍历要插入的字符数组,填充到对应的指标中,当指标到达结点数据域的最后时,链接这个结点到上一个结点上,并制定上一个结点为当前结点,新建一个结点,继续赋值。(注意如果字符数组的最后一个元素都已经赋值了,就不需要新建了)

⑥cur!=0时,需要链接一下前一个结点和当前新加结点,这里是弥补前面cur没有达到最后而没有进行链接,再链接新加结点和目标结点,使整条链表链接起来了

⑦chars数组元素已经插入,下面就要看被插的数据是否需要前移

⑦①当cur==0并且dataIndex==0表示不用迁移,也就是说被插元素的位置刚好的结点的第一位,在它前面插入数据,只需要新建结点保存数据就好,同时cur==0表示插入的数据刚好填充满新加的结点,这时,只需要将他们链接起来。

⑦②只需要移动少许的情况就是,目标结点被插入位置后的数据刚好可以填满,新加结点剩下的数据区域,这时只需要填充好数据,再直接链接,新加结点和目标结点的下一个结点,也就是说target结点就没用了。(这里需要注意的是目标结点是尾结点的情况)

⑦③最麻烦的就是要移动了,goIndex是需要移动元素位置的指标,用于判断移动完没,jNode,jIndex对应为前移数据的结点和位置,iNode,iIndex对应为前移数据的目标结点和位置,当前移的位置大于结点数据的长度时,就表示移动后,最后一个结点的数据都移动到前面去了,所以删除掉这结点。

⑧最后长度+插入字符数组的长度

 


这里是删除指定位置长度的子串

①先检查各种的合法性

②找到要删除位置的目标结点和位置(下标),并保存目标结点的上一个结点和目标结点

③如果是直接删除目标位置后面所有的子串的话

③①目标位置是1,则清空整条串

③②目标位置不是1,则删除目标结点目标位置后面的子串,注意如果目标位置为0时,说明目标结点整个都要被删除,这时串的尾结点就是我们先前保存的目标结点的前一个结点了

③③长度减小对应的值,返回删除成功

④对于只删除目标位置后面串的部分的,这时就需要移动了,通过index+length得到需要保留的子串的第一个位置,通过这个索引得到对应的结点和下标,遍历保留子串的每个字符,向前移动到对应被删除的位置,注意这时尾结点就是最后被赋值的结点

⑤长度减少length

 


在尾部链接加上字符串数组

①检查串和字符数组是否为空

②计算出偏移,就是最后结点可以填充字符的下标,然后其他跟赋值时差不多,只不过现在是从当前结点的offset位置开始

 


KMP匹配字符串的算法,详情看前一篇博客

 


这里是替换字符串,这里直接调用了三个写好的方法,我偷懒了(这样是不好的),也没什么好说的,用Index方法匹配到位置,再用Delete方法删除匹配的内容,再调用Insert方法插入替换的字符串

 


测试

 

结果

串的链式存储结构


写的时候我就在考虑了,这样子特么就像把链式结构写成顺序结构,后来我也想了下,能把想法,成功写出来,也特么是一种锻炼,想太多的时间,还不写出来,以后在测试性能也是可以的!

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

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