[数据结构]顺序表详解+完整源码(顺序表初始化、销毁、扩容、元素的插入和删除)
目录
1.什么是顺序表
2.顺序表的分类
2.1静态顺序表
2.2动态顺序表
3.动态顺序表的实现
3.1定义顺序表的类型
3.2 顺序表的初始化和销毁
3.3 判断空间是否充足
3.4插入数据元素（尾插和头插）
3.5 打印顺序表
3.6 删除数据元素（尾删头删）
3.7指定位置插入和指定位置删除
4.顺序表完整代码
SeqList.h
SeqList.c
text.c
1.什么是顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
- 特点：顺序表中逻辑上相邻的元素在物理位置上也相邻，这使得只要确定了起始位置，就可以通过公式计算出表中任一元素的地址。
- 存储结构：顺序表的存储结构通常由一个数组和相关的属性（如长度）组成。数组用于存储元素，属性用于记录顺序表的状态。
- 基本操作：顺序表支持初始化、插入、删除、查找等基本操作。这些操作可以通过对数组的操作来实现，同时需要更新顺序表的属性以反映操作结果。
- 优势：顺序表便于随机访问，即可以快速访问表中的任意元素。
顺序表是数据结构学习中的基础概念，对于理解线性表的存储和操作方式具有重要意义
2.顺序表的分类
2.1静态顺序表
typedef int SLDateType;
#define N 7;
typedef struct seqlist
{
SLDateType arr[N]; //空间大小固定
int size; //有效数据个数
}SL;2.2动态顺序表
typedef int SLDateType;
typedef struct seqlist
{
SLDateType* arr;//可以增容
int capacity; //空间大小
int size; //有效数据个数
}SL;3.动态顺序表的实现
3.1定义顺序表的类型
typedef int SLDateType;//定义顺序表存储的元素类型，这里假设为int型
typedef struct seqlist
{
SLDateType* arr;
int capacity; //空间大小
int size; //有效数据个数
}SL;3.2 顺序表的初始化和销毁
//初始化
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;
}3.3 判断空间是否充足
//判断空间是否充足
void SLCheckCapacity(SL * ps)
{
if (ps->size == ps->capacity)
{
//如果没有空间则扩容为4个字节,若有空间则内存扩大一倍
int NewCapacit = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDateType* tmp =(SLDateType*)realloc(ps->arr, NewCapacit * sizeof(SLDateType));
if (tmp == NULL) //realloc返回的不为空，也就是扩容没成功时打印错误
{
perror("realloc fail!");
exit(-1);
}
ps->arr = tmp; //扩容成功则将扩容后的内存大小赋值给arr
ps->capacity = NewCapacit; //扩容后的空间大小重新赋值
}
}3.4插入数据元素（尾插和头插）
//尾插
void SLPushBack(SL* ps, SLDateType x)
{
//断言
assert(ps);
//判断空间是否充足
SLCheckCapacity(ps);
//插入数据
ps->arr[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
//把所有数据向后挪动一位，第一位空出来
for (int i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i-1];
}
//把x赋值给第一位
ps->arr[0] = x;
ps->size++;
}3.5 打印顺序表
//打印
void SLprint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}3.6 删除数据元素（尾删头删）
//尾删
void SLDeleteBack(SL* ps)
{
assert(ps);
assert(ps->size);//断言ps->size不为0
ps->size--;
}
//头删
void SLDeleteFront(SL* ps)
{
assert(ps);
assert(ps->size);//断言ps->size不为0
for (int i = 0; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}3.7指定位置插入和指定位置删除
//指定位置插入
void SLInsert(SL* ps, SLDateType x, int n)
{
assert(ps);
assert(n <= ps->size && n >= 0);
SLCheckCapacity(ps);
for (int i = ps->size; i > n; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[n] = x;
ps->size++;
}
//指定位置删除
void SLErase(SL* ps,int n)
{
assert(ps);
assert(n < ps->size && n >= 0);
for (int i = n; i <ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
4.顺序表完整代码
完整代码包含三个文件，其中一个头文件（.h），两个源文件(.c);分别为头文件SeqList.h，源文件SeqList.c和源文件text.c。
以下为完整代码：
SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define _CRT_SECURE_NO_WARNINGS
typedef int SLDateType;
typedef struct seqlist
{
SLDateType* arr;
int capacity; //空间大小
int size; //有效数据个数
}SL;
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//判断空间是否充足
void SLCheckCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDateType x);
//头插
void SLPushFront(SL* ps, SLDateType x);
//打印
void SLprint(SL* ps);
//尾删
void SLDeleteBack(SL* ps);
//头删
void SLDeleteFront(SL* ps);
//指定位置插入
void SLInsert(SL* ps, SLDateType x,int n);
//指定位置删除
void SLErase(SL* ps,int n);SeqList.c
#include "SeqList.h"
//初始化
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 SLCheckCapacity(SL * ps)
{
if (ps->size == ps->capacity)
{
int NewCapacit = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDateType* tmp =(SLDateType*)realloc(ps->arr, NewCapacit * sizeof(SLDateType));
if (tmp == NULL) //realloc返回的不为空，也就是扩容没成功时打印错误
{
perror("realloc fail!");
exit(-1);
}
ps->arr = tmp; //扩容成功则将扩容后的内存赋值给arr
ps->capacity = NewCapacit; //扩容后的空间大小重新赋值
}
}
//尾插
void SLPushBack(SL* ps, SLDateType x)
{
//断言
assert(ps);
//判断空间是否充足
SLCheckCapacity(ps);
//插入数据
ps->arr[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
//把所有数据向后挪动一位，第一位空出来
for (int i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i-1];
}
//把x赋值给第一位
ps->arr[0] = x;
ps->size++;
}
//打印
void SLprint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//尾删
void SLDeleteBack(SL* ps)
{
assert(ps);
assert(ps->size);//断言ps->size不为0
ps->size--;
}
//头删
void SLDeleteFront(SL* ps)
{
assert(ps);
assert(ps->size);//断言ps->size不为0
for (int i = 0; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//指定位置插入
void SLInsert(SL* ps, SLDateType x, int n)
{
assert(ps);
assert(n <= ps->size && n >= 0);
SLCheckCapacity(ps);
for (int i = ps->size; i > n; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[n] = x;
ps->size++;
}
//指定位置删除
void SLErase(SL* ps,int n)
{
assert(ps);
assert(n < ps->size && n >= 0);
for (int i = n; i <ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}text.c
#include "SeqList.h"
void SLtext()
{
//定义顺序表名
SL s;
//顺序表初始化
SLInit(&s);
//头插尾插
SLCheckCapacity(&s);
SLPushBack(&s, 4);
//SLprint(&s);
SLPushFront(&s,3);
//SLprint(&s);
SLPushBack(&s, 5);
//SLprint(&s);
SLPushFront(&s, 2);
//SLprint(&s);
SLPushBack(&s, 6);
//SLprint(&s);
SLPushFront(&s, 1);
//SLprint(&s);
SLDeleteBack(&s);
//SLprint(&s);
SLDeleteFront(&s);
//SLprint(&s);
//SLDestroy(&s);
指定插
//SLprint(&s);
//SLInsert(&s, 10, 1);
//SLprint(&s);
//SLInsert(&s, 22, 0);
//SLprint(&s);
//SLInsert(&s, 33, 6);
//SLprint(&s);
//SLDestroy(&s);
//指定删
SLprint(&s);
SLErase(&s,0);
SLprint(&s);
SLErase(&s, 2);
SLprint(&s);
SLDestroy(&s);
}
int main()
{
SLtext();
return 0;
}