【图解数据结构】串全面总结

2024-07-13 08:12| 来源: 网络整理| 查看: 265

一、基本概念

二、串的类型

1.定长顺序串

2.堆串

3.块链串

三、模式匹配

四、总结与提高

String函数：

五、附录：

一、基本概念串（string）:由0个或多个字符组成的有序序列，称为字符串，记为s='abcdefg' 其中s是字符串的名字，a b c称为串的值，可以是字母、数字或者字符串长度：串中元素个数空串：不含任何字符的串，串长度为0子串：主串中任意连续字符组成的字符串串s1、s2相等的条件： s1、s2长度相等s1、s2对应位置的元素处处相等二、串的类型 1.定长顺序串

定义：用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。

静态存储分布代码实现：

#define MAXLEN 30 // 用户可在255以内定义最大串长 typedef struct { char ch[MAXLEN]； int len； } SString ;

动态演示：

其实就是依次插入

算法：

串插入：

int StrInsert(SString *s, int pos, SString t) /*在串s中下标为pos的字符之前插入串t */ { int i; if (poss->len) /*插入位置不合法*/ return(0); if (s->len + t.lenlen + t.len-1;i>=t.len + pos;i--) s->ch[i]=s->ch[i-t.len]; //将插入位置现有字符后移 for (i=0;ich[i+pos]=t.ch[i]; //在空出的位置逐个插入字符串 s->len=s->len+t.len; } else { if (pos+t.lenMAXLEN,但串t的字符序列可以全部插入*/ { for (i=MAXLEN-1;i>t.len+pos-1;i--) s->ch[i]=s->ch[i-t.len]; //将插入位置现有字符后移 for (i=0;ich[i+pos]=t.ch[i]; //在空出的位置逐个插入字符串 s->len=MAXLEN; } else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/ { for (i=0;ich[i+pos]=t.ch[i]; s->len=MAXLEN; } return(1); } }

串删除：

int StrDelete(SString *s, int pos, int len) /*在串s中删除从下标pos起len个字符*/ { int i; if (pos(s->len-len)) /*删除参数不合法*/ return(0); for (i=pos+len;ilen;i++) s->ch[i-len]=s->ch[i]; /*从pos+len开始至串尾依次向前移动，实现删除len个字符*/ s->len=s->len - len; /*s串长减len*/ return(1); }

串复制：

void StrCopy(SString *s, SString t) /*将串t的值复制到串s中*/ { int i; for (i=0;ich[i]=t.ch[i]; s->len=t.len; }

串比较：

int StrCompare(SString s, SString t) /*若串s和t相等则返回0；若s>t则返回正数；若slen]; //t的下标从0开始 s->len+=t.len; flag=1; } else { if (s->lenlen;ich[i]=t.ch[i-s->len]; s->len=MAXLEN; flag=0; } else flag=0; /* 串s的长度等于MAXLEN ,串t不被连接*/ return(flag); }

求子串：

int SubString(SString *sub, SString s, int pos, int len) /*将串s中下标pos起len个字符复制到sub中*/ { int i; if (poss.len || lens.len-pos) //位置或长度不合法时 { sub->len=0; return(0); } else { for (i=0; ich[i]=s.ch[i+pos]; sub->len=len; return(1); } } 2.堆串堆：自由存储区域，malloc()实现以一组地址连续的存储单元存储串值的字符序列，在程序执行过程中由动态分配而得到

代码：

typedef struct { char *ch; // 若非空串则按串长分配存储区,否则为NULL int length;// 串长度 } HString; 3.块链串定义：与链表类似，但每一个结点可以存放多个字符，结尾增加尾指针

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA55-l5b-D5a6d6LSd,size_20,color_FFFFFF,t_70,g_se,x_16

代码实现：

#define BLOCK_SIZE 4 // 可由用户定义的块大小 typedef struct Block { char ch[BLOCK_SIZE]; struct Block *next; } Block; 三、模式匹配定义：求解子串首次在主串中出现的位置模式匹配也称为子串的定位操作，用函数StrIndex(S,pos,T)实现，T被称为模式串。

代码：

int StrIndex(SString s,int pos, SString t) /*求从主串s的下标pos起，串t第一次出现的位置，成功返回位置序号，不成功返回-1*/ { int i, j, start; if (t.len==0) return(0); /* 模式串为空串时，是任意串的匹配串 */ start=pos; i=start; j=0; /* 主串从pos开始，模式串从头（0）开始 */ while (i

【本文地址】

公司简介

联系我们