不定长顺序表（C语言）

不定长顺序表（C语言）

结构体定义：

#define Maxsize 10
typedef int ElemType;
typedef struct Dsqlist
{
	ElemType* elem;//指针，接受malloc返回值
	int length;//有效长度
	int list_size;//存放一个整型值，这个变量用来存储最大容量空间个数，以格子为单位
}Dsqlist, * PDsqlist;

不定长顺序表可以实现的功能：

//初始化
void Init_Dsqlist(struct Dsqlist* p);//void Init_sqlist(Psqlist p);

//按位置插入
bool DInsert_pos(PDsqlist p, int pos, int val);

//按位置删除
bool DDel_pos(PDsqlist p, int pos);

//按值删除
bool DDel_val(PDsqlist p, int val);

//获取其有效长度
int DGet_length(PDsqlist p);

//扩容   2倍
void Inc(PDsqlist p);

//获取值所在下标（如果数据重复，则返回val第一次出现的位置）
int DSearch(PDsqlist p, int val);

//判空
bool DIsEmpty(PDsqlist p);

//判满
bool DIsFull(PDsqlist p);

//清空
void DClear(PDsqlist p);

//销毁
void DDestroy(PDsqlist p);

//打印
void DShow(PDsqlist p);

接下来分别是实现功能的具体函数：

初始化：

//初始化
void Init_Dsqlist(struct Dsqlist* p)//void Init_sqlist(PDsqlist p);
{
	assert(p != NULL);
	if (NULL == p)
	{
		return;
	}
	p->elem = (ElemType*)malloc(sizeof(ElemType) * Maxsize);
	assert(p->elem != NULL);
	if (p == NULL)
	{
		return;
	}
	p->length = 0;
	p->list_size = Maxsize;
}

判空，判满

bool DIsEmpty(PDsqlist p)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return false;
	}
	return p->length==0;
}

bool DIsFull(PDsqlist p)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return false;
	}
	return p->length == p->list_size;
}

按位置删除：

bool DDel_pos(PDsqlist p, int pos)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return false;
	}
	//2.判断插入位置 是否合法
	assert(pos <= p->length && pos >= 0);
	if (pos > p->length || p < 0)
	{
		return false;
	}
	//3.判空操作
	if (DIsEmpty(p))
	{
		return false;
	}
	//4.将待删除位置后面的有效值，一次向前挪动一位，将删除位置覆盖掉即可
	//（删除，向前覆盖数据，离待删除位置最近的元素先挪动）
	for (int i = pos ; i < p->length; i++)
	{
		p->elem[i] = p->elem[i + 1];
	}
	//此时，for循环执行结束  标识着数据向前覆盖完成   现在只需要将p->length--
	p->length--;

	return true;
}

按位置插入：

bool DInsert_pos(PDsqlist p, int pos, int val)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return false;
	}
	//2.判断插入位置 是否合法
	assert(pos <= p->length && pos >= 0);
	if (pos > p->length || p < 0)
	{
		return false;
	}
	//3.判满操作
	if (DIsFull(p))
	{
		Inc(p);
	}
	//此时，肯定p不为NULL， 并且pos位置合法， 并且还用空闲位置让我插入
	// 4.首先挪动数据，让待插入位置空出来，再将值val放进去即可
		//（插入，挪动数据，从后先前挪）
	for (int i = p->length - 1; i >= pos; --i)
	{
		p->elem[i + 1] = p->elem[i];
	}
	//此时，for循环执行结束  标识着挪动数据完成   现在只需要将插入的值val赋值进去
	p->length++;
	return true;
}

按值删除：

bool DDel_val(PDsqlist p, int val)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return false;
	}
	//判断val这个值  存不存在
	int index = DSearch(p, val);
	if (index == -1)
	{
		return false;
	}
	return DDel_pos(p, index);
}

获取有效长度：

int DGet_length(PDsqlist p)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return -1;
	}
	return p->length;
}

扩容：（这里以2倍为例）

void Inc(PDsqlist p)
{

	

	//上面的方法借助第三方变量可以防止内存泄漏；
	p->elem = (ElemType*)realloc(p->elem, sizeof(ElemType) * p->list_size * 2);
	//必须加断言,因为realloc失败后，会返回一个NULL，如果不加断言，会导致内存泄漏
	assert(p->elem != NULL);
	if(p==NULL)
	{
		return;
	}
	p->list_size = 2 * p->list_size;
}

以上是两种扩容的方法，接下来是：获取值所在下标（如果数据重复，则返回val第一次出现的位置）

int DSearch(PDsqlist p, int val)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return -1;
	}
	for (int i = 0; i < p->length; i++)
	{
		if (p->elem[i] == val)
		{
			return i;
		}
	}
	return -1;
}

清空，销毁，打印：

//清空
void DClear(PDsqlist p)
{
	assert(p != NULL);
	if (p == NULL)
	{
		return;
	}
	p->length = 0;
}

//销毁
void DDestroy(PDsqlist p)
{
	//assert
	free(p);
}

//打印
void DShow(PDsqlist p)
{
	//assert
	for (int i = 0; i < p->length; i++)
	{
		printf("%d ", p->elem[i]);
	}
	printf("n");
}