|
串的链式存储 链串 用单链表方式存储串值串的这种链式存储结构简称为链串 链串的结构类型定义 typedef struct node{ char data; struct node *next; }LinkStrNode; //结点类型 typedef LinkStrNode *LinkString; //LinkString为链串类型 LinkString S; //S是链串的头指针 注意 ①链串和单链表的差异仅在于其结点数据域为单个字符 ②一个链串由头指针唯一确定 链串的结点大小 通常将结点数据域存放的字符个数定义为结点的大小结点的大小的值越大存储密度越高 （）结点大小为的链串 【例】串值为abcdef的结点大小为的链串S如下图所示 这种结构便于进行插入和删除运算但存储空间利用率太低 （）结点大小>的链串 【例】串值为abcdef的结点大小为的链串S如下图所示 注意 ①为了提高存储密度可使每个结点存放多个字符 ②当结点大小大于时串的长度不一定正好是结点大小的整数倍因此要用特殊字符来填充最后一个结点以表示串的终结 ③虽然提高结点的大小使得存储密度增大但是做插入删除运算时可能会引起大量字符的移动给运算带来不便 【例】上图中在S的第个字符后插入xyz时要移动原来S中后面个字符的位置结果见下图 |
