数据结构第四章串

以你之姓@ 2022-06-18 12:11 274阅读 0赞

**数据结构笔记链接：**

[第一章 绪论][Link 1]

[第二章 线性表][Link 2]

[第三章 栈和队列][Link 3]

[第四章 串][Link 4]

[第五章 数组和广义表][Link 5]

[第六章 树和二叉树][Link 6]

[第七章 图][Link 7]

[第八章 排序][Link 8]

[第九章 查找][Link 9]

--------------------

*   *   *  4.1 串的基本概念
            
             *  4.1.1 串的概念
             *  4.1.2 串的基本运算
         *  4.2 串的存储结构
            
             *  4.2.1 顺序存储
                
                 *  4.2.1.1 定长顺序串
                 *  4.2.1.2 堆串
             *  4.2.2 链式存储
         *  4.3 模式匹配
            
             *  4.3.1 BF算法
             *  4.3.2 KMP算法（略）
         *  4.4 例题
            
             *  4.4.1 例1
             *  4.4.2 例2

--------------------

### 4.1 串的基本概念 ###

#### 4.1.1 串的概念 ####

**串**(String)是零个或多个字符组成的有限序列。一般记作 **S=“a1a2a3…an”**，其中S是`串名`，用双引号括起来的字符序列是`串值`；ai(1≦i≦n)可以是字母、数字或其它字符。串中所包含的字符个数称为该`串的长度`。

（1）主串和子串

串中**任意个连续字符**组成的**子序列**称为该串的**子串**。包含子串的串相应地称为**主串**。

通常将子串在主串中**首次**出现时的该子串的**首字符**对应的主串中的序号，定义为子串在主串中的**序号**（或**位置**）。

（2）空白串和空串

长度为零的串称为`空串(Empty String)`，它不包含任何字符。

通常将仅由一个或多个空格组成的串称为`空白串(Blank String)`。

空白串和空串的不同，如“ ”和“”分别表示**长度为1**的空白串和**长度为0**的空串。

（3）串相等

**当且仅当**两个串的**值相等**时,称这两个串是相等的,即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。

#### 4.1.2 串的基本运算 ####

（1）串赋值  
strassign(S,T)，表示将T串的值赋给S串。

（2）联接  
strcat(T1,T2)，表示将T1串和T2串联接起来，组成一个新的T1串。

（3）求串长度  
strlen (T)，求T串的长度。

（4）子串  
substr (S, i, len)，表示截取S串中从第i个字符开始连续len个字符，构成一个新串（显然该新串是S串的子串）。

（5）串比较大小  
strcmp(S,T)，比较S串和T串的大小，若S

### 4.2 串的存储结构 ###

#### 4.2.1 顺序存储 ####

##### 4.2.1.1 定长顺序串 #####

定长顺序串是将串设计成一种**静态结构类型**,串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似,可用一组**地址连续的存储单元存** 储串的字符序列。

定长顺序串类型定义如下:

#define MAXLEN 40 typedef struct { /*串结构定义*/ 
        char ch[ MAXLEN]; /*存储字符串的一维数组,每个分量存储一 个字符*/
        int len;  /*字符串的长度*/
    }
    SString;

（1）串插入

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

（2）串删除

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

##### 4.2.1.2 堆串 #####

字符串包括串名与串值两部分,而串值采用堆串存储方法存储,串名用符号表存储。

这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。

C语言已经有一个称为`堆`的自由存储空间,并可用函数`malloc()`和函数`free()`完成动态存储管理。因此,可以直接利用C语言中的“堆”来实现堆串。此时堆串可定义如下:

typedef   struct {
        char *ch; // 若是非空串, 则按串长分配存储区, 否则 ch 为NULL
        int  length;  //串长度
    } HString ;

（1）求串长

int strlen(HString s) {
        return s.length; 
    }

（2）置空

Status clearstring(HString s) {
        if (s.ch){ 
            free(s.ch);
             s.ch=NULL; 
        }
        s.length=0;
    }

（3）生成堆

//生成一个其值等于串常量chars的串t 
    Status strassign(HString t, char *chars){ 
        if(t.ch)  
            free(t.ch);  //释放原空间
        i=strlen(chars);     //求串长
        if (!i) { 
            t.ch=NULL; 
            t.length=0;  
        }  //空串
        else{ 
            if(!(t.ch=(char *)malloc(i*sizeof(char))))  //申请存储
                exit(OVERFLOW); 
            for (j=0;j<i;j++)
                t.ch[j]=chars[j];  //复制
             t.length=i;
         }
    }

（4）比较函数

int strcmp(HString s, HString t) {  
    //S>T, 返回值>0; S==T, 返回值0 ; S<T, 返回值<0 
        for(i=0;i<s.length && i<t.length; ++i)
            if(s.ch[i]!=t.ch[i]) 
                return(s.ch[i]-t.ch[i]);
        return s.length-t.length;
    }

（5）拼接函数

// 用T返回由S1和S2联接而成的新串
    Status strcat(HString t, HString s1,HString s2) { 
        if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char)))
            exit(OVERFLOW);
        for(j=0; j< s1.length ; j++)  
            t.ch[j]=s1.ch[j];
        for(k=0;k< s2.length ;k++)  
            t.ch[j+k]=s2.ch[k];
        t.length=s1.length+s2.length;
    }

（6）求子串

//用Sub返回串S的第pos个字符起长度为len的子串
    Status substr(HString sub, HString s, int pos, int len) { 
        if (pos<1 || pos>s.length || len<0 || len>s.length-pos+1)
            return ERROR;
        if (sub.ch)     
            free(sub.ch); // 释放旧空间
        if (!len) {   
            sub.ch=NULL;   
            sub.length=0; 
        } // 空子串
        else{
            sub.ch=(char *)malloc(len*sizeof(char));
            for(j=0;j<len;j++) 
                sub.ch[j]=s.ch[pos-1+j];
            s.length=len;
        }
    }

#### 4.2.2 链式存储 ####

由于串也是一种线性表,因而也可以采用链式存储。因为串是一个特殊的线性表(表中每 个元素就是一个字符)。

在具体实现时,一个链表存放一个串值,每个结点既可以存放一个字符, 如下所示：

typedef struct node{
        char data;
        struct node *next;
    }lstring;

但这种方式存储的密度太低，为了提高存储的密度，使得每个节点能够存储多个字符，为便于操作,再增加一个`尾指针`，结构可定义如下：

#define BLOCK_SIZE 4 //每结点存放字符个数
    
    typedef  struct Block  {  // 结点结构
        char  ch[ BLOCK_SIZE ];
        struct Block  *next;
    } Block;
    
    typedef struct {    // 串的链表结构
        Block *head, *tail;  // 串的头和尾指针
        int  len;     // 串的当前长度
    } BLtring;

### 4.3 模式匹配 ###

#### 4.3.1 BF算法 ####

（1）算法思想：  
将主串的第pos个字符和模式的第1个字符比较，若**相等**，继续逐个比较后续字符；若**不等**，从主串的下一字符 (pos+1) 起，重新与第一个字符比较。直到主串的一个连续子串字符序列与模式**相等** 。返回值为S中与T匹配的子序列**第一个字符的序号**，即**匹配成功**。否则，**匹配失败**，返回值 0 。

（2）程序段：

int S_index(SString t, SString p, int pos) {
        int n,m,i,j;
        m=strlen(t); n=strlen(p);
        for (i=pos-1; i<=m-n; i++){
            for (j=0; j<n && t[i+j]==p[j]; j++) ;
            if(j==n) 
                return(i+1);
        }
        return(0);
    }

#### 4.3.2 KMP算法（略） ####

### 4.4 例题 ###

#### 4.4.1 例1 ####

若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为***\_\_\_\_\_\_\_\_\_\_***。

> (n - m + 1) \* m

#### 4.4.2 例2 ####

设有两个串s和t，其中t是s的子串，求子串t在主串s中首次出现位置的算法。  
解：

int S_index(SString s, SString t) { //找到返回下标(>=1)，否则返回0;串类型为SString
        int n,m,i,j;
        m=strlen(s); 
        n=strlen(t);
        for (i=0; i<=m-n; i++){
            for (j=0; j<n && s[i+j]==t[j]; j++) ;
            if(j==n) return(i+1);
        }
        return(0);
    }

[Link 1]: http://blog.csdn.net/yuanlaijike/article/details/69442950
[Link 2]: http://blog.csdn.net/yuanlaijike/article/details/69451381
[Link 3]: http://blog.csdn.net/yuanlaijike/article/details/69472125
[Link 4]: http://blog.csdn.net/yuanlaijike/article/details/69480358
[Link 5]: http://blog.csdn.net/yuanlaijike/article/details/69486729
[Link 6]: http://blog.csdn.net/yuanlaijike/article/details/78070403
[Link 7]: http://blog.csdn.net/yuanlaijike/article/details/78074765
[Link 8]: http://blog.csdn.net/yuanlaijike/article/details/78078434
[Link 9]: http://blog.csdn.net/yuanlaijike/article/details/78078788