数据结构：字符串的堆分配存储结构，基本操作实现和测试。

//All rights reserved by panqiaomu  from:http://blog.csdn.net/panqiaomu
// the Heap and Stack are different data structures....
//Heap must be always dynamic but The stack can be static with array or dynamic with linklist...
//Heap has no fixed order but the Stack must obey the rule:FILO

# include <stdlib.h>
# include <stdio.h>
# include <string.h>
//the storage structure:
typedef struct {
        char* ch;
        int length;
}*HeapStr;
//Create a "string variable"(memory space) for a string constant;
void StrAssign(HeapStr s, char* strconst){
    int len = strlen(strconst);
    if(s->ch) free(s->ch);
    if(!len){
        s->ch = NULL;
        s->length = 0;
    }
    else{
        s->ch = (char*)malloc(len+1);   //+1
        if(!s->ch)
            exit(0);
        strcpy(s->ch,strconst);
        s->length = len;
    }
}
// Insert a string  into another before position pos which bases on the whole operation;
void InserStr(HeapStr s, int pos ,HeapStr t){
    int i;
    int len = t->length;
    if(pos < 1 || pos > s->length + 1)
        exit(0);
    if(t->ch){// or t->length;
        if(!(s->ch = (char*)realloc(s->ch,s->length + t->length)))
            exit(0);
            //"Tim,fall back";
        for(i = s->length ; i >= pos - 1; --i)    //include the '\0'so beginning with s->length not -1....
            s->ch[i + len] = s->ch[i];
        //Begin inserting the char streams;
        //Don't call the function strcpy and copy the '\0' to string s which is wrong;
        for(i = 0; i< len; ++i)
            s->ch[pos-1 + i] = t->ch[i];
        s->length += len;
    }
}
//Return the length of the string
int StrLen(HeapStr s){
    return s->length;
}
//Clear the string to empty(NULL);
void ClearStr(HeapStr s){
    if(s->ch){
        free(s->ch);
        s->ch = NULL;
    }
    s->length = 0;
}
// ** Important OP:the match of strings beteen the main string and mode string;
// ** the classic one:String-Search Thought that we will realize it as follows;
// ** the rest ones:KMP and its progress,BM,KR and so on
int PatMatch(HeapStr ms, HeapStr pat , int pos){
    int i,j;
    if(pos < 1 || pos > ms->length) //match after 'pos';
        exit(0);
    i = pos-1;
    j = 0;
    while(i < ms->length && j < pat->length){
        if(ms->ch[i] == pat->ch[j]){
            ++i;
            ++j;
        }
        else{ //i and j "fall back ",the worst situation is O(s->length*m->length);
            i = i-j+2;
            j = 1;
        }
    }//while
    if (j >= pat->length)
        return i - pat->length+1;
    else
        return 0; //Failure and return 0;
}

//Replace the substring Sub with string Target in string  Ms;
void ReplaceStr(HeapStr ms,HeapStr sub, HeapStr tar){
    int pos = 1;
    int i;
    if(!tar->ch) return;
    pos = PatMatch(ms,sub,pos);
    while(pos){
        if(tar->length <= sub->length){
            for(i = 0; i< tar->length; ++i) //replace...
                ms->ch[pos-1+i] = tar->ch[i];
            if(tar->length != sub->length)  // not equal that is to say: <
                for(i = pos-1+sub->length;i <= ms->length; ++i)  // move to the front....
                    ms->ch[i - sub->length + tar->length] = ms->ch[i];
             ms->length -= (sub->length - tar->length);
            }//if
         else{
            ms->ch = (char*)realloc(ms->ch,ms->length+tar->length - sub->length);   //reallocate...not +1
            if(!ms->ch)
                exit(0);
            for(i = ms->length; i >= pos-1+sub->length; --i)  //move to the back....
                ms->ch[i+tar->length-sub->length] = ms->ch[i];
            for(i = 0;i< tar->length; ++i)       //replace....
                ms->ch[i+pos-1] = tar->ch[i];
            ms->length += (tar->length - sub->length);
        }//else
        pos += tar->length+1;
        pos = PatMatch(ms,sub,pos);
    }
}
//Request the substring from the position 'pos' with the length 'len'
void SubStr(HeapStr sub, HeapStr s, int pos, int len){
    if(pos < 1 || pos > s->length || len < 0 || len > s->length - pos + 1)
        exit(0); // make sure the strenth of codes;
    if(sub->ch) free(sub->ch);
    if(!len){  //request an empty string ;
        sub->ch = NULL;
        sub->length = 0;
    }
    else{
        if(!(sub->ch = (char*)malloc(len+1)))
            exit(0);
        strncpy(sub->ch,s->ch+pos-1,len);  //Call function strncpy();
        sub->ch[len] = '\0';
        sub->length = len;
    }
}
//Begin testing in function main()
int main(){
int pos;
HeapStr r,s,t,sub;
StrAssign(s,"Hello,my name is panqiaomu and your name?");
StrAssign(t,"qiaomu ");
StrAssign(r,"mumumumumu");
StrAssign(sub,""); //(sub,NULL)
printf("Call the function InserStr() ........\n");
InserStr(s,7,t);
printf("the Inserted string is:%s\n",s->ch);
printf("the ms string length is:%d\n" ,StrLen(s));
printf("Call the function ReplaceStr().......\n");
ReplaceStr(s,t,r);
printf("the Replaced  string is:%s\n",s->ch);
printf("Call the function SubStr()...........\n");
SubStr(sub,s,3,3);
printf("the substring is:\n%s\n",sub->ch);
getch();
return 0;
}
/*Summary:(1)不要等到所有的子函数全部写完后再在主函数里面测试，这样的会有很多麻烦，应该每一个模块写完后及时测试。
          (2)不要一上来就动手编程，应该首先在大脑里面有一个解决问题的总体框架，要考虑全面，包括所有可能出现的情况。
          (3)指针向数组转化的时候，要注意数组的下标是从0开始的，这一点在C语言中最让人头痛和讨厌。
          (4)为字符串申请空间，注意什么时候加1，什么时候不加1，比如建立字符串变量要加1的，其他的操作比如替换，插入
             就不需要，因为原字符串中就已经存在了'\0'.*********************/