#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#define CHUNKSIZE 10  
#define stuff ‘#‘  
typedef struct Chunk  
{  
    char ch[CHUNKSIZE];  
    struct Chunk *next;  
}Chunk;//串的结点类型定义  
typedef struct  
{  
    Chunk *head;  
    Chunk *tail;  
    int length;  
}LinkString;  
  
void InitString(LinkString *S);//初始化字符串  
int StrAssign(LinkString *S,char *cstr);//生成串  
int StrEmpty(LinkString S);//推断出串是否为空  
int StrLength(LinkString S);//求串长度  
int StrCopy(LinkString *T,LinkString S);//串的复制操作  
int ToChars(LinkString S,char **cstr);//串的转换操作  
int StrCompare(LinkString S,LinkString T);//串的比較操作  
int StrConcat(LinkString *T,LinkString S);//串的连接操作  
int StrInsert(LinkString *S,int pos,LinkString T);//串的插入操作  
int StrDelete(LinkString *S,int pos,int len);//串的删除操作  
int SubString(LinkString *Sub,LinkString S,int pos,int len);//取子串操作  
void ClearString(LinkString *S);//清空串操作  



#include "LinkString.h"  
  
void InitString(LinkString *S)//初始化字符串  
{  
    S->length = 0;  
    S->head = NULL;  
    S->tail = NULL;  
}  
int StrAssign(LinkString *S,char *cstr)//生成串  
{  
    Chunk *p,*q;  
    int i,j,k,len;  
    len = strlen(cstr);  
    if(!len)  
    {  
        return 0;  
    }  
    S->length = len;  
    j = len/CHUNKSIZE;  
    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++;  
        }  
        if(0 == i)  
        {  
            S->head = q;  
            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;  
}  
int StrEmpty(LinkString S)//推断出串是否为空  
{  
    if(S.length == 0)  
    {  
        return 1;  
    }  
    else  
    {  
        return 0;  
    }  
}  
int StrLength(LinkString S)//求串长度  
{  
    return S.length;  
}  
int StrCopy(LinkString *T,LinkString S)//串的复制操作  
{  
    char *str;  
    int flag;  
    if(!ToChars(S,&str))  
    {  
        return 0;  
    }  
    flag = StrAssign(T,str);  
    free(str);  
    return flag;  
}  
int ToChars(LinkString S,char **cstr)//串的转换操作  
{  
    Chunk *p = S.head ;  
    int i;  
    char *q;  
    *cstr = (char*)malloc((S.length + 1)*sizeof(char));  
    if(!cstr||!S.length)  
    {  
        return 0;  
    }  
    q = *cstr;  
    while(p)  
    {  
        for(i = 0;i < CHUNKSIZE;i++)  
        {  
            if(p->ch[i] != stuff)  
            {  
                *q++ = (p->ch[i]);  
            }  
        }  
        p = p->next ;  
    }  
    (*cstr)[S.length] = 0;  
    return 1;  
}  
int StrCompare(LinkString S,LinkString T)//串的比較操作  
{  
    char *p,*q;  
    int flag;  
    if(!ToChars(S,&p))  
    {  
        return 0;  
    }  
    if(!ToChars(T,&q))  
    {  
        return 0;  
    }  
    for(;*p != ‘\0‘&&*q != ‘\0‘;)  
    {  
        if(*p == *q)  
        {  
            p++;  
            q++;  
        }  
        else  
        {  
            flag = *p - *q;  
        }  
    }  
    free(p);  
    free(q);  
    if(*p == ‘\0‘||*q == ‘\0‘)  
    {  
        return S.length - T.length ;  
    }  
    else  
    {  
        return flag;  
    }  
}  
int StrConcat(LinkString *T,LinkString S)//串的连接操作  
{  
    int flag1,flag2;  
    LinkString S1,S2;  
    InitString(&S1);  
    InitString(&S2);  
    flag1 = StrCopy(&S1,*T);  
    flag2 = StrCopy(&S2,S);  
    if(flag1 == 0 || flag2 == 0)  
    {  
        return 0;  
    }  
    T->head = S1.head ;  
    S1.tail->next = S2.head ;  
    T->tail = S2.tail ;  
    T->length = S1.length + S2.length ;  
    return 1;  
}  
int StrInsert(LinkString *S,int pos,LinkString T)//串的插入操作  
{  
    char *t1,*s1;  
    int i,j;  
    int flag;  
    if(pos < 1 || pos > S->length-1)  
    {  
        return 0;  
    }  
    if(!ToChars(*S,&s1))  
    {  
        return 0;  
    }  
    if(!ToChars(T,&t1))  
    {  
        return 0;  
    }  
    j = strlen(s1);  
    s1 = (char*)realloc(s1,(j+strlen(t1)+1)*sizeof(char));  
    for(i = j;i >= pos-1;i--)  
    {  
        s1[i+strlen(t1)] = s1[i];  
    }  
    for(i = 0;i <(int)strlen(t1);i++)  
    {  
        s1[pos+i-1] = t1[i];  
    }  
    InitString(S);  
    flag = StrAssign(S,s1);  
    free(s1);  
    free(t1);  
    return flag;  
}  
int StrDelete(LinkString *S,int pos,int len)//串的删除操作  
{  
    char *str;  
    int i;  
    int flag;  
    if(pos < 1 || len < 0 || pos > S->length-len+1)  
    {  
        return 0;  
    }  
    if(!ToChars(*S,&str))  
    {  
        return 0;  
    }  
    for(i = pos+len-1;i <= (int)strlen(str);i++)  
    {  
        str[i-len] = str[i];  
    }  
    InitString(S);  
    flag = StrAssign(S,str);  
    free(str);  
    return flag;  
}  
int SubString(LinkString *Sub,LinkString S,int pos,int len)  
{  
    char *t,*str;  
    int flag;  
    if(pos < 1||pos > S.length||len < 0||len > S.length - pos + 1)  
    {  
        return 0;  
    }  
    if(!ToChars(S,&str))  
    {  
        return 0;  
    }  
    t = pos+str-1;  
    t[len] = ‘\0‘;  
    flag = StrAssign(Sub,t);  
    free(str);  
    return flag;  
}//取子串操作  
void ClearString(LinkString *S)//清空串操作  
{  
    Chunk *p,*q;  
    p = S->head ;  
    while(p)  
    {  
        q = p->next ;  
        free(p);  
        p = q;  
    }  
    S->head = NULL;  
    S->tail = NULL;  
    S->length = 0;  
}