串也是一類特殊的線性表，故其存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似，只不過(guò)組成串的結(jié)點(diǎn)是單個(gè)字符而已。本文我們就結(jié)合線性表的存儲(chǔ)結(jié)構(gòu)和大家一起來(lái)探討一下3種字符串存儲(chǔ)結(jié)構(gòu)。

1.定長(zhǎng)順序存儲(chǔ)

也稱為靜態(tài)存儲(chǔ)分配的順序串。即用一組地址連續(xù)的存儲(chǔ)單元依次存放串中的字符序列?！岸ㄩL(zhǎng)”、“靜態(tài)”的意思可簡(jiǎn)單地理解為一個(gè)確定的存儲(chǔ)空間，它的長(zhǎng)度是不變的。

串長(zhǎng)的表示方法：

1)在串的存貯區(qū)首地址顯式地記錄串的長(zhǎng)度。 方便使用，一目了然，比如Pascal語(yǔ)言。

2)在串之后加結(jié)束標(biāo)志，隱式記錄串的長(zhǎng)度，不直觀，如C/C++ 使用 “\0”。這里使用的是1)中的顯式方式記錄串長(zhǎng)度。

字符串This is a dog. 的存儲(chǔ)形式對(duì)比，要知道，串的靜態(tài)存儲(chǔ)結(jié)構(gòu)(簡(jiǎn)單一維數(shù)組表示)，大小不可變。

注意：

1)串的實(shí)際長(zhǎng)度可在這個(gè)預(yù)定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)預(yù)定義長(zhǎng)度的串值則被舍去，稱之為“截?cái)唷薄?/p>

2)字符類型存儲(chǔ)的是對(duì)應(yīng)字符在 ASCII 里的值，10進(jìn)制表示!

#define len 255

typedef unsigned char string[len + 1];//0單元存儲(chǔ)穿的長(zhǎng)度

定長(zhǎng)順序存儲(chǔ)表示時(shí)串操作的缺點(diǎn) ：

需事先預(yù)定義串的最大長(zhǎng)度，這在實(shí)際的程序運(yùn)行前是很難估計(jì)的。

由于定義了串的最大長(zhǎng)度，使得串的某些操作受限(截尾)，如串的聯(lián)接、插入、置換等運(yùn)算。

克服辦法：不限定最大長(zhǎng)度——?jiǎng)討B(tài)分配串值的存儲(chǔ)空間。

需要注意的是，C沒(méi)有字符串類型，C的字符串類型實(shí)際上是字符數(shù)組。而常說(shuō)的C風(fēng)格字符串，實(shí)際是末尾元素為零的字符數(shù)組。其他字符串風(fēng)格取決于該語(yǔ)言設(shè)計(jì)思想，如Pascall語(yǔ)言為了強(qiáng)化類型管理與簡(jiǎn)化實(shí)現(xiàn)，字符串類型不要求字符串尾部有特殊字符表示字符串結(jié)束，而采用一種數(shù)據(jù)結(jié)構(gòu)來(lái)管理字符串，在字符串頭部分別有兩個(gè)字段表示了該字符串的長(zhǎng)度和引用計(jì)數(shù)。這樣，簡(jiǎn)單的指針賦值直接復(fù)制地址并增加引用計(jì)數(shù)即可。而且字符串長(zhǎng)度也不用每次都要重新計(jì)算。后來(lái)的C++、Java等語(yǔ)言都借鑒了這樣的設(shè)計(jì)思想。

2.堆分配存儲(chǔ)(很重要，經(jīng)常用)

堆存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：

仍以一組空間足夠大的、地址連續(xù)的存儲(chǔ)單元依次存放串值字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配的，C 語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。

由動(dòng)態(tài)分配函數(shù) malloc() 分配一塊實(shí)際串長(zhǎng)所需要的存儲(chǔ)空間(“堆”)，如果分配成功，則返回此空間的起始地址，作為串的基址，由 free( ) 釋放串不再需要的空間。

typedef struct {

char *chr;//存放穿的手地址，其實(shí)編寫程序，只要思路清晰，基礎(chǔ)知識(shí)點(diǎn)明白，那么一定能寫出來(lái)

int len;

} strHeap;

這樣分配的字符串，對(duì)分配的，可以動(dòng)態(tài)改變長(zhǎng)度，進(jìn)行串的復(fù)制，插入，連接，置換算法等

堆存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：

堆存儲(chǔ)結(jié)構(gòu)既有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，處理(隨機(jī)取子串)方便，操作中對(duì)串長(zhǎng)又沒(méi)有任何限制，更顯靈活，因此在串處理的應(yīng)用程序中常被采用。

3.塊鏈存儲(chǔ)

剛剛的堆分配，其實(shí)還是順序表的動(dòng)態(tài)分配的演化。那么自然有鏈表的演化，串值也可用單鏈表存儲(chǔ)，簡(jiǎn)稱為鏈串。 鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。

優(yōu)點(diǎn)：便于插入和刪除 缺點(diǎn)：空間利用率低 ，這里知道一個(gè)公式：

為了提高空間利用率，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符(這是順序串和鏈串的綜合 (折衷) )，稱為塊鏈結(jié)構(gòu)。 實(shí)際應(yīng)用時(shí)，可以根據(jù)問(wèn)題所需來(lái)設(shè)置結(jié)點(diǎn)的大小。例如：在編輯系統(tǒng)中，整個(gè)文本編輯區(qū)可以看成是一個(gè)串，每一行是一個(gè)子串，構(gòu)成一個(gè)結(jié)點(diǎn)。即：同一行的串用定長(zhǎng)結(jié)構(gòu)(80個(gè)字符)，行和行之間用指針相聯(lián)接。

為了便于進(jìn)行串的操作(連接等)，當(dāng)以塊鏈存儲(chǔ)串值時(shí)，除頭指針外還可附設(shè)一個(gè)尾指針指示鏈表中的最后一個(gè)結(jié)點(diǎn)，并給出當(dāng)前串的長(zhǎng)度。

先表示塊鏈的結(jié)點(diǎn)的結(jié)構(gòu)(這也是這類問(wèn)題的慣常做法，鏈?zhǔn)降?，可以考慮定義單個(gè)的結(jié)點(diǎn)，然后定義整體的組織，從小到大，由內(nèi)而外。)

typedef struct string{

char chr[100];//數(shù)據(jù)=塊

struct string *next;//鏈

} string;

串的鏈表結(jié)構(gòu)

typedef struct {

string *head;//

string *tail;

int len;

} String;

以上就是3種字符串存儲(chǔ)結(jié)構(gòu)的詳細(xì)情況，我們可以根據(jù)字符串的特性來(lái)判斷字符串存儲(chǔ)結(jié)構(gòu)。這些基本的Java知識(shí)在本站的Java基礎(chǔ)教程中都有很完美的講解，需要的小伙伴可以隨時(shí)觀看學(xué)習(xí)。