顺序表

概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。

顺序表实现

头文件

#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)
{//顺序表不为空，且有效数据个数不为0assert(ps && ps->size);--ps->size;
}

头删

时间复杂度O（n）

//头删
void SLTPopFront(SLT* ps)
{//顺序表不为空，且有效数据个数不为0assert(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);//查找元素,返回对应位置下标，没有返回-1int 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;
}