3種字符串存儲結構詳解

串也是一類特殊的線性表，故其存儲結構與線性表的存儲結構類似，只不過組成串的結點是單個字符而已。本文我們就結合線性表的存儲結構和大家一起來探討一下3種字符串存儲結構。

1.定長順序存儲

也稱為靜態存儲分配的順序串。即用一組地址連續的存儲單元依次存放串中的字符序列?！岸ㄩL”、“靜態”的意思可簡單地理解為一個確定的存儲空間，它的長度是不變的。

串長的表示方法：

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

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

字符串This is a dog. 的存儲形式對比，要知道，串的靜態存儲結構(簡單一維數組表示)，大小不可變。

注意：

1)串的實際長度可在這個預定義長度的范圍內隨意設定，超過預定義長度的串值則被舍去，稱之為“截斷”。

2)字符類型存儲的是對應字符在 ASCII 里的值，10進制表示!

#define len 255

typedef unsigned char string[len + 1];//0單元存儲穿的長度

定長順序存儲表示時串操作的缺點 ：

需事先預定義串的最大長度，這在實際的程序運行前是很難估計的。

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

克服辦法：不限定最大長度——動態分配串值的存儲空間。

需要注意的是，C沒有字符串類型，C的字符串類型實際上是字符數組。而常說的C風格字符串，實際是末尾元素為零的字符數組。其他字符串風格取決于該語言設計思想，如Pascall語言為了強化類型管理與簡化實現，字符串類型不要求字符串尾部有特殊字符表示字符串結束，而采用一種數據結構來管理字符串，在字符串頭部分別有兩個字段表示了該字符串的長度和引用計數。這樣，簡單的指針賦值直接復制地址并增加引用計數即可。而且字符串長度也不用每次都要重新計算。后來的C++、Java等語言都借鑒了這樣的設計思想。

2.堆分配存儲(很重要，經常用)

堆存儲結構的特點：

仍以一組空間足夠大的、地址連續的存儲單元依次存放串值字符序列，但它們的存儲空間是在程序執行過程中動態分配的，C 語言中提供的串類型就是以這種存儲方式實現的。

由動態分配函數 malloc() 分配一塊實際串長所需要的存儲空間(“堆”)，如果分配成功，則返回此空間的起始地址，作為串的基址，由 free( ) 釋放串不再需要的空間。

typedef struct {

char *chr;//存放穿的手地址，其實編寫程序，只要思路清晰，基礎知識點明白，那么一定能寫出來

int len;

} strHeap;

這樣分配的字符串，對分配的，可以動態改變長度，進行串的復制，插入，連接，置換算法等

堆存儲結構的優點：

堆存儲結構既有順序存儲結構的特點，處理(隨機取子串)方便，操作中對串長又沒有任何限制，更顯靈活，因此在串處理的應用程序中常被采用。

3.塊鏈存儲

剛剛的堆分配，其實還是順序表的動態分配的演化。那么自然有鏈表的演化，串值也可用單鏈表存儲，簡稱為鏈串。 鏈串與單鏈表的差異只是它的結點數據域為單個字符。

優點：便于插入和刪除 缺點：空間利用率低 ，這里知道一個公式：

為了提高空間利用率，可使每個結點存放多個字符(這是順序串和鏈串的綜合 (折衷) )，稱為塊鏈結構。 實際應用時，可以根據問題所需來設置結點的大小。例如：在編輯系統中，整個文本編輯區可以看成是一個串，每一行是一個子串，構成一個結點。即：同一行的串用定長結構(80個字符)，行和行之間用指針相聯接。

為了便于進行串的操作(連接等)，當以塊鏈存儲串值時，除頭指針外還可附設一個尾指針指示鏈表中的最后一個結點，并給出當前串的長度。

先表示塊鏈的結點的結構(這也是這類問題的慣常做法，鏈式的，可以考慮定義單個的結點，然后定義整體的組織，從小到大，由內而外。)

typedef struct string{

char chr[100];//數據=塊

struct string *next;//鏈

} string;

串的鏈表結構

typedef struct {

string *head;//

string *tail;

int len;

} String;

以上就是3種字符串存儲結構的詳細情況，我們可以根據字符串的特性來判斷字符串存儲結構。這些基本的Java知識在本站的Java基礎教程中都有很完美的講解，需要的小伙伴可以隨時觀看學習。