动态顺序表实现

动态顺序表

顺序表概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
分类：
一般分为静态顺序表和动态顺序表；
静态顺序表：数组大小是固定的用完了无法增容；同时我们无法控制给数组开多少空间合适，开少了，空间不够；开多了，有回会存在空间浪费；
动态顺序表：空间是可以变动的，空间满了我们就增容；解决了静态顺序表的空间不足问题，同时也在一定程度上减少了空间浪费；
因此本篇博客主要实现动态顺序表；（静态顺序表实现思路差不多，读者可以自行写一下😁😁😁）
动态顺序表数据结构：

基本操作

#pragmaonce#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<assert.h>typedefint SLDateType;typedefstructSeqList{
    SLDateType* a;//用于维护动态开辟的数组size_t size;//用于维护动态数组有多少个有效值size_t capacity;// size_t==unsigned int//用于维护当前动态数组有多少空间}SeqList;// 对数据的管理:增删查改 //初始化顺序表voidSeqListInit(SeqList* ps);//销毁顺序表voidSeqListDestroy(SeqList* ps);//显示顺序表voidSeqListPrint(SeqList* ps);//尾插voidSeqListPushBack(SeqList* ps, SLDateType x);//头插voidSeqListPushFront(SeqList* ps, SLDateType x);//头删voidSeqListPopFront(SeqList* ps);//尾删voidSeqListPopBack(SeqList* ps);// 顺序表查找intSeqListFind(SeqList* ps, SLDateType x);// 顺序表在pos位置插入xvoidSeqListInsert(SeqList* ps,size_t pos, SLDateType x);// 顺序表删除pos位置的值voidSeqListErase(SeqList* ps,size_t pos);

功能实现

#include"SeqList.h"staticvoidCheck_Capacity(SeqList* ps){if(ps->capacity == ps->size)//容量满了或者还没开辟空间{size_t NewCapacity =(ps->capacity ==0)?4: ps->capacity *2;int* tmp =(int*)realloc(ps->a, NewCapacity *sizeof(int));if(tmp ==NULL)exit(-1);
        ps->a = tmp;
        ps->capacity = NewCapacity;}}voidSeqListInit(SeqList* ps){assert(ps);
    ps->a =NULL;
    ps->capacity =0;
    ps->size =0;}voidSeqListDestroy(SeqList* ps){assert(ps);free(ps->a);
        ps->capacity =0;
        ps->size =0;}voidSeqListPrint(SeqList* ps){assert(ps);if(ps->size){int len = ps->size;for(int i =0; i <len; i++)printf("%d ", ps->a[i]);}elseprintf("NULL\n");}voidSeqListPushBack(SeqList* ps, SLDateType x){assert(ps);Check_Capacity(ps);//在插入数据之前要先检查一下是否还有剩余容量
    ps->a[ps->size]= x;
    ps->size++;}voidSeqListPushFront(SeqList* ps, SLDateType x){assert(ps);Check_Capacity(ps);int end = ps->size -1;for(end; end >=0; end--)
        ps->a[end +1]= ps->a[end];
    ps->a[end +1]= x;
    ps->size++;}voidSeqListPopFront(SeqList* ps){assert(ps);assert(ps->size>0);//都没元素了就不删了int begin =1;int len = ps->size;for(begin; begin < len; begin++)
        ps->a[begin -1]= ps->a[begin];
    ps->size--;}voidSeqListPopBack(SeqList* ps){assert(ps);assert(ps->size>0);
    ps->size--;}intSeqListFind(SeqList* ps, SLDateType x){assert(ps);assert(ps->size>0);int len = ps->size;for(int i =0; i < len; i++)if(ps->a[i]== x)return i;return-1;}voidSeqListInsert(SeqList* ps,size_t pos, SLDateType x){assert(ps);//如果pos给我乱传，超出合法范围?assert(pos<=ps->size);Check_Capacity(ps);int end = ps->size -1;int target = pos;for(; end >= target; end--)//这里会发生向上转换，最好把pos类型转换一下
        ps->a[end +1]= ps->a[end];
    ps->a[end+1]= x;
    ps->size++;}voidSeqListErase(SeqList* ps,size_t pos){assert(ps);assert(ps->size>0);//pos乱传?assert(pos<=ps->size);int begin = pos +1;int len = ps->size;for(; begin < len; begin++){
        ps->a[begin -1]= ps->a[begin];}
    ps->size--;}

程序运行