顺序表的基本操作

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

//定义顺序表
#define ERROR 0
#define OK 1
#define INFEASIBLE -1
#define OVERFLOW -2

#define ElemType int
#define Status int

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

Status compare(ElemType x, ElemType y){
	if (x == y){
		return OK;
	}
	else
	{
		return ERROR;
	}
}

//1.构造顺序表
Status InitList_Sq(SqList &L){
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if (!L.elem)
		exit(OVERFLOW);
	L.length = 0;
	L.listsize = LISTINCREMENT;
	return OK;
}

//2.销毁顺序表
Status DestoryList(SqList &L){
	if (L.elem){
		free(L.elem);
	}
	if (L.elem == NULL){
		return OK;
	}
	else
	{
		return ERROR;
	}
}

//3.清空顺序表
void ClearList(SqList &L){
	L.length = 0;
}

//4.判断线性表是否为空
Status ListEmpty(SqList L){
	if (L.length==0)
	{
		return ERROR;
	}
	else
	{
		return OK;
	}
}

//5.求顺序表的长度
Status ListLength(SqList L){
	return L.length;
}

//6.顺序表的元素
Status GetElem(SqList L,int i,ElemType e){
	if (i<1||i>L.length)
	{
		return ERROR;
	}
	else
	{
		e = L.elem[i - 1];
	}
	return OK;
}

//7.顺序表的定位
Status LocateElem(SqList L,ElemType e){
	int i = 1;
	while (i<=L.length&&L.elem[i-1]!=e)
	{
		i++;
	}
	if (i>L.length)
	{
		return ERROR;
	}
	else
	{
		return i;
	}
}

//8.返回前驱
ElemType PriorElem(SqList L,int cur_e){
	int pre_e, i = 1;
	int *p;
	p = L.elem + 1;
	while (i<L.length&&compare(cur_e,L.elem[i-1]))
	{
		p++;
		i++;
	}
	if (i>L.length){
		return ERROR;
	}
	else
	{
		pre_e = L.elem[i];
		return pre_e;
	}
}

//9.返回后继
ElemType NextElem(SqList L,int cur_e){
	int next_e, i = 0;
	int *p = L.elem;
	while (i<L.length&&!compare(cur_e,L.elem[i]))
	{
		p++;
		i++;
	}
	if (i == L.length){
		return ERROR;
	}
	else
	{
		next_e = *(++p);
		return next_e;
	}
}

//10.顺序表的查找
int LocateElm_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)){
	int i, *p;
	i = 1;
	p = L.elem;
	while (i<L.length&&!(*compare)(*p++, e))
	{
		++i;
	}
	if (i <= L.length)
		return i;
	else
	{
		return ERROR;
	}
}

//11.顺序表的插入
Status ListInsert_Sq(SqList &L, int i, ElemType e){
	ElemType *newbase, *q, *p;
	if (i<1 || i>L.length + 1){
		return ERROR;
	}
	if (L.length >= L.listsize){
		newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
		if (!newbase)
		{
			exit(OVERFLOW);
		}
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	q = &(L.elem[i - 1]);
	for (p = &(L.elem[L.length-1]); p >= q; --p)
	{
		*(p + 1) = *p;
	}
	*q = e;
	++L.length;
	return OK;
}

//12.顺序表的删除
Status ListDelete_Sq(SqList &L, int i, ElemType &e){
	if ((i<1)||(i>L.length))
	{
		return ERROR;
	}
	ElemType *p, *q;
	p = &(L.elem[i - 1]);
	e = *p;
	q = L.elem + L.length - 1;
	for (p++; p <= q; p++){
		*(p - 1) = *p;
	}
	L.length++;
	return OK;
}

//13.顺序表的遍历
Status ListTraverse(SqList L){
	ElemType *p = L.elem;
	int i;
	for (i = 1; i < L.length; i++)
	{
		printf("%d ", *p++);
	}
	printf("\n");
	return OK;
}

int main(){
	int m, n;
	SqList L;
	ElemType e=0;
	printf("顺序表初始化");
	InitList_Sq(L);
	printf("请输入顺序表的长度n:\n");
	scanf("%d", &n);
	for (m = 1; m <= n; m++)
	{
		printf("请输入第%d个元素的值:\n", m);
		scanf("%d", &L.elem[m - 1]);
		L.length++;
	}
	printf("顺序表的长度为%d\n", L.length);
	printf("顺序表中的元素为:\n");
	ListTraverse(L);
	printf("…………判断顺序表是否空表…………\n");
	if (ListEmpty(L) == 1)
		printf("顺序表非空\n");
	else
		printf("顺序表为空\n");
	printf("…………顺序表中取元素操作…………\n");
	printf("%d\n",GetElem(L,4,e));
	printf("…………顺序表中元素的定位…………\n");
	printf("%d\n", LocateElem(L, 5));
	printf("…………顺序表中元素的前驱…………\n");
	printf("%d\n", PriorElem(L, 3));
	printf("…………顺序表中元素的后继…………\n");
	printf("%d\n", NextElem(L, 3));
	printf("…………顺序表元素插入测试…………\n");
	ListInsert_Sq(L, 6, 6);
	printf("此时顺序表中的元素为:\n");
	ListTraverse(L);
	printf("…………顺序表元素删除测试…………\n");
	ListDelete_Sq(L,6,e);
	printf("此时顺序表中的元素为:\n");
	ListTraverse(L);
	printf("恭喜您成功完成顺序表的所有功能！！！！\n");
	return 0;
}