首页 > 代码库 > 第四章:1.串 -- 串类型定义及串的表示和实现

第四章:1.串 -- 串类型定义及串的表示和实现

前言:

  计算机上的应用程序几乎都是以字符串数据作为处理对象,然而,现今我们使用的计算机的硬件结构主要是反映数值计算的需要的,因此,在处理字符串数据时比处理整数和浮点数要复杂得多。而且,在不同类型的应用中,所处理的字符串具有不同的特点,要有效地实现字符串的处理,就必须根据具体情况使用合适的存储结构。这一章,我们将讨论一些基本的串处理操作 和 几种不同的存储结构。

 

目录:

  1.串类型的定义

  2.串的表示和实现

    2.1.定长顺序存储表示

    2.2.堆分配存储表示

    2.3.串的快链存储表示

  3.串的模式匹配算法

  4.串操作应用剧烈

 

正文:

  串类型的定义

  串(string)(或字符串)是由 零个或多个字符 组成的有限序列,一般记为:

      s=‘ a1a2...an ‘

  注意:由一个或多个空格组成的串,称为空格串。而不是空串。

    

    串 和 字符序列(char * =‘hello‘)的区别:

      串是一种数据结构,是字符的集合,实现并提供对这种集合操作的各种方法。

      char 是c 的一种基本数据类型,没有已实现的对字符序列的复杂操作。

 

  串的逻辑结构和线性表极为相似,区别在于:

    1.串的数据对象约束为字符集。

    2.在线性表的基本操作中,以“单个数据元素” 为操作对象。 在串中 以 “串的整体” 作为操作对象,例如:查找子串、插入及删除子串。

 

  串的表示及实现

    串有3种机内表示方法:

    1.定长顺序存储 表示

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

 

      存储表示:

        #define MAXSTRLEN 255                 //定义最大串长

        typedef  unsigned char SString [MAXSTRLEN +1];    //0单元存放串的长度

 

      串的实际长度可在这预定义长度的范围内随意, 超出的部分被舍弃,称之为 “截断” 。

 

      弊端:当合并两个 串的时候,如果长度超过 预定义最大串长MAXSTRLEN ,其它部分将会丢失即 “截断”。

 

      解决方案:使用不限定串长的最大长度, 即动态分配串值的存储空间。

 

    2.堆分配存储表示

      特点:仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得。

      在 C 语言中,存在一个称之为 “堆” 的自由存储区, 并由C 语言的动态分配函数 malloc() 和 free()来管理。利用malloc 函数为每个新产生的串分配一块实际串长所需的存储空间,若分配成功,则返回一个指向起始地址的指针,作为串的基址,同时,为了处理方便,约定串长也作为存储结构的一部分。

 

      堆分配存储表示:

        typedef struct {

          char *ch;          //若是非空串,则按串长分配存储区,否则 ch 为 NULL

          int  length;         // 串长度

        }HSring;

 

      代码实现:

#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define MAXQSIZE 5
//Status是函数的类型,其值是函数结果状态码
typedef int Status;

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

//生成一个其值等于串常量 chars  的串T
Status StrAssign(HString &S,char * chars){
    int i;
    for(i=0;chars[i];i++){}
    //if(S.ch){
    //    free(S.ch);
    //    S.ch=NULL;
    //}
    if(!i){
        S.ch=NULL;
        S.length=0;
    }else{
        S.ch=(char *)malloc(i*sizeof(char));
        if(!S.ch) exit(OVERFLOW);
        S.length=i;
        for(int j=0;j<i;j++)
            S.ch[j]=chars[j];
    }
    return OK;
}

//返回串长度
int StrLength(HString &S){
    return S.length;
}

//比较大小,若 S>T 返回值>0。相等 返回0 ,否则返回 <0
int StrCompare(HString S,HString T){
    for(int 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;
}

//清空串S为空串,并释放所占空间
Status ClearString(HString &S){
    if(S.ch){
        free(S.ch);
        S.ch=NULL;
    }
    S.length=0;
    return OK;
}

//连接两个字符串,生成一个新的字符串
Status Concat(HString &T,HString S1,HString S2){
    //if(T.ch) free(T.ch);
    T.ch=(char *)malloc((S1.length+S2.length)*sizeof(char));
    if(!T.ch) exit(OVERFLOW);
    T.length=S1.length+S2.length;
    for(int i=0;i<S1.length;i++)
        T.ch[i]=S1.ch[i];

    for(i=0;i<S2.length;i++)
        T.ch[i+S1.length]=S2.ch[i];

    return OK;
}

//字符串截取,返回截取的串
Status SubString(HString &sub,HString S,int pos,int len){
    if(pos<1||pos>S.length||len<0||(S.length-pos+1)<len)
        return ERROR;
    //if(sub.ch) free(sub.ch);
    sub.ch=(char *)malloc(len*sizeof(char));    
    if(!sub.ch) exit(OVERFLOW);
    for(int i=0;i<len;i++)
        sub.ch[i]=S.ch[i+pos-1];
    sub.length=len;
    return OK;
}

void printV(HString &S){
    for(int i=0;i<S.length;i++){
        printf("地址:%p,",&S.ch[i]);
        printf("值:%c\n",S.ch[i]);    
    }    
}

void prints(HString &S){
    for(int i=0;i<S.length;i++){        
        printf("%c",S.ch[i]);    
    }    
    printf("%s\n"," ");
}

void main(){
    HString S1;
    char *c="hello";    
    StrAssign(S1,c);
    ClearString(S1);
    c="hello";    
    StrAssign(S1,c);
    printf("%s","S1:");
    prints(S1);
    printV(S1);

    HString S2;
    c="China";    
    StrAssign(S2,c);
    printf("%s","S2:");
    prints(S2);
    printV(S2);

    HString T;
    Concat(T,S1,S2);
    printf("%s","T:");
    prints(T);
    printV(T);

    HString sub;
    SubString(sub,T,6,5);
    printf("%s","sub:");
    prints(sub);
    printV(sub);
}

 

      运行结果:

      技术分享      

第四章:1.串 -- 串类型定义及串的表示和实现