4.2.3 串的块链存储表示

  由于在一般情况下,串的操作都是从前往后进行的,因此串的链表通常不设双链,也不设头结点,但为了便于进行诸如串的联接等操作,链表中还附设有尾指针,并且由于串的长度不一定是结点大小的整数倍(链表中最后一个结点中的字符非都是有效字符),因此还需要一个指示串长的域。称如此定义的存储结构为串的块链存储结构,其定义如下:

  const CHUNKSIZE = 80;     // 可由用户定义的块(结点)大小
  typedef struct Chunk {   // 结点结构
   char ch[CUNKSIZE];
   struct Chunk *next;
  } Chunk;
  typedef struct {      // 串的链表结构
   Chunk *head, *tail;     // 串的头指针和尾指针
   int curlen;         // 串的当前长度
  } LString;
 
 
  和线性表的链式存储结构类似,也可用链表来存储串值。但由于串的结构的特殊性,即串的数据元素是一个字符,它只有8位二进制数,因此用链表存储串值时通常采用的办法是在一个结点中存放多个字符(如下图所示),因此称它为"块链"存储表示。图中的 "结点大小" CHUNKSIZE=4。


 
    在以链表存储串值时,定义串的存储密度为

   

  显然,以块链作存储结构时实现串的操作很不方便,如在串中插入一个子串时可能需要分割结点,联接两个串时,若第一个串的最后一个结点没有填满时还需要添加其它字符等等。但在应用程序中,可将串的链表存储结构和串的定长结构结合使用。例如在正文编辑系统中,整个"正文"可以看成是一个串,每一行是一个子串,构成一个结点,即:同一行的串用定长结构(80个字符),而行和行之间用指针相链。
 

  假设指针域 next 占16"位(bit)",则上图中串的存储密度为2/3。