// bo4-3.cpp 串采用塊鏈存儲結(jié)構(gòu)(由c4-3.h定義)的基本操作(16個)
 void InitString(LString &T)
 { // 初始化(產(chǎn)生空串)字符串T。另加
   T.curlen=0;
   T.head=NULL;
   T.tail=NULL;
 }

 Status StrAssign(LString &T,char *chars)
 { // 生成一個其值等于chars的串T(要求chars中不包含填補空余的字符)
   // 成功返回OK，否則返回ERROR
   int i,j,k,l;
   Chunk *p,*q;
   i=strlen(chars); // i為串的長度
   if(!i||strchr(chars,blank)) // 串長為0或chars中包含填補空余的字符
     return ERROR;
   T.curlen=i;
   j=i/CHUNKSIZE; // j為塊鏈的結(jié)點數(shù)
   if(i%CHUNKSIZE)
     j++;
   for(k=0;k<j;k++)
   {
     p=(Chunk*)malloc(sizeof(Chunk));
     if(!p)
       return ERROR;
     if(k==0) // 第一個鏈塊
       T.head=q=p;
     else
     {
       q->next=p;
       q=p;
     }
     for(l=0;l<CHUNKSIZE&&*chars;l++)
       *(q->ch+l)=*chars++;
     if(!*chars) // 最后一個鏈塊
     {
       T.tail=q;
       q->next=NULL;
       for(;l<CHUNKSIZE;l++) // 用填補空余的字符填滿鏈表
         *(q->ch+l)=blank;
     }
   }
   return OK;
 }

 Status StrCopy(LString &T,LString S)
 { // 初始條件:串S存在。操作結(jié)果:由串S復(fù)制得串T(連填補空余的字符一塊拷貝)
   Chunk *h=S.head,*p,*q;
   T.curlen=S.curlen;
   if(h)
   {
     p=T.head=(Chunk*)malloc(sizeof(Chunk));
     *p=*h; // 復(fù)制1個結(jié)點
     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 OK;
   }
   else
    return ERROR;
 }

 Status StrEmpty(LString S)
 { // 初始條件:串S存在。操作結(jié)果:若S為空串,則返回TRUE,否則返回FALSE
   if(S.curlen) // 非空
     return FALSE;
   else
     return TRUE;
 }

 int StrCompare(LString S,LString T)
 { // 若S>T,則返回值>0;若S=T,則返回值=0;若S<T,則返回值<0
   int i=0; // i為當(dāng)前待比較字符在S,T串中的位置
   Chunk *ps=S.head,*pt=T.head; // ps,pt分別指向S和T的待比較塊
   int js=0,jt=0; // js,jt分別指示S和T的待比較字符在塊中的位序
   while(i<S.curlen&&i<T.curlen)
   {
     i++; // 分別找S和T的第i個字符
     while(*(ps->ch+js)==blank) // 跳過填補空余的字符
     {
       js++;
       if(js==CHUNKSIZE)
       {
         ps=ps->next;
         js=0;
       }
     }; // *(ps->ch+js)為S的第i個有效字符
     while(*(pt->ch+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 // 繼續(xù)比較下一個字符
     {
       js++;
       if(js==CHUNKSIZE)
       {
         ps=ps->next;
         js=0;
       }
       jt++;
       if(jt==CHUNKSIZE)
       {
         pt=pt->next;
         jt=0;
       }
     }
   }
   return S.curlen-T.curlen;
 }

 int StrLength(LString S)
 { // 返回S的元素個數(shù),稱為串的長度
   return S.curlen;
 }

 Status ClearString(LString &S)
 { // 初始條件: 串S存在。操作結(jié)果: 將S清為空串
   Chunk *p,*q;
   p=S.head;
   while(p)
   {
     q=p->next;
     free(p);
     p=q;
   }
   S.head=NULL;
   S.tail=NULL;
   S.curlen=0;
   return OK;
 }

 Status Concat(LString &T,LString S1,LString S2)
 { // 用T返回由S1和S2聯(lián)接而成的新串
   LString a1,a2;
   InitString(a1);
   InitString(a2);
   StrCopy(a1,S1);
   StrCopy(a2,S2);
   T.curlen=S1.curlen+S2.curlen;
   T.head=a1.head;
   a1.tail->next=a2.head;
   T.tail=a2.tail;
   return OK;
 }

 Status SubString(LString &Sub, LString S,int pos,int len)
 { // 用Sub返回串S的第pos個字符起長度為len的子串。
   // 其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
   Chunk *p,*q;
   int i,k,n,flag=1;
   if(pos<1||pos>S.curlen||len<0||len>S.curlen-pos+1)
     return ERROR;
   n=len/CHUNKSIZE; // 生成空的Sub串
   if(len%CHUNKSIZE)
     n++; // n為塊的個數(shù)
   p=new Chunk;
   Sub.head=p;
   for(i=1;i<n;i++)
   {
     q=new Chunk;
     p->next=q;
     p=q;
   }
   p->next=NULL;
   Sub.tail=p;
   Sub.curlen=len;
   for(i=len%CHUNKSIZE;i<CHUNKSIZE;i++)
     *(p->ch+i)=blank; // 填充Sub尾部的多余空間
   q=Sub.head; // q指向Sub串即將復(fù)制的塊
   i=0; // i指示即將復(fù)制的字符在塊中的位置
   p=S.head; // p指向S串的當(dāng)前塊
   n=0; // n指示當(dāng)前字符在串中的序號
   while(flag)
   {
     for(k=0;k<CHUNKSIZE;k++) // k指示當(dāng)前字符在塊中的位置
       if(*(p->ch+k)!=blank)
       {
         n++;
         if(n>=pos&&n<=pos+len-1) // 復(fù)制
         {
           if(i==CHUNKSIZE)
           { // 到下一塊
             q=q->next;
             i=0;
           }
           *(q->ch+i)=*(p->ch+k);
           i++;
           if(n==pos+len-1) // 復(fù)制結(jié)束
           {
             flag=0;
             break;
           }
         }
       }
     p=p->next;
   }
   return OK;
 }

 int Index(LString S,LString T,int pos)
 { // T為非空串。若主串S中第pos個字符之后存在與T相等的子串,
   // 則返回第一個這樣的子串在S中的位置,否則返回0
   int i,n,m;
   LString sub;
   if(pos>=1&&pos<=StrLength(S)) // pos滿足條件
   {
     n=StrLength(S); // 主串長度
     m=StrLength(T); // T串長度
     i=pos;
     while(i<=n-m+1)
     {
       SubString(sub,S,i,m); // sub為從S的第i個字符起,長度為m的子串
       if(StrCompare(sub,T)!=0) // sub不等于T
         ++i;
       else
         return i;
     }
   }
   return 0;
 }

 void Zip(LString &S)
 { // 壓縮串(清除塊中不必要的填補空余的字符)。加
   int j,n=0;
   Chunk *h=S.head;
   char *q;
   q=(char*)malloc((S.curlen+1)*sizeof(char));
   while(h) // 將LString類型的字符串轉(zhuǎn)換為char[]類型的字符串
   {
     for(j=0;j<CHUNKSIZE;j++)
       if(*(h->ch+j)!=blank)
       {
         *(q+n)=*(h->ch+j);
         n++;
       }
     h=h->next;
   }
   *(q+n)=0; // 串結(jié)束符
   ClearString(S); // 清空S
   StrAssign(S,q); // 重新生成S
 }

 Status StrInsert(LString &S,int pos,LString T)
 { // 1≤pos≤StrLength(S)+1。在串S的第pos個字符之前插入串T
   int i,j,k;
   Chunk *p,*q;
   LString t;
   if(pos<1||pos>StrLength(S)+1) // pos超出范圍
     return ERROR;
   StrCopy(t,T); // 復(fù)制T為t
   Zip(S); // 去掉S中多余的填補空余的字符
   i=(pos-1)/CHUNKSIZE; // 到達插入點要移動的塊數(shù)
   j=(pos-1)%CHUNKSIZE; // 到達插入點在最后一塊上要移動的字符數(shù)
   p=S.head;
   if(pos==1) // 插在S串前
   {
     t.tail->next=S.head;
     S.head=t.head;
   }
   else if(j==0) // 插在塊之間
   {
     for(k=1;k<i;k++)
       p=p->next; // p指向插入點的左塊
     q=p->next; // q指向插入點的右塊
     p->next=t.head; // 插入t
     t.tail->next=q;
     if(q==NULL) // 插在S串后
       S.tail=t.tail; // 改變尾指針
   }
   else // 插在一塊內(nèi)的兩個字符之間
   {
     for(k=1;k<=i;k++)
       p=p->next; // p指向插入點所在塊
     q=new Chunk; // 生成新塊
     for(i=0;i<j;i++)
       *(q->ch+i)=blank; // 塊q的前j個字符為填補空余的字符
     for(i=j;i<CHUNKSIZE;i++)
     {
       *(q->ch+i)=*(p->ch+i); // 復(fù)制插入點后的字符到q
       *(p->ch+i)=blank; // p的該字符為填補空余的字符
     }
     q->next=p->next;
     p->next=t.head;
     t.tail->next=q;
   }
   S.curlen+=t.curlen;
   Zip(S);
   return OK;
 }

 Status StrDelete(LString &S,int pos,int len)
 { // 從串S中刪除第pos個字符起長度為len的子串
   int i=1; // 當(dāng)前字符是S串的第i個字符(1～S.curlen)
   Chunk *p=S.head; // p指向S的當(dāng)前塊
   int j=0; // 當(dāng)前字符在當(dāng)前塊中的位序(0～CHUNKSIZE-1)
   if(pos<1||pos>S.curlen-len+1||len<0) // pos,len的值超出范圍
     return ERROR;
   while(i<pos) // 找第pos個字符
   {
     while(*(p->ch+j)==blank) // 跳過填補空余的字符
     {
       j++;
       if(j==CHUNKSIZE) // 應(yīng)轉(zhuǎn)向下一塊
       {
         p=p->next;
         j=0;
       }
     }
     i++; // 當(dāng)前字符是S的第i個字符
     j++;
     if(j==CHUNKSIZE) // 應(yīng)轉(zhuǎn)向下一塊
     {
       p=p->next;
       j=0;
     }
   }; // i=pos,*(p->ch+j)為S的第pos個有效字符
   while(i<pos+len) // 刪除從第pos個字符起到第pos+len-1個字符
   {
     while(*(p->ch+j)==blank) // 跳過填補空余的字符
     {
       j++;
       if(j==CHUNKSIZE) // 應(yīng)轉(zhuǎn)向下一塊
       {
         p=p->next;
         j=0;
       }
     }
     *(p->ch+j)=blank; // 把字符改成填補空余的字符來＂刪除＂第i個字符
     i++; // 到下一個字符
     j++;
     if(j==CHUNKSIZE) // 應(yīng)轉(zhuǎn)向下一塊
     {
       p=p->next;
       j=0;
     }
   };
   S.curlen-=len; // 串的當(dāng)前長度
   return OK;
 }

 Status Replace(LString &S,LString T,LString V)
 { // 初始條件: 串S,T和V存在,T是非空串（此函數(shù)與串的存儲結(jié)構(gòu)無關(guān)）
   // 操作結(jié)果: 用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串
   int i=1; // 從串S的第一個字符起查找串T
   if(StrEmpty(T)) // T是空串
     return ERROR;
   do
   {
     i=Index(S,T,i); // 結(jié)果i為從上一個i之后找到的子串T的位置
     if(i) // 串S中存在串T
     {
       StrDelete(S,i,StrLength(T)); // 刪除該串T
       StrInsert(S,i,V); // 在原串T的位置插入串V
       i+=StrLength(V); // 在插入的串V后面繼續(xù)查找串T
     }
   }while(i);
   return OK;
 }

 void StrPrint(LString T)
 { // 輸出字符串T。另加
   int i=0,j;
   Chunk *h;
   h=T.head;
   while(i<T.curlen)
   {
     for(j=0;j<CHUNKSIZE;j++)
       if(*(h->ch+j)!=blank) // 不是填補空余的字符
       {
         printf("%c",*(h->ch+j));
         i++;
       }
     h=h->next;
   }
   printf("\n");
 }

 void DestroyString()
 { // 塊鏈類型的字符串無法銷毀
 }