数据结构与算法：线性表-顺序表（顺序存储）-EW帮帮网

一、线性表的定义（逻辑结构）

线性表是由 n (n >= 0) 个相同数据类型的数据元素组成的有限序列，其中 n 为线性表的表长，当 n = 0 时，线性表为空表。如果用 L 命名线性表，那么一般表示为：L = (a₁, a₂, …, a_n)，其中

a₁ 是唯一的第一个数据元素，又称为表头元素。
a_n 是唯一的最后一个数据元素，又称为表尾元素。
除了第一个数据元素外，每个数据元素有且仅有一个直接前驱。
除了最后一个数据元素外，每个数据元素有且仅有一个直接后驱。
以上就是线性表的逻辑特性，所以，线性表的逻辑结构如下

二、线性表的基本操作

一个数据结构的基本操作是指最核心、最基本的操作，其他较为复杂的操作可以通过调用其基本操作来实现，线性表主要的基本操作如下

init_list(*list); // 初始化线性表，构造一个空表
destroy_list(*list); // 销毁线性表
print_list(*list); // 打印线性表的所有数据元素
list_append(*list, elem); // 从线性表的末尾插入一个元素
list_insert(*const list, index, elem); // 插入一个元素到线性表中, 参数 index 是下标，从 0 开始
list_delete(*list, index, *elem); // 从线性表中删除一个元素，参数 index 是下标，从 0 开始
list_get_elem(*list, index); // 获取线性表中 index 下标的值
list_locate_elem(*list, elem); // 在线性表中查找第一个元素值为 elem 的下标，找到返回相应的下标，否则返回 -1

三、线性表的顺序表示（物理结构）

用顺序存储的方式实现的线性表称为顺序表，它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个数据元素在物理位置上也相邻。
在这里插入图片描述

在 C 语言中，使用数组来描述线性表的顺序存储结构，数组可以静态分配，也可以动态分配。

使用静态分配时，由于数组的容量和空间已经固定死，当数据空间占满，再加入新的数据就会产生溢出，导致程序崩溃。用静态分配来描述线性表的数据结构可以如下

#define MAX_CAP 1024	// 顺序表容量
typedef struct {
	elem_type data[MAX_CAP];	// 顺序表的元素，elem_type 是数据元素类型
	int length;	// 顺序表的当前长度
}seq_list_t;

使用动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，当数据空间占满，就开辟一块更大的存储空间，用以替换原来的存储空间。用动态分配来描述线性表的数据结构可以如下

#define INIT_CAP 8	// 顺序表容量
typedef struct {
	elem_type* data;		// 指向数组的首元素
	int capacity;	// 顺序表的容量
	int length;		// 顺序表的当前长度
}seq_list_t;

四、顺序表基本操作的实现

seq_list.h

#pragma once
#include <stdbool.h>
#include <string.h>

#define INIT_CAP 8		// 默认最大容量

extern const char* err_strings[];
/*
const char* err_strings[] = {
	"success",
	"invalid index",
	"pointer can't NULL"
};
*/
#define ERR_SUCCESS 0
#define ERR_INVALID_INDEX 1
#define ERR_POINTER_NULL 2

typedef struct {
	int* data;		// 指向数组的首元素
	int capacity;	// 顺序表的容量
	int length;		// 顺序表的当前长度
}seq_list_t;

// 初始化顺序表
void init_list(seq_list_t* const list);	
// 销毁顺序表
void destroy_list(seq_list_t* const list);
// 打印顺序表的所有数据元素
void print_list(seq_list_t* const list);

// 插入一个元素到顺序表中, 参数 index 是下标，从 0 开始
int list_insert(seq_list_t* const list, const int index, const int elem);
// 从顺序表的末尾插入一个元素
void list_append(seq_list_t* const list, const int elem);
// 从顺序表中删除一个元素，参数 index 是下标，从 0 开始
int list_delete(seq_list_t* const list, const int index, int* elem);
// 顺序表是否为空，即顺序表的表长是否为 0，为 0 返回 true，否则返回 false
bool list_empty(seq_list_t* const list);
// 获取顺序表的表长
int list_length(seq_list_t* const list);
// 获取顺序表中 index 下标的值
int list_get_elem(seq_list_t* const list, const int index, int *elem);
// 在顺序表中查找第一个元素值为 elem 的下标，找到返回相应的下标，否则返回 -1
int list_locate_elem(seq_list_t* const list, const int elem);


// 扩容
void increase_cap(seq_list_t* const list);

seq_list.c

#include "seq_list.h"
#include <stdio.h>	// printf 函数
#include <stdlib.h>	// malloc free 函数

const char* err_strings[] = {
	"success",
	"invalid index",
	"pointer can't NULL"
};

void init_list(seq_list_t* const list) {
	list->capacity = INIT_CAP;
	list->data = (int*)malloc(sizeof(int) * list->capacity);	// 用 malloc 函数申请一片连续的存储空间
	list->length = 0;
}
void destroy_list(seq_list_t* const list) {
	free(list->data);	// 用 free 函数释放一片连续的存储空间
}

void print_list(seq_list_t* const list) {
	for (int i = 0; i < list->length; i++)
		printf("%d\n", list->data[i]);
	printf("print_list finished\n");
}

int list_insert(seq_list_t* const list, const int index, const int elem) {
	if (index < 0 || index > list->length)
		return ERR_INVALID_INDEX;

	if (list->length >= list->capacity)	// 容量已满，扩容
		increase_cap(list);

	// 把第 index 索引(包括第 index 索引) 后的每个个元素往后移
	for (int i = list->length; i > index; i--)
		list->data[i] = list->data[i-1];

	list->data[index] = elem;
	list->length++;

	return ERR_SUCCESS;
}
void list_append(seq_list_t* const list, const int elem) {
	if (list->length >= list->capacity) // 容量已满，扩容
		increase_cap(list);

	list->data[list->length] = elem;
	list->length++;
}

int list_delete(seq_list_t* const list, const int index, int* elem) {
	if (index < 0 || index >= list->length) 
		return ERR_INVALID_INDEX;

	if (elem)
		*elem = list->data[index];
	// 把第 index 索引后的每一个元素向前移
	for (int i = index; i < list->length; i++)
		list->data[i] = list->data[i + 1];
	list->length--;

	return ERR_SUCCESS;
}

bool list_empty(seq_list_t* const list) {
	return list->length == 0 ? true:false;
}

int list_length(seq_list_t* const list) {
	return list->length;
}

int list_get_elem(seq_list_t* const list, const int index, int *elem) {
	if (!elem)
		return ERR_POINTER_NULL;

	if (index < 0 || index >= list->length)
		return ERR_INVALID_INDEX;

	*elem = list->data[index];

	return ERR_SUCCESS;
}

int list_locate_elem(seq_list_t* const list, const int elem) {
	for (int i = 0; i < list->length; i++) {
		if (list->data[i] == elem)
			return i;
	}

	return -1;
}

void increase_cap(seq_list_t* const list) {
	int* p = list->data;
	list->capacity = list->capacity * 2;
	list->data = (int*)malloc(sizeof(int) * list->capacity);

	// 将数据复制到新区域
	for (int i = 0; i < list->length; i++)
		list->data[i] = p[i];
	free(p);
}

main.c

#include <stdio.h>
#include "seq_list.h"

int main(int argc, const char* argv[]) {
	seq_list_t list;
	init_list(&list);
	if (list_empty(&list))
		printf("list empty\n");
	else
		printf("list length = %d\n", list_length(&list));

	for (int i = 0; i < 3; i++)
		list_append(&list, i);
	print_list(&list);

	int err = -1;
	int elem = 5;
	int index = 0;
	err = list_insert(&list, index, elem);
	if (err != ERR_SUCCESS)
		printf("list_insert failed: %s, length = %d, index = %d\n", err_strings[err], list_length(&list), index);
	else
		print_list(&list);

	index = 5;
	err = list_delete(&list, index, &elem);
	if (err != ERR_SUCCESS)
		printf("list_delete failed: %s, length = %d, index = %d\n", err_strings[err], list_length(&list), index);
	else
		printf("list_delete success: index = %d, elem = %d\n", index, elem);

	index = 2;
	err = list_get_elem(&list, index, &elem);
	if (err != ERR_SUCCESS)
		printf("list_get_elem failed: %s, length = %d, index = %d\n", err_strings[err], list_length(&list), index);
	else
		printf("list_get_elem success: index = %d, elem = %d\n", index, elem);
	
	elem = 4;
	index = list_locate_elem(&list, elem);
	if (index != -1)
		printf("index = %d, elem = %d\n", index, elem);
	else
		printf("elem = %d not in the list\n", elem);

	destroy_list(&list);

	return 0;
}

五、算法分析

1. 插入操作

int list_insert(seq_list_t* const list, const int index, const int elem) {
	if (index < 0 || index > list->length)
		return ERR_INVALID_INDEX;

	if (list->length >= list->capacity)	// 容量已满，扩容
		increase_cap(list);

	// 把第 index 索引(包括第 index 索引) 后的每个个元素往后移
	for (int i = list->length; i > index; i--)
		list->data[i] = list->data[i-1];

	list->data[index] = elem;
	list->length++;

	return ERR_SUCCESS;
}

最好情况：在表尾插入，数据元素后移语句不执行，时间复杂度为：O(1)
最坏情况：在表头插入，数据元素后移语句执行 n 次，时间复杂度为：O(n)
平均情况：在已有 n 个数据元素的顺序表中，假设插入每个位置的概率是相等的，那么插入到每个位置的概率为: 1/n。又插入到第 1 个位置数据元素，后移语句需要执行 n 次；插入到第 2 个位置数据元素，后移语句需要执行 n-1 次；…；插入到第 n 个位置数据元素，后移语句需要执行 0 次。那么，平均移动次数为 $\frac{1}{n}\sum_{i=1}^{n}(n + n-1 + ... + 0)=\frac{1}{n}\frac{n*n}{2}=\frac{n}{2}$ ，所以，插入操作的时间复杂度为：O(n)

2. 删除操作

int list_delete(seq_list_t* const list, const int index, int* elem) {
	if (index < 0 || index >= list->length) 
		return ERR_INVALID_INDEX;

	if (elem)
		*elem = list->data[index];
	// 把第 index 索引后的每一个元素向前移
	for (int i = index; i < list->length; i++)
		list->data[i] = list->data[i + 1];
	list->length--;

	return ERR_SUCCESS;
}

最好情况：删除表尾数据元素，数据元素前移语句不执行，时间复杂度为：O(1)
最坏情况：删除表头数据元素，数据元素前移语句执行 n-1 次，时间复杂度为：O(n)
平均情况：在已有 n 个数据元素的顺序表中，假设删除每个位置数据元素的概率是相等的，那么删除每个位置的元素的概率为: 1/n。又删除第 1 个位置数据元素，前移语句需要执行 n-1 次；删除第 2 个位置数据元素，前移语句需要执行 n-2 次；…；删除第 n 个位置数据元素，前移语句需要执行 0 次。那么，平均移动次数为 $\frac{1}{n}\sum_{i=1}^{n}(n-1 + ... + 0)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2}$ ，所以，删除操作的时间复杂度为：O(n)

3. 按值查找

int list_locate_elem(seq_list_t* const list, const int elem) {
	for (int i = 0; i < list->length; i++) {
		if (list->data[i] == elem)
			return i;
	}

	return -1;
}

最好情况：查找的元素在表头时，只需要比较 1 次，时间复杂度为：O(1)
最坏情况：查找的元素在表尾（或不存在）时，需要比较 n 次，时间复杂度为：O(n)
平均情况：在已有 n 个数据元素的顺序表中，假设查找的数据元素出现在顺序表中的位置的概率是相等的，那么查找元素所在的位置的概率为：1/n。又查找的元素出现在第 1 个位置，需要比较的次数为 1 次；查找的元素出现在第 2 个位置，需要比较的次数为 2 次；…；查找的元素出现在第 n 个位置，需要比较的次数为 n 次。那么平均比较次数为 $\frac{1}{n}\sum_{i=1}^{n}(1 + 2 + ... + n)=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}$ ，所以，按值查找的时间复杂度为：O(n)

4. 随机访问

int list_get_elem(seq_list_t* const list, const int index, int *elem) {
	if (!elem)
		return ERR_POINTER_NULL;

	if (index < 0 || index >= list->length)
		return ERR_INVALID_INDEX;

	*elem = list->data[index];

	return ERR_SUCCESS;
}

通过顺序表的首地址和下标，可以在 O(1) 时间内找到指定的元素。

六、总结

用顺序存储实现的线性表，即顺序表中

插入操作的时间复杂度为：O(n)
删除操作的时间复杂度为：O(n)
按值查找的时间复杂度为：O(n)
随机访问的时间复杂度为：O(1)

数据结构与算法：线性表-顺序表（顺序存储）

一、线性表的定义（逻辑结构）

二、线性表的基本操作

三、线性表的顺序表示（物理结构）

四、顺序表基本操作的实现

五、算法分析

六、总结

网站公告

今日签到

热门文章

最新发布