串的鏈式存儲

串的鏈式存儲

鏈串
    　用單鏈表方式存儲串值串的這種鏈式存儲結構簡稱為鏈串
  
鏈串的結構類型定義
    typedef struct node{
        char data;
        struct node *next;
      }LinkStrNode;  //結點類型
    typedef LinkStrNode *LinkString; //LinkString為鏈串類型
    LinkString S; //S是鏈串的頭指針
 
　注意
　　①鏈串和單鏈表的差異僅在於其結點數據域為單個字符
　　②一個鏈串由頭指針唯一確定

鏈串的結點大小
　　通常將結點數據域存放的字符個數定義為結點的大小結點的大小的值越大存儲密度越高
（）結點大小為的鏈串
　　【例】串值為abcdef的結點大小為的鏈串S如下圖所示

　　這種結構便於進行插入和刪除運算但存儲空間利用率太低

（）結點大小>的鏈串
　【例】串值為abcdef的結點大小為的鏈串S如下圖所示

　注意
　　①為了提高存儲密度可使每個結點存放多個字符
　　②當結點大小大於時串的長度不一定正好是結點大小的整數倍因此要用特殊字符來填充最後一個結點以表示串的終結
　　③雖然提高結點的大小使得存儲密度增大但是做插入刪除運算時可能會引起大量字符的移動給運算帶來不便
　　【例】上圖中在S的第個字符後插入xyz時要移動原來S中後面個字符的位置結果見下圖

       

From:http://tw.wingwit.com/Article/program/sjjg/201311/22628.html