二分法插入.cpp

商品货架管理

#include<stdlib.h>
#include<stdio.h>
#define NUM 10//开始时有10数据
void main()
{
	int i,k,space,low=0,high=NUM-1,mid;//k是存储插入的数值，space是指插入位置的前一个位置
	int List[NUM+1];//开辟一个能够存储11个数据的数组
	printf("请输入十个数值(按顺序输入，空格作间隔)\n");
	for(i=0;i<NUM;i++)//读入数值
	{
		scanf("%d",&List[i]);
	}
	printf("打印出数据\n");
	for(i=0;i<NUM;i++)//打印
	    printf("%d ",List[i]);
    printf("\n");
    printf("输入插入的数字:");
	printf("\n");
	scanf("%d",&k);
	while(low<=high)
	{
		mid=(low+high)/2;
		if(k==List[mid])
		{
			if(k<=List[mid+1])//如果k大于List[mid]的值小于mid后面的值，那么就找出space；<=是考虑到插入的数字与原表中有一样的
				space=mid;break;
        }
		else if(k<List[mid])
		{
			if(k>=List[mid-1])
			{
				space=mid-1;break;
			}
			else
		        high=mid-1;
		}
		else
		{
			if(k<=List[mid+1])
			{
				space=mid;break;
			}
			else
				low=mid+1;
		}
	}
    for(i=NUM;i>space;i--)//将space后面的数值依次向后面移动一个
	{
		List[i]=List[i-1];
	}
	List[space+1]=k;//插入k的值
	printf("打印出插入后的数据:\n");
	for(i=0;i<NUM+1;i++)//打印
	    printf("%d ",List[i]);
    printf("\n");
}