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

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

7 人参与  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）
  • 赞助本站

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

最新文章

  • 霜打青梅免费阅读全文，主角江月周霆小说
  • 霜打青梅江月周霆小说全文章节阅读
  • 抖音小说《景晴顾启江秋生》全集免费版在线阅读
  • 《儿子想要换妈妈，我成全他们献身祖国》赵安安赵凯最新章节在线阅读
  • 爱在灰烬里重燃小说(连载文)-徐穆瑶顾谨砚无广告阅读
  • [抖音]小说苏鸿运陈柏芝官场：从每天一个视频开始逆袭
  • 书荒必备《身处女尊，我倾尽所有只为活着》全文章节阅读
  • 新上《宁汐橙顾晏迟》宁汐橙小说免费阅读
  • 林见女姜恩赐完整版《我死后，极致厌女的姑姑遭报应了》全文最新阅读
  • (抖音小说)虞唯骆昀迟小说全文阅读免费
  • 刘景尘林七夜结局是什么 刘景尘林七夜免费阅读全文
  • 宋诗诗孟寻州《七零下乡美人成了大院竹马心尖宠》全文(宋诗诗孟寻州)章节免费阅读

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

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