数据结构(一) 顺序表 【超详细!】(文末附源码)

数据结构(一) 顺序表的定义及其基本操作

前言

在学习顺序表前，需了解线性表这一结构，顺序表的定义是这样写的：由零个或多个数据元素的有限序列。
线性表有多种实现方式，今天我们要了解的是实现最简单的顺序表

线性表的结构特征

一、顺序表的定义

线性表的顺序存储结构就是用一段地址连续的存储空间一次存储线性表的数据元素

顺序表的底层就是数组，进行结构上的包装就成了顺序表

顺序表结构特征

二、顺序表的分类

顺序表分两类：静态顺序表和动态顺序表

1.静态顺序表

#defineN100//静态顺序表structSeqList{intarr[N];intsize;//有效数据个数};

2.动态顺序表

typedefstructSeqList{SLDataType*arr;intsize;//有效数据个数intcapacity;//空间大小}SL;

大部分情况下我们会使用动态顺序表，静态顺序表的缺点明显数组开小了，空间不够用，数组开大了，空间浪费。而动态顺序表可随时开辟空间

仔细观察结构体我们会发现定义顺序表需要三个属性：
1.存储空间的起始位置：arr数组的首地址指针
2.当前线性表的长度：size
3.线性表的最大存储容量：即空间大小capacity

三.顺序表的基本操作

1.准备工作

和扫雷项目一样
我们用三个文件
1.Sqlist.h:头文件的是用来声明接口函数，定义顺序表并且把头文件集合起来
2.SqList.c:用来实现具体的接口函数
3.test.c:用于接口函数的测试工作

2.具体基本操作

需要实现的接口函数

//顺序表初始化voidSLInit(SL*ps);//顺序表的销毁voidSLDestroy(SL*ps);voidSLPrint(SL s);//头部插入删除 / 尾部插入删除voidSLPushBack(SL*ps,SLDataType x);voidSLPushFront(SL*ps,SLDataType x);voidSLPopBack(SL*ps);voidSLPopFront(SL*ps);//指定位置之前插入/删除数据voidSLInsert(SL*ps,intpos,SLDataType x);voidSLErase(SL*ps,intpos);intSLFind(SL*ps,SLDataType x);

2.1初始化

//初始化voidSLInit(SL*ps){ps->arr=NULL;ps->capacity=ps->size=0;}

2.2销毁

//销毁voidSLDestroy(SL*ps){if(ps->arr!=NULL){free(ps->arr);}ps->arr=NULL;ps->size=ps->capacity=0;}

2.3打印顺序表

//打印voidSLPrint(SL s){for(inti=0;i<s.size;i++){printf("%d ",s.arr[i]);}printf("\n");}

2.4头插/尾插

voidSLCheckCapacit(SL*ps){if(ps->size==ps->capacity){//用malloc realloc 继续申请intnewCapacity=ps->capacity==0?4:2*ps->capacity;SLDataType*tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataType));if(tmp==NULL){perror("realloc fail!");exit(1);//直接退出程序}ps->arr=tmp;//换成新空间ps->capacity=newCapacity;}}//尾插voidSLPushBack(SL*ps,SLDataType x){//在处理边界问题时，一定要assertassert(ps);//在插入前要检验空间是否够用，我们用SLCheckCapacity函数检验，若空间不够用就继续申请SLCheckCapacit(ps);ps->arr[ps->size++]=x;}//头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacit(ps);//将顺序表中的数据整体后移一位for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[0]=x;ps->size++;}

2.5头删/尾删

//尾删voidSLPopBack(SL*ps){assert(ps);assert(ps->size);//两种方式，第二种更直接//ps->arr[ps->size - 1] = -1;--ps->size;}//头删voidSLPopFront(SL*ps){assert(ps);assert(ps->size);//直接将数据前移一位，覆盖arr[0]for(inti=0;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}ps->size--;}

四.写在最后

顺序表就写到这，顺序表可随时找到数据元素但缺点也明显，下一篇我们会介绍链式存储形式~~
尽情期待