严蔚敏数据结构：线性表的基本 *** 作--纯C语言实现可直接运行

严蔚敏数据结构：线性表的基本 *** 作--纯C语言实现可直接运行

复习的时候随手敲的，可以直接运行，main函数里是我检查结果的，可以自行删去。

如果有地方可以改进可以评论我谢谢！仅供参考

# include 
#include
#include
# define SIZE 10
# define OK 1
# define TRUE 1
# define ERROR 0
# define FALSE 0
#define  OVERFLOW  -1 
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10//线性表初始存储空间的分配增量

typedef int Status; 
typedef int ElemType;
typedef struct{
	ElemType * elem;//储存空间基地址
	int length;//当前表长
	int listsize;//当前分配的存储容量（单位为sizeof(ElemType)）
}SqList;

Status InitList_Sq(SqList * L);
Status DestroyList_Sq(SqList * L);
Status ClearList_Sq(SqList * L);
Status ListEmpty(SqList L);
int ListLength(SqList L);
Status GetElem(SqList L, int i, ElemType * e);
Status LocateElem(SqList L, ElemType e, Status(*Compare)());
Status PriorElem(SqList L, ElemType cur_e, ElemType * pre_e);
Status NextElem(SqList L, ElemType cur_e, ElemType * next_e);
Status ListInsert_Sq(SqList * L, int i, ElemType e);
Status ListDelete_Sq(SqList * L, int i, ElemType * e);
Status ListTraverse(SqList L, Status(*Visit)());
Status Compare(ElemType e1, ElemType e2);
Status Visit(ElemType e);
void input(SqList * L);
int main()
{
	int i=1;
	SqList  L1;
	ElemType e1,e2,e3,e4;
	input(&L1);
	printf("遍历线性表-->n");
	ListTraverse(L1, Visit);
	GetElem(L1, 2, &e1);
	printf("n第 2 个元素是 %dn", e1);
	printf("查找第一个Compare(默认大于) 4 的位序是 %d n",LocateElem(L1, 4, Compare));
	PriorElem(L1, 5, &e2);
	printf(" 5 的前驱元素是 %d n", e2);
	NextElem(L1, 5, &e3);
	printf(" 5 的后继元素是 %d n", e3);
	int res1 = ListInsert_Sq(&L1, 4, 9);
	printf("插入结果是 %d n", res1);
	printf("遍历线性表-->n");
	ListTraverse(L1, Visit);
	int res2=ListDelete_Sq(&L1, 4, &e4);
	printf("n删除结果是 %d ", res2);
	printf("删除的第 4 个元素为 %d n", e4);
	printf("遍历线性表-->n");
	ListTraverse(L1, Visit);
	printf("n");
	return 0;
}
Status InitList_Sq(SqList * L)
{
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));//为线性表开辟空间，大小为初始分配量*数据元素的大小，成功则返回指向首地址的指针
	if (!L->elem) exit(OVERFLOW);//如果elem指向空，则说明分配失败，程序退出，返回码为OVERFLOW
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}
Status DestroyList_Sq(SqList * L)
{
	free(L->elem);//释放elem所指向的内存空间区域
	L->elem = NULL;//指针elem置空
	L->length = 0;//当前表长清零
	L->listsize = 0;//分配的存储容量清零
	return OK;
}
Status ClearList_Sq(SqList * L)
{
	L->length = 0;//当前表长设为0
	return OK;
}
Status ListEmpty(SqList L)
{
	if (L.length ==0)	return TRUE;//表长为0则为空表
    return FALSE;
}
int ListLength(SqList L)
{
	return L.length;
}
Status GetElem(SqList L, int i,ElemType * e)
{
	if (i<0 || i>L.length)//判断位置i是否合法
	{
		return ERROR;
	}
	else
	{
		* e = L.elem[i - 1];//将对应的元素传递给指针
	return OK;
	}
} 
Status LocateElem(SqList L,ElemType e, Status (*Compare)()) 
{
	int i = 0;
	while (i <=L.length &&(*Compare)(L.elem[i], e)!=1) i++;//若i<=表长且元素不符合Compare要求则i++
	if (i > L.length) return FALSE;//找完了没有符合的返回FALSE
	return i+1;//找到了则返回对应的次序
}
Status PriorElem(SqList L, ElemType cur_e, ElemType * pre_e) 
{
	if (L.elem[0] == cur_e)//若cur_e为表头则返回ERROR
	{
		return ERROR;
	}
	for (int i = 1; i <= L.length; i++)
	{
		if (L.elem[i] == cur_e)
		{
			*pre_e = L.elem[i-1];//将后继元素的值传递给指针
			return OK;
		}
	}
	return ERROR;
}
Status NextElem(SqList L, ElemType cur_e, ElemType * next_e)
{
	if (L.elem[L.length] == cur_e)//若cur_e为表尾则返回ERROR
	{
		return ERROR;
	}
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == cur_e)
		{
			*next_e = L.elem[i + 1];//将前驱元素的值传递给指针
			return OK;
		}
	}
	return ERROR;
}
Status ListInsert_Sq(SqList * L, int i, ElemType e)
{
	//在第i个位置前插入新元素e
	ElemType * newbase;
	ElemType * 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));//定义newbase来存储重新分配的地址（realloc）
		if (!newbase) exit(OVERFLOW);//分配失败，程序退出，返回码为OVERFLOW
		L->elem = newbase;//将elem指向新的地址
		L->listsize += LISTINCREMENT;//listsize更新为加上增量后的值
	}
	q = &(L->elem[i - 1]);//q为插入位置

	for (p = &(L->elem[L->length - 1]);p >=q;--p) *(p + 1) = *p;//p为临时变量，将所有i后的元素都往右移动一个位置
	*q = e;
	++L->length;
	return OK;
}
Status ListDelete_Sq(SqList * L, int i, ElemType * e)
{
	ElemType *q,* p;
	if (i<1 || i>L->length) return ERROR;
	p=&(L->elem[i - 1]);//p为被删除元素的位置
	*e = *p;
	q = L->elem + L->length - 1;//q为表尾元素的位置，L->elem为首地址
	for (++p;p<=q;++p)	*(p-1) = *p; //删除元素后的元素都往左移动一个位置
	--L->length;
	return OK;
}
Status ListTraverse(SqList L, Status(*Visit)()) 
{
	for (int i = 1;i <= L.length;i++) {
		if (!Visit(L.elem[i - 1])) return ERROR;
	}
	return OK;
}
Status Compare(ElemType e1, ElemType e2)
{
	if (e1 > e2) return 1;
	if (e1 == e2) return 0;
	return -1;
}
Status Visit(ElemType e)
{
	if (!e) return ERROR;
	printf("%d  ", e);
	return OK;
}
void input(SqList * L)
{
	//初始化线性表
	int i = 1;
	ElemType x;
	InitList_Sq(L);
	printf("请输入一组数据，以0做为结束符：n");
	scanf("%d", &x);
	while (x)
	{
		L->elem[i - 1] = x;
		i++;
		scanf("%d", &x);
	}
	L->length = i - 1;
}