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

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

线性表是由 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 2typedef 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");elseprintf("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);elseprint_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);elseprintf("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);elseprintf("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);elseprintf("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;
}