(4.2.2)-4.2串的存储结构-串的链式表示

1一、串的定义二、串的顺序表示三、串的链式表示四、串的模式匹配五、串的应用ontents2串的块链存储表示[特点：]

用链表存储串值，易插入和删除。简称为链串。法1：链表结点（数据域）大小取1

A

B

C

INULLhead通常将结点数据域存放的字符个数定义为结点的大小。法2：链表结点大小取4head1ABCDEFGHI###NULL显然，若数据元素很多时，用法2存储更优—称为块链结构存储密度为1/2存储密度为9/15=3/5ontents3#defineCHUNKSIZE80//定义结点大小typedefstructChunk{//首先定义结点类型

charch[CHUNKSIZE];//结点中的数据域

structChunk*next;//结点中的指针域}Chunk;块链类型定义：typedefstruct{//其次定义用链式存储的串类型

Chunk*head;//串的头指针

Chunk*tail;//串的尾指针

intcurLen;//串的当前结点个数（长度）}LString;ontents串的块链存储表示//Lstring_main.c程序#include<stdio.h>#include<stdlib.h>#defineCHUNKSIZE4//可由用户定义的块大小typedefstructChunk{//首先定义结点类型

charch[CHUNKSIZE];//结点中的数据域,有4个

structChunk*next;//结点中的指针域}Chunk;typedefstruct{//其次定义用链式存储的串类型

Chunk*head;//串的头指针

Chunk*tail;//串的尾指针

intcurLen;//串的当前结点个数（长度）}LString;intmain(){ LStringhead2; Chunk*s,r; charch; inti,j; head2.head=(Chunk*)malloc(sizeof(Chunk));//生成头指针 head2.head->ch[0]='A';//给头指针的4个数据域赋值 head2.head->ch[1]='B'; head2.head->ch[2]='C'; head2.head->ch[3]='D'; head2.head->next=NULL;//当前只有一个结点，所以next域为空 head2.tail=head2.head;//尾指针也指向该结点 head2.curLen=1;//当前串长为1 printf("第一个结点为:%c%c%c%c\n",head2.head->ch[0],head2.head->ch[1],head2.head->ch[2],head2.head->ch[3]);

ch=getchar(); while(ch!='$') { i=0; s=(Chunk*)malloc(sizeof(Chunk)); s->ch[i]=ch; i++;//1

ch=getchar(); if(ch!='$') { s->ch[i]=ch; i++;//2 } else { s->ch[i]='\0'; s->ch[i+1]='\0'; s->ch[i+2]='\0'; head2.tail->next=s; head2.tail=s; break; }

ch=getchar(); if(ch!='$') { s->ch[i]=ch; i++;//3 } else { s->ch[i]='\0'; s->ch[i+1]='\0'; head2.tail->next=s; head2.tail=s; break; }

ch=getchar(); if(ch!='$') { s->ch[i]=ch; i++;//4 } else { s->ch[i]='\0'; head2.tail->next=s; head2.tail=s; break; }

head2.tail->next=s; head2.tail=s; ch=getchar(); } head2.tail->next=NULL;

s=head2.head; i=0;j=0; while(s!=NULL) { printf("输出第%d个结点值：",i+1);i++; printf("%c%c%c%c\n",s->ch[j],s->ch[j+1],s->ch[j+2],s->ch[j+3]); s=s->next; }}4head2A