数据结构复习要点第四章串
编辑整理:陕西自考网 发表时间:2018-05-23 12:26:53 字体大小:【大 中 小】 【添加招生老师微信】
《自考视频课程》名师讲解,轻松易懂,助您轻松上岸!低至199元/科!
串是零个或多个字符组成的有限序列。 ·空串:是指长度为零的串,也就是串中不包含任何字符(结点)。
·空白串:指串中包含一个或多个空格字符的串。
·在一个串中任意个连续字符组成的子序列称为该串的子串,包含子串的串就称为主串。
·子串在主串中的序号就是指子串在主串中首次出现的位置。
·空串是任意串的子串,任意串是自身的子串。
串分为两种: ·串常量在程序中只能引用不能改变;
·串变量的值可以改变。
串的基本运算有: ·求串长strlen(char*s)
·串复制strcpy(char*to,char*from)
·串联接strcat(char*to,char*from)
·串比较charcmp(char*s1,char*s2)
·字符定位strchr(char*s,charc)
.串是特殊的线性表(结点是字符),所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。顺序串又可按存储分配的不同分为: ·静态存储分配:直接用定长的字符数组来定义。优点是涉及串长的操作速度快,但不适合插入、链接操作。
·动态存储分配:是在定义串时不分配存储空间,需要使用时按所需串的长度分配存储单元。
串的链式存储就是用单链表的方式存储串值,串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。为了解决"存储密度"低的状况,可以让一个结点存储多个字符,即结点的大小。 顺序串上子串定位的运算:又称串的"模式匹配"或"串匹配",是在主串中查找出子串出现的位置。在串匹配中,将主串称为目标(串),子串称为模式(串)。这是比较容易理解的,串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是O((n-m+1)m),假如m与n同阶的话则它是O(n^2)。链串上的子串定位运算位移是结点地址而不是整数
本文标签:陕西自考串讲笔记数据结构复习要点第四章串
转载请注明:文章转载自(http://www.sxzk.sx.cn)
《陕西自考网》免责声明:
1、由于各方面情况的调整与变化,本网提供的考试信息仅供参考,考试信息以省考试院及院校官方发布的信息为准。
2、本网信息来源为其他媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com。