折半插入排序.cpp

实现了循环便利一棵树

# include <stdio.h>
# include<malloc.h>
# include<stdlib.h>
# define Maxsize 20
# define ERROR 0
# define OK 1
# define LT(a,b) ((a)<(b))
typedef int KeyType;
typedef char *InfoType;
typedef int Status;
typedef struct  { KeyType key;
                  InfoType otherinfor;
				} RcdType;
typedef struct  { RcdType r[Maxsize+1];
                  int length;
				}SqList;

void InsertSort(SqList &L)
{   	int i,low,high,m,j;
	for(i=2;i<=L.length;i++)
	{	L.r[0]=L.r[i];
	    low=1;	high=i-1;
    	while(low<=high)
		{   m=(low+high)/2;
	    	if(LT(L.r[0].key,L.r[m].key)) high=m-1;
	 	    else low=m+1;
		}
    	for(j=i-1;j>=high+1;j--) L.r[j+1]=L.r[j];
    	L.r[high+1]=L.r[0];
	}
}

Status CreateSqlist(SqList &L)
{	RcdType *rc;
	int i;
	static char str[Maxsize+1][10];
	if(!(rc=(RcdType*)malloc((1+Maxsize)*sizeof(RcdType))))
		return(ERROR);
	rc=L.r;
	L.length=0;
	printf("请输入表中记录个数:");
	scanf("%d",&L.length);
	for(i=0;i<=L.length;i++)
		L.r[i].otherinfor=&str[i][0];
	printf("请输入表中各条记录(输入格式为：整型关键字 字符串型其它信息)：\n");
	for(i=1;i<=L.length;i++)
	{	scanf("%d%*c",&L.r[i].key);
		scanf("%s",L.r[i].otherinfor);
	}
	return OK;
}

Status PrintSqlist(SqList L)
{	int i;
	for(i=1;i<=L.length;i++)
	{	printf("%d\t",L.r[i].key);
		printf("%s",L.r[i].otherinfor);
		printf("\n");
	}
	return OK;
}

void main()
{	SqList L;
	CreateSqlist(L);
	InsertSort(L);
	printf("\n输出排序结果:\n"); PrintSqlist(L);
}