文章目录
🌟前言
🌟动态顺序表建立和初始化
🌟检查容量和扩容
🌟尾插和尾删
🌟头插和头删
🌟查找和指定pos下标位置插入
🌟删除指定pos位置的数据 和摧毁
🌟完整代码工程
🌟SeqList.h头文件
🌟SeqList.c文件
🌟text.c测试文件
🌟前言
| 为了体现出程序的模块化思想，下面的每一个功能都用一个独立函数来封装 |
| 如果想要其中一个功能请直接复制代码块和函数声明即可使用 |
🌟动态顺序表建立和初始化
| 动态顺序表相比于静态顺序表在容量大小方面更加灵活，故用动态顺序表演示 |
动态顺序表的建立
typedef int SLDateType; //可能有时候要存储的数据类型不一样
//这样做可以更容易修改
//动态顺序表
typedef struct SeqList
{
SLDateType* a; //用来存放顺序表的地址
int size; //表示数组存了多少个有效数据
int capacity; //数组实际能存多少个数据
}SL;
SL a；
顺序表的初始化
初始化只需要把SL结构体里的数据置零即可
//初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
🌟检查容量和扩容
这里的想法是：刚开始顺序表初始化之后为零，还没给它分配空间，故每次进去的时候，判断是否有容量或者容量是否满了，如果没有容量，就是刚初始化完，所以第一次进去就给它先分配空间，后续就每一次进入如果满了，就进行2倍扩容
//检查容量
void SeqListCheckCapacity(SL* ps)
{
//如果内存不够或者没有内存就扩容
if (ps->size == ps->capacity)
{
//判断是否有容量，如果没有就先给newcapacity赋值4，有就扩容2倍
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDateType* tem = (SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));
if (tem == NULL) //失败就结束程序
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tem; //把新地址传给a
ps->capacity = newcapacity;//更新新容量
}
}| realloc是一个C语言扩容函数，如果本身没有容量的，就会自动进行malloc这个函数的功能 |
| realloc函数参数 realloc（需要重新分配的内存空间指针，新的内存空间的大小） |
经过上面的处理，顺序表已经是实实在在的解决容量和初始化问题，接下来就对它进行各种操作
🌟尾插和尾删
尾插顾名思义，就是在顺序表的最后一个元素的后面添加一个元素，我们只需要知道原来顺序表的有效个数大小就即可尾插
//尾插
void SeqListPushBack(SL* ps, SLDateType x) //x是要插入的数据
{
//进行尾插时间要检查容量是否满了，不然容易越界访问
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++; //插入之后记得有效个数+1
}
尾删的话，直接对size-1即可，因为有效个数size减1后，原来size这个位置的数就访问不到，下次可以直接覆盖赋值，如果直接对原来size位置进行置零也可以，不过是多此一举
进行尾删的时候要检查原来是顺序表有没有元素，没有的话就不用进行尾删了
//尾删
void SeqListPopBack(SL* ps)
{
//assert是判断括号里的条件是否满足，不满足就报错，是比较暴力的写法
assert(ps->a != NULL&&ps->size!=0);
ps->size--;
}
上面那个assert也可以用if语句进行更改，if语句是一个比较温柔的处理方法，但不会报错，个人比较喜欢暴力一点的，严厉一点😎（assert头文件<assert.h>）
🌟头插和头删
头插：进行头插前，我们是需要把原来所有的数据往后移动一个位置，然后在第一个位置即可插入数据。听起来是不是挺简单的！！
//头插
void SeqListPushFront(SL* ps, SLDateType x)
{
//插入数据前先检查容量是否满了，满了就扩容
SeqListCheckCapacity(ps);
//判断是否有有效个数
if (ps->size == 0)
{
ps->a[0] = x;
}
//有有效个数就进行移动数据
int tail = 0;
for (tail = ps->size-1; tail >= 0; tail--)
{
ps->a[tail + 1] = ps->a[tail];
}
ps->a[0] = x;
ps->size++; //别忘了有效个数+1
}想法是简单的，但是有一个特殊位置需要注意，就是如果顺序表没有有效个数的时候，进行尾插是不需要移动数据的，因为都没有数据，就不需要移动了，直接对第一个位置进行赋值即可！
头删也是要判断是否有有效个数，如果没有有效个数，就没必要头删了，因为都没数据可删了 思想就是把除了第一位元素的所有元素进行前移即可
//头删
void SeqListPopFront(SL* ps)
{
//判断是否有有效个数，没有就报错
assert(ps->a != NULL && ps->size != 0);
//元素前移
int tail = 0;
for (tail = 0; tail < ps->size-1; tail++)
{
ps->a[tail]=ps->a[tail + 1];
}
ps->size--; //别忘了size-1
}
🌟查找和指定pos下标位置插入
查找的话就是遍历一遍顺序表即可，没有多大的技巧可言，有序的话另当别论。
//找到了返回x位置的下标，找不到返回-1
int SeqListFind(SL* ps,SLDateType x)
{
assert(ps->a != NULL && ps->size != 0);
int i = 0;
//遍历顺序表
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}指定pos下标位置插入：首先要判断指定pos下标是否合法，要遵循顺序表是按顺序存放的，所以如果顺序表里有3个有效个数的时候，你是不能往第5，6等等往后个位置插入，也不能往-1，-2这些非法位置插入，它的有效范围应该是0~size
pos下标合法之后，知道pos位置，把pos位置的元素及往后的元素统统往后移动一位，然后在pos位置插入元素即可
//指定pos下标位置插入
void SeqListInsert(SL* ps,int pos,SLDateType x)
{
//先判断pos是否合法
assert(pos<=ps->size&&pos>=0);
int end = ps->size-1;
SeqListCheckCapacity(ps);
//往后挪动数据
while(end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x; //插入元素
ps->size++; //别忘了size+1
}
| 指定pos位置插入是可以直接代替上面的尾插和头插，嫌麻烦的可以直接用这个，忽略尾插和头插！ |
🌟删除指定pos位置的数据和摧毁
删除：也是首先要判断pos位置是否合法，合法的话，就直接把pos后的元素往前挪动一位即可覆盖pos位置的数据，也就是删除，最后记得size-1
这一次的pos下标合法范围是0~size-1
//删除指定pos位置的数据
void SeqListErase(SL* ps, int pos)
{
//判断pos是否合法
assert(pos < ps->size&& pos >= 0);
//挪动元素
int i =0;
for (i = pos+1; i < ps->size; i++)
{
ps->a[i-1] = ps->a[i ];
}
ps->size--;
}摧毁就是把顺序表进行内存释放，最后把结构体里的数据置零即可
//摧毁顺序表
void SeqListDestroy(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
🌟完整代码工程
| 遵循模块化思想，写成一个比较正规的工程，分三个文件 |
| 第一个是SeqList.h整个工程的头文件 |
| 第二个是SeqList.c整个工程的函数实现文件 |
| 第三个是text.c测试文件 |
🌟SeqList.h头文件
//SeqList.h头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
typedef int SLDateType;//可能有时候要存储的数据类型不一样
//这样做可以更容易修改
//动态顺序表
typedef struct SeqList
{
SLDateType* a; //用来存放顺序表的地址
int size; //表示数组存了多少个有效数据
int capacity; //数组实际能存多少个数据
}SL;
//打印顺序表
void SeqListPrint(SL* ps);
//初始化
void SeqListInit(SL* ps);
//摧毁顺序表
void SeqListDestroy(SL* ps);
//检查容量
void SeqListCheckCapacity(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDateType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDateType x);
//头删
void SeqListPopFront(SL* ps);
//找到了返回x位置的下标，找不到返回-1
int SeqListFind(SL* ps, SLDateType x);
//指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDateType x);
//删除pos位置的数据
void SeqListErase(SL* ps, int pos);
🌟SeqList.c文件
//SeqList.c文件
#define _CRT_SECURE_NO_WARNINGS //vs2019用到scanf函数时需这个，其他编译器请忽略
#include"SeqList.h"
//打印顺序表
void SeqListPrint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
//摧毁顺序表
void SeqListDestroy(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;
SLDateType* tem = (SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));
if (tem == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tem;
ps->capacity = newcapacity;
}
}
//尾插
void SeqListPushBack(SL* ps, SLDateType x)
{
//进行尾插时间要检查容量是否满了，不然容易越界访问
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//尾删
void SeqListPopBack(SL* ps)
{
assert(ps->a != NULL&&ps->size!=0);
ps->size--;
}
//头插
void SeqListPushFront(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);
if (ps->size == 0)
{
ps->a[0] = x;
}
int tail = 0;
for (tail = ps->size-1; tail >= 0; tail--)
{
ps->a[tail + 1] = ps->a[tail];
}
ps->a[0] = x;
ps->size++;
}
//头删
void SeqListPopFront(SL* ps)
{
assert(ps->a != NULL && ps->size != 0);
int tail = 0;
for (tail = 0; tail < ps->size-1; tail++)
{
ps->a[tail]=ps->a[tail + 1];
}
ps->size--;
}
//找到了返回x位置的下标，找不到返回-1
int SeqListFind(SL* ps,SLDateType x)
{
assert(ps->a != NULL && ps->size != 0);
int i = 0;
//遍历顺序表
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
//指定pos下标位置插入
void SeqListInsert(SL* ps,int pos,SLDateType x)
{
assert(pos<=ps->size&&pos>=0);
int end = ps->size-1;
SeqListCheckCapacity(ps);
//挪动数据
while(end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//删除指定pos位置的数据
void SeqListErase(SL* ps, int pos)
{
assert(pos < ps->size&& pos >= 0);
int i =0;
for (i = pos+1; i < ps->size; i++)
{
ps->a[i-1] = ps->a[i ];
}
ps->size--;
}
🌟text.c测试文件
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void menu()
{
printf("************************************\n");
printf(" 1.头插 2.头删\n");
printf(" 3.尾插 4.尾删\n");
printf(" 5.打印 6.插入\n");
printf(" 7.查找 8.删除指定位置\n");
printf(" -1.退出\n");
printf("************************************\n");
printf(" 请选择>: \n");
}
void menuText()
{
SL s1;
int input = 0;
SLDateType x1 = 0;
SLDateType x2 = 0;
SeqListInit(&s1);
while(input!=-1)
{
menu();
scanf("%d", &input);
switch (input)
{
case 1:
printf("请输入你要头插入的数，以-1为结束\n");
scanf("%d", &x1);
while (x1 != -1)
{
SeqListPushFront(&s1, x1);
scanf("%d", &x1);
}
printf("插入成功\n");
break;
case 2:
SeqListPopFront(&s1);
printf("头删成功\n");
break;
case 3:
printf("请输入你要尾插入的数，以-1为结束\n");
scanf("%d", &x1);
while (x1 != -1)
{
SeqListPushBack(&s1, x1);
scanf("%d", &x1);
}
printf("插入成功\n");
break;
case 4:
SeqListPopBack(&s1);
printf("尾删成功\n");
break;
case 5:
SeqListPrint(&s1);
printf("打印成功\n");
break;
case 6:
printf("请输入按“在哪个位置 插入”的数据为顺序输入。如在第二个位置，插入3，“2 3”\n");
scanf("%d %d", &x1, &x2);
SeqListInsert(&s1, x1, x2);
printf("插入成功\n");
break;
case 7:
printf("请输入你要查找的数据\n");
scanf("%d", &x1);
int ret=SeqListFind(&s1, x1);
if (ret != -1)
{
printf("查到了，下标为%d\n", ret);
}
else
printf("查不到\n");
break;
case 8:
printf("请输入你要删除数据的位置\n");
scanf("%d", &x1);
SeqListErase(&s1, x1);
printf("删除成功\n");
break;
case -1:
printf("退出成功\n");
break;
default:
printf("无此选项，请重新输入\n");
break;
}
}
SeqListDestroy(&s1);
}
int main()
{
menuText();
}一部分测试截图>
头插和打印功能测试：
尾插和查找功能：
有bug或者哪里出错误请指出！！
