数据结构（初阶）（二）----顺序表
顺序表
概念与结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。
顺序表实现
头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SeqList
{
SLTDataType* arr;
int size;
int capacity;
}SLT;
//初始化
void SLTInit(SLT* slt);
//判断空间大小，如果不够增容
void SLTCheckCapacity(SLT* ps);
//尾插
void SLTPushBack(SLT* ps,SLTDataType x);
//打印顺序表
void SLTPrint(SLT* ps);
//头插
void SLTPushFront(SLT* ps, SLTDataType x);
//尾删
void SLTPopBack(SLT* ps);
//头删
void SLTPopFront(SLT* ps);
//查找元素,返回对应位置下标，没有返回-1
int SLTFind(SLT* ps, SLTDataType x);
//指定位置之前插入数据
void SLTInsert(SLT* ps, int pos, SLTDataType x);
//删除指定位置元素
void SLTErase(SLT* ps, int pos);
//销毁顺序表
void SLTDestory(SLT* ps);
创建与初始化
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
//初始化
void SLTInit(SLT* ps)
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
尾插
在插入之前我们需要先判断顺序表的空间大小是否足够，如果不够就需要对原有空间增容，判断依据是size == capacity,如果等式成立，那么空间就满了，需要增容。
增容，一般是成倍的增加，这里我们使用2倍的增容。
判断空间大小
//判断空间大小，如果不够增容
void SLTCheckCapacity(SLT* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
//注意在初始状态下，空间大小为0，需要判断给定初始空间
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//扩容有可能失败，需要创建新的指针来接收，成功后再赋给原数组
SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
if (tmp == NULL)
{
perrpr("SLTCheckCapacity()::realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//尾插
void SLTPushBack(SLT* ps,SLTDataType x)
{
assert(ps);
SLTCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
头插
//头插
void SLTPushFront(SLT* ps, SLTDataType x)
{
assert(ps);
SLTCheckCapacity(ps);
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
++ps->size;
}
尾删
时间复杂度为O（1）
//尾删
void SLTPopBack(SLT* ps)
{
//顺序表不为空，且有效数据个数不为0
assert(ps && ps->size);
--ps->size;
}
头删
时间复杂度O（n）
//头删
void SLTPopFront(SLT* ps)
{
//顺序表不为空，且有效数据个数不为0
assert(ps && ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
--ps->size;
}
查找
//查找元素,返回对应位置下标，没有返回-1
int SLTFind(SLT* ps, SLTDataType x)
{
assert(ps);
if (ps->size == 0)
{
return -1;
}
for(int i = 0;i < ps->size;i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
指定位置之前插入数据
//指定位置之前插入数据
void SLTInsert(SLT* ps, int pos, SLTDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
++ps->size;
}
指定位置删除数据
//删除指定位置元素
void SLTErase(SLT* 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;
}
销毁（回收）
//销毁顺序表
void SLTDestory(SLT* ps)
{
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
测试文件
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void test1()
{
SLT slt;
SLTInit(&slt);
//尾插
SLTPushBack(&slt,1);
SLTPushBack(&slt,2);
SLTPushBack(&slt,3);
SLTPushBack(&slt,4);
SLTPushBack(&slt,5);
头插
//SLTPushFront(&slt, 11);
//SLTPushFront(&slt, 12);
//SLTPushFront(&slt, 13);
//SLTPushFront(&slt, 14);
///尾删
//SLTPopBack(&slt);
//SLTPopBack(&slt);
//头删
//SLTPopFront(&slt);
//SLTPopFront(&slt);
//打印顺序表
SLTPrint(&slt);
//查找元素,返回对应位置下标，没有返回-1
int ret = SLTFind(&slt, 12);
printf("%d\n", ret);
指定位置之前插入数据
//SLTInsert(&slt, ret, 21);
//SLTInsert(&slt, ret, 22);
//删除指定位置元素
SLTErase(&slt, ret);
SLTErase(&slt, ret);
//打印顺序表
SLTPrint(&slt);
销毁顺序表
//SLTDestory(&slt);
}
int main()
{
test1();
return 0;
}
原文地址：https://blog.csdn.net/2401_88328558/article/details/145228380
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！