数据结构C语言版_串的块链存储表示和实现
数据结构C语言版 串的块链存储表示和实现.txt成熟不是心变老，而是眼泪在眼里打转却还保持微笑。把一切平凡的事做好既不平凡，把一切简单的事做对既不简单。/* 数据结构C语言版 串的块链存储表示和实现 P78 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月12日
*/
#include
#include
#include
#include
// LString.h 串的块链存储表示
#define CHUNKSIZE 4 // 可由用户定义的块大小
typedef struct Chunk
{
char ch[CHUNKSIZE]; //块的数据域 struct Chunk *next; //块的指针域
}Chunk;
typedef struct
{
Chunk *head, // 串的头指针 *tail; // 串的尾指针 int curlen; // 串的当前长度
}LString;
char blank = '#'; // 全局变量,用于填补空余
// 初始化(产生空串)字符串T。 void InitString(LString *T)
{
(*T).curlen=0; (*T).head=NULL; (*T).tail=NULL;
}
// 生成一个其值等于chars的串T(要求chars中不包含填补空余的字符)
// 成功返回1，否则返回0 int StrAssign(LString *T,char *chars)
{
int i,j,k,l; Chunk *p,*q; i=strlen(chars); // i为串的长度 if(!i||strchr(chars,blank)) // 串长为0或chars中包含填补空余的字符 return 0; (*T).curlen=i; j=i/CHUNKSIZE; // j为块链的结点数，块的个数 if(i%CHUNKSIZE) //不足一个块的，当成一个块即块数加1 j++; for(k=0;knext=p; q=p; } for(l=0;lch+l)=*chars++; if(!*chars) // 最后一个链块 { (*T).tail=q; q->next=NULL; for(;lch+l)=blank; } } return 1;
}
// 由串S复制得串T(连填补空余的字符一块拷贝) int StrCopy(LString *T,LString S)
{
Chunk *h=S.head,*p,*q; (*T).curlen=S.curlen; if(h) { p=(*T).head=(Chunk*)malloc(sizeof(Chunk)); *p=*h; // 复制1个结点 h=h->next; while(h) //没到队尾，继续复制块 { q=p; p=(Chunk*)malloc(sizeof(Chunk)); q->next=p; *p=*h; h=h->next; } p->next=NULL; (*T).tail=p; return 1; } else return 0;
}
// 若S为空串,则返回1,否则返回0 int StrEmpty(LString S)
{
if(S.curlen) // 非空 return 0; else return 1;
}
// 若S>T,则返回值>0;若S=T,则返回值=0;若Sch+jt)==blank) // 跳过填补空余的字符 { jt++; if(jt==CHUNKSIZE) { pt=pt->next; jt=0; } }; // *(pt->ch+jt)为T的第i个有效字符 if(*(ps->ch+js)!=*(pt->ch+jt)) return *(ps->ch+js)-*(pt->ch+jt); else // 继续比较下一个字符 { js++; if(js==CHUNKSIZE) { ps=ps->next; js=0; } jt++;
*/
#include
#include
#include
#include
// LString.h 串的块链存储表示
#define CHUNKSIZE 4 // 可由用户定义的块大小
typedef struct Chunk
{
char ch[CHUNKSIZE]; //块的数据域 struct Chunk *next; //块的指针域
}Chunk;
typedef struct
{
Chunk *head, // 串的头指针 *tail; // 串的尾指针 int curlen; // 串的当前长度
}LString;
char blank = '#'; // 全局变量,用于填补空余
// 初始化(产生空串)字符串T。 void InitString(LString *T)
{
(*T).curlen=0; (*T).head=NULL; (*T).tail=NULL;
}
// 生成一个其值等于chars的串T(要求chars中不包含填补空余的字符)
// 成功返回1，否则返回0 int StrAssign(LString *T,char *chars)
{
int i,j,k,l; Chunk *p,*q; i=strlen(chars); // i为串的长度 if(!i||strchr(chars,blank)) // 串长为0或chars中包含填补空余的字符 return 0; (*T).curlen=i; j=i/CHUNKSIZE; // j为块链的结点数，块的个数 if(i%CHUNKSIZE) //不足一个块的，当成一个块即块数加1 j++; for(k=0;knext=p; q=p; } for(l=0;lch+l)=*chars++; if(!*chars) // 最后一个链块 { (*T).tail=q; q->next=NULL; for(;lch+l)=blank; } } return 1;
}
// 由串S复制得串T(连填补空余的字符一块拷贝) int StrCopy(LString *T,LString S)
{
Chunk *h=S.head,*p,*q; (*T).curlen=S.curlen; if(h) { p=(*T).head=(Chunk*)malloc(sizeof(Chunk)); *p=*h; // 复制1个结点 h=h->next; while(h) //没到队尾，继续复制块 { q=p; p=(Chunk*)malloc(sizeof(Chunk)); q->next=p; *p=*h; h=h->next; } p->next=NULL; (*T).tail=p; return 1; } else return 0;
}
// 若S为空串,则返回1,否则返回0 int StrEmpty(LString S)
{
if(S.curlen) // 非空 return 0; else return 1;
}
// 若S>T,则返回值>0;若S=T,则返回值=0;若Sch+jt)==blank) // 跳过填补空余的字符 { jt++; if(jt==CHUNKSIZE) { pt=pt->next; jt=0; } }; // *(pt->ch+jt)为T的第i个有效字符 if(*(ps->ch+js)!=*(pt->ch+jt)) return *(ps->ch+js)-*(pt->ch+jt); else // 继续比较下一个字符 { js++; if(js==CHUNKSIZE) { ps=ps->next; js=0; } jt++;