[例6-25] 對已排好序的字符指針數組進行指定字符串的查找。字符串按字典順序排列，查找算法采用二分法，或稱為折半查找。折半查找算法描述：
1.設按開序（或降序）輸入n個字符串到一個指針數組。
2.設low指向指針數組的低端，high指向指針數組的高端，mid=(low+high)/2
3.測試mid所指的字符串，是否為要找的字符串。
4.若按字典順序，mid所指的字符串大於要查找的串，表示被查字符串在low和mid之間，否則，表示被查字符串在mid和high之間。
5.修改low式high的值，重新計算mid，繼續尋找。
#include <stdlib.h>
#include <alloc.h>
#include <string.h>
#include <stdio.h>
main()
{
char *binary();/*函數聲明*/
char *ptr1[5],*temp;
int i,j;
for(i=0;i<5;i++)
{
ptr1[i]=malloc(20);/*按字典順序輸入字符串*/
gets(ptr1[i]);
}
printf("\n");
printf("original string:\n");
for(i=0;i<5;i++)
printf("%s\n",ptr1[i]);
printf("input search string:\n");
temp=malloc(20);
gets(temp);/輸*入被查找字符串*/
i=5;
temp=binary(ptr1,temp,i);/*調用查找函數*/
if(temp)printf("succesful-----%s\n",temp);
else printf("nosuccesful!\n");
return;
}
char *binary(char *ptr[],char *str,int定n)義返回字符指針的函數*/
{/*折半查找*/
int hig,low,mid;
low=0;
hig=n-1;
while(low<=hig)
{
mid=(low+hig)/2;
if(strcmp(str,ptr[mid])<0)
hig=mid-1;
else if(strcmp(str,ptr[mid])>0)
low=mid+1;
else return(str);/*查帳成功，返回被查字符串*/
}
return NULL; / *查找失敗，返回空指針* /
}
[例6-26] 在一個已排好序的字符串數組中，插入一個鍵盤輸入的字符串，使其繼續保持有序。
在上述程序查找成功的基礎上，我們將該字符串插入到字符數組中。插入的位置可以是數組頭、中間或數組尾。查找的算法采用折半算法，找到插入位置後，將字符串插入。
#include <stdlib.h>
#include <alloc.h>
#include <string.h>
#include <stdio.h>
m a i n ( )
{
int binary(); / *查找函數聲明* /
void insert(); / *插入函數聲明* /
char *temp,*ptr1[6];
int i,j;
for (i=0;i<5;i++)
{
ptr1[i]=malloc(20);/*為指針分配地址後*/
gets(ptr1[i]);/*輸入字符串*/
}
ptr1[5]=malloc(20);
printf("\n");
printf("original string:\n");
for(i=0;i<5;i++)/*輸出指針數組各字符串*/
printf("%s\n",ptr1[i]);
printf("input search string:\n");
temp=malloc(20);
gets(temp);/*輸入被插字符串*/
i=binary(ptr1,temp,5)/*;尋找插入位置i*/
printf("i=%d\n",i);
insert(ptr1,temp,5,i);/*在插入位置i處插入字符串*/
printf("outputstrings:\n");
for(i=0;i<6;i++)/*輸出指針數組的全部字符串*/
printf("%s\n",ptr1[i]);
return;
}
intbinary(char*ptr[],char*str,intn)
{/*折半查找插入位置*/
int hig,low,mid;
low=0;
hig=n-1;
if(strcmp(str,ptr[0])<0)return0;
/*若插入字符串比字符串數組的第0個小，則插入位置為0*/
if(strcmp(str,ptr[hig])>0)returnn;
/*若插入字符串比字符串數組的最後一個大，則應插入字符串數組的尾部*/
while(low<=hig)
{
mid=(low+hig)/2;
if(strcmp(str,ptr[mid])<0)
hig=mid-1;
else if(strcmp(str,ptr[mid])>0)
low=mid+1;
else return(mid);/*插入字符串與字符串數組的某個字符串相同*/
}
returnlow;/*插入的位置在字符串數組中間*/
}
void insert(char*ptr[],char*str,intn,inti)
{
int j;
for(j=n;j>i;j--)/*將插入位置之後的字符串後移*/
strcpy(ptr[j],ptr[j-1]);
strcpy(ptr[i],str);將被插字符串按字典順序插入字符串數組*/
}
在程序中，字符串數組的6個指針均分配存放20字節的有效地址。語句ptr1[5]=malloc(20)保證插入字符串後，也具有安全的存儲空間，字符串的長度以串中最長的為基准向系統申請存儲空間，以保證在串的移動中有足夠的存儲空間。
