Question

串的链式存储

Answer 1

串的链式存储

链串     　用单链表方式存储串值 串的这种链式存储结构简称为链串    链串的结构类型定义     typedef struct node{        char data;        struct node *next;      }LinkStrNode;  //结点类型    typedef LinkStrNode *LinkString; //LinkString为链串类型    LinkString S; //S是链串的头指针  　注意 　　①链串和单链表的差异仅在于其结点数据域为单个字符 　　②一个链串由头指针唯一确定

链串的结点大小 　　通常 将结点数据域存放的字符个数定义为结点的大小 结点的大小的值越大 存储密度越高 （ ）结点大小为 的链串 　　【例】串值为 abcdef 的结点大小为 的链串S如下图所示

　　这种结构便于进行插入和删除运算 但存储空间利用率太低

（ ）结点大小> 的链串 　【例】串值为 abcdef 的结点大小为 的链串S如下图所示

　 注意 　　①为了提高存储密度 可使每个结点存放多个字符 　　②当结点大小大于 时 串的长度不一定正好是结点大小的整数倍 因此要用特殊字符来填充最后一个结点 以表示串的终结 　　③虽然提高结点的大小使得存储密度增大 但是做插入 删除运算时 可能会引起大量字符的移动 给运算带来不便 　　【例】上图中 在S的第 个字符后插入 xyz 时 要移动原来S中后面 个字符的位置 结果见下图

lishixinzhi/Article/program/sjjg/201311/22628