C語言字符串和數(shù)組怎么定義使用

這篇文章主要介紹了C語言字符串和數(shù)組怎么定義使用的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇C語言字符串和數(shù)組怎么定義使用文章都會(huì)有所收獲，下面我們一起來看看吧。

字符串和數(shù)組

字符串簡(jiǎn)稱串，是一種特殊的線性表，其特殊性在于數(shù)據(jù)元素僅由一個(gè)個(gè)字符組成。作為一種基本數(shù)據(jù)類型，字符在計(jì)算機(jī)信息處理中意義非同一般，計(jì)算機(jī)非數(shù)值處理的對(duì)象經(jīng)常是字符串?dāng)?shù)據(jù)。另外，串還具有自身的特性，常常把一個(gè)串作為一個(gè)整體來處理，因此，把串作為獨(dú)立結(jié)構(gòu)的概念加以研究是非常有必要的。本章簡(jiǎn)單介紹了串的存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算。

數(shù)組可視為線性表的推廣，其特點(diǎn)是表中數(shù)據(jù)元素仍然是一個(gè)表。從本質(zhì)上看，維數(shù)大于1的數(shù)組中數(shù)據(jù)元素之間不再是簡(jiǎn)單的一對(duì)一關(guān)系，因此，嚴(yán)格地說多維數(shù)組是非線性的。然而，由于數(shù)組中數(shù)據(jù)元素類型的一致性和其內(nèi)部結(jié)構(gòu)上的同一性，在實(shí)際處理數(shù)組時(shí)可以借助線性表的方法來實(shí)現(xiàn)數(shù)組及其運(yùn)算。本章將會(huì)介紹數(shù)組的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)、稀疏矩陣及其壓縮存儲(chǔ)等內(nèi)容。

第一節(jié) ：串

1.1 串的基本概念

串（String）是由零個(gè)或多個(gè)任意字符串組成的字符序列。記做：s ="a1a2··an"，其中，s是串名。a1（1<=i <=n）是一個(gè)任意字符，i是該元素在整個(gè)串中的序號(hào)；n為串的長(zhǎng)度，表示串中所包含的字符個(gè)數(shù)，當(dāng)n=0時(shí)，稱為空串。

子串和主串：串中任意連續(xù)的字符組成的子序列稱為該串的子串；包含子串的串相應(yīng)地稱為主串。

子串的位置：子串的第一個(gè)字符在主串中的序號(hào)稱為子串在主串中的位置。

串相等：若兩個(gè)串的長(zhǎng)度相等且每一個(gè)對(duì)應(yīng)字符都相等，就稱這兩個(gè)串是相等的。

1.2 串的基本運(yùn)算

求串長(zhǎng)：StrLength(s);
串賦值：StrAssign(s1,s2); // 將s2的串值賦予s1
連接運(yùn)算：StrConcat(s1,s2,s) 或 StrConcat(s1,s2).//在s1后面連接s2的串值，產(chǎn)生新串s
求子串：SubStr(s,i,len)；//返回s的第i至len個(gè)字符的子串值。len=0為空串。例如：SubStr("abcdefg",2,3) = "bcd"
串比較：StrComp(s1,s2)；//若s1 =s2 ,操作返回值為0；s1<s2，返回值<0；反之>0
串定位：StrIndex(s,t);//若t被包含于s中，則返回值為t的位置，反之值為-1
串插入：StrInsert(s,i,t);//將串t插入到s的第i個(gè)字符位置上
串刪除：StrDelete(s,i,len);//刪除串t中第i至len個(gè)字符的子串
串修改：StrRep(s,t,r);//用串r替換s中出現(xiàn)的所有與串t相等且不重疊的子串

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

因?yàn)榇菙?shù)據(jù)元素類型為字符的線性表，所有線性表的存儲(chǔ)方式仍適用于串，也因?yàn)樽址奶厥庑院妥址?jīng)常作為一個(gè)整體來處理的特點(diǎn)，串在存儲(chǔ)時(shí)還有一些與一般線性表不同的地方。

1、串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)：

類似于順序表，可以用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值中的字符串序列，所謂定長(zhǎng)是指按預(yù)定義的大小為每一個(gè)串變量分配固定長(zhǎng)度的存儲(chǔ)區(qū)。如下，串的最大長(zhǎng)度不能超過256。

#define MAXSIZE 256
char s[MAXSIZE]

標(biāo)識(shí)實(shí)際長(zhǎng)度的常用方法有三種：

第一種：類似順序表，用一個(gè)指針來指向最后一個(gè)字符，這樣表示的串描述如下：

typedef struct{
    char data[MAXSIZE];
    int curlen;
}SeqString;
 
SeqString s;//串變量

這種存儲(chǔ)方式可以直接得到串的長(zhǎng)度：s.curlen+1 。

第二種：在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符串作為串的終結(jié)符，以此表示串的結(jié)尾。例如，C語言中處理定長(zhǎng)串的方法就是這一點(diǎn)，它用“\0”來表示串的結(jié)束。這種存儲(chǔ)方法不能直接得到串的長(zhǎng)度，根據(jù)當(dāng)前字符是否是“\0”來確定串是否結(jié)束，從而計(jì)算出串的長(zhǎng)度。

第三種：設(shè)定串長(zhǎng)存儲(chǔ)空間：chars[MAXSIZE+1]，用s[0]來存放串實(shí)際長(zhǎng)度，而串值存放在s[1]~s[MAXSIZE]中，字符的序號(hào)和存儲(chǔ)位置一致，應(yīng)用更為方便。

2、堆分配存儲(chǔ)結(jié)構(gòu)

在順序串上的插入、刪除操作并不方便，必須移動(dòng)大量的字符，而且當(dāng)操作中出現(xiàn)串值序列的長(zhǎng)度超過上界MAXSIZE時(shí)，只能用截尾法處理。要克服這個(gè)弊病，只有不限定串的最大長(zhǎng)度，動(dòng)態(tài)分配串值的存儲(chǔ)空間。

堆分配存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是：仍以一組地址連續(xù)的存儲(chǔ)單元存放串的字符序列，但其存儲(chǔ)空間是在算法執(zhí)行過程中動(dòng)態(tài)分配得到的。在C語言中，由動(dòng)態(tài)分配函數(shù)malloc（）和free（）來管理。利用函數(shù)malloc（）為每一個(gè)新產(chǎn)生的串分配一塊實(shí)際需要的存儲(chǔ)空間，若分配成功，則返回一個(gè)指針，指向串的起始地址。串的對(duì)分配存儲(chǔ)結(jié)構(gòu)如下：

typedef struct{
    char *ch;
    int len;
 }HSTRING:

由于堆分配存儲(chǔ)結(jié)構(gòu)的串既有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，在操作中又沒有串長(zhǎng)的限制，顯得很靈活，因此，在串處理的應(yīng)用程序中常被選用。

3、定長(zhǎng)順序串基本運(yùn)算的實(shí)現(xiàn)

串連接：把兩個(gè)串s1和s2首尾連接成一個(gè)新串s，即s<-s1+s2

int StrConcat(s1,s2,s)
    char s1[],s2[],s[];//將串s1，s2合并到串s，合并成功返回1，否則返回0
{
    int i =0,j,len1,len2;
    len1 = StrLength(s1);
    len2 = StrLength(s2);
    
    if(len1+len2>MAXSIZE-1) return 0;    //s 長(zhǎng)度不夠
 
    j = 0 ;
    while(s1[j]! ="\0"){
        s[i] = s1[j];
        i++;
        j++;
    }
     while(s2[j]! ="\0"){
        s[i] = s2[j];
        i++;
        j++;
    }
    s[i] = "\0";
    return 1;
}

求子串：

int StrSub(char *t ,char *s,int i , in len){
//用t返回串s中第i個(gè)字符串開始的長(zhǎng)度為len的子串，1<=i串長(zhǎng)
    
    int slen;
    slen = StrLength(s);
    if(i<1 || i>slen || len<0 || len>slen-i+1){
        return 0;
    }
    
    for(j =0 ; j<len ; j++){
        t[j] =s[i+j-1];
        t[j] ="\0";
        return 1;
    }
}

串比較：

int StrComp(char *s1 ,char *s2){
    int i =0;
    while(s1[i] == s2[i] && s1[i]!="\0"){
        i++;
    }
    return (s1[i] -s2[i]);
}

串定位：

int StrIndex(char *s ,char *t)
//返回子串t在主串s中的位置，若不存在則返回-1
{
    int i=0, j = 0;
    while(s[i] !="\0" && t[j] !="\0"){
 
        if(s[i] == t[j]){//匹配成功，繼續(xù)比較下一個(gè)字符
            ++i;
            ++j;
        }else{         //否則主串換一個(gè)起始位置，子串重0開始
            i = i-j+1;
            j =0;
        }
        
        if( t[j] == "\0") { //匹配成功，返回匹配的第一個(gè)字符位置
            return i -j;
        }else{            
            return -1;
        }
    }

子串的定位操作通常稱做串的模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。上面的算法是一種簡(jiǎn)單的帶回溯的匹配算法，該算法思路比較簡(jiǎn)單，容易理解，但其視覺復(fù)雜度較高，最壞情況下為O(slen*slen)。

第二節(jié)： 數(shù)組

2.1 數(shù)組的邏輯結(jié)構(gòu)和基本操作

數(shù)組（Array）是一種數(shù)據(jù)結(jié)構(gòu)，高級(jí)語言一般都支持?jǐn)?shù)組這種數(shù)據(jù)類型。特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上，可以把數(shù)組看做一般線性表的擴(kuò)充。例如，一維數(shù)組就是一個(gè)線性表，二維數(shù)組就是"數(shù)據(jù)元素是一維數(shù)組"的一維數(shù)組。以此類推，即可得到多維數(shù)組的定義。

如有一個(gè)m行n列的二維數(shù)組：

可以把二維數(shù)組看成是一個(gè)線性表：A=(a1,a2····，an)，其中aj(1<=j<=n）本身也是一個(gè)線性表，稱為列向量（Column Vector），即aj=(a1j,a2j···，amj）。同樣還可以將數(shù)組A看成另外一個(gè)線性表：B={B1,B2,···，Bm),其中Bi(1<=i<=n）本身也是一個(gè)線性表，稱為行向量（Row Vector），即Bi=（ai1,ai2,····aim）。

在二維數(shù)組中，元素aij處在第i行和第j列的交叉處，即元素aij同時(shí)有兩個(gè)線性關(guān)系約束，aij既是同行元素aij-1 的“行后繼”，又是同列元素ai-1j的“列后繼”，又是同列元素ai-1j的“列后繼”。同理，三維數(shù)組可以看成這樣的一個(gè)線性表，即其中每個(gè)數(shù)據(jù)元素均是一個(gè)二維數(shù)組，即三維數(shù)組中每個(gè)元素同時(shí)有三個(gè)線性關(guān)系約束，推廣之，n維數(shù)組就是“數(shù)據(jù)元素為n-1維數(shù)組”的線性表。

由數(shù)組的結(jié)果可以看出，數(shù)組中的每一個(gè)元素由一個(gè)值和一組下表來描述。值表示數(shù)組中元素的數(shù)據(jù)信息，下標(biāo)用來描述該元素咋數(shù)組中的相對(duì)位置。數(shù)組的維數(shù)不同，描述其相對(duì)位置的下標(biāo)的個(gè)數(shù)也不同。例如，在二維數(shù)組中，元素aij由兩個(gè)下標(biāo)i、j來描述，其中i表示該元素的行號(hào)，j表示該元素的列號(hào)。

數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集，即，一旦定義了數(shù)組的維數(shù)和每維的上、下限，數(shù)組的元素個(gè)數(shù)就固定了，而且數(shù)組中的每一個(gè)元素也由唯一的一組下標(biāo)來標(biāo)識(shí)。因此，在數(shù)組上一般不能做插入、刪除數(shù)據(jù)元素的操作。對(duì)數(shù)組的操作通常只有下面兩類。

（1）取值操作：給定一組下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。

（2）賦值操作：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。

因此，數(shù)組的操作注意是數(shù)據(jù)元素的定位，即給定元素的下標(biāo)，得到該元素在計(jì)算機(jī)中的存儲(chǔ)位置。其本質(zhì)就是地址計(jì)算問題。接下來以二維數(shù)組展開說明，因?yàn)槎S數(shù)組是應(yīng)用最廣泛的，也是最基本的，對(duì)于大于二維的多維數(shù)組的存儲(chǔ)和操作方法可以類推。

2.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)

由于數(shù)組的特點(diǎn)是數(shù)組中數(shù)據(jù)元素的個(gè)數(shù)固定且其結(jié)構(gòu)不變化，數(shù)組操作基本就是取值、賦值運(yùn)算，因此，對(duì)于數(shù)組而言，采用順序存儲(chǔ)結(jié)構(gòu)表示比較合適。對(duì)于一維數(shù)組可以直接按其下標(biāo)順序分配內(nèi)存空間；而對(duì)于多維數(shù)組，必須按某種次序?qū)?shù)組中元素排成一個(gè)線性序列，然后按該序列將數(shù)據(jù)元素存放在一維的內(nèi)存空間中。

存儲(chǔ)二維數(shù)組時(shí)，一般有兩種存儲(chǔ)方式：第一種是以行序?yàn)橹餍颍ㄏ刃泻罅校┑捻樞虼鎯?chǔ)方式，即從第一行開始存放，一行存放完了接著存放下一行，直到最后一行為止；另一種是以列序?yàn)橹餍颍ㄏ攘泻笮校┑捻樞虼鎯?chǔ)方式，即一列一列的存儲(chǔ)。

以行序?yàn)橹餍虻拇鎯?chǔ)分配的規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個(gè)下標(biāo)再變，···，從右向左，最后是左下標(biāo)。以列序?yàn)橹餍虼鎯?chǔ)分配的規(guī)律恰好相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個(gè)下標(biāo)再變，···，從左向右，最后是右下標(biāo)。例如，一個(gè)2X3的二維數(shù)組，以行序?yàn)橹餍虻姆峙漤樞驗(yàn)椋篴1,a2,a3 | a4,a5,a6 ；以列序?yàn)橹餍虻姆峙漤樞驗(yàn)椋篴1,a4 | a2 ,a5| a3,a6 。

設(shè)有m × n 二維數(shù)組Amn ,按元素的下標(biāo)求存儲(chǔ)地址：

以行序?yàn)橹餍驗(yàn)槔涸O(shè)數(shù)組的基址為L(zhǎng)OC(a11）,每個(gè)數(shù)組元素占據(jù)L個(gè)地址單元，那么aij的物理地址可用一線性尋址函數(shù)計(jì)算：LOC(aij) = LOC(a11)+((i-1)× n+j-1) ×L 。因?yàn)閿?shù)組元素aij的前面有i-1行，每一行的元素個(gè)數(shù)為n，在第i行中它的前面還有j-1個(gè)數(shù)組元素。在C語言中，數(shù)組中每一維的下屆定義為0，則：LOC(aij) = LOC(a00) +(i×n+j）×L。

推廣到一般二維數(shù)組A[c1···d1][c2···d2]，則aij的物理地址計(jì)算函數(shù)為：LOC(aij) = LOC(ac1c2) +((i-c1) ×(d2-c2+1)+(j-c2))×L。同理，對(duì)于三維數(shù)組Amnp，即m×n×p數(shù)組，數(shù)組元素aijk的物理地址為：LOC(aijk) = LOC(a111）+（(i-1)×n×p+(j-1）×p+k-1）×L。

2.3 稀疏矩陣

稀疏矩陣（Sparse Matrix）是指矩陣中大多數(shù)元素為零元素的矩陣，即設(shè)m×n矩陣中有t個(gè)非零元素且t<<m×n ，則稱之為稀疏矩陣。

很多科學(xué)管理及工程計(jì)算中，常會(huì)遇到階數(shù)很高的大型稀疏矩陣。如果按常規(guī)分配方法，順序分配在計(jì)算機(jī)內(nèi)，那將是相當(dāng)浪費(fèi)內(nèi)存的。為此提出另外一種存儲(chǔ)方法，僅存放非零元素。但對(duì)于這類矩陣，通常零元素分布沒有規(guī)律，為了能找到相應(yīng)的元素，僅存儲(chǔ)非零元素的值是不夠的，還要記下它所在的行和列。于是采取如下方法：非零元素所在的行、列及它的值構(gòu)成一個(gè)三元組（i，j，v），然后按某種規(guī)律存儲(chǔ)這些三元組，這種方法可以大大節(jié)約存儲(chǔ)空間。

1、稀疏矩陣的三元組表存儲(chǔ)

將三元組按行優(yōu)先的順序，同一行中列號(hào)從小到大的規(guī)律排列成一個(gè)線性表，稱為三元組表，采用順序存儲(chǔ)方法存儲(chǔ)該表。如下圖：

這種存儲(chǔ)結(jié)構(gòu)的具體實(shí)現(xiàn)如下：

#define SMAX 1024 //足夠大的空間
typedef struct{
    int i ,j ; //非零元素的行、列
    datatype v; //非零元素值
}SPNode;     //三元組類型
 
typedef struct{
    int mu,nu,tu; //行列及非零元素個(gè)數(shù)
    SPNode data[SMAX];//三元組表
}SPMatrix; //三元組表的存儲(chǔ)類型
 
//定義一個(gè)稀疏矩陣的變量：
SPMatrix M;

稀疏矩陣的轉(zhuǎn)置運(yùn)算：

設(shè)A為一個(gè)m×n的稀疏矩陣，則其轉(zhuǎn)置矩陣B就是一個(gè)n×m的稀疏矩陣，因此它們可以采用相同的數(shù)據(jù)類型，即：

SPMatrix A，B;

轉(zhuǎn)置運(yùn)算需要完成的工作包括：A的行、列分別轉(zhuǎn)化成B的列、行；將A.data中每一個(gè)三元組的行與列交換后復(fù)制到B.data中。以上兩點(diǎn)完成之后，似乎完成了B，但實(shí)際上沒有。因?yàn)榍懊嬉?guī)定的三元組表是按行從小到大且同一行中的元素按列號(hào)從小到大的規(guī)律順序存放的，因此轉(zhuǎn)置后的矩陣B也必須按此規(guī)律排列。算法思路如下：

（1）A的行、列轉(zhuǎn)行成B的列、行；

（2）在A.data中依次找第一列的、第二列的直到最后一列的三元組，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B.data中即可。

void TransM1(SPMatrix *A){
    SPMatrix *B;
    int p,q,col;
    B = malloc(sizeof(SPMatrix));//申請(qǐng)存儲(chǔ)空間
    B ->mu =A ->nu; 
    B ->nu =A ->mu;
    B ->tu =A ->tu;//稀疏矩陣的行、列、元素個(gè)數(shù)
    if(B->tu>0){
        q=0;
        for(col =1 ;col <=(A->nu);col++){//掃描整個(gè)三元組數(shù)
            for(p=1;p<(A->nu);col++){
                if(A->data[p].j == col）{
                    B->data[q].i = A ->data[p].j;
                    B->data[q].j = A ->data[p].i;
                    B->data[q].v = A ->data[p].v;
                    q++;
                }
            }
        }
    }
    if(B->tu > 0){
        return B；
    }
}

分析該算法，其時(shí)間主要耗費(fèi)在col和p的二重循環(huán)上，所以時(shí)間復(fù)雜性為O(n×t)（設(shè)m、n是原矩陣的行、列數(shù)，他是稀疏矩陣的非零元素個(gè)數(shù)），顯然，當(dāng)非零元素的個(gè)數(shù)t和m×n同數(shù)量級(jí)時(shí)，算法的時(shí)間復(fù)雜度為O(m×n2），和通常存儲(chǔ)方式下矩陣轉(zhuǎn)置算法相比，可能節(jié)約了一定量的存儲(chǔ)空間，但算法的時(shí)間復(fù)雜度更差了一些。

算法改進(jìn)：上面算法低效率的原因是算法要從A的三元組表中尋找第一列、第二列、···，要反復(fù)查找A，若能直接確定A中每一三元組在B中的位置，則對(duì)A的三元組表掃描一次即可。這是可以做到的，因?yàn)锳中第一列的第一個(gè)非零元素一定存儲(chǔ)在B.data[1]中，如果還知道第一列的非零元素的個(gè)數(shù)，那么第二列的第一個(gè)非零元素在B.data中的位置便等于第一列的第一個(gè)非零元素在B.data中位置加上第一列的非零元素的個(gè)數(shù)。以此類推，因?yàn)锳中三元組的存放順序是先行后列，對(duì)同一行來說，必定先遇到列號(hào)小的元素，這樣只需掃描一遍A.data即可。

根據(jù)上面的想法，需要引入兩個(gè)向量來實(shí)現(xiàn)：num[n+1]和cpot[n+1]，num[col]表示矩陣A中第col列的非零元素的個(gè)數(shù)（為了方便均從1單元用起），cpot[col]初始值表示矩陣A中的第col列的第一個(gè)非零元素在B.data中位置。于是cpot的初始值為：cpot[1] =1 ；cpot[col] = cpot[col-1]+num[col -1]; 2<=col<=n 。

SPMatrix *TransM2(SPMatrix *A){
    SPMatrix *B;
    int i,j,l;
    int num[n+1],cpot[n+1];
    B = malloc(sizeof(SPMatrix));//申請(qǐng)空間
    //稀疏矩陣行列元素個(gè)數(shù)
    B->mu = A ->nu;
    B->nu =A ->mu;
    B ->tu =A ->tu;
    if(B->to > 0){
        for(i=1;i<=A->nu;i++){
            num[i] = 0;
         }
        for(i=1 ;i<=A ->tu ;i++){
             j=A->data[i].j;
             num[j]++;
         }
        cpot[1] =1; //求矩陣A中每一列第一個(gè)非零元素在B.data中的位置
        for(i =2 ;i<A->nu;i++){
            cpot[i] =cpot[i-1]+num[i-1];
        }
        for(i =1 ;i<(A->tu);i++){ // 掃描三元組表
            j =A->data[i].j;
            k =cpot[j];
            B->data[k].i = A->data[i].j;
            B->data[k].j = A ->data[i].i;
            B->data[k].v = A->data[i].v;
        }
    return B;
}

分析這個(gè)算法的時(shí)間復(fù)雜度：這個(gè)算法中有四個(gè)循環(huán)，分別執(zhí)行了n、t、n-1、t次，在每一個(gè)循環(huán)中，每次迭代的實(shí)際是一個(gè)常量，因此總的時(shí)間復(fù)雜度是O(n+t)。當(dāng)然，它所需要的存儲(chǔ)空間比前一個(gè)算法多了兩個(gè)向量的存儲(chǔ)空間。

關(guān)于“C語言字符串和數(shù)組怎么定義使用”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“C語言字符串和數(shù)組怎么定義使用”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。