1. 什么是顺序表
在学习顺序表之前我们首先要了解线性表：
1.1 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
1.2 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。
顺序表一般可以分为静态顺序表和动态顺序表。
1.2.1 静态顺序表
静态顺序表采用定长数组存储元素。
也就是说顺序表能够存储的数据一开始就固定好了，即存储元素的最大个数为固定值。
下面为用结构体定义一个静态顺序表的代码：
//静态顺序表 #define N 1000; //N表示顺序表（数组）的长度，用define定义N，便于修改数据； typedef int SLDataType; //由于顺序表存储的数据并不一定是整型，所以用typedef定义SLDataType，便于修改数据类型； struct SeqList { SLDataType a[N]; //顺序表的长度； int size; //一个顺序表不一定会放满，用size表示顺序表已存放数据的个数； };
1.2.2 动态顺序表
动态顺序表使用动态开辟的数组存储。
看一下上面的静态顺序表不难看出，有时开辟的数组过大，会存不满，导致了空间浪费；也有时开辟的数组过小，会不够存。为避免这种情况，我们可以采用动态开辟的方法定义顺序表。
代码如下：
//动态顺序表 静态顺序表会出现空间不够或空间浪费的情况，所以用动态顺序表方便扩容 typedef int SLDataType; typedef struct SeqList { SLDataType* a; //指向动态开辟的数组 int size; //已存储的数据个数 int capacity; //数组容量大小，当size≥capacity时就动态开辟空间 }SL;
知道了这些概念我们再继续本篇博客的重头戏。
顺序表的功能无非就是增删查改，再加上上面的动态顺序表如何开辟和销毁
所以实现这些功能，无非就是实现一个个函数的过程。
2. 顺序表的实现
2.1 初始化函数（SLInit）的实现
void SLInit(SL* ps) { ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); if (ps->a == NULL) { perror("malloc failed");//如果扩容失败，说明原因 exit(-1); } ps->size = 0;//当size≥capacity时就动态开辟空间 ps->capacity = 4;//初始化数组容量为4 }
2.2 销毁函数（SLDestroy）的实现
void SLDestroy(SL* ps) { free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; }
2.3 打印函数（SLPrint）的实现
void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
2.4 扩容函数(SLCheckCapacity)的实现
void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { SLDataType* tmp = realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType))); if (tmp == NULL) { perror("realloc failed"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } }
2.5 插入函数
2.5.1 尾插函数(SLPushBack)的实现
void SLPushBack(SL* ps, SLDataType x) { SLCheckCapacity(ps); //先检查扩容 ps->a[ps->size] = x; ps->size++; }
2.5.2 头插函数(SLPushFront)的实现
void SLPushFront(SL* ps, SLDataType x) { SLCheckCapacity(ps); int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[0] = x; ps->size++; }
2.5.3 在pos位置插入数值x函数(SLInsert)的定义
void SLInsert(SL* ps, int pos, SLDataType x) { assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; }
2.6 删除函数
2.6.1 尾删函数(SLPopBack)的实现
void SLPopBack(SL* ps) { assert(ps->size > 0); ps->size--; }
2.6.2 头删函数(SLPopFront)的实现
void SLPopFront(SL* ps) { assert(ps->size > 0); int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; }
2.6.3 删除pos位置数值函数（SLErase）的实现
void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; }
2.7 查找函数
2.7.1 查找函数1（SLFind1）的实现
int SLFind1(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { printf("数值%d的下标为%d\n", x, i); return 0; } } printf("发生错误\n"); return -1; }
2.7.2 查找函数2（SLFind2）的实现
int SLFind2(SL* ps, int x) { assert(ps); for (int i = 0; i <= ps->size; i++) { if (ps->a[i] == ps->a[x]) { printf("下标%d的值为%d\n", x, ps->a[i]); return 0; } } printf("发生错误\n"); return -1; }
2.8 修改函数
修改函数（SLMofidy）的实现
void SLModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
3. 函数验证（使用）
3.1 尾插4 5 6
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); return 0; }
3.2 头插3 2 1
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); return 0; }
3.3 在下标2位置插入22
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); return 0; }
3.4 删除末尾数字
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); //删除末尾数字 SLPopBack(&sl); SLPrint(&sl); return 0; }
3.5 删除开头数字
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); //删除末尾数字 SLPopBack(&sl); SLPrint(&sl); //删除开头数字 SLPopFront(&sl); SLPrint(&sl); return 0; }
3.6 删除下标2位置数字
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); //删除末尾数字 SLPopBack(&sl); SLPrint(&sl); //删除开头数字 SLPopFront(&sl); SLPrint(&sl); //删除下标2位置数字 SLErase(&sl,2); SLPrint(&sl); return 0; }
3.7 查找数值4的下标
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); //删除末尾数字 SLPopBack(&sl); SLPrint(&sl); //删除开头数字 SLPopFront(&sl); SLPrint(&sl); //删除下标2位置数字 SLErase(&sl,2); SLPrint(&sl); //查找数值4的下标 SLFind1(&sl, 4); SLPrint(&sl); return 0; }
3.8 查找下标2的数值
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); //删除末尾数字 SLPopBack(&sl); SLPrint(&sl); //删除开头数字 SLPopFront(&sl); SLPrint(&sl); //删除下标2位置数字 SLErase(&sl,2); SLPrint(&sl); //查找数值4的下标 SLFind1(&sl, 4); SLPrint(&sl); //查找下标2的数值 SLFind2(&sl, 2); SLPrint(&sl); return 0; }
3.9 修改下标1的数值为33
int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); //删除末尾数字 SLPopBack(&sl); SLPrint(&sl); //删除开头数字 SLPopFront(&sl); SLPrint(&sl); //删除下标2位置数字 SLErase(&sl,2); SLPrint(&sl); //查找数值4的下标 SLFind1(&sl, 4); SLPrint(&sl); //查找下标2的数值 SLFind2(&sl, 2); SLPrint(&sl); //修改下标1的数值为33 SLModify(&sl, 1, 33); SLPrint(&sl); return 0; }
4.源代码
4.1 SeqList.h源代码
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> //用结构体定义一个顺序表 静态顺序表 // //#define N 1000; //N表示顺序表（数组）的长度，用define定义N，便于修改数据； // //typedef int SLDataType; //由于顺序表存储的数据并不一定是整型，所以用typedef定义SLDataType，便于修改数据类型； //struct SeqList //{ // SLDataType a[N]; //顺序表的长度； // int size; //一个顺序表不一定会放满，用size表示顺序表已存放数据的个数； //}; //动态顺序表 静态顺序表会出现空间不够或空间浪费的情况，所以用动态顺序表方便扩容 typedef int SLDataType; typedef struct SeqList { SLDataType* a; //指向动态开辟的数组 int size; //已存储的数据个数 int capacity; //数组容量大小，当size≥capacity时就动态开辟空间 }SL; void SLInit(SL* ps); //初始化函数的声明 void SLDestroy(SL* ps); //销毁函数的声明 void SLPrint(SL* ps); //打印函数的声明 void SLCheckCapacity(SL* ps); //扩容函数的声明 void SLPushBack(SL* ps, SLDataType x); //尾插函数的声明 void SLPushFront(SL* ps, SLDataType x); //头插函数的声明 void SLPopBack(SL* ps); //尾删函数的声明 void SLPopFront(SL* ps); //头删函数的声明 void SLInsert(SL* ps, int pos, SLDataType x); //在pos位置插入数值x函数的声明 void SLErase(SL* ps, int pos); //删除pos位置的数值函数的声明 int SLFind1(SL* ps, SLDataType x); //查找函数1的声明（知数值找下标） int SLFind2(SL* ps, int x); //查找函数2的声明（知下标找数值） void SLModify(SL* ps, int pos, SLDataType x); //修改函数的声明
4.2 SeqList.c源代码
#include "SeqList.h" //初始化函数（SLInit）的实现 void SLInit(SL* ps) { ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); if (ps->a == NULL) { perror("malloc failed");//如果扩容失败，说明原因 exit(-1); } ps->size = 0;//当size≥capacity时就动态开辟空间 ps->capacity = 4;//初始化数组容量为4 } //销毁函数（SLDestroy）的实现 void SLDestroy(SL* ps) { free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } //打印函数（SLPrint）的实现 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } //扩容函数(SLCheckCapacity)的实现 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { SLDataType* tmp = realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType))); if (tmp == NULL) { perror("realloc failed"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } } //尾插函数(SLPushBack)的实现 void SLPushBack(SL* ps, SLDataType x) { SLCheckCapacity(ps); //先检查扩容 ps->a[ps->size] = x; ps->size++; } //头插函数(SLPushFront)的实现 void SLPushFront(SL* ps, SLDataType x) { SLCheckCapacity(ps); int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[0] = x; ps->size++; } //尾删函数(SLPopBack)的实现 void SLPopBack(SL* ps) { assert(ps->size > 0); ps->size--; } //头删函数(SLPopFront)的实现 void SLPopFront(SL* ps) { assert(ps->size > 0); int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; } //在pos位置插入数值x函数(SLInsert)的定义 void SLInsert(SL* ps, int pos, SLDataType x) { assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; } //删除pos位置数值函数（SLErase）的定义 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; } //查找函数1（SLFind1）的定义 int SLFind1(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { printf("数值%d的下标为%d\n", x, i); return 0; } } printf("发生错误\n"); return -1; } //查找函数2（SLFind2）的定义 int SLFind2(SL* ps, int x) { assert(ps); for (int i = 0; i <= ps->size; i++) { if (ps->a[i] == ps->a[x]) { printf("下标%d的值为%d\n", x, ps->a[i]); return 0; } } printf("发生错误\n"); return -1; } //修改函数（SLMofidy）的定义 void SLModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
4.3 test.c源代码
#include "SeqList.h" int main() { SL sl; SLInit(&sl); //尾插4 5 6 SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPrint(&sl); //头插3 2 1 SLPushFront(&sl, 3); SLPushFront(&sl, 2); SLPushFront(&sl, 1); SLPrint(&sl); //下标2位置插入22 SLInsert(&sl,2,22); SLPrint(&sl); //删除末尾数字 SLPopBack(&sl); SLPrint(&sl); //删除开头数字 SLPopFront(&sl); SLPrint(&sl); //删除下标2位置数字 SLErase(&sl,2); SLPrint(&sl); //查找数值4的下标 SLFind1(&sl, 4); SLPrint(&sl); //查找下标2的数值 SLFind2(&sl, 2); SLPrint(&sl); //修改下标1的数值为33 SLModify(&sl, 1, 33); SLPrint(&sl); return 0; }
