数据结构学习笔记之线性表

v 定义完结构体，我们就可以对其来进行操作了，下面是我自己实现对线性表操作的一些接口函数。Ps:以下的函数均是基于Sq *Sequence;这个结构体指针。

v 1.初始化操作，建立一个空线性表

nt InitSequence(Sq **s)
{
	*s = (Sq *)malloc(sizeof(Sq));  //为结构体变量在堆上分配一段空间 
	if(NULL == *s)
	{
		return FAILURE;
	}

	(*s)->a = (Elemtype *)malloc(sizeof(Elemtype)*SIZE); //为结构体中的数据分配一段空间 
	if(NULL == (*s) -> a)
	{
		return FAILURE;
	}

	(*s)->size  = SIZE;    //初始化线性表的容量和长度 
	(*s)->length = 0;

	return SUCCESS;
}

注意：在本函数中，函数的形参是Sq **s。如果传递的形参是Sq  *s，那么就与我之前一个博客讲的一样最后分配的空间会在函数最后一步被释放，最后运行程序出现段错误。

v 2.判断线性表是否为空

int ListEmpty(Sq *s)
{
	if(0 == s->length)
	{
		return TURE;  //若为空，返回 TURE
	}
	else 
	{
		return FALSE;  //若不为空，返回 FALSE
	}
}

v 3.在线性表第i个位置插入新的元素e

int ListInsert(Sq *s,int i,Elemtype e)
{
	int *p;

	if(NULL == s)    //入参判断 
	{
		return FAILURE;
	}

	if(i <= 0 || i > SIZE)
	{
		return FAILURE;
	}

	if(s->length >= s->size)
	{
		return FAILURE;
	}

	for(p = s->a + s->length;p >= s->a + i;p--)  //注意循环判断的范围
	{
		memcpy(p,p-1,sizeof(Elemtype));   //从第i+1个元素到最后一个位置向后移动一位 
	}
	memcpy(s->a+i-1,&e,sizeof(Elemtype));   //将e插入第i个位置 

	s->length++;   //此时，线性表加一 

	return SUCCESS;

}

v 遍历一个线性表

int ListTraverse(Sq *s,void (*visit)(Elemtype))
{
	int i;

	if(NULL == s)
	{
		return FAILURE;
	}
	
	for(i = 0;i < s->length;i++)
	{
		visit(*(s->a+i));   //访问线性表中的每一个元素 
	}

	return SUCCESS;
}

Ø 线性表中的形参void (*visit)(Elemtype)是一个函数指针，指向一个形参为int型，返回值为void的函数，我把这个函数也贴出来

Ø 程序示例

void print(Elemtype e)
{
	printf("%d ",e);
}

v 返回线性表元素的个数

int Listlength(Sq *s)
{
	return s->length;
}

v 将线性表第i个位置的元素返回给e

int GetElem(Sq *s,int i,Elemtype *e)
{
	if(NULL == s || i < 0 || i > s->length)
	{
		return FAILURE;
	}

	*e = *(s->a+i-1);  //直接定位返回 

	return SUCCESS;
}

Ø 程序示例：

int Equal(Elemtype a,Elemtype b)
{
	return (a == b)? TURE:FALSE;
}

分析：结合Compare指向的函数，其实if(Compare(*(s->a+i),e))就是判断当前循环数据与e是否相同。

v 输入一个数据，如果数据在线性表内就输出这个数据的前驱

int PriorElem(Sq *s,Elemtype e)
{
	int i;

	if(NULL == s || e == *(s->a))  //当s指向空或者当前数据是表中第一个元素时，函数返回失败 
	{
		return FAILURE;
	}

	for(i = 0;i < s->length;i++)
	{
		if(e == *(s->a+i))   //定位输入的元素 
		{
			return *(s->a+i-1);  //定位成功，输出数据的前驱 
		}
	}

	return FAILURE;

}

v 删除线性表中的第i个位置的元素，并用e返回其值

int ListDelete(Sq *s,int i,Elemtype *e)
{
	int *p;

	if(NULL == s)
	{
		return FAILURE;
	}

	if(i < 0 || i >= s->length)
	{
		return FAILURE;
	}

	if(s->length > s->size)
	{
		return FAILURE;
	}

	*e = *(s->a+i-1);  //返回第i个位置上数据的值 
	for(p = s->a+i-1;p <= s->a+s->length-1;p++)
	{
		memcpy(p,p+1,sizeof(Elemtype));  //从第i个位置后的数据 到最后的数据向前移动一位 
	} 
	
	
	s->length--;  //此时线性表减一 

}

v 线性表清空

int ClearList(Sq *s)
{
	if(NULL != s)
	{
		free(s->a);  //先释放数据空间 
		free(s);     //再释放结构体指针变量的空间 
		s->length = 0;   //表的长度与容量清零 
		s->size = 0;
		return SUCCESS;
	}

	return FAILURE;
}

以上就是我线性表所学习的一些接口函数整理，纯手敲的。若是各位发现不对之处，还望多多指教！一起学习，一起进步！