顺序表

//SetConsoleOutputCP(CP_UTF8);
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
struct List
{
	int max;
	int n;
	DataType* elem;
};
typedef struct List* SeqList;

SeqList SetNullList_seq(int m)
{
	SeqList slist = (SeqList)malloc(sizeof(struct List));
	if (slist != NULL)
	{
		slist->elem = (DataType*)malloc(sizeof(DataType) *m);
		if (slist->elem){
			slist->max=m;
			slist->n = 0;
			return slist;
		}
		else
			free(slist);
	}
	printf("out of space!\n");
	return NULL;
}

int IsNullList(SeqList slist)
{
	return(slist->n == 0);
}

int InsertPre_seq(SeqList slist, int p, DataType x)
{
	int q;
	if (slist->n >= slist->max) {/*顺序表满溢出*/
		printf("overflow");
		return(0);
	}
	if(p<0 || p>slist->n){//不存在下标为p的元素
		printf("not exist!\n");
		return(0);
	}
	for (q = slist->n - 1; q >= p; q--)//插入位置以及之后的元素后移
		slist->elem[q + 1] = slist->elem[q];
	slist->elem[p] = x;//插入元素x
	slist->n = slist->n + 1;//顺序表长度加1
	return(1);
}

int DelIndex_seq(SeqList slist, int p)//删除下标为p的元素
{
	int q;
	if(p<0 || p>=slist->n){//不存在下标为p的元素
		printf("Not exist\n");
		return 0;
	}
	for (q = p; q<slist->n; q++) {//p位置之后的元素向前移动
		slist->elem[q] = slist->elem[q + 1];
	}
	slist->n = slist->n - 1;//顺序表长度减1
	return 1;
}

void print(SeqList slist) //输出顺序表
{
	int i;
	for (i = 0; i < slist->n; i++) //依次遍历顺序表，并输出
		printf("%d ", slist->elem[i]);
	printf("\n");
}

int LocateIndex_seq(SeqList slist, int x)//查找值为x的元素，返回元素所在下标
{
	int q;
	for (q = 0; q < slist->n; q++)
	{
		if (slist->elem[q] == x)//查找成功，返回对应的下标
			return q;
	}
	return -1;//查找失败，返回-1
}

//二分查找（检索）:降序或升序
int binsearch(SeqList slist, int key)
{
	int index = 1; int mid;
	int low = 0; int high = slist -> n - 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (slist->elem[mid] == key) {
			printf("找到，共进行%d次比较\n", index);
			printf("要找的数据%d在位置%d上\n", key, mid);
			return 1;
		}
		else if (slist->elem[mid] > key)
			high = mid - 1;
		else low = mid + 1;
		index++;
	}
	printf("没有找到，共进行%d次比较\n", index - 1);
	printf("可将次数据插入到位置%d上\n", low);
	return -1;
}

int main()
{	
	SeqList seqlist;
	int i, x;
	seqlist = SetNullList_seq(12);
	printf("%d", IsNullList(seqlist));
	printf("输入顺序表的元素：");
	for (i = 0; i < 6; i++)
	{
		scanf_s("%d", &x);
		InsertPre_seq(seqlist, i, x);//通过插入建立顺序表
	}
	printf("顺序表是否为空，1为空，0为非空：%d\n", IsNullList(seqlist));
	printf("当前顺序表的元素是：");
	print(seqlist);//输出顺序表
	DelIndex_seq(seqlist, 3);//删除下标为3的元素
	printf("删除下标为3的元素后的顺序表：");
	print(seqlist);//输出顺序表
	InsertPre_seq(seqlist, 5, 99);//在下标5位置之前插入99
	printf("在下标2位置之前插入99后的顺序表:");
	print(seqlist);//输出顺序表
	printf("查找值为99，如果查找成功，返回对应下标，查找失败，返回-1：%d\n", LocateIndex_seq(seqlist, 99));
	printf("二分法查找值为3，找到为1，找不到为-1：%d\n",binsearch(seqlist, 3));
}