数据结构：串（c语言版）

向右看齐 2023-02-28 12:56 70阅读 0赞

# 一、串类型的定义 #

计算机上的非数值处理的对象基本上都是字符串数据。

串（或者字符串）是由零个或者多个字符组成的有限序列，串的值可以是字母、数字或者其他字符，串中字符的数目n称为串的长度，零个字符的串称为空串，它的长度为零。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

如果两个串相等，当且仅当这两个串的值相等，也就是说，只有当两个串的长度相等，并且各个对应的位置的字符都相等才相等。

由一个或者多个空格组成的串，称为空格串，它的长度为串中空格字符的个数。

在线性表中的基本操作，大多是以单个元素作为操作对象，而在串的基本操作中，通常以串的整体作为操作对象。

例1：实现定位函数Index(S,T,pos)

基本思想：在主串S中取从第i个字符起，长度和串T相等的子串和串T比较，若相等，则求得函数值为i,否则i增1直至串S中不存在和串T相等的子串为止。算法实现如下：

int Index(String S,String T,int pos){
    //T为非空串，若主串S中第pos个字符之后存在与T相等的子串
    //则返回第一个这样的子串在S中的位置，否则返回0
        if(pos>0){
        n=StrLength(S);m=Strlength(T);i=pos;
        while(i<=n-m+1){
            SubString(sub,S,i,m);//用sub返回串S的第i个字符长度为m的子串
            if(StrCompare(Sub,T)!=()) ++i;
            else return i;返回子串在主串中的位置
    }
    }
    return 0;//S中不存在与T相等的子串
    }

# 二、串的表示和实现 #

如果在程序设计语言中，串只是作为输入和输出的常量出现，则只需要存储串的串值，即字符序列即可。但是在多数非数值处理的程序中，串也以变量的形式出现。串有三种表示方法，分别如下：

## 1、定长顺序存储表示 ##

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串定长顺序存储结构中，按照预定义的大小，为每一个定义的串变量分配一个固定长度的存储区，则可用定长数组描述如下：

/*串的定长顺序存储表示*/
    # define MAXSTARLEN 255//用户可在255以内定义最大串长
    typedef unsigned char SString[MAXSTRLEN+1]//0号单元存放串的长度

串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称为截断。

（1）串联接Concat(&T,S1,S2)

假设S1、S2和T都死SString型的串变量，且串T是由串S1联结S2得到的，即串T的值的前一段和串S1的值相等，串T的值的后一段和串S2的值相等，则只要进行相应的“串值复制”操作即可，只是需按前述约定，对超长部分使用“截断”操作。基于串S1和S2长度的不同情况，串T值的产生可能有如下三种情况：1）S\[0\]+S2\[0\]<=MAXSTRLEN 2)S1\[0\]<=MAXSTRLEN,而S1\[0\]+s2\[0\]>MAXSTRLEN,则将串S2的一部分截断，得到的串T只包含串S2的一个子串 3）S1\[0\]=MAXSTRLEN，则得到的串T并非联结结果，而和串S1相等，算法描述如下：

Status Concat(SString &T,SString S1,SString s2){
    //用T返回由S1和S2联结而成的新串，若未截断，则返回TRUE,否则返回FALSE
        if(S1[0]+S2[0]<=MAXSTRLEN){//未截断
            T[1..S1[0]] = S1[1..S1[0]];
            T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
            T[0] = S1[0]+S[0];uncut=True;
    }
        else if (S1[0]<MAXSTRLEN){//截断
        T[1..S1[0]] = S1[1..S1[0]];
        T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN-S1[0]];uncut=FALSE;
    }
    else{//截断
       T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; uncut=False;
    }
    return uncut;
    }

(2)求子串SubString(&Sub,S,pos,len)

求子串的过程即为复制字符序列的过程，将串S中从第pos个字符开始长度为len的字符序列复制到串sub中。显然，本操作不会有截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回ERROR。算法描述如下：

Status SubString(SString &Sub,SString S,int pos,int len){
    //用Sub返回串S的第pos个字符起长度为len的子串
    //其中1=<pos<=StrLength且0=<len<=StrLength(S)-pos+1
    if(pos<1 || pos>S[0]||len<0||len>S[0]-pos+1)
        return ERROR;
    Sub[1..Len] = S[pos..pos+len-1];
    Sub[0]=len;return OK;
    }

综上两个操作可见，在顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度基于复制的字符序列的长度。另一操作的特点是，如果在操作中出现串序列的长度超过上界MAXSTRLEN时，约定用截尾法处理，这种情况不仅在求联接串时可能发生，在串的其他操作中，如插入、置换等也有可能发生，如果要克服这个弊端只有不限定串的最大长度，即动态分配串值的存储空间。

## 2、堆分配存储表示 ##

这种存储表示的特点是，还是以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。在c语言中，存在一个称为“堆”的自由存储区，并由c语言的动态分配函数malloc()和free()来管理。利用函数malloc()为每一个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结构的一部分。

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

这中存储结构表示是的串操作仍然是基于“字符序列的复制”。

1、串的复制操作StrCopy(&T,S)的实现算法是，若串T已经存在，则先释放串T所占空间，当串S不空时，首先为串T分配大小和串S长度相等的存储空间，然后将串S的值复制到串T中；

2、串插入的操作StrInsert（&S，pos,T）的实现算法是，为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串值的复制，算法实现如下：

Status StrInsert(HString &S,int pos,HString T){
    //1=<POS<=StrLength(S)+1,在串S的第pos个字符之前插入串T
        if(pos<1||pos>S.length+1) return ERROR;//pos不合法
        if(T.length){//T非空，则重新分配空间，插入T
            if(!(S.ch=(cahr *)realloc(S.ch,(S.length+T.length)*sizeof(cahr))))
                exit(OVERFLOW);
            for(i=S.length-1;i>=pos-1;--i)//为插入T而腾出位置
                S.ch[i+T.length]= S.ch[i];
            S.ch[pos-1..pos+T.length-2] = T.ch[0..T.length-1];//输入T
            S.length +=T.length;
    }
    return OK;
    }

以上两种存储表示通常为高级程序设计所采用。由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中也常被选用。

3、基本操作算法的描述

Status StrAssign(HString &T,char *chars){
        //生成一个其值等于串常量chars的串T
        if(T.ch) free(T.ch);//释放T原有的空间
        for(i=0,c=chars;c;++i,++c);//求chars的长度i
        if(!i){T.ch=NULL;T.length=0;}
        else{
            if(!(T.ch=(char *)malloc(i*sizeof(char))))
                exit(OVERFLOW);
            T.ch[0..i-1] = chars[0..i-1]
            T.length = i;
    }
    return OK;
    }

int StrLength(HString S){
    //返回S的元素个数，称为串的长度
        return S.length;
    }

int StrCompare(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;
    }

Status ClearString(HString &S){
        //将S清空为空串
        if(S.ch) {free(S.ch);S.ch=NULL;}
        S.length=0;
        return OK;
    }

Status Concat(HString &T,HString S1,HString S2){
    //用T返回由S1和S2连接而成的新串
        if(T.ch) free(T.ch);//释放旧空间
        if(!(T.ch=(char *)malloc((S1.length+S2.length)*sizeof(char))))
            exit(OVERFLOW);
        T.ch[0..S1.length-1] = S1[0..S1.length-1];
        T.length = S1.length+S2.length;
        T.ch[S1.length..T.length-1] = S2[0..S2.length-1];
        return OK;
    }

Status SubString(HString &Sub,HString S,int pos,int len){
    //用sub返回串S的第pos个字符长度为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));
            Sub.ch[0..len-1] = S.ch[pos-1..pos+len-2];
            Sub.length= len;
    }
        return OK;
    }

## 3、串的块链存储表示 ##

和线性表的链式存储结构类似，也可采用链表的方式存储串值。由于串结构的特殊性-结构中每个数据元素时一个字符，则用链表存储串值时，存在一个结点大小的问题，即每个结点可以存放一个字符，也可以存放多个字符。

为了方便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度，称如此定义的串存储结构为块链结构。

串的块链存储表示

#define CHUNKSIZE 80//可由用户定义的块大小
    typedef struct Chunk{
        char ch[CHUNKSIZE];
        struct Chunk *next;
    }Chunk;
    
    typedef struct{
        Chunk *head,*tail;//串的头和尾指针
        int curlen;//串的当前长度
    }LString;

由于在一般情况下，对串进行操作时，只需要从头向尾部顺序扫描即可，则对串值不必建立双向链表。设尾指针的目的是为了便于进行链接操作，但应注意连接时需处理第一个串尾的无效字符。

在链式存储方式中，结点的大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。在各种串的处理系统中，所处理的串往往很长或者很多，例如，一本书的几百万个字符，情报资料的成千上万。这就要求我们考虑串值的存储密度，存储密度可定义为

存储密度 = 串值所占的存储位/实际分配的存储位

显然，存储密度小（如结点大小为1时），运算处理放标，然而，存储占用量大。如果在串处理过程中需要进行内外存交换的话，则会因为内外存交换操作过多而影响处理的总效率，应该看到，串的字符集的大小也是一个重要的因素。一般的，字符集小，则字符的机内编码就短，这也影响串值的存储方式的选取。

串值的链式存储结构对某些串操作，如联结操作等有一定方便之处，但总的来说不如另外两种存储结构灵活，它占用存储量大则操作复杂。此外，串值在链式存储结构中串操作的实现和线性表在链表存储结构中的操作类似。