顺序表——功能实现
1.0 前言 学习顺序表之前，我们需要具备三方面的知识点。指针，结构体，动态内存的开辟。
2.0 线性表
线性表是数据结构中的一种基本形式，是 n 个数据元素的有限序列。线性表中的数据元素之间有序且连续，可以用一组地址连续的存储单元存储。
线性表可以表示一维数组，也可以表示一串具有相同类型的元素。线性表中的元素可以是数字、字符、对象等。线性表有两种基本形式：顺序表和链表。
线性表中的数据结构有哪些相同的特性：
线性表的特性：结构不一定连续，逻辑结构一定连续的。
顺序表的特性：物理结构一定连续的，逻辑结构一定连续的。
本章主要讲的是顺序表。
2.1 顺序表
顺序表和数组的区别：顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。
2.2 顺序表的分类
开辟数组我们有两个方法：
1.静态内存开辟,开辟一个固定的空间。如：int arr[10]={0};
2.动态内存开辟，确定大小之后再去申请空间。如：int *arr
同理，顺序表分类也有两种：
1.静态顺序表定义
struct SeqList
{
int arr[100];//定长数组
int size;//顺序表当前有效的数据个数
};2.动态顺序表定义
struct SeqList
{
int* arr;
int size;//有效的数据个数
int capcacity;//空间大小
}这两种哪一个好呢？
举个例子： 某app原定只能储存100万的用户信息，但随着app的爆火，越来越多的人注册使用这app，但这个后台只能储存100万，剩下的数据全部丢失，这将是一次重大的事故。
若动态数组，那么我们就能够在空间不够的情况下，再一次进行开辟空间，代码更加灵活。
2.3 顺序表功能的实现
开始之前我们需要创建三个文件，分别是
test.c 顺序表结构声明，顺序表的方法。 SeqList.h 实现顺序表的方法。 SeqList.c 对实现的顺序表进行测试
在之前我们就讲过了多文件的好处，这里就不在重复了。
2.3.1 准备前奏
顺序表的实现需要创建一个动态顺序表。其中包括了有效数据的大小size，已经整个动态空间的大小。
SeqList.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;//将int重命名，方便后续其他类型的修改
//动态顺序表
typedef struct SeqList
{
SLDataType* arr;//指向动态开辟的数组
int size; //有效数据个数
int capacity; //空间大小
}SL;
//typedef struct SeqList Sl;text.c
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
int main()
{
SL s1;//创建变量s1
return 0;
}SeqList.c
#include"SeqList.h"接下来就能进入我们函数的实现了。
2.3.2 初始化
//初始化
//错误示范
void SLInit(SL ps)
{
ps.arr = NULL;
ps.capacity = ps.size = 0;
}
//正确代码
void SLInit(SL * ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}刚刚开始的时候，数组空间还没开辟所以是0；arr也还没有数据所以是空。
坑：错误的代码中采用了传值，而传值实际是是实参，拷贝一份给形参。还没进行初始化没有值。
所以这里要用传地址，用指针来接收。
2.3.3 打印
void SLPrint(SL s)
{
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.arr[i]);
}
printf("\n");
}完成的函数，要验证它它能不能符合要求，就要打印出来，方便观察。
2.3.4 销毁空间
动态内存用完之后，我们要进行销毁。且将ps置为空，将size和capacity赋为0。
有借有还，再借不难。
void SLDestroy(SL * ps)
{
if (ps->arr)//等价于if(ps->arr != NULL)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}2.3.5 申请空间
//申请空间的判断
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc error");
exit(1);
}
//空间申请成功
ps->capacity = newCapacity;
ps->arr = tmp;
}
}由于空间的申请不止一个函数需要用到，在这就单独给它封装函数，方便后续的使用。
首先，要判断arr数组空间内存的大小。
如果数组的空间容量Capacity不等于有效数据size，则跳出函数。
相反，相等的情况下，开始开辟空间，创建一个变量newCapacity来储存新的空间容量大小，再创建tmp来存放首元素的地址(防止realloc开辟失败，将原来的arr置为NULL)。并且判断tmp是否开辟成功。
最后将newCapacity赋给capacity，将tmp赋值给arr。
2.3.6 头部插入
//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
for (int i = ps->size ; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}头部插入之前要满足两个条件：
- 传入指针不能为空。
- 判断是否需要申请空间。
因为这里是头部插入，所以需要讲数组内的数据往后移一位。然后将新的数据插入数组下标为0的地址。最后对size进行+1即可。
2.3.7 删除头部数据
void SLPopFront(SL* ps)
{
assert(ps);
for (int i = 0; i > ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}删除头部数据之前，首先要assert断言传入的指针是不是空指针。删除头部数据只需要将后一位往前移，循环往复，最后size进行-1。
2.3.8 尾部插入
void SLPushBack(SL*ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}尾插相比于头插会简单点，但同样也是需要断言，看传入的指针是否为空。在末尾插入数据需要在size处插入新的数据，然后对size进行+1即可。
2.3.9 删除尾部数据
void SLPopBack(SL* ps)
{
assert(ps);
--ps->size;
}同样尾删也是需要断言，看传入的指针是否为空。然后厎size-1就行了，有效数据减一，不会影响其他功能。
2.3.10 指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos ; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
//pos 表示数组的下标值。掌握了头插和尾插，那么在指定位置之前插入数据就不难，这其实就是头插和尾插的结合。
在插入之前，要用assert断言传入指针是否为空。pos只能在0~size之间插入数据，当传入的数据不是这个范围，程序就会出错，所以这里也需要用assert来断言assert(pos >= 0 && pos <= ps->size)。
假设在下标为2的位置插入新的数据，就需要讲下标为2的数据移到后面，从后往前移（防止数据被覆盖），然后对size进行+1。
中间的值会了，插入两边就是头插和尾插，前面已经讲过了，这里就都是一样的。
2.3.11 指定位置之前删除
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->size--;
}在删除数据之前，要用assert断言传入指针是否为空。pos只能在0~size之间删除数据，但size指向的地址是没有数据的，当传入的数据不是这个范围，程序就会出错，所以这里也需要用assert来断言assert(pos >= 0 && pos < ps->size)。
接下来就是删除数据的部分，假设删除数组下标为2内容，只需要将后面的的数组往前放，循环往复，最后对size进行-1。
2.3.12 寻找指定数字
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;
}
}寻找指定数据，对传入的地址进行断言，然后用一个for循环来寻找数组的值，再用if-else来判断，若ps->arr[i] == x则返回的值。相反则返回-1。
3.0 完整代码
3.1 SeqList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* arr;
int size; //有效数据个数
int capacity; //空间大小
}SL;
//typedef struct SeqList Sl;
//开辟空间
void SLCheckCapacity(SL* ps);
//初始化
void SLInit(SL* ps);
//打印
void SLPrint(SL s);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//尾删
void SLPopBack(SL* ps);
//指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置之前删除
void SLErase(SL* ps, int pos);
//查找数据
int SLFind(SL* ps, SLDataType x);
//销毁
void SLDestroy(SL* ps);3.2 SeqList.c
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
//申请空间的判断
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc error");
exit(1);
}
//空间申请成功
ps->capacity = newCapacity;
ps->arr = tmp;
}
}
//初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//打印
void SLPrint(SL s)
{
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.arr[i]);
}
printf("\n");
}
//销毁
void SLDestroy(SL * ps)
{
if (ps->arr)//等价于if(ps->arr != NULL)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
for (int i = ps->size ; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
//尾插
void SLPushBack(SL*ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
ps->arr[0] = -1;
for (int i = 0; i > ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
--ps->size;
}
//指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos ; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
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->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;
}
}3.3 test.c
void SLTest01()
{
SL sl;
SLInit(&sl);
//增删查改操作
//测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(sl);//1 2 3 4
//SLPushFront(&sl, 5);
//SLPushFront(&sl, 6);
//测试尾删
SLPopBack(&sl);
SLPrint(sl);//1 2 3
SLPopBack(&sl);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPrint(sl);
//...........
SLDestroy(&sl);
}
void SLTest02()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(sl);//1 2 3 4
//测试指定位置之前插入数据
//SLInsert(&sl, 1, 99);
//SLInsert(&sl, sl.size, 88);
//测试删除指定位置的数据
//SLErase(&sl, 1);
//SLPrint(sl);//1 3 4
//测试顺序表的查找
int find = SLFind(&sl, 40);
if (find < 0)
{
printf("没有找到！\n");
}
else {
printf("找到了！下标为%d\n",find);
}
SLDestroy(&sl);
}
int main()
{
//SLTest01();
//SLTest02();
ContactTest01();
return 0;
}腾讯云开发者
