【初阶数据结构与算法 3】顺序表（1）

顺序表

前言

本文开始学习新的内容，主要包括：

• 线性表
• 顺序表

例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。

1、线性表

• 线性表（linear list）是 n 个具有相同特性的数据元素的有限序列
• 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
• 线性表在逻辑上是线性结构，即连续的一条直线
• 线性表在物理结构上并不一定是连续的
• 线性表在物理上存储时，通常以数组和链式结构的形式存储

2、顺序表

2.1 定义

• 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储
• 在数组上完成数据的增删查改

2.2 静态顺序表

使用定长数组存储元素

#defineN200typedefint SLDataType;//给int类型起一个别名//静态顺序表typedefstructSeqList{
    SLDataType a[N];//静态数组不能改变大小，要么偏大，要么偏小int size;}SL;

2.3 动态顺序表

使用动态开辟的数组存储

#defineN200typedefint SLDataType;//给int类型起一个别名//动态顺序表typedefstructSeqList{
    SLDataType* a;//动态数组得指针int size;//数组当前存放数值的个数int capacity;//数组存储数值的最大个数}SL;

3、动态顺序表的实现

• 静态顺序表只适用于确定知道需要存多少数据的场景
• 静态顺序表的定长数组无法根据实际需求，动态调整数组的长度，因此现实中基本都是使用动态顺序表
• 动态顺序表可根据需要动态的分配空间大小

动态顺序表的实现功能有很多种，主要包括：

• 顺序表尾插、尾删、头插、头删、查找、在p目标位置插入数据、删除目标位置的值、销毁、打印

3.1 顺序表初始化

voidSLInit(SL* ps){//结构体数据初始化
    ps->a =NULL;//指针置空
    ps->size =0;//数组当前存放数值的个数
    ps->capacity =0;//数组存储数值的最大个数}

3.2 顺序表容量检查

//检查容量，是否能够存放新的数值，满了就扩容voidSLCheckCapacity(SL* ps){// 检查容量空间，满了扩容if(ps->size == ps->capacity){//需要扩容的量，最初是0，就扩容成4个，如果4个满了，则扩容一倍的量int newCapacity = ps->capacity ==0?4: ps->capacity *2;//SLDataType 是数据类型，有通用性
        SLDataType* tmp =(SLDataType*)realloc(ps->a, newCapacity *sizeof(SLDataType));if(tmp ==NULL){printf("realloc fail\n");//exit(-1);return;}
        ps->a = tmp;
        ps->capacity = newCapacity;//更新最新的容量大小}}

3.3 顺序表打印

voidSLPrint(SL* ps){for(int i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}

3.4 顺序表尾插

//尾插  插入目标的地址   要插入的数据voidSLPushBack(SL* ps, SLDataType x){SLCheckCapacity(ps);
    ps->a[ps->size]= x;//在最后位置插入
    ps->size++;//当前存储的数值个数 +1}

分5次插入数据，依次插入1 2 3 4 5，分析见下图：

3.5 顺序表头插

//头插  在数组前面插入数据，voidSLPushFront(SL* ps, SLDataType x){SLCheckCapacity(ps);//所有数据向后移动，从最后一个属开始移动int end = ps->size -1;while(end >=0){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[0]= x;
    ps->size++;}

分5次插入数据，依次插入1 2 3 4 5，分析见下图：

3.6 顺序表尾删

//尾删  在数组后面要删除的数据voidSLPopBack(SL* ps, SLDataType x){//方法1 先检查和是否越界assert(ps->size >0);
    ps->size--;//方法2/*if (ps->size == 0)
    {
        printf("SeqList is empty\n");
        return;
    }
    ps->size--;*///检查越界，在free的时候检查//SLDestroy(ps);}

3.7 顺序表头删

//头删  删除头部的数据voidSLPopFront(SL* ps){assert(ps->size >0);int begin =1;while(begin < ps->size){
        ps->a[begin -1]= ps->a[begin];
        begin++;}
    ps->size--;}

3.8 顺序表指定位置插入

SLInsert 也可以实现头插、尾插的功能：

//在指定位置插入数据voidSLInsert(SL* ps,int pos, SLDataType x){assert(ps);assert(pos >=0&& pos <= ps->size);SLCheckCapacity(ps);//移动数据int end = ps->size -1;while(end>=pos){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[pos]= x;
    ps->size++;}

3.9 顺序表指定位置删除

//删除指定位置的数据voidSLErase(SL* ps,int pos){assert(ps);assert(pos >=0&& pos <= ps->size);int begin = pos;while(begin<ps->size-1){
        ps->a[begin]= ps->a[begin +1];
        begin++;}
    ps->size--;}

3.10 顺序表查找指定数据

//查找数据intSLFind(SL* ps, SLDataType x){assert(ps);for(int i=0; i < ps->size; i++){if(ps->a[i]== x){return i;//返回下标}}return-1;//代表没找到数据}

3.11 顺序表修改指定位置的数据

//修改指定位置的数据voidSLModify(SL* ps,int pos, SLDataType x){assert(ps);assert(pos >=0&& pos <= ps->size);
    ps->a[pos]= x;}

总结

本文主要学习了动态顺序表，重点学习了顺序表尾插、尾删、头插、头删、查找、在目标位置插入数据、删除目标位置的值、销毁、打印等常用的功能。

这些功能的实现仍然是基于C语言阶段所学的知识。

在初阶数据结构与算法的阶段，要注重复习指针、数组、结构体、库函数、动态内存管理的知识点。

下一篇将继续巩固和复习顺序表的知识。