数据结构复习总结第四章串

数据结构复习总结第四章串  

　　第四章串

　　 串及其运算

　　 串的基本概念

　　串是由零个或多个字符组成的有限序列;

　　包含字符的个数称串的长度;长度为零的串称空串;由一个或多个空格组成的串称空白串;

　　串中任意个连续字符组成的子序列称该串的子串;包含子串的串称主串;

　　子串的首字符在主串中首次出现的位置定义为子串在主串中的位置;

　　空串是任意串的子串;任意串是自身的子串;

　　串常量在程序中只能引用但不能改变其值;串变量取值可以改变;

　　 串的基本运算

　　 ) int strlen(char *s);求串长

　　 ) char *strcpy(char * to char * from);串复制

　　 ) char *strcat(char * to char * from);串联接

　　 ) int strcmp(char *s char *s );串比较

　　 ) char *strchr(char *s char c);字符定位

　　 串的存储结构

　　 串的顺序存储

　　串的顺序存储结构称顺序串 按存储分配不同分为

　　 ) 静态存储分配的顺序串

　　直接用定长的字符数组定义 以 表示串值终结

　　#define maxstrsize

　　typedef char seqstring[maxstrsize];

　　seqstring s;

　　不设终结符 用串长表示

　　Typedef struct{

　　Char ch[maxstrsize];

　　Int length;

　　}seqstring;

　　以上方式的缺点是 串值空间大小是静态的 难以适应插入 链接等操作

　　 ) 动态存储分配的顺序串

　　简单定义 typedef char * string;

　　复杂定义 typedef struct{

　　char *ch;

　　int length;

　　}hstring;

　　 串的链式存储

　　串的链式存储结构称链串 链串由头指针唯一确定 类型定义

　　typedef struct node{

　　char data;

　　struct node *next;

　　}linkstrnode;

　　typedef linkstrnode *linkstring;

　　linkstring s;

　　将结点数据域存放的字符个数定义为结点的大小 结点大小不为 的链串类型定义

　　#define nodesize

　　typedef struct node{

　　char data[nodesize];

　　struct node * next;

　　}linkstrnode;

　　 串运算的实现

　　 顺序串上的子串定位运算

　　子串定位运算又称串的模式匹配或串匹配 主串称目标串;子串称模式串

　　朴素的串匹配算法 时间复杂度为O(n^ ) 比较的字符总次数为(n m+ )m

　　Int naivestrmatch(seqstring t seqstring p)

　　{

　　int i j k;

　　int m=p length;

　　int n=t length;

　　for(i= ;i<=n m;i++){

　　j= ;k=i;

　　while(j &&t.ch[k]==p.ch[j]){

　　j++;k++;

　　}

　　if (j==m) return i;

　　}

　　return –1;

　　}

　　2. 链串上的子串定位运算。tW.WINGwIT.Com时间复杂度为O(n^2)。比较的字符总次数为(n-m+1)m。

　　Linkstrnode * lilnkstrmatch(linkstring T, linkstring P)

　　{

　　linkstrnode *shift, *t, *p;

　　shift=T;

　　t=shift;p=P;

　　while(t&&p){

　　if(t->data==p->data){

　　t=t->next;

　　p=p->next;

　　}

　　else{

　　shift=shift->next;

　　t=shift;

　　p=P;

　　}

　　}

　　if(p==NULL)

　　return shift;

　　else

　　return NULL;

　　}

　　附二:

　　第四章串

　　*************************************************************************************

　　串是零个或多个字符组成的有限序列。 ·空串：是指长度为零的串，也就是串中不包含任何字符(结点)。

　　·空白串：指串中包含一个或多个空格字符的串。

　　·在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。

　　·子串在主串中的序号就是指子串在主串中首次出现的位置。

　　·空串是任意串的子串，任意串是自身的子串。

　　串分为两种： ·串常量在程序中只能引用不能改变;

　　·串变量的值可以改变。

　　*************************************************************************************

　　串的基本运算有： ·求串长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)。链串上的子串定位运算位移是结点地址而不是整数。