数据结构与算法-顺序表

数据结构

顺序表

基本概念

• 顺序表：顺序存储的线性表
• 链式表：链式存储的线性表，简称链表

顺序存储就是将数据存储到一片连续的内存中，在C语言环境下，可以是具名的栈数组，也可以是匿名的堆数组。

存储方式不仅仅只是提供数据的存储空间，而是必须要体现数据之间的逻辑关系。当采用顺序存储的方式来存放数据时，唯一能用来表达数据间本身的逻辑关系的就是存储位置。

基本操作

顺序表设计

一般而言，为了方便操作顺序表，需要一个专门管理顺序表的“管理结构体”，结构体中一般包含：

1. 顺序表总容量
2. 顺序表当前最末元素下标位置
3. 顺序表指针

下面是管理结构体的代码：

typedef int DATA;typedef struct
{int capacity;  //顺序表容量int last;      //最末元素下标DATA *data;     //顺序表数据
} SequenceList;

其中，DATA是定义的数据类型，可以更改为其他数据类型。

初始化顺序表

所谓初始化就是建立一个不包含任何元素的顺序表，设置好管理结构体中的表的总容量、末元素下标，申请好顺序表内存空间等系列准备工作。

/*** 初始化顺序表* @param cap 初始化容量*/
SequenceList *init_seqlist(int cap)
{SequenceList *list = (SequenceList *)malloc(sizeof(SequenceList));if(list != NULL){//给顺序表中的元素分配存储空间（顺序表就是数组，数据是存储在元素中的）list->data = malloc(sizeof(int) * cap);if (list->data == NULL){free(list);return NULL;}//初始化list->capacity = cap;list->last = -1;}return list;
}

增删遍历节点

在顺序表中增加一个数据，可以有多种方式，比如在原数组的末尾增加，或者在原数组的头部增加，或者在数组中间任意一个位置增加，根据实际需要来定。

/*** 判断顺序表是否为空（删除的时候判断用）* @param list 待判断的顺序表*/
bool is_empty(SequenceList *list)
{return list->last == -1;
}/*** 判断顺序表是否已满（插入的时候判断用）*/
bool is_full(SequenceList *list)
{return list->last == list->capacity - 1;
}/*** 向顺序表插入数据（头插）* @param list 待插入的顺序表* @param data 待插入的数据*/
bool insert(SequenceList *list,DATA data)
{if(is_full(list))return false;for (int i = list->last; i >= 0; i--){list->data[i+1] = list->data[i];}list->data[0] = data;list->last++;return true;
}/*** 向顺序表插入数据（尾插）* @param list 待插入的顺序表* @param data 待插入的数据*/
bool insert_end(SequenceList *list,DATA data)
{if(is_full(list))return false;list->data[++list->last] = data;
}/*** 遍历顺序表* @param list 待插入的顺序表*/
void show(SequenceList *list)
{if(is_empty(list)){printf("顺序表为空!\n");return;}printf("顺序表中的元素：");for(int i = 0; i <= list->last; i++){printf("%d ", list->data[i]);}printf("\n");
}/*** 删除顺序表数据* @param list 待删除的顺序表* @param data 待删除的数据*/
bool remove_node(SequenceList *list,DATA data)
{if(is_empty(list))return false;for(int i = 0; i <= list->last; i++){if(memcmp(&(list->data[i]),&data,sizeof(DATA)) == 0){for (int j = i; j < list->last; j++){list->data[j] = list->data[j+1];}list->last--;return true;}}return false;
}

销毁顺序表

一个顺序表最后不再需要，应当要释放其所占用的内存空间，这被称为顺序表的销毁。

/*** 释放内存* @param list 待释放的顺序表*/
void destory(SequenceList *list)
{if (list == NULL){return;}free(list->data);free(list);list = NULL;
}