在了解顺序表之前我们需要先了解什么是线性表
1.线性表的定义
线性表(Linear List)：是n个具有相同特征的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串
线性表在逻辑上是线性结构，也就是说一条连续的直线。但在物理结构上并不一定是连续的
线性表在物理上存储时，通常以数组和链式结构的形式存储
2.顺序表
2.1顺序表的概念以及结构
顺序表是用一段物理地址连续的存储单元依次储存数据的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改
2.2顺序表的类型
->1.静态顺序表：使用定长数组存储元素
开辟一个固定长度的数组，向数组中存储数据
缺点：
这样开辟的顺序表空间是固定的，如果我们需要存储的空间大于这个固定空间，那我们就需要重新来开辟空间，如果我们只需要存放几个数据，那就会浪费不少空间
->2.动态顺序表：使用动态开辟的数组存储
相比于静态顺序表的优点：
更加的灵活，不会出现空间不足或者浪费大量空间的情况，所以现实中基本都是使用动态顺序表
下面我们实将现动态顺序表
3.顺序表的增删查改
->1.实现顺序表所需要用到的接口
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4
typedef int SLDATATYPE;//初始化
void INITSeqList(SL* ps);//清除顺序表
void SLDestroy(SL* ps);//增容
void IncrCapacity(SL* ps);//打印
void print(SL* ps);//尾插
void SLPushBack(SL* ps, SLDATATYPE x);//尾删
void SLPopBack(SL* ps);//头插
void SLPushFront(SL* ps, SLDATATYPE x);//头删
void SLPopFront(SL* ps);//顺序表再pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x);//顺序表删除再pos位置的元素
void SLErase(SL* ps, SLDATATYPE pos);//查找元素
int SLFind(SL* ps, SLDATATYPE x);->2.顺序表的创建
//顺序表的动态存储
typedef struct SeqList
{SLDATATYPE* a;int size; //有效数据的个数int capacity; //空间容量}SL;->3.初始化
//顺序表初始化
void INITSeqList(SL* ps)
{assert(ps);ps->a = (SLDATATYPE*)malloc(sizeof(int) * INIT_CAPACITY);if (ps->a == NULL){perror("INITSeqList::malloc");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}->4.销毁数据表
//销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}->5.在进行增删的时候检查一下空间是否为满
//检查容量是否已满
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDATATYPE* ptr = (SLDATATYPE*)realloc(ps->a, sizeof(int) * (INIT_CAPACITY * 2));if (NULL == ptr){perror("IncrCapacity::realloc");return;}ps->a = ptr;ps->capacity *= 2;}
}->6.打印
//打印内容
void print(SL* ps)
{assert(ps);for(int i = 0; i < ps->size; i++)printf("%d ", ps->a[i]);printf("\n");
}->7.头插
//头插
void SLPushFront(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);//整体向后移动for (int end = ps->size - 1; end >= 0; --end){ps->a[end + 1] = ps->a[end];}ps->a[0] = x;++ps->size;
}->8.头删
//头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}--ps->size;
}->9.尾插
//尾插
void SLPushBack(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}->10.尾删
//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->a[ps->size--] = 0;
}->11.在顺序表pos处增加元素
//在顺序表pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];}ps->a[pos] = x;++ps->size;
}->12.删除在pos位置的元素
//顺序表删除再pos位置的元素
void SLErase(SL* ps, SLDATATYPE pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);SLDATATYPE begin = pos + 1;while (begin < ps->size){ps->a[begin] = ps->a[begin - 1];++begin;}--ps->size;
}->13.顺序表查找
//查找
int SLFind(SL* ps, SLDATATYPE x)
{assert(ps);for (int i = 0; i < ps->size - 1; ++i){if (ps->a[i] == x)printf("找到了！！！%d\n", i);}return -1;
}4.源代码
->1.test.c
#include "SeqList.h"int main()
{SL a;INITSeqList(&a);test();int input = -1;//尾插SLPushBack(&a,1);print(&a);SLPushBack(&a, 2);print(&a);SLPushBack(&a, 3);print(&a);SLPushBack(&a, 4);print(&a);//尾删SLPopBack(&a);print(&a);//在pos位置插入8SLInsert(&a, 3, 8);print(&a);//查找该元素的位置，返回下标int pos = SLFind(&a, 2);return 0;
}->2.SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4
typedef int SLDATATYPE;typedef struct SeqList
{SLDATATYPE* a;int size; //有效数据的个数int capacity; //空间容量}SL;//初始化
void INITSeqList(SL* ps);//清除顺序表
void SLDestroy(SL* ps);//增容
void IncrCapacity(SL* ps);//打印
void print(SL* ps);//尾插
void SLPushBack(SL* ps, SLDATATYPE x);//尾删
void SLPopBack(SL* ps);//头插
void SLPushFront(SL* ps, SLDATATYPE x);//头删
void SLPopFront(SL* ps);//顺序表再pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x);//顺序表删除再pos位置的元素
void SLErase(SL* ps, SLDATATYPE pos);//查找元素
int SLFind(SL* ps, SLDATATYPE x);->3.SeqList.c
#include "SeqList.h"//顺序表初始化
void INITSeqList(SL* ps)
{assert(ps);ps->a = (SLDATATYPE*)malloc(sizeof(int) * INIT_CAPACITY);if (ps->a == NULL){perror("INITSeqList::malloc");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}//清除顺序表
void SLDestroy(SL* ps)
{assert(ps);assert(ps->size > 0);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}//打印内容
void print(SL* ps)
{assert(ps);assert(ps->size > 0);for(int i = 0; i < ps->size; i++)printf("%d ", ps->a[i]);printf("\n");
}//检查容量是否已满
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDATATYPE* ptr = (SLDATATYPE*)realloc(ps->a, sizeof(int) * (INIT_CAPACITY * 2));if (NULL == ptr){perror("IncrCapacity::realloc");return;}ps->a = ptr;ps->capacity *= 2;}
}//尾插
void SLPushBack(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->a[ps->size--] = 0;
}//头插
void SLPushFront(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);for (int end = ps->size - 1; end >= 0; --end){ps->a[end + 1] = ps->a[end];}ps->a[0] = x;++ps->size;
}//头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}--ps->size;
}//在顺序表pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];}ps->a[pos] = x;++ps->size;
}//删除顺序表pos处的元素
void SLErase(SL* ps, SLDATATYPE pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);SLDATATYPE begin = pos + 1;while (begin < ps->size){ps->a[begin] = ps->a[begin - 1];++begin;}--ps->size;
}//查找
int SLFind(SL* ps, SLDATATYPE x)
{assert(ps);for (int i = 0; i < ps->size - 1; ++i){if (ps->a[i] == x)printf("找到了！！！%d\n", i);}return -1;
}测试结果：
