41_指针数组

//_41_指针数组
//_41_main.cpp

//实例：在一个已经排好序的字符串数组中，插入一个键盘输入的字符串，
//使其继续保持有序
//区分char *point[10]和char (*point)[10]的区别

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
	//声明子函数
	int binary(char *ptr[],char *str,int n);//查找函数声明
	void insert(char *ptr[],char *str,int n,int i);//插入函数声明

	int i;
	char *ptr1[6];
	printf("请为字符型指针数组赋初值：\n");
	for(i=0;i<5;i++)
	{
		ptr1[i] = (char *)malloc(20);//为指针分配地址
		gets(ptr1[i]);//输入字符串
	}
	ptr1[5] = (char *)malloc(20);
	printf("\n");
	printf("original string:\n");
	for(i=0;i<5;i++)//输出指针数组各个字符串
		printf("%s\n",ptr1[i]);

	printf("\ninput search string:\n");
	char *temp;
	temp = new char[20];//(char *)malloc(20)
	gets(temp);//输入被插字符串
	i = binary(ptr1,temp,5);//寻找插入位置
	printf("i = %d\n",i);
	insert(ptr1,temp,5,i);//在插入位置i初插入字符串
	printf("output strings:\n");
	for(i=0;i<6;i++)//输出指针数组全部字符串
		printf("%s\n",ptr1[i]);

	system("pause");
	return 0;
}

int binary(char *ptr[],char *str,int n)
{
	//折半查找插入位置
	int high,low,mid;
	low = 0;
	high = n-1;
	//若插入字符串比字符串数组的第0个小，则插入位置为0
	if(strcmp(str,ptr[0])<0)
		return 0;
	//若插入字符串比字符串数组的最后一个大，则应插入字符串数组的尾部
	if(strcmp(str,ptr[high])>0)
		return n;
	while(low <= high)
	{
		mid = (low+high)/2;
		if(strcmp(str,ptr[mid])<0)
			high = mid - 1;
		else if(strcmp(str,ptr[mid])>0)
			low = mid + 1;
		else
			return mid;//插入字符串与字符数组的某个字符串相同
	}
	return low;//插入位置在字符数组中间
}

void insert(char *ptr[],char *str,int n,int i)
{
	for(int j=n;j>i;j--)
	{
		strcpy(ptr[j],ptr[j-1]);//将插入位置后的字符串后移
	}
	strcpy(ptr[i],str);//将被插字符串按字典排序插入字符串数组
}