系列文章目錄

第五話 數(shù)據(jù)結(jié)構(gòu)之串

前言

串（即字符串）是一種特殊的線性表，在信息檢索、文本編輯等領(lǐng)域有廣泛的應(yīng)用。其特殊性體現(xiàn)在組成線性表的每個(gè)數(shù)據(jù)元素是單個(gè)字符，而由一個(gè)個(gè)字符串起的字符串卻是最基本的非數(shù)值數(shù)據(jù)，在操作過程中常常作為一個(gè)整體來處理。研究串的特點(diǎn)、存儲(chǔ)結(jié)構(gòu)和基本操作實(shí)現(xiàn)，是非常有必要的。

一、串的定義

1.串的定義

串是由零個(gè)或任意多個(gè)字符組成有限序列。一般記為：s="a1a2a3...an"(n>=0)

串可以是字母、數(shù)字或其他字符，n為串的長(zhǎng)度。

2.串的相關(guān)術(shù)語

（1）空串。不含任何字符的串稱為空串，即串的長(zhǎng)度n=0時(shí)，稱為空串。

（2）空格串。由一個(gè)或多個(gè)稱為空格的特殊字符組成的串稱為空格串，其長(zhǎng)度是串中空格字符的個(gè)數(shù)。

（3）子串。串中任意連續(xù)的字符組成的子序列稱為該串的子串。另外，空串是任意串的子串，任意串是自身的子串。

（4）主串。包含子串的串稱為該子串的主串。

（5）匹配模式。子串的定位運(yùn)算又稱為串的匹配模式，是一種求子串在主串中第一次出現(xiàn)的第一個(gè)字符的位置。

（6）串相等。兩個(gè)串的長(zhǎng)度相等且各個(gè)位置上對(duì)應(yīng)的字符也都相同。

二、串的基本特征

對(duì)照串的定義和線性表的定義可知，串是一種其數(shù)據(jù)元素固定為字符的線性表。但是，串的基本操作對(duì)象和線性表的操作對(duì)象卻有很大的不同。線性表上的操作是針對(duì)其某個(gè)元素進(jìn)行的，而串上的操作主要是針對(duì)串的整體或串的一部分子串進(jìn)行的。這也是把串單獨(dú)作為一章的原因。

三、串的基本操作?

1.定義存儲(chǔ)結(jié)構(gòu)--順序存儲(chǔ)

#include<stdio.h>
#include<stdlib.h>
#define maxsize 80
typedef char Elemtype;
typedef struct{
    Elemtype date[maxsize];
    int Len;
}String;

2.將串進(jìn)行初始化

String *init_string()
{
    String *s;
    s = (String*)malloc(sizeof(String));
    if(s!=NULL){
        s->Len=0;
    }
    return s;
}

3. 創(chuàng)造一個(gè)串并求其串長(zhǎng)度

void createstring(String *s)
{
    printf("請(qǐng)輸入一段字符串，按回車結(jié)束：\n");
    gets(s->date);
    int i=0,j=0;
    while(s->date[i]!='\0'){
        i++;
        j++;
    }
    s->Len = j;
}

?4.在主函數(shù)中實(shí)現(xiàn)調(diào)用

int main()
{
    String *s1;
    s1 = init_string();
    createstring(s1);
    printf("%s",s1->date);
    return 0;
}

?

四、字符串的匹配模式

?1.在主串中找子串第一次出現(xiàn)的位置

int stringindex(String *s1,String *s2)
{
    int i=0,j=0,k;
    while(i<s1->Len&&j<s2->Len){
        if(s1->date[i]==s2->date[j]){
            i++;
            j++;
        }else{
            i = i-j+1;
            j = 0;
        }
    }
    if(j>=s2->Len){
        k=i-s2->Len+1;
    }else{
        k=-1;//如果沒找到則返回值-1;
    }
    return k;
}

2.在主串中刪除子串

void deletestring(String *s,int i,int j)
{
    int k;
    if(i+j-1>s->Len){
        printf("所要?jiǎng)h除的子串越界!");
    }else{
        for(k=i+j-1;k<s->Len;k++,i++){
            s->date[i-1] = s->date[k];
        }
    s->Len = s->Len-j;
    s->date[s->Len]= '\0';
    }
}

在主函數(shù)中實(shí)現(xiàn) 如下:

int main()
{
    String *s1;
    String *s2;
    s1 = init_string();
    s2 = init_string();
    createstring(s1);//創(chuàng)造一個(gè)主串
    createstring(s2);//創(chuàng)造一個(gè)子串
    int a = stringindex(s1,s2);//得到子串的位置
    int b = s2->Len;//得到子串的長(zhǎng)度從而刪除
    deletestring(s1,a,b);
    printf("%s",s1->date);
    return 0;
}

3.在主串中插入子串?

void insertstring(String *s1,String *s2,int i)//在第i位中插入
{
    int j;
    if(i>s1->Len+1){
        printf("插入的位置錯(cuò)誤");
    }else if(s1->Len+s2->Len>maxsize){
        printf("兩串長(zhǎng)度超過存儲(chǔ)空間長(zhǎng)度");
    }else{
        for(j=s1->Len-1;j>=i-1;j--){//將第i位開始的字符各向后移動(dòng)s2串長(zhǎng)度
            s1->date[s2->Len+j] = s1->date[j];
        }
        for(j=0;j<s2->Len;j++){
            s1->date[i+j-1] = s2->date[j];//將子串s2插入到s1的第i個(gè)位置處
        }
        s1->Len = s1->Len+s2->Len-1;
        s1->date[s1->Len] = '\0';
    }
}

在主函數(shù)中實(shí)現(xiàn) 如下:

int main()
{
    String *s1;
    String *s2;
    s1 = init_string();
    s2 = init_string();
    createstring(s1);//創(chuàng)造一個(gè)主串
    createstring(s2);//創(chuàng)造一個(gè)子串
    int a = s1->Len;//得到主串的位置
    insertstring(s1,s2,a);
    printf("%s",s1->date);
    return 0;

4.比較兩個(gè)串的大小?

void cmpstring(String *s1,String *s2)
{
    int i=0,flag=0;
    while(s1->date[i]!='\0'&&s2->date[i]!='\0'){
        if(s1->date[i]!=s2->date[i]){//兩串對(duì)應(yīng)的位置是否相等
            flag = 1;
            break;
        }else{
            i++;
        }
    }
    if(flag==0&&s1->Len==s2->Len){
        printf("兩串相等\n");
    }else{
        printf("兩個(gè)串不相等,兩串ASCII差值為%d\n",s1->date[i]-s2->date[i]);
        //不相等返回不同位置的ASCII碼差值
    }
}

?在主函數(shù)中實(shí)現(xiàn) 如下:

int main()
{
    String *s1;
    String *s2;
    s1 = init_string();
    s2 = init_string();
    creatstring(s1);
    creatstring(s2);
    cmpstring(s1,s2);
    return 0;
}

?

五、總結(jié)

1、串的基本概念

串是一種特殊的線性表，規(guī)定每個(gè)數(shù)據(jù)元素僅由一個(gè)字符組成。串上的操作主要是針對(duì)串的整體或串的一部分子串進(jìn)行的。

2、串的存儲(chǔ)結(jié)構(gòu)

串是字符型的線性表，與線性表類似，串也有兩種基本存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。由于串的特殊性。主要運(yùn)用順序存儲(chǔ)。

3、串的運(yùn)算實(shí)現(xiàn)

串的基本運(yùn)算包括串的連接、插入、刪除、比較、尋找等，要求重點(diǎn)掌握串的定長(zhǎng)順序存儲(chǔ)的基本算法。文章來源地址http://www.zghlxwxcb.cn/news/detail-415969.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--串的基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！