//_DataStructure_C_Impl:链串 #include<stdio.h> #include<stdlib.h> #include<string.h> #define ChunkSize 4 #define stuff '#' //串的结点类型定义 typedef struct Chunk{ char ch[ChunkSize]; struct Chunk *next; }Chunk; //链串的类型定义 typedef struct{ Chunk *head; Chunk *tail; int length; }LinkString; //初始化字符串S void InitString(LinkString *S){ S->length=0; //将串的长度置为0 S->head=S->tail=NULL; //将串的头指针和尾指针置为空 } //生成一个其值等于cstr的串S。成功返回1,否则返回0 int StrAssign(LinkString *S,char *cstr){ int i,j,k,len; Chunk *p,*q; len=strlen(cstr); //len为链串的长度 if(!len) return 0; S->length=len; j=len/ChunkSize; //j为链串的结点数 if(len%ChunkSize) j++; for(i=0;i<j;i++){ p=(Chunk *)malloc(sizeof(Chunk)); //动态生成一个结点 if(!p) return 0; for(k=0;k<ChunkSize&&*cstr;k++) *(p->ch+k)=*cstr++; //将字符串ctrs中的字符赋值给链串的数据域 if(i==0) //假设是第一个结点 S->head=q=p; //头指针指向第一个结点 else{ q->next=p; q=p; } if(!*cstr){ //假设是最后一个链结点 S->tail=q; //将尾指针指向最后一个结点 q->next=NULL; //将尾指针的指针域置为空 for(;k<ChunkSize;k++) *(q->ch+k)=stuff; //将最后一个结点用'#'填充 } } return 1; } //推断串是否为空。假设S为空串,则返回1,否则返回0 int StrEmpty(LinkString S){ if(S.length==0) return 1; else return 0; } //求串的长度 int StrLength(LinkString S){ return S.length; } //串的转换操作。将串S的内容转换为字符串,将串S中的字符复制到cstr。成功返回1,否则返回0 int ToChars(LinkString S,char **cstr){ Chunk *p=S.head; //将p指向串S中的第1个结点 int i; char *q; *cstr=(char *)malloc((S.length+1)*sizeof(char)); if(!cstr||!S.length) return 0; q=*cstr; //将q指向cstr while(p){ //块链没结束 for(i=0;i<ChunkSize;i++) if(p->ch[i]!=stuff) //假设当前字符不是填充的特殊字符'#'。则将S中字符赋值给q *q++=(p->ch[i]); p=p->next; } (*cstr)[S.length]='