数算部分第二节——顺序表(C语言实现+思路分析+源码分析+运行)

Source

大家好,我是@jxwd,

开心学编程,学到无极限。

你还在数据结构的苦海中挣扎吗?

你难道还在抱着一本厚厚的数据结构书在那里硬啃吗?

你难道还是对于数据结构一无所措吗?

别急,因为~~~👇👇

在未来的几个月里,我会为大家推出精品的数据结构文章。涵盖广、内容深。

如果你能够静下心来,看了我的文章以后,你会发现,课本就是一本小说。🐎🐎😀

我在未来还会给大家推出视频,用视频的方式讲解。

想要了解我的视频,以及我的文章,那就持续关注我,订阅专栏《完全自学数据结构与算法和C++》吧😀😀

你知道什么叫顺序表吗?

据说,它长这样:

 

 然而,实际上,它就是一个数组。

( 注:我们本节只讨论顺序表,对于链表和以及其循环链表我们都将会拿出专门的一个章节去讲解。)

顺序表,顾名思义就是(在内存上)顺着往后排的。

其实说白了,千言万语一句话,它几乎就是一个数组。

目录

本节我们将介绍:

顺序表的有关概念

顺序表的特点

顺序表的代码实现:

编译环境:gcc;编辑器:vscode

(1)创建3个文件:SeqList.h  SeqList.c  mock.c  

(2)创建节点

(3)具体实现:

1、初始化列表

void SeqListInit(SeqList* pq);  

//接口1:初始化列表(函数)

2、销毁列表

void SeqListDestory(SeqList* pq);

//接口2: 用于销毁列表

3、打印列表

void SeqListPrint(SeqList* pq);  

 //接口3:用于打印列表

4、计算容量函数

void SeqCheckCapacity(SeqList* pq);

//接口4:用于计算列表的容量

5、尾插

void SeqListPushBack(SeqList* pq, SeqDataType x);

//接口5:用于在顺序表的尾部增加数据

6、头插

void SeqListPushFront(SeqList* pq, SeqDataType x);  

//接口6:用于在顺序表的前面增加数据

7、尾删

void SeqListPopBack(SeqList* pq);   

//接口7:用于尾删

8、头删

void SeqListPopFront(SeqList* pq);    

//接口8:用于头删

9、查找

int SeqListFind(SeqList* pq, SeqDataType x);        

//接口9:查找某个元素

10、插入(任意位置)

void SeqListInsert(SeqList* pq, int pos, SeqDataType x);

 //接口10:在pos的后面插入一个数据 

11、删除

void SeqListErase(SeqList* pq, int pos);  

//接口11:删除pos位置的数据

12、修改

void SeqListModify(SeqList* pq, int pos, SeqDataType x);

 //接口12:将在pos位置的数据修改为x


顺序表的有关概念

简而言之,就是用一段地址连续的存储单元依次存储数据的线性结构。

如图:

简而言之一句话,类比数组就行,和数组的存储方式几乎一模一样。 

顺序表的特点:

1、空间连续;


2、缺点:在中间或前面部分的插入删除时间复杂度为O(n),增容的代价比较大;

3、优点:支持随机访问;更适合频繁访问第n个元素的场景。

顺序表的代码实现:

好,废话不多说,我们来开始模拟实现顺序表(C语言版)

我们将会以项目工程和接口的形式来完成顺序表的实现。

编译环境:gcc;编辑器:vscode

很多童鞋说VS太大,用的不多,那好,我今天就用vscode来为大家展示(当然vscode的优势不在这里)

前提是大家要会vscode的多文件编译。

(1)创建3个文件:SeqList.h  SeqList.c  mock.c  

        

 我们接下来的操作,会在这三个文件当中去切换。

当然,我会为大家标注出切换到何处了。

好,我们正式开始。

(2)创建节点

实际上就是创建一个结构体。

首先,在SeqList.h中:

 

//SeqList.h

#pragma once//防止头文件被重复引用

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SeqDataType;//将int 重命名一下,这样我们以后如果存储的不是int类型,
                          就可以直接在这里改一下就可以了


typedef struct SeqList  //创建一个结构体,作为顺序表的一个节点
{
    SeqDataType* a;     //一个指针(或者叫数组),用来存放数据
    size_t capacity;    //顺序表的总容量
    size_t size;        //顺序表的总大小
}SeqList;              //同样的道理,我们重命名一下,这样以后的书写中,就不用带上struct了

 视图效果:

 那么接下来,我们将依次实现下面这些接口:

这些接口分别是:

增、删、查、改、打印、初始化、销毁等等

概览一下:

具体分析如下:

//SeqList.h

#pragma once
typedef int SeqDataType;
typedef struct SeaqList
{
    int* a;
    int capacity;
    int size;
}SeaqList;


void SeqListInit(SeqList* pq);     //接口1:用于初始化列表
void SeqListDestory(SeqList* pq);  //接口2:用于销毁列表
void SeqListPrint(SeqList* pq);    //接口3:用于打印列表
void SeqCheckCapacity(SeqList* pq);//接口4:用于计算列表的容量,判断是否需要增容
void SeqListPushBack(SeqList* pq, SeqDataType x); //接口5:用于在顺序表的尾部增加数据
void SeqListPushFront(SeqList* pq, SeqDataType x);  //接口6:用于在顺序表的前面增加数据
void SeqListPopBack(SeqList* pq);                   //接口7:用于尾删
void SeqListPopFront(SeqList* pq);                  //接口8:用于头删
int SeqListFind(SeqList* pq, SeqDataType x);        //接口9:查找某个元素
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);  //接口10:在pos的后面插入一个数据
void SeqListErase(SeqList* pq, int pos);   //接口11:删除在pos位置的一个数据
void SeqListModify(SeqList* pq, int pos, SeqDataType x);  //接口12:将在pos位置的数据修改为x

别着急,接下来,我们将一个一个实现。

(3)具体实现:

1、初始化列表

void SeqListInit(SeqList* pq);  

//接口1:初始化列表(函数)

初始化函数,简而言之,我们想要它能够将我的这个顺序表初始化(就什么数据也不给,最最开始的时候)

 具体的作用见下:

//SeqList.c

#include "SeqList.h"
void SeqListInit(SeqList* pq)
{
    assert(pq);          //断言一下,防止pq本身是个空指针
    pq->a = NULL;        //将a置为空
    pq->capacity = pq->size = 0;   //将容量和大小都置为0
}

接下来,

2、销毁列表

void SeqListDestory(SeqList* pq);

//接口2: 用于销毁列表

因为我们的内存空间是动态开辟的,所以用完以后,我们需要手动销毁

我们想用它将整个顺序表销毁,它是这样的:

具体分析见下:

//SeqList.c


void SeqListDestory(SeqList* pq)
{
    assert(pq);              //同样的道理,断延一下,防止pq为空
    free(pq);                //将pq  free掉。
                               (后面在我们创建时会知道,pq实际上是动态开辟出来的)
    pq->a = NULL;           //将a弄为空
    pq->capacity = pq->size = 0;   //容量和大小都变成0
}

3、打印列表

void SeqListPrint(SeqList* pq);  

 //接口3:用于打印列表

很简单,就是将列表中的数据打印出来。(假设都是整形)

这个还是比较容易理解的,就是一个for循环搞定的事情:


//SeqList.c

void SeqListPrint(SeqList* pq)
{
    assert(pq);
    for(int i =0;i < pq->size;i++)
    {
        printf("%d ",pq->a[i]);
    }
    printf("\n");           //为了使下一次打印的时候能够换行
}

 来整体感受一下代码之美:

我们继续

4、计算容量函数

void SeqCheckCapacity(SeqList* pq);

//接口4:用于计算列表的容量

检测容量,如果不够要扩容(假如我们以二倍扩容)

解析如下: 

//SeqList.c


void SeqCheckCapacity(SeqList* pq)
{
    assert(pq);                   //断延一下
    if(pq->size == pq->capacity)  //判断,如果二者相等,问你就要进行扩容
    {
        int NewCapacity = pq->capacity == 0 ? 4 : pq->capacity*2;   
        //如果原来的容量为0,那么就规定增至4,否则,扩容至原容量的二倍

        SeqDataType* NewA = (SeqDataType*)realloc(pq->a, sizeof(SeqList)*NewCapacity);
        //动态开辟一块这么大的空间

        if(NewA == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }//对是否开辟成功进行检测

        pq->a = NewA;       //将新的地址赋给a
        pq->capacity = NewCapacity;  //新的容量赋给capacity
    }
}

那么如果我们有了上面的接口,实现插入就是比较简单的了。

来看尾插:

5、尾插

void SeqListPushBack(SeqList* pq, SeqDataType x);

//接口5:用于在顺序表的尾部增加数据

//SeqList.c


void SeqListPushBack(SeqList* pq, SeqDataType x)
{
    assert(pq);             //断延
    SeqCheckCapacity(pq);   //检测容量是否够我插入的,不够则要自动扩容 
    pq->a[pq->size++] = x;  //在a[pq->size]的位置插入x,插入完之后size++
}

 

继续:

6、头插

void SeqListPushFront(SeqList* pq, SeqDataType x);  

//接口6:用于在顺序表的前面增加数据

//SeqList.c

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
    assert(pq);                    //断延
    SeqCheckCapacity(pq);          //容量检测,容量不够要扩容
    int end = pq->size;            //标记size位置
    while(end)                     //将顺序表中所有元素循环右移一位
    {
        pq->a[end] = pq->a[end-1];
        end--;
    }
    pq->a[0] = x;                 //把x的值给第一位
    pq->size++;                   //值加一
}

那么接下来,我们可以来玩玩试试看了。

我们在mock.c中来去创建一个这样一个顺序表:

(就像这样) 

那么我们让程序运行,得到如下的结果:

可以看到,我们成功了。它按照我们的方式,打印了我们所需要的数据。

好,我们继续:

7、尾删

void SeqListPopBack(SeqList* pq);   

//接口7:用于尾删

//SeqList.c

void SeqListPopBack(SeqList* pq)
{
    assert(pq);                    //断延
    assert(pq->size>0);            //断延    
    pq->size--;                    //size减一
}

这个其实比较简单。 

下一个:

8、头删

void SeqListPopFront(SeqList* pq);    

//接口8:用于头删

//SeqList.c


void SeqListPopFront(SeqList* pq)    //头删
{ 
    assert(pq);                      //断延
    assert(pq->size > 0);            //断延
    for(int i =0;i<pq->size -1;i++)  //将所有后面的元素依次前移
    {
        pq->a[i] = pq->a[i+1];
    }
    pq->size--;                     //size减1
}

继续,

9、查找

下面的是查找一个元素:

int SeqListFind(SeqList* pq, SeqDataType x);        

//接口9:查找某个元素

如果找到我们想要的元素,那么我们就返回这个元素所在的下标。否则,返回-1。

//SeqList.c
int SeqListFind(SeqList* pq, SeqDataType x)
{
    assert(pq);                          //断延
    int end = 0;                         //标记一个位置
    while(end<pq->size)                  
    {   
        if(pq->a[end]==x)return end;     //如果找到,则返回下标
        else end++;
    }
    return -1;                         //如果没找到,则返回-1
}

10、插入(任意位置)

在pos元素后面插入一个元素x:

void SeqListInsert(SeqList* pq, int pos, SeqDataType x);

 //接口10:在pos的后面插入一个数据 

void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
    assert(pq);
    assert(pos < pq->size);              //断延
    SeqCheckCapacity(pq);                //检测容量大小,是否需要扩容
    int end = pq->size - 1;              //找到这个列表中最后一个元素的下标
    while(end>=pos)                     
    {                                    
        pq->a[end+1] = pq->a[end];      //将在pos前面的元素依次左移
        end--;                          
    }
    pq->a[pos] = x;                     //将在pos的位置赋值给x
    pq->size++;
}


 

11、删除

删除下标为pos的元素:

void SeqListErase(SeqList* pq, int pos);  

//接口11:删除pos位置的数据

void SeqListErase(SeqList* pq, int pos)
{
    assert(pq);      
    assert(pos < pq->size && pos > 0);             //两次断延
    int del = pos;                                 //标记pos位置
    while(del < pq->size - 1)                      
    {
        pq->a[del] =pq->a[del+1];                  //将pos后面的元素依次左移
        del++;
    }
    pq->size--;                                   //size减1
}

12、修改

void SeqListModify(SeqList* pq, int pos, SeqDataType x);

 //接口12:将在pos位置的数据修改为x

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
    assert(pq);
    assert(pq->size>pos);                 //两次断延
    pq->a[pos] = x;                       //直接将下标为pos的元素改为x
}

好,现在我们就将所有的接口全部写完了。

我们再来玩玩看:

在mock.c中打入:

 运行结果:

 我们可以看到,我们成功了。

好啦,

本章的内容,我们就到这里啦,

关注我@jxwd,订阅专栏《完全自学数据结构与算法和C++》,

就能看到我后期出的视频和文章啦~~~~~