1. 线性表
- 是n个具有相同特性的数据元素的有限序列
- 当n=0时称为空表
- 常见的线性表有：顺序表、链表、栈、队列、字符串等
2. 顺序表（Sequence List）
- 本质上就是数组（静态/动态）
- 数据必须从头连续存储，不能跳跃间隔
2.1 静态顺序表
- 即直接在结构体中确定存储数据的数组的大小，之后不能对其进行改变
- 特点：MAX给小了不够用，MAX大了浪费空间
- 定义：
#define MAX 1000 typedef int SLDataType; //定义顺序表存储的元素类型 typedef struct SeqList { SLDataType[MAX]; int size; //数组中存储了多少个数据 }SL;
2.2 动态顺序表
- 定义：
- 利用动态管理，对内存进行动态开辟，方便后续调整数组大小
#define MAX 5 typedef int SLDataType; //定义顺序表存储的元素类型 typedef struct SeqList { SLDataType* data; int size; //用来表示当前存储了多少个数据 int capacity; //用来表示最大容量 }SeqList;
3. 基本操作
注：以下都以动态顺序表为例：
3.1 顺序表的初始化
void SeqListInit(SeqList* ps);
要使用顺序表，我们首先就先要对其初始化：
- 确定确定初始最大容量
- 动态开辟内存
- 将
size置零
void SeqListInit(SeqList* ps) //初始化 { assert(ps); //保证指针有效 ps->capacity = MAX; //确定初始最大容量 ps->data = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity); //动态开辟内存 if (NULL == ps->data) //检验 { perror("malloc"); exit(-1); } ps->size = 0; //将`size`置零 }
3.2 顺序表的销毁
void SeqListDestory(SeqList* ps);
顺序表使用完后，就要对其进行销毁：
- 释放动态内存
- 将
size，和最大容量capacity置零
void SeqListDestory(SeqList* ps) //销毁 { assert(ps);//保证指针有效 free(ps->data); ps->size = 0; ps->capacity = 0; }
3.3 尾插SeqListPushBack()
void SeqListPushBack(SeqList* ps, SLDataType val);
在插入之前，我们必须要对存储数据的数组进行检查，如果size已经等于最大容量capacity，那么我们首先就要对其进行增容
3.3.1 判满SeqListFull()
bool SeqListFull(const SeqList* ps) //判满 { assert(ps); return ps->capacity == ps->size; }
3.3.2 增容SeqListIncreaseCapacity()
void SeqListIncreaseCapacity(SeqList* ps) //增容 { assert(ps); ps->capacity *= 2; //每次将容量扩大为原来的两倍 SLDataType* temp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity); if (NULL == temp) { perror("realloc"); exit(-1); } ps->data = temp; }
3.3.3 SeqListPushBack()
尾插的逻辑十分简单，检查完容量后，直接将新数据插入到最后即可：
提醒：不要忘了将size加一
void SeqListPushBack(SeqList* ps, SLDataType val) //尾插 { assert(ps); //检验指针有效性 //检查容量 if (SeqListFull(ps)) SeqListIncreaseCapacity(ps); //实现尾插 ps->data[ps->size++] = val; }
3.4 尾删SeqListPopBack()
void SeqListPopBack(SeqList* ps);
注意，在删除数据之前，必须保证顺序表中存放了数据，即size > 0，因此首先要进行判空操作
3.4.1 判空SeqListEmpty()
bool SeqListEmpty(const SeqList* ps) //判空 { assert(ps); return ps->size == 0; }
3.4.2 SeqListPopBack()
尾删操作也十分简单，如果顺序表中存储了数据，那么直接将size减一就可以了，因为这样就访问不到最后一个数据，也就可以看作是删除了。
void SeqListPopBack(SeqList* ps) //尾删 { assert(ps); //检验指针有效性 assert(!SeqListEmpty(ps)); //顺序表不能为空 ps->size--; //尾删 }
3.5 头插SeqListPushFront()
void SeqListPushFront(SeqList* ps, SLDataType val);
和尾插一样，同样首先要对容量进行检查。
要将新数据插入到数组的第一个位置，那么我们就先要将原来的数据全部往后移动一位。
而为了原有数据不被覆盖，必须从后往前挪动数据（如果有疑惑，可以通过画图来理解）
void SeqListPushFront(SeqList* ps, SLDataType val) //头插 { assert(ps); //检验指针有效性 //检查容量 if (SeqListFull(ps)) SeqListIncreaseCapacity(ps); //挪动数据 for (int i = ps->size - 1; i >= 0; i--) ps->data[i + 1] = ps->data[i]; //头插 ps->data[0] = val; ps->size++; }
3.6 头删SeqListPopFront()
void SeqListPopFront(SeqList* ps)
和尾删一样，也先要对顺序表判空，如果为空，就不能进行删除
要实现头删，我们就需要将出第一个元素之外的所有元素向前挪动一位，这样，第一个元素就会被覆盖，从而也就实现了头删
而为了确保原有数据不被覆盖，我们要从前往后挪动数据（有疑惑的可以画图理解）
提醒：删完之后，记得将size减一
void SeqListPopFront(SeqList* ps) //头删 { assert(ps); //检验指针有效性 assert(!SeqListEmpty(ps)); //判空 //挪动数据，实现头删 for (int i = 1; i < ps->size; i++) ps->data[i - 1] = ps->data[i]; ps->size--; }
3.7 在下标pos处插入SeqListInsert()
void SeqListInsert(SeqList* ps, int pos, SLDataType val);
和头插的逻辑类似，要在下标为pos处插入新元素，我们就要将pos和pos之后的元素都向后挪动一位
注意1：同样先要进行容量检查，要注意控制循环边界，防止越界
注意2：由于顺序表要求必须对数据进行连续的存储，因此我们对下标pos也有要求
void SeqListInsert(SeqList* ps, int pos, SLDataType val) //在pos处插入 { assert(ps); //检验指针有效性 assert(pos >= 0 && pos <= ps->size); //检验pos的有效性 //检查容量 if (SeqListFull(ps)) SeqListIncreaseCapacity(ps); //挪动数据 for (int i = ps->size - 1; i >= pos; i--) ps->data[i + 1] = ps->data[i]; //实现插入 ps->data[pos] = val; ps->size++; }
3.8 删除下标为pos的数据SeqListErase(SeqList* ps, int pos)
void SeqListErase(SeqList* ps, int pos);
和头删的逻辑类似，我们只需要将pos后面的所有数据向前挪动一位就可以实现将pos位置的数据删除了
注1：删除之前要判空
注2：要记得检查pos的有效性，防止越界访问
void SeqListErase(SeqList* ps, int pos) //删除pos处元素 { assert(ps); //检验指针有效性 assert(!SeqListEmpty(ps)); //判空 assert(pos < ps->size); //检验pos有效性 //挪动数据实现删除 for (int i = pos + 1; i < ps->size; i++) ps->data[i - 1] = ps->data[i]; ps->size--; }
3.9 查找值为val的数据SeqListFind()
int SeqListFind(const SeqList* ps, SLDataType val); //找到后返回下标，否则返回-1
这个操作逻辑十分简单，遍历一遍顺序表，如果找到了，就返回这个下标，否则就返回-1
int SeqListFind(const SeqList* ps, SLDataType val) //查找值为val的数据 { assert(ps);//检验指针有效性 for (int i = 0; i < ps->size; i++) { if (ps->data[i] == val) { return i; } } return -1; }
3.10 修改下标为pos处的数据
这个操作也十分简单，直接访问下标为pos处的元素就可以了。只是同样需要注意对pos的有效性进行检查
void SeqListModify(SeqList* ps, int pos, int val) //将下标为pos处的数据修改为val { assert(ps); assert(pos >= 0 && pos < ps->size); ps->data[pos] = val; }
4. 顺序表的优缺点
4.1 优点
- 实现尾删和尾插的效率很高
- 随机访问：由于顺序表使用数组来表示元素，因此可以通过索引快速地随机访问元素。这种特性使得顺序表在查找特定元素时非常高效。
- 内存连续：顺序表中的元素在内存中是连续存储的，这有助于提高缓存的利用率，从而提高访问效率。
- 直接存取：相比于其他数据结构，如链表，顺序表的存取操作较为简单，不需要像链表那样处理节点指针，使得存取操作速度更快。
- 适合小规模数据：对于元素数量较少的情况，顺序表通常比较适用，因为它的内存开销相对较小。
4.2 缺点
- 插入和删除低效：当需要在顺序表中插入或删除元素时，需要将后续元素移动，以保持连续存储的特性。这样的操作导致插入和删除操作的时间复杂度为O(n)，其中n是元素数量。对于频繁的插入和删除操作，顺序表的性能较差。
- 固定大小：顺序表在创建时需要预先分配一定的存储空间，因此其大小是固定的。如果需要存储的元素数量超过了初始大小，就需要进行扩容操作，这可能导致额外的内存分配和数据搬移开销。
- 内存浪费：如果实际存储的元素数量远小于顺序表的最大容量，会造成内存空间的浪费。
- 不易动态调整：由于顺序表的大小固定且内存连续，动态调整其大小较为复杂。在某些场景下，需要频繁调整大小的数据结构时，顺序表可能不是最佳选择。
5. 参考代码
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> #define MAX 5 typedef int SLDataType; typedef struct SeqList { SLDataType* data; int size; int capacity; }SeqList; void SeqListInit(SeqList* ps); //初始化 void SeqListDestory(SeqList* ps); //销毁 void SeqListPrint(const SeqList* ps); //打印 bool SeqListEmpty(const SeqList* ps); //判空 bool SeqListFull(const SeqList* ps); //判满 void SeqListIncreaseCapacity(SeqList* ps); //增容 void SeqListPushBack(SeqList* ps, SLDataType val); //尾插 void SeqListPopBack(SeqList* ps); //尾删 void SeqListPushFront(SeqList* ps, SLDataType val); //头插 void SeqListPopFront(SeqList* ps); //头删 void SeqListInsert(SeqList* ps, int pos, SLDataType val); //在pos处插入 void SeqListErase(SeqList* ps, int pos); //删除pos处元素 int SeqListFind(const SeqList* ps, SLDataType val); //查找值为val的数据 void SeqListModify(SeqList* ps, int pos, int val); //将下标为pos处的数据修改为val void SeqListInit(SeqList* ps) //初始化 { assert(ps); ps->capacity = MAX; ps->data = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity); if (NULL == ps->data) { perror("malloc"); exit(-1); } ps->size = 0; } void SeqListDestory(SeqList* ps) //销毁 { assert(ps); free(ps->data); ps->size = 0; ps->capacity = 0; } void SeqListPrint(const SeqList* ps) //打印 { assert(ps); for (int i = 0; i < ps->size; i++) printf("%d ", ps->data[i]); printf("\n"); } bool SeqListEmpty(const SeqList* ps) //判空 { assert(ps); return ps->size == 0; } bool SeqListFull(const SeqList* ps) //判满 { assert(ps); return ps->capacity == ps->size; } void SeqListIncreaseCapacity(SeqList* ps) //增容 { assert(ps); ps->capacity *= 2; SLDataType* temp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity); if (NULL == temp) { perror("realloc"); exit(-1); } ps->data = temp; } void SeqListPushBack(SeqList* ps, SLDataType val) //尾插 { assert(ps); if (SeqListFull(ps)) SeqListIncreaseCapacity(ps); ps->data[ps->size++] = val; } void SeqListPopBack(SeqList* ps) //尾删 { assert(ps); assert(!SeqListEmpty(ps)); ps->size--; } void SeqListPushFront(SeqList* ps, SLDataType val) //头插 { assert(ps); if (SeqListFull(ps)) SeqListIncreaseCapacity(ps); for (int i = ps->size - 1; i >= 0; i--) ps->data[i + 1] = ps->data[i]; ps->data[0] = val; ps->size++; } void SeqListPopFront(SeqList* ps) //头删 { assert(ps); assert(!SeqListEmpty(ps)); for (int i = 1; i < ps->size; i++) ps->data[i - 1] = ps->data[i]; ps->size--; } void SeqListInsert(SeqList* ps, int pos, SLDataType val) //在pos处插入 { assert(ps); assert(pos >= 0 && pos <= ps->size); if (SeqListFull(ps)) SeqListIncreaseCapacity(ps); for (int i = ps->size - 1; i >= pos; i--) ps->data[i + 1] = ps->data[i]; ps->data[pos] = val; ps->size++; } void SeqListErase(SeqList* ps, int pos) //删除pos处元素 { assert(ps); assert(!SeqListEmpty(ps)); assert(pos < ps->size); for (int i = pos + 1; i < ps->size; i++) ps->data[i - 1] = ps->data[i]; ps->size--; } int SeqListFind(const SeqList* ps, SLDataType val) //查找值为val的数据 { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->data[i] == val) { return i; } } return -1; } void SeqListModify(SeqList* ps, int pos, int val) //将下标为pos处的数据修改为val { assert(ps); assert(pos >= 0 && pos < ps->size); ps->data[pos] = val; } int main() { SeqList* sl; sl = (SeqList*)malloc(sizeof(SeqList)); if (NULL == sl) { perror("malloc"); return -1; } SeqListInit(sl); //…………………… SeqListDestory(sl); return 0; }
