一.概念
顺序表是线性表的一种(其中常见的线性表：顺序表，链表，栈，队列，字符串......），顺序表的底层是数组，但顺序表能够实现数据的增删查改等操作，而数组不行。因此学习线性表能够让我们更好的管理数据。
二.分类
顺序表主要分为静态顺序表和动态顺序表，动态顺序表应用广泛，下面讲解的是动态顺序表
补充：静态顺序表主要框架
//静态顺序表 #define N 100 struct SeqList { int arr[N]; int size;//有效个数 };
三.代码实现
1.顺序表框架--结构体
typedef int SLDataType;//对类型重命名 typedef struct SeqList { SLDataType* arr; int size;//有效数据个数 int capacity;//空间大小 }SL;//对结构体类型重命名
2.顺序表初始化
void SLInit(SL* ps); void SLInit(SL* ps) { ps->arr = NULL;//空指针 ps -> size = ps -> capacity = 0; }
3.顺序表的销毁
void SLDestroy(SL* ps); void SLDestroy(SL* ps) { if (ps->arr)//判断是否为空指针 {//不为空指针，销毁 free(ps->arr); } ps->arr = NULL;//销毁后置为空指针 ps->size = ps->capacity = 0; }
4.顺序表的尾插
void SLPushBack(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity)//判断size和capacity是否相等 { //判断空间大小是否为0，创建新变量 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //申请/增容空间realloc： //一般增容增2/3倍 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//注意乘数据类型大小+强制类型转化+临时指针变量 if (tmp == NULL) { perror("realloc"); return 1; } ps->arr = tmp; ps->capacity = newCapacity;//别漏 } } void SLPushBack(SL* ps, SLDataType x) { assert(ps);//注意判断是否为空指针 //或： //if(ps==NULL) //{ // return; //} SLCheckCapacity(ps); ps->arr[ps->size++] = x; //或：ps->arr[ps->size] = x; //++ps->size; }
5.顺序表的头插
void SLPushFront(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity)//判断size和capacity是否相等 { //判断空间大小是否为0，创建新变量 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //申请/增容空间realloc： //一般增容增2/3倍 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//注意乘数据类型大小+强制类型转化+临时指针变量 if (tmp == NULL) { perror("realloc"); return 1; } ps->arr = tmp; ps->capacity = newCapacity;//别漏 } } void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); for (int i = ps->size; i>0; i--) { ps->arr[i] = ps->arr[i - 1]; } //memmove： ps->arr[0] = x; ps->size++;//别漏！！！只要插入数据，size要++ }
6.顺序表的尾删
void SLPopBack(SL* ps); void SLPopBack(SL* ps) { assert(ps); assert(ps->size);//顺序表不为空 //ps->arr[ps->size-1]=-1; --ps->size; }
7.顺序表的头删
void SLPopFront(SL* ps); void SLPopFront(SL* ps) { assert(ps); assert(ps->size); for (int i = 0; i < ps->size-1; i++) { ps->arr[i] = ps->arr[i + 1];//最后一次：ps->arr[i-2]=ps->arr[i-1] } ps->size--; }
8.在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x); void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps);//判断空间够不够 //让pos及以后的数据整体往后挪动一位 for (int i = ps->size; i> pos; i--) { ps->arr[i] = ps->arr[i - 1];//ps->arr[pos+1]=ps->arr[pos]; } ps->arr[pos] = x; ps->size++; }
9.删除指定位置的数据
void SLErase(SL* ps, int pos); void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);//注意不能等于 for (int i = pos; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1];//ps->arr[ps->size-2]=ps->arr[ps->size-1] } ps->size--; }
10.顺序表的查找
int SLFind(SL* ps, SLDataType x); int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++)//通过下标遍历每个元素 { if (ps->arr[i] == x)//判断二者是否相等 { return i;//找到了，返回下标 } } return -1;//没找到，返回-1 }
整体代码
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h"//注意头文件 /* struct SeqList { int* arr; int size；//有效数据个数 int capacity;//空间大小 }; */ #include<stdio.h> SL sl;//sl无初始化，因此传址调用 void SLTest01() { //顺序表的初始化 SLInit(&sl); //顺序表的增删查改等操作 //尾插： SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPrint(sl);//打印1 2 3 4 5 //头插： SLPushFront(&sl, 0); SLPrint(sl);//打印0 1 2 3 4 5 //尾删： SLPopBack(&sl); SLPrint(sl);//打印1 2 3 4 //头删： SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPrint(sl);//打印2 3 4 //顺序表的销毁 SLDestroy(&sl); } SLTest02() { //顺序表的初始化 SLInit(&sl); SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPrint(sl);//打印1 2 3 4 5 SLInsert(&sl, 1, 100); SLPrint(sl);//打印1 100 2 3 4 5 SLInsert(&sl, sl.size, 200); SLPrint(sl);//打印1 100 2 3 4 5 200 SLInsert(&sl, 0, 0); SLPrint(sl);//打印0 1 100 2 3 4 5 200 SLErase(&sl, 1); SLPrint(sl);//打印0 100 2 3 4 5 200 printf("%d\n",SLFind(&sl, 100)); } int main() { //SLTest01(); SLTest02(); return 0; }SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h"//注意头文件 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity)//判断size和capacity是否相等 { //判断空间大小是否为0，创建新变量 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //申请/增容空间realloc： //一般增容增2/3倍 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//注意乘数据类型大小+强制类型转化+临时指针变量 if (tmp == NULL) { perror("realloc"); return 1; } ps->arr = tmp; ps->capacity = newCapacity;//别漏 } } void SLInit(SL* ps) { ps->arr = NULL;//空指针 ps -> size = ps -> capacity = 0; } void SLDestroy(SL* ps) { if (ps->arr)//判断是否为空指针 {//不为空指针，销毁 free(ps->arr); } ps->arr = NULL;//销毁后置为空指针 ps->size = ps->capacity = 0; } void SLPushBack(SL* ps, SLDataType x) { assert(ps);//注意判断是否为空指针 //或： //if(ps==NULL) //{ // return; //} SLCheckCapacity(ps); ps->arr[ps->size++] = x; //或：ps->arr[ps->size] = x; //++ps->size; } void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); for (int i = ps->size; i>0; i--) { ps->arr[i] = ps->arr[i - 1]; } //memmove： ps->arr[0] = x; ps->size++;//别漏！！！只要插入数据，size要++ } void SLPrint(SL s) { for (int i = 0; i < s.size; i++) { printf("%d ", s.arr[i]); } printf("\n"); } void SLPopBack(SL* ps) { assert(ps); assert(ps->size);//顺序表不为空 //ps->arr[ps->size-1]=-1; --ps->size; } void SLPopFront(SL* ps) { assert(ps); assert(ps->size); for (int i = 0; i < ps->size-1; i++) { ps->arr[i] = ps->arr[i + 1];//最后一次：ps->arr[i-2]=ps->arr[i-1] } ps->size--; } void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps);//判断空间够不够 //让pos及以后的数据整体往后挪动一位 for (int i = ps->size; i> pos; i--) { ps->arr[i] = ps->arr[i - 1];//ps->arr[pos+1]=ps->arr[pos]; } ps->arr[pos] = x; ps->size++; } void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);//注意不能等于 for (int i = pos; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1];//ps->arr[ps->size-2]=ps->arr[ps->size-1] } ps->size--; } int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++)//通过下标遍历每个元素 { if (ps->arr[i] == x)//判断二者是否相等 { return i;//找到了，返回下标 } } return -1;//没找到，返回-1 } //注意不要漏assert // realloc常见易错点 // ps->arr,ps->capacity注意要赋值 //插入或删除数据后size要变化SeqList.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //定义顺序表的结构 //静态顺序表 //#define N 100 //struct SeqList //{ // int arr[N]; // int size;//有效个数 //}; //动态顺序表 typedef int SLDataType;//对类型重命名 typedef struct SeqList { SLDataType* arr; int size;//有效数据个数 int capacity;//空间大小 }SL;//对结构体类型重命名 //顺序表初始化 void SLInit(SL* ps); //顺序表的销毁 void SLDestroy(SL* ps); //尾部插入 void SLPushBack(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 //头部插入 void SLPushFront(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 //尾部删除 void SLPopBack(SL* ps); //头部删除 void SLPopFront(SL* ps); //顺序表的打印 void SLPrint(SL s);//打印不传指针 //在指定位置插入数据 void SLInsert(SL* ps, int pos, SLDataType x); //删除指定位置的数据 void SLErase(SL* ps, int pos); //顺序表的查找 int SLFind(SL* ps, SLDataType x);
文章到这里就结束了，创造不易，如果喜欢的话点个关注，点个赞，谢谢大家！
