🔥个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题
🍉学习方向：C/C++方向
⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平
前言：本篇文章，我们继续介绍顺序表和链表相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们继续学习第二部分中的顺序表和链表部分内容啦。
目录
正文
二、顺序表（续）
（五）详解顺序表书写（续）
2、动态顺序表
上文给大家详解了尾插，上文受篇幅限制，剩余内容本文将继续介绍。
(2)头插
（1）SeqList.h
#ifdef __SEQLIST__H__
#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
//增强程序可维护性
typedef int SLTDataType;
typedef struct SeqList
{
SQDataType*a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListPushBack(SL*ps,SLTDataType x);//尾插
void SeqListPushFront(SL*ps,SLTDataType x);//头插
void SeqListPopBack(SL*ps);//尾删
void SeqListPopFront(SL*ps);//头删
#endif （2）SeqList.c
#include"SeqList.h"
void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListCheckCapacity(SL*ps)
{
//满了就要扩容
if(ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
void SeqListPushBack(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
void SeqListPushFront(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
//1、初始条件
//2、结束条件
//3、迭代过程
int end = ps->size - 1;
while(end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopBack(SL*ps);
void SeqListPopFront(SL*ps);
//测试能不能打印出来
void SeqListPrint(SL*ps)
{
for(int i = 0;i < ps->size;++i)
{
printf("%d ",ps->a[i]);
}
printf("\n");
}（3）test.c
#include"SeqList.h"
void TestSeqList2()
{
SL sl;
SeqListInit(&sl);
SeqListPushFront(&sl,1);
SeqListPushFront(&sl,2);
SeqListPushFront(&sl,3);
SeqListPushFront(&sl,4);
SeqListPushFront(&sl,5);
SeqListPushFront(&sl,6);
……
SeqListPrint(&sl);
}
int main()
{
TestSeqList2();
return 0;
}(3)尾删
（1）SeqList.h
#ifdef __SEQLIST__H__
#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
//增强程序可维护性
typedef int SQDataType;
typedef struct SeqList
{
SQDataType*a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListPushBack(SL*ps,SQDataType x);//尾插
void SeqListPushFront(SL*ps,SQDataType x);//头插
void SeqListPopBack(SL*ps);//尾删
void SeqListPopFront(SL*ps);//头删
#endif （2）SeqList.c
#include"SeqList.h"
void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListCheckCapacity(SL*ps)
{
//满了就要扩容
if(ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
void SeqListPushBack(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
void SeqListPushFront(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
//1、初始条件
//2、结束条件
//3、迭代过程
int end = ps->size - 1;
while(end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopBack(SL*ps)
{
//粗暴一点直接assert
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;//这句代码加上也可以，没有也不影响
ps->size--;
}
void SeqListPopFront(SL*ps);
//测试能不能打印出来
void SeqListPrint(SL*ps)
{
for(int i = 0;i < ps->size;++i)
{
printf("%d ",ps->a[i]);
}
printf("\n");
}（3）test.c
#include"SeqList.h"
void TestSeqList3()
{
SL sl;
SeqListInit(&sl);
SeqListPopBack(&sl,1);
SeqListPopBack(&sl,2);
SeqListPopBack(&sl,3);
SeqListPopBack(&sl,4);
SeqListPopBack(&sl,5);
SeqListPopBack(&sl,6);
SeqListPopBack(&sl);
SeqListPrint(&sl);
}
int main()
{
TestSeqList3();
return 0;
}(4)头删
（1）SeqList.h
#ifdef __SEQLIST__H__
#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<assert.h>
//增强程序可维护性
typedef int SLTDataType;
typedef struct SeqList
{
SQDataType*a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListPushBack(SL*ps,SLTDataType x);//尾插
void SeqListPushFront(SL*ps,SLTDataType x);//头插
void SeqListPopBack(SL*ps);//尾删
void SeqListPopFront(SL*ps);//头删
#endif （2）SeqList.c
#include"SeqList.h"
void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListCheckCapacity(SL*ps)
{
//满了就要扩容
if(ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
//尾插
void SeqListPushBack(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//头插
void SeqListPushFront(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
//1、初始条件
//2、结束条件
//3、迭代过程
int end = ps->size - 1;
while(end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
//尾删
void SeqListPopBack(SL*ps)
{
//粗暴一点直接assert
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;//这句代码加上也可以，没有也不影响
ps->size--;
}
//头删
void SeqListPopFront(SL*ps)
{
assert(ps->size > 0);
int start = 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//测试能不能打印出来
void SeqListPrint(SL*ps)
{
for(int i = 0;i < ps->size;++i)
{
printf("%d ",ps->a[i]);
}
printf("\n");
}（3）test.c
#include"SeqList.h"
void TestSeqList4()
{
SL sl;
SeqListInit(&sl);
SeqListPushFront(&sl,1);
SeqListPushFront(&sl,2);
SeqListPushFront(&sl,3);
SeqListPushFront(&sl,4);
SeqListPushFront(&sl,5);
SeqListPushFront(&sl,6);
SeqListPrint(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPrint(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl);
}
int main()
{
TestSeqList4();
return 0;
}(5)随机位置插入
（1）SeqList.h
#ifdef __SEQLIST__H__
#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<assert.h>
//增强程序可维护性
typedef int SLTDataType;
typedef struct SeqList
{
SQDataType*a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListPushBack(SL*ps,SLTDataType x);//尾插
void SeqListPushFront(SL*ps,SLTDataType x);//头插
void SeqListPopBack(SL*ps);//尾删
void SeqListPopFront(SL*ps);//头删
void SeqListInsert(SL*ps,int pos,SLTDataType x);//随机插入
void SeqListErase(SL*ps,int pos);//随机删除
#endif （2）SeqList.c
#include"SeqList.h"
void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListCheckCapacity(SL*ps)
{
//满了就要扩容
if(ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
//尾插
void SeqListPushBack(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//头插
void SeqListPushFront(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
//1、初始条件
//2、结束条件
//3、迭代过程
int end = ps->size - 1;
while(end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
//尾删
void SeqListPopBack(SL*ps)
{
//粗暴一点直接assert
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;//这句代码加上也可以，没有也不影响
ps->size--;
}
//头删
void SeqListPopFront(SL*ps)
{
assert(ps->size > 0);
int start = 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//随机插入
void SeqListInsert(SL*ps,int pos,SLTDataType x)
{
assert(ps->size > 0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while(end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
//随机删除
void SeqListErase(SL*ps,int pos);
//测试能不能打印出来
void SeqListPrint(SL*ps)
{
for(int i = 0;i < ps->size;++i)
{
printf("%d ",ps->a[i]);
}
printf("\n");
}这个就是我们写的这个随机插入的接口。
（3）test.c
#include"SeqList.h"
void TestSeqList5()
{
SL sl;
SeqListInit(&sl);
SeqListPushFront(&sl,1);
SeqListPushFront(&sl,2);
SeqListPushFront(&sl,3);
SeqListPushFront(&sl,4);
SeqListPushFront(&sl,5);
SeqListPushFront(&sl,6);
SeqListPrint(&sl);
SeqListInsert(&sl,1,20);
SeqListPrint(&sl);
}
int main()
{
TestSeqList5();
return 0;
}(6)随机位置删除
（1）SeqList.h
#ifdef __SEQLIST__H__
#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<assert.h>
//增强程序可维护性
typedef int SLTDataType;
typedef struct SeqList
{
SQDataType*a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListDestory(SL*ps);//销毁
void SeqListPushBack(SL*ps,SLTDataType x);//尾插
void SeqListPushFront(SL*ps,SLTDataType x);//头插
void SeqListPopBack(SL*ps);//尾删
void SeqListPopFront(SL*ps);//头删
void SeqListInsert(SL*ps,int pos,SLTDataType x);//随机插入
void SeqListErase(SL*ps,int pos);//随机删除
#endif （2）SeqList.c
#include"SeqList.h"
void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListDestory(SL*ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListCheckCapacity(SL*ps)
{
//满了就要扩容
if(ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
//尾插
void SeqListPushBack(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//头插
void SeqListPushFront(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
//1、初始条件
//2、结束条件
//3、迭代过程
int end = ps->size - 1;
while(end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
//尾删
void SeqListPopBack(SL*ps)
{
//粗暴一点直接assert
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;//这句代码加上也可以，没有也不影响
ps->size--;
}
//头删
void SeqListPopFront(SL*ps)
{
assert(ps->size > 0);
int start = 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//随机位置插入
void SeqListInsert(SL*ps,int pos,SLTDataType x)
{
assert(ps->size > 0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while(end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
//随机位置删除
void SeqListErase(SL*ps,int pos)
{
assert(pos < ps->size)
int start = pos + 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//测试能不能打印出来
void SeqListPrint(SL*ps)
{
for(int i = 0;i < ps->size;++i)
{
printf("%d ",ps->a[i]);
}
printf("\n");
}（3）test.c
#include"SeqList.h"
void TestSeqList6()
{
SL sl;
SeqListInit(&sl);
SeqListPushFront(&sl,1);
SeqListPushFront(&sl,2);
SeqListPushFront(&sl,3);
SeqListPushFront(&sl,4);
SeqListPushFront(&sl,5);
SeqListPushFront(&sl,6);
SeqListPrint(&sl);
SeqListInsert(&sl,1,20);
SeqListPrint(&sl);
SeqListErase(&sl,1);
SeqListPrint(&sl);
SeqListDestory(&sl);
}
int main()
{
TestSeqList6();
return 0;
}注意：
1、删除数据之后空间还是在的，因为顺序表是连续的，只是把后面的数据挤到一起，只删数据，不删空间；
2、start用前置++和后置++都是一样的，前置会高一点点，但是现在的计算机的算力非常强大，可以忽略不计，以后遇到前置和后置有区别的地方主包会讲的。
我们动态申请的内存要还给操作系统（销毁），数据没了，空间还在，只是还给操作系统了。我们的六个接口虽然是分开写的，但实际上它们是写在同一个文件里面的，因此博主就只在【随机位置插入】写了void SeqListDestory(SL*ps);。
讲到这里，我们顺序表的增删查改接口函数已经讲完了增删了。
(7)查改：查找和修改
（1）SeqList.h
#ifdef __SEQLIST__H__
#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<assert.h>
//增强程序可维护性
typedef int SLTDataType;
typedef struct SeqList
{
SLTDataType*a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListDestory(SL*ps);//销毁
void SeqListPushBack(SL*ps,SLTDataType x);//尾插
void SeqListPushFront(SL*ps,SLTDataType x);//头插
void SeqListPopBack(SL*ps);//尾删
void SeqListPopFront(SL*ps);//头删
void SeqListInsert(SL*ps,int pos,SLTDataType x);//随机插入
void SeqListErase(SL*ps,int pos);//随机删除
int SeqListFind(SL*ps,SLTDataType x);// 查找
void SeqListModity((SL*ps,int pos,SLTDataType x);//修改
#endif （2）SeqList.c
#include"SeqList.h"
void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListDestory(SL*ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListCheckCapacity(SL*ps)
{
//满了就要扩容
if(ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
//尾插
void SeqListPushBack(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//头插
void SeqListPushFront(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
//1、初始条件
//2、结束条件
//3、迭代过程
int end = ps->size - 1;
while(end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
//尾删
void SeqListPopBack(SL*ps)
{
//粗暴一点直接assert
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;//这句代码加上也可以，没有也不影响
ps->size--;
}
//头删
void SeqListPopFront(SL*ps)
{
assert(ps->size > 0);
int start = 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//随机位置插入
void SeqListInsert(SL*ps,int pos,SLTDataType x)
{
assert(ps->size > 0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while(end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
//随机位置删除
void SeqListErase(SL*ps,int pos)
{
assert(pos < ps->size)
int start = pos + 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//查找
int SeqListFind(SL*ps,SLTDataType x)
{
//如果查找的地方是有序的，可以用二分查找，但是现在不是有序，就不能写二分查找
for(int i = 0;i < ps->size;++i)
{
if(ps->a[i] == x)
{
return i;
}
}
return -1;
}
//修改
void SeqListModity((SL*ps,int pos,SLTDataType x)
{
assert(pos < ps->size);
ps->a[pos] = x;
}
//测试能不能打印出来
void SeqListPrint(SL*ps)
{
for(int i = 0;i < ps->size;++i)
{
printf("%d ",ps->a[i]);
}
printf("\n");
}（3）test.c
#include"SeqList.h"
void TestSeqList6()
{
SL sl;
SeqListInit(&sl);
SeqListPushFront(&sl,1);
SeqListPushFront(&sl,2);
SeqListPushFront(&sl,3);
SeqListPushFront(&sl,4);
SeqListPushFront(&sl,5);
SeqListPushFront(&sl,6);
SeqListPrint(&sl);
SeqListInsert(&sl,1,20);
SeqListPrint(&sl);
SeqListErase(&sl,1);
SeqListPrint(&sl);
SeqListDestory(&sl);
}
int main()
{
TestSeqList6();
return 0;
}如果我们还要实现一些接口，比如说空、满、size啊这些接口，uu们感兴趣可以自己加。
我们学完了这几个接口，是时候做点什么练练手了！我们来写一个【菜单】——
(8)写菜单
提醒：
（1）SeqList.h
#ifdef __SEQLIST__H__
#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<assert.h>
//增强程序可维护性
typedef int SLTDataType;//ContactInfo
typedef int SLTDataType;
typedef struct SeqList
{
SLTDataType*a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListDestory(SL*ps);//销毁
void SeqListPushBack(SL*ps,SLTDataType x);//尾插
void SeqListPushFront(SL*ps,SLTDataType x);//头插
void SeqListPopBack(SL*ps);//尾删
void SeqListPopFront(SL*ps);//头删
void SeqListInsert(SL*ps,int pos,SLTDataType x);//随机插入
void SeqListErase(SL*ps,int pos);//随机删除
int SeqListFind(SL*ps,SLTDataType x);// 查找
void SeqListModity((SL*ps,int pos,SLTDataType x);//修改
#endif （2）SeqList.c
#include"SeqList.h"
void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListDestory(SL*ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListCheckCapacity(SL*ps)
{
//满了就要扩容
if(ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if(tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
//尾插
void SeqListPushBack(SL*ps,SLTDataType x);
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//头插
void SeqListPushFront(SL*ps,SLTDataType x)
{
SeqListCheckCapacity(ps);
//1、初始条件
//2、结束条件
//3、迭代过程
int end = ps->size - 1;
while(end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
//尾删
void SeqListPopBack(SL*ps)
{
//粗暴一点直接assert
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;//这句代码加上也可以，没有也不影响
ps->size--;
}
//头删
void SeqListPopFront(SL*ps)
{
assert(ps->size > 0);
int start = 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//随机位置插入
void SeqListInsert(SL*ps,int pos,SLTDataType x)
{
assert(ps->size > 0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while(end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
//随机位置删除
void SeqListErase(SL*ps,int pos)
{
assert(pos < ps->size)
int start = pos + 1;
while(start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//查找
int SeqListFind(SL*ps,SLTDataType x)
{
//如果查找的地方是有序的，可以用二分查找，但是现在不是有序，就不能写二分查找
for(int i = 0;i < ps->size;++i)
{
if(ps->a[i] == x)
{
return i;
}
}
return -1;
}
//修改
void SeqListModity((SL*ps,int pos,SLTDataType x)
{
assert(pos < ps->size);
ps->a[pos] = x;
}
//测试能不能打印出来
void SeqListPrint(SL*ps)
{
for(int i = 0;i < ps->size;++i)
{
printf("%d ",ps->a[i]);
}
printf("\n");
}（3）test.c
#include"SeqList.h"
void TestSeqList6()
{
SL sl;
SeqListInit(&sl);
SeqListPushFront(&sl,1);
SeqListPushFront(&sl,2);
SeqListPushFront(&sl,3);
SeqListPushFront(&sl,4);
SeqListPushFront(&sl,5);
SeqListPushFront(&sl,6);
SeqListPrint(&sl);
SeqListInsert(&sl,1,20);
SeqListPrint(&sl);
SeqListErase(&sl,1);
SeqListPrint(&sl);
SeqListDestory(&sl);
}
void menu()
{
printf("******************************\n");
printf("1.尾插数据, 2.头插数据\n");
printf("3.尾删数据, 4.头删数据\n");
printf("5.打印数据,-1.退出\n");
printf("******************************\n");
printf("请输入你的操作选项:");
}
int main()
{
SL s:
SeqListInit(&s):
int option = 0;
int x = 0;
while(option != -1)
{
menu();
scanf("%d",&option);
switch(option)
{
case 1:
printf（"请输入你要插入的数据，以-1为结束\n");
do
{
scanf("%d",x);
if(x != -1)
{
SeqListPushBack(&s,x);
}
}while((x != -1);
break;
//中间几个选项类似
case 2:
break;
case 3:
break;
case 4:
break;
case 5:
SqeListPrint(&s);
break;
default:
break;
}
}
SeqListDestory(&s);
return 0;
}我们不要直接写菜单，要测试到所有的接口都没问题了，再来写，因为一个接口出问题了，就可能浪费大把时间，自己把自己难住了。因此我们先写接口，再写菜单。
(9)复用
这里我们我们展示一下复用的强大之处，复用一般是指“复制代码”。
（1）SeqList.h
#pragma once
//#ifdef __SEQLIST__H__
//#define __SEQLIST__H__
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
//增强程序可维护性
typedef int SLTDataType;
typedef struct SeqList
{
SLTDataType* a;
int size; //有效数据的个数
int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestory(SL* ps);//销毁
void SeqListPushBack(SL* ps, SLTDataType x);//尾插
void SeqListPushFront(SL* ps, SLTDataType x);//头插
void SeqListPopBack(SL* ps);//尾删
void SeqListPopFront(SL* ps);//头删
void SeqListInsert(SL* ps, int pos, SLTDataType x);//随机插入
void SeqListErase(SL* ps, int pos);//随机删除
int SeqListFind(SL* ps, SLTDataType x);// 查找
void SeqListModity(SL* ps, int pos, SLTDataType x);//修改
/*#endif */ （2）SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SL* ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
//当然我们也可以直接malloc
}
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListCheckCapacity(SL* ps)
{
//满了就要扩容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLTDataType* tmp = realloc(ps->a, newcapacity * sizeof(SLTDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
//头插 尾插 头删 尾删
//尾插
void SeqListPushBack(SL* ps, SLTDataType x)
{
//SeqListCheckCapacity(ps);
//ps->a[ps->size] = x;
//ps->size++;
SeqListInsert(ps, ps->size, x);
}
//头插
void SeqListPushFront(SL* ps, SLTDataType x)
{
//SeqListCheckCapacity(ps);
1、初始条件
2、结束条件
3、迭代过程
//int end = ps->size - 1;
//while (end >= 0)
//{
// ps->a[end + 1] = ps->a[end];
// --end;
//}
//ps->a[0] = x;
//ps->size++;
//SeqListCheckCapacity(ps);
SeqListInsert(ps, 0, x);
}
//尾删
void SeqListPopBack(SL* ps)
{
粗暴一点直接assert
//assert(ps->size > 0);
//ps->a[ps->size - 1] = 0;//这句代码加上也可以，没有也不影响
//ps->size--;
SeqListErase(ps, ps->size - 1);
}
//头删
void SeqListPopFront(SL* ps)
{
/* assert(ps->size > 0);
int start = 1;
while (start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;*/
SeqListErase(ps, 0);
}
//随机位置插入
void SeqListInsert(SL* ps, int pos, SLTDataType x)
{
assert(pos <= ps->size);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
//随机位置删除
void SeqListErase(SL* ps, int pos)
{
assert(pos < ps->size);
int start = pos + 1;
while (start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}
//查找
int SeqListFind(SL* ps, SLTDataType x)
{
//如果查找的地方是有序的，可以用二分查找，但是现在不是有序，就不能写二分查找
for (int i = 0; i < ps->size; ++i)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
//修改
void SeqListModity(SL* ps, int pos, SLTDataType x)
{
assert(pos < ps->size);
ps->a[pos] = x;
}
//测试能不能打印出来
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}（3）test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void TestSeqList6()
{
SL sl;
SeqListInit(&sl);
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPushFront(&sl, 5);
SeqListPushFront(&sl, 6);
SeqListPrint(&sl);
SeqListInsert(&sl, 1, 20);
SeqListPrint(&sl);
SeqListErase(&sl, 1);
SeqListPrint(&sl);
SeqListDestory(&sl);
}
int main()
{
TestSeqList6();
return 0;
}是不是很爽？这就是复用大王的实力！
结尾
往期回顾：
本期内容需要回顾的C语言知识放在下面了（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了），大家如果对前面部分的知识点印象不深，可以去看看：
【动态内存管理】深入详解：malloc和free、calloc和realloc、常见的动态内存的错误、柔性数组、总结C/C++中程序内存区域划分
【自定义类型：结构体】：类型声明、结构体变量的创建与初始化、内存对齐、传参、位段
C语言指针深入详解（六）：sizeof和strlen的对比，【题解】数组和指针笔试题解析、指针运算笔试题解析
【深入详解】函数栈帧的创建与销毁：寄存器、压栈、出栈、调用、回收空间
结语：本篇文章到这里就结束了，对数据结构的顺序表知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，有什么错误欢迎在评论区斧正，感谢友友们的关注和支持！