数据结构笔记 四：顺序表

2024-04-12 21:34:14

说明：本笔记依照《王道论坛-数据结构》视频内容整理。

一、定义

顺序表：用顺序存储的方式实现线性表。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间关系由存储单元的邻近关系来体现。

二、顺序表实现

1、静态分配

使用数组方式实现。

#define MAXSIZE 10          			// 定义最大长度
typedef int ElemType;					// 根据实际情况定义

typedef struct{
	ElemType data[MAXSIZE]; 	        // 用数组存放数据元素（ElemType - 实际数据类型）
	int length;             			// 顺序表的当前长度
}ListT;									// List（列表）T（数据类型）Q（指针类型）

typedef ListT* ListTQ;

1、静态分配表长无法更改。设置小了空间不够，设置大了浪费空间。

2、动态分配

#define MAXSIZE 10		// 顺序表的初始长度
typedef int ElemType;	// 根据实际情况定义

typedef struct{
	ElemType *data;		// 指示动态分配数组的指针（ElemType - 实际数据类型）
	int MaxSize;		// 顺序表的最大容量
	int length;			// 顺序表的当前长度
}ListT;					// List（列表）T（数据类型）Q（指针类型）

typedef ListT* ListTQ;

1、动态分配表长可以更改，因此需要一个变量指示最大容量。

2、在 C 语言中使用 malloc() 进行分配空间，free() 进行释放空间。

三、静态分配操作实现

1、InitList(&L)

void initList(ListT *l)
{
	for (int i = 0; i < MAXSIZE; i++) {
		l->data[i] = 0;		// 将所有元素设置为默认初始值
	}
	l->length = 0;			// 顺序表初始长度为0 
}

如果不进行初始化，顺序表静态分配可以会有脏数据（和静态分配位置有关，局部变量会出现这种情况）。
数据结构笔记 四：顺序表

2、DestroyList(&L)

变量程序启动后自动分配，不可以进行销毁。

3、ListInsert(&L,i,&e)

/****************************************
* l - 要操作顺序表首地址
* i - 插入位置（注意位序和数组下标的关系、检查下标合法性）
* e - 插入元素
* 注：
* 	1、注意表满的情况
*	2、进行处理是只用元素位序进行考虑，数据移动时才需要考虑数组下标
* 时间复杂度：O(n)
****************************************/
int listInsert(ListT *l, int i, ElemType e)
{
	if (i<1 || i>l->length + 1) return 1;		// 插入位置错误
	if (l->length >= MAXSIZE) return 1;			// 存储空间满
	for (int j = l->length; j >= i; j--) {		// j 表示现有长度
		l->data[j] = l->data[j - 1];			// 第i元素后数据后移
	}
	l->data[i - 1] = e;							// 将e存放到第i位置
	l->length++;								// 长度加 1
	return 0;
}

数据结构笔记 四：顺序表

4、ListDelete(&L,i,&e)

/****************************************
* l - 要操作的顺序表首地址
* i - 删除位置（注意位序和数组下标的关系）
* e - 保存删除位置的数据内容（用于从函数返回数据）
* 时间复杂度：O(n)
****************************************/
int listDelete(ListT *l, int i, ElemType *e)
{
	if (i<1 || i >l->length) return 1;			// 判断 i 的范围是否有效
	*e = l->data[i - 1];						// 将被删除的元素赋值给e
	for (int j = i; j < l->length; j++) {		// 使用 i 进行计算，不定义 j 也可以
		l->data[j - 1] = l->data[j];			// 将第 i 位置后的元素前移
	}
	l->length--;								// 线性表长度减 1

	return 0;
}

数据结构笔记 四：顺序表

5、LocateElem(L,e)

/****************************************
* l - 要操作的顺序表首地址
* e - 要查找的值
* 注：不适用于结构类型（因为不可以直接比较数据）
****************************************/
int locateElem(ListT *l, ElemType e)
{
	for (int i = 0; i < l->length; i++) {
		if (l->data[i] == e) return i + 1;	// 数组下标为i的元素值等于e，返回其位序i+1（注意位序和数组下标关系）
	}

	return 0;								// 查找失败，返回0
}

6、GetElem(L,i)

/****************************************
* l - 要操作的顺序表首地址
* i - 查找位置
****************************************/
ElemType getElem(ListT *l, int i)
{
	if (i<1 || i>l->length) return 0;			// 判断 i 的范围是否有效

	return l->data[i - 1];						// 返回下标为 i 的数据内容
}

7、Length(L)

int length(ListT *l)
{
	return l->length;
}

8、PrintfList(L)

/****************************************
* l - 要操作的顺序表首地址
* 注：不同数据类型使用打印语句不同
****************************************/
void printfList(ListT *l)
{
	printf("l->length = %d\n",l->length);
	for(int i = 0; i < l->length; i++){
		printf("l->data[%d] = %d\n",i,l->data[i]);
	}
}

9、Empty(L)

int enpty(ListT *l)
{
	if(l->length == 0) return 0;
	else return 1;
}

四、静态分配和动态分配之间关系

静态分配内存布局图：
数据结构笔记 四：顺序表
动态分配内存布局图：
数据结构笔记 四：顺序表
静态分配中：顺序表存储空间首地址 - L.data。

动态分配中：顺序表存储空间首地址 - L.data

总结：静态分配和动态分配除使用空间在内存中布局不同，因此操作处理基本相同。

五、动态分配操作实现

1、InitList(&L)

void initList(ListT *l)
{
	l->data = (ElemType*)malloc(MAXSIZE*sizeof(ListT)); // 分配一片连续空间
	l->length = 0;                                      // 使用长度设置为0
	l->maxSize = MAXSIZE;                               // 设置最大长度
	for (int i = 0; i < l->maxSize; i++) {
		l->data[i] = 0;                                 // 分配空间清零
	}
}

数据结构笔记 四：顺序表

2、IncreaseSize（特有）

void increaseSize(ListT *l, int len)
{
	ElemType *p = l->data;                                         	// 使用局部变量指向当前空间
	l->data = (ElemType *)malloc((l->maxSize + len)*sizeof(ListT));	// 新分配一片空间
	for (int i = 0; i < l->length; i++) {
		l->data[i] = p[i];                                      	// 将旧空间数据拷贝到新空间
	}
	l->maxSize = l->maxSize + len;                              	// 更改最大长度值
	free(p);                                                    	// 释放旧空间
}

// realloc 库函数实现以上过程

数据结构笔记 四：顺序表

3、DestroyList(&L)

/****************************************
* l - 要操作的顺序表首地址
* 注：只可以释放使用 malloc 分配的部分（不释放会引起内存泄漏）
****************************************/
void DestroyList(ListT *l)
{
	if(l->data != NULL){
		free(l->data);
		l->data = NULL;
		l->maxSize = 0;
		l->length = 0;
	}
}

4、ListInsert(&L,i,&e)

/****************************************
* l - 要操作顺序表首地址
* i - 插入位置（注意位序和数组下标的关系、检查下标合法性）
* e - 插入元素
* 注：
* 	1、注意表满的情况
*	2、进行处理是只用元素位序进行考虑，数据移动时才需要考虑数组下标
* 时间复杂度：O(n)
****************************************/
int listInsert(ListT *l, int i, ElemType e)
{
	if (i<1 || i>l->length + 1) return 1;		// 插入位置错误
	if (l->length >= l->maxSize) return 1;		// 存储空间满(和静态分配有区别)
	for (int j = l->length; j >= i; j--) {		// j 表示现有长度
		l->data[j] = l->data[j - 1];			// 第i元素后数据后移
	}
	l->data[i - 1] = e;							// 将e存放到第i位置
	l->length++;								// 长度加 1
	return 0;
}

5、ListDelete(&L,i,&e)

/****************************************
* l - 要操作的顺序表首地址
* i - 删除位置（注意位序和数组下标的关系）
* e - 保存删除位置的数据内容（用于从函数返回数据）
* 时间复杂度：O(n)
****************************************/
int listDelete(ListT *l, int i, ElemType *e)
{
	if (i<1 || i >l->length) return 1;			// 判断 i 的范围是否有效
	*e = l->data[i - 1];						// 将被删除的元素赋值给e
	for (int j = i; j < l->length; j++) {		// 使用 i 进行计算，不定义 j 也可以
		l->data[j - 1] = l->data[j];			// 将第 i 位置后的元素前移
	}
	l->length--;								// 线性表长度减 1

	return 0;
}

6、LocateElem(L,e)

/****************************************
* l - 要操作的顺序表首地址
* e - 要查找的值
* 注：不适用于结构类型（因为不可以直接比较数据）
****************************************/
int locateElem(ListT *l, ElemType e)
{
	for (int i = 0; i < l->length; i++) {
		if (l->data[i] == e) return i + 1;	// 数组下标为i的元素值等于e，返回其位序i+1（注意位序和数组下标关系）
	}

	return 0;								// 查找失败，返回0
}

7、GetElem(L,i)

/****************************************
* l - 要操作的顺序表首地址
* i - 查找位置
****************************************/
ElemType getElem(ListT *l, int i)
{
	if (i<1 || i>l->length) return 0;			// 判断 i 的范围是否有效

	return l->data[i - 1];						// 返回下标为 i 的数据内容
}

8、Length(L)

int length(ListT *l)
{
	return l->length;
}

9、PrintfList(L)

/****************************************
* l - 要操作的顺序表首地址
* 注：不同数据类型使用打印语句不同
****************************************/
void printfList(ListT *l)
{
	printf("l->length = %d\n",l->length);
	for(int i = 0; i < l->length; i++){
		printf("l->data[%d] = %d\n",i,l->data[i]);
	}
}

10、Empty(L)

int enpty(ListT *l)
{
	if(l->length == 0) return 0;
	else return 1;
}
上一篇：线性表


下一篇：学习线性表