[数据结构与算法]顺序表结构

线性结构-顺序表

• 特点1：有一个唯一的表名来标识该顺序表

• 特点2：内存单元连续存储

• 特点3：数据按顺序存放

利用结构体和typedef 设计一个顺序表结构

typedef struct
{
	ElemType data[MAXSIZE];
	int length;
}SqList;

优点1：无须为表示表中元素之间的逻辑关系而增加额外的存储空间
缺点2：当线性表长度变化较大时，难以确定存储空间的容量
缺点3：造成存储空间的"碎片"

• 在内存中的结构

?利用for循环往顺序表插入数据

• 参数1：顺序表指针
• 参数2：插入的位置
• 参数3：插入的数据

Status ListInsert(SqList* L, int index/*人类角度的下标*/, const ElemType e) {
	//1.插入的位置必须有效
	//2.不能超出顺序表的长度
	if ((index >= 1) && (L->length < MAXSIZE))
	{
		//第一次：插入的位置1 <= 0 不成立 
		//第二次：插入的位置1 <= 1 成立 
		if (index <= L->length) {
			//第二次第A次循环：k = 0, 0 >= 0 成立
			for (int k = L->length - 1; k >= index - 1; k--)
			{
				L->data[k + 1] = L->data[k];//数据迁移到后一个格子
			};
		}
		L->data[index - 1/*要插入的位置*/] = e/*数据*/;
		L->length++;
		return OK;
	}
	return ERROR;
}

缺点1：插入和删除操作需要移动大量元素

?利用for循环遍历顺序表

Status ListTraverse(SqList* L) {
	for (int i = 0; i < L->length; i++)
	{
		visit(L->data[i]);
	}
	printf("\r\n");
	return OK;
}
//分层思维
Status visit(ElemType e) {
	printf("%d → ", e);
	return OK;
}

?通过设置长度为0来清除顺序表

Status ClearList(SqList* L) {
	if (L == NULL)
		return ERROR;
	L->length = 0;
	return OK;
}

?查询指定位置的数据

• 参数1：顺序表指针
• 参数2：要查询的顺序表位置
• 参数3：存储数据的指针

Status getElem(SqList* L, int index/*人类思维的查询位置*/, ElemType* e) {
	//第一种情况，长度等于0
	//第二种情况：查询的位置小于1
	//第三种情况：查询的位置大于顺序表的长度
	if ((L->length == 0) || (index < 1) || (index > L->length))
	{
		return ERROR;
	}
	*e = L->data[index - 1];
	return OK;
}

优点2：可以快速地存取表中任一位置的元素

?删除一个指定的位置

• 参数1：顺序表指针?
• 参数2：要删除的下标
• 参数3：存储要删除的位置里面的数据指针

Status listDelete(SqList* L, int index/*人类思维的下标*/, ElemType* e) {
	//第一种情况：长度为零
	//第二种情况：要删除的位置不存在
	//第三种情况：要删除的下标 > 顺序表的长度
	if ((L->length == 0) || (index <= 0) || (index > L->length))
	{
		return ERROR;
	}
	*e = L->data[index - 1];//保存要删除的位置里面的数据
	//第一次：11 < 11，不成立
	//第二次：10 < 11，成立
	if (index < L->length)
	{
		//第二次第A次
		for (int k = index; k < L->length; k++) {
			L->data[k - 1] = L->data[k];//要删除的位置里面的数据 = 下一个格子里面的数据
		};
	}
	L->length--;
	return OK;
}

缺点1：插入和删除操作需要移动大量元素

?