当前位置：首页 » 《随便一记》 » 正文

数算部分第二节——顺序表（C语言实现+思路分析+源码分析+运行）_xdnxl的博客

23 人参与  2022年04月21日 17:40  分类 : 《随便一记》  评论

点击全文阅读


大家好，我是@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++》，

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


点击全文阅读


本文链接：http://zhangshiyu.com/post/38654.html

接口  顺序  用于  
<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 林柒薇宋延桉小说全文免费阅读穿到八零年代和司令丈夫离婚那天全文免费阅读
  • 好看的妻子嫁作他人妇，我和女儿不认小说-妻子嫁作他人妇，我和女儿不认最新章节阅读
  • 《七零：那两口子万人嫌，太发癫了》完整版-盛春香裴清远在线全文阅读
  • 最新小说被山里糙汉追着满地跑主角闵小小闵烨全文在线阅读
  • 李慕云陶金辉全文小说最新章节阅读李慕云陶金辉
  • 《看到三十年后的联姻生活，我决定离婚》颜雯程绛-小说txt全文阅读
  • 长公主她风华正茂无弹窗在线阅读
  • 你敢说话，我就敢质疑主角是李云初张景小说百度云全文完整版阅读
  • 娶资助的贫困生当晚，她和竹马一起入洞房小说(完结)-安枫符垚无删减阅读
  • 心机女插足后，她和相亲对象闪婚了（全本）姜初棠夏芝芝完整章节列表免费阅读
  • 被撞流产后，我选择离婚小说百度云完整章节列表免费阅读
  • 沈糯周钦然《老公白月光在我家别墅养胎》全章节免费阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1