顺序表的相关操作算法实现

顺序表的相关操作算法实现

//函数结果状态代码
# define MAXSIZE 100
#define OVERFLOW -2
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0

//数据元素及顺序表的结构体类型定义


typedef struct
{
	char name[50];
	int price;
}Book;
typedef struct
{
	Book* elem;
	int length;
}SqList;

typedef Book ElemType;   //把Book重命名为ElemType,Book就与Elem等价了

//顺序表的操作函数声明
// 线性表初始化
int InitList_Sq(SqList* L);
//销毁线性表L
void DestroyList_Sq(SqList* L);
//清空线性表L
void ClearList_Sq(SqList* L);



//求线性表的长度
int GetLength_Sq(SqList* L);
//判断线性表L是否为空
int IsEmpty(SqList L);



//以上操作，函数都只有一个参数

//查找要特殊一点，一种是某查元素的位置（按值查找），一种是查某位置的元素（按位查找）
//顺序表的取值，根据位置i获取相应位置的元素e
int GetElem(SqList L, int i, ElemType* e);  //结构体可以直接传值的
//顺序表的按值查找，如果存在，返回是第几个元素，如果不存在，返回0
int LocateElem(SqList L, ElemType e);




// 顺序表的插入，将新元素e插入到顺序表的第i个位置
int ListInsert_Sq(SqList* L, int i, ElemType e);
//顺序表的删除，将第i个位置的元素删除，同时第i个位置后的元素位置减1
int ListDelete_Sq(SqList* L, int i);

//操作函数的具体实现

//线性表初始化
//构造一个空的顺序表
int InitList_Sq(SqList* L)
{
	// 为顺序表分配空间
	L->elem = malloc(sizeof(ElemType) * MAXSIZE);
	// 判断是否成功分配好空间
	if (!L->elem)
	{
		exit(OVERFLOW);
	}
	L->length = 0;
	return OK;
}


//销毁线性表L
void DestroyList_Sq(SqList* L)
{
	if (L->elem)
	{
		free(L);  // 释放存储空间
	}
}

// 清空线性表
void ClearList_Sq(SqList* L)
{
	L->length = 0;   //将线性表长度置为0
}

//求线性表的长度
int GetLength_Sq(SqList *L)
{
	return (L->length);
}

//判断线性表L是否为空
int IsEmpty(SqList L)
{
	if (L.length == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}


//顺序表的取值，根据位置i获取相应位置的元素e
int GetElem(SqList L, int i, ElemType* e)  //结构体可以直接传值的
{
	if (i<1 || i>L.length)
	{
		return ERROR;
	}
	//这里注意要对e进行解引用
	*e = L.elem[i - 1];  //第i个元素的下标为i-1
	return OK;
}



//顺序表的按值查找，如果存在，返回是第几个元素，如果不存在，返回0
int LocateElem(SqList L, ElemType e)
{
	int i = 0;
	for (i = 0; i < L.length; i++)   //for和if不加花括号害死人
	{
		if(!strcmp(L.elem[i].name,e.name)) //这里结构体倘若直接比较（strcmp(L.elem[i],e)）虽然不会报错，但是运行会出错
		{
			return i + 1;
		}
	}
	return 0;       
}


// 顺序表的插入，将新元素e插入到顺序表的第i个位置
int ListInsert_Sq(SqList* L, int i, ElemType e)
{
	//插入位置必须是1<=i<=L.length+1,如果非法，则返回ERROR
	if (i<1 || i>L->length + 1)
	{
		return ERROR;
	}
	//插入位置合法以后，也还需要判断表格是否已经满了，如果满了，也要返回ERROR
	if (L->length == MAXSIZE)
	{
		return ERROR;
	}
	//插入新元素之前，要先把第i个元素及其后面的元素都往后移一个位置
	//而且需要从最后一个元素往前移，这样就会把第i个位置空出来
	int j = 0;
	for (j = L->length - 1; j >= i - 1; j--)  //下标比位置标号要少1
	{
		L->elem[j + 1] = L->elem[j];
	}
	//现在在第i个位置插入新的元素,e是一个结构体，结构体之间是可以直接赋值的
	L->elem[i - 1] = e;
	//插入新的元素之后，表的长度要加1
	L->length++;
	return OK;
}


//顺序表的删除，将第i个位置的元素删除，同时第i个位置后的元素位置减1
int ListDelete_Sq(SqList* L, int i)
{
	//删除的位置必须是1<=i<=L->length，如果非法，返回ERROR
	if (i<1 || i>L->elem)
	{
		return ERROR;
	}
	//因为要删除第i个位置的元素，所以直接覆盖第i个位置的元素即可，所以删除第i个元素什么都不需要做
	//接下来将第i+1个元素及其之后的元素都往前移1位，且先移动第i+1个元素，即从下标i开始移动到下标L->length-1结束
	int j = 0;
	for (j = i; j <= L->elem - 1; j++)
	{
		L->elem[j - 1] = L->elem[i];
	}
	//现在表的长度要减1
	L->elem--;
	return OK;
}