摘要:顺序表,顾名思义就是在内存上顺着往后排的。顺序表的代码实现好,废话不多说,我们来开始模拟实现顺序表语言版我们将会以项目工程和接口的形式来完成顺序表的实现。创建节点实际上就是创建一个结构体。
大家好,我是@jxwd,
开心学编程,学到无极限。
你还在数据结构的苦海中挣扎吗?
你难道还在抱着一本厚厚的数据结构书在那里硬啃吗?
你难道还是对于数据结构一无所措吗?
别急,因为~~~??
在未来的几个月里,我会为大家推出精品的数据结构文章。涵盖广、内容深。
如果你能够静下心来,看了我的文章以后,你会发现,课本就是一本小说。???
我在未来还会给大家推出视频,用视频的方式讲解。
想要了解我的视频,以及我的文章,那就持续关注我,订阅专栏《完全自学数据结构与算法和C++》吧??
你知道什么叫顺序表吗?
据说,它长这样:
然而,实际上,它就是一个数组。
( 注:我们本节只讨论顺序表,对于链表和以及其循环链表我们都将会拿出专门的一个章节去讲解。)
顺序表,顾名思义就是(在内存上)顺着往后排的。
其实说白了,千言万语一句话,它几乎就是一个数组。
目录
本节我们将介绍:
(1)创建3个文件:SeqList.h SeqList.c mock.c
void SeqListInit(SeqList* pq);
void SeqListDestory(SeqList* pq);
void SeqListPrint(SeqList* pq);
void SeqCheckCapacity(SeqList* pq);
void SeqListPushBack(SeqList* pq, SeqDataType x);
void SeqListPushFront(SeqList* pq, SeqDataType x);
void SeqListPopBack(SeqList* pq);
void SeqListPopFront(SeqList* pq);
int SeqListFind(SeqList* pq, SeqDataType x);
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);
void SeqListErase(SeqList* pq, int pos);
void SeqListModify(SeqList* pq, int pos, SeqDataType x);
简而言之,就是用一段地址连续的存储单元依次存储数据的线性结构。
如图:
简而言之一句话,类比数组就行,和数组的存储方式几乎一模一样。
1、空间连续;
2、缺点:在中间或前面部分的插入删除时间复杂度为O(n),增容的代价比较大;3、优点:支持随机访问;更适合频繁访问第n个元素的场景。
好,废话不多说,我们来开始模拟实现顺序表(C语言版)
我们将会以项目工程和接口的形式来完成顺序表的实现。
很多童鞋说VS太大,用的不多,那好,我今天就用vscode来为大家展示(当然vscode的优势不在这里)
前提是大家要会vscode的多文件编译。
我们接下来的操作,会在这三个文件当中去切换。
当然,我会为大家标注出切换到何处了。
好,我们正式开始。
实际上就是创建一个结构体。
首先,在SeqList.h中:
//SeqList.h#pragma once//防止头文件被重复引用#include#include#includetypedef int SeqDataType;//将int 重命名一下,这样我们以后如果存储的不是int类型, 就可以直接在这里改一下就可以了typedef struct SeqList //创建一个结构体,作为顺序表的一个节点{ SeqDataType* a; //一个指针(或者叫数组),用来存放数据 size_t capacity; //顺序表的总容量 size_t size; //顺序表的总大小}SeqList; //同样的道理,我们重命名一下,这样以后的书写中,就不用带上struct了
视图效果:
那么接下来,我们将依次实现下面这些接口:
这些接口分别是:
增、删、查、改、打印、初始化、销毁等等
概览一下:
具体分析如下:
//SeqList.h#pragma oncetypedef 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
别着急,接下来,我们将一个一个实现。
初始化函数,简而言之,我们想要它能够将我的这个顺序表初始化(就什么数据也不给,最最开始的时候)
具体的作用见下:
//SeqList.c#include "SeqList.h"void SeqListInit(SeqList* pq){ assert(pq); //断言一下,防止pq本身是个空指针 pq->a = NULL; //将a置为空 pq->capacity = pq->size = 0; //将容量和大小都置为0}
接下来,
因为我们的内存空间是动态开辟的,所以用完以后,我们需要手动销毁
我们想用它将整个顺序表销毁,它是这样的:
具体分析见下:
//SeqList.cvoid SeqListDestory(SeqList* pq){ assert(pq); //同样的道理,断延一下,防止pq为空 free(pq); //将pq free掉。 (后面在我们创建时会知道,pq实际上是动态开辟出来的) pq->a = NULL; //将a弄为空 pq->capacity = pq->size = 0; //容量和大小都变成0}
很简单,就是将列表中的数据打印出来。(假设都是整形)
这个还是比较容易理解的,就是一个for循环搞定的事情:
//SeqList.cvoid SeqListPrint(SeqList* pq){ assert(pq); for(int i =0;i < pq->size;i++) { printf("%d ",pq->a[i]); } printf("/n"); //为了使下一次打印的时候能够换行}
来整体感受一下代码之美:
我们继续
检测容量,如果不够要扩容(假如我们以二倍扩容)
解析如下:
//SeqList.cvoid 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 }}
那么如果我们有了上面的接口,实现插入就是比较简单的了。
来看尾插:
//SeqList.cvoid SeqListPushBack(SeqList* pq, SeqDataType x){ assert(pq); //断延 SeqCheckCapacity(pq); //检测容量是否够我插入的,不够则要自动扩容 pq->a[pq->size++] = x; //在a[pq->size]的位置插入x,插入完之后size++}
继续:
//SeqList.cvoid 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中来去创建一个这样一个顺序表:
(就像这样)
那么我们让程序运行,得到如下的结果:
可以看到,我们成功了。它按照我们的方式,打印了我们所需要的数据。
好,我们继续:
//SeqList.cvoid SeqListPopBack(SeqList* pq){ assert(pq); //断延 assert(pq->size>0); //断延 pq->size--; //size减一}
这个其实比较简单。
下一个:
//SeqList.cvoid SeqListPopFront(SeqList* pq) //头删{ assert(pq); //断延 assert(pq->size > 0); //断延 for(int i =0;isize -1;i++) //将所有后面的元素依次前移 { pq->a[i] = pq->a[i+1]; } pq->size--; //size减1}
继续,
下面的是查找一个元素:
如果找到我们想要的元素,那么我们就返回这个元素所在的下标。否则,返回-1。
//SeqList.cint SeqListFind(SeqList* pq, SeqDataType x){ assert(pq); //断延 int end = 0; //标记一个位置 while(endsize) { if(pq->a[end]==x)return end; //如果找到,则返回下标 else end++; } return -1; //如果没找到,则返回-1}
在pos元素后面插入一个元素x:
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++;}
删除下标为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}
void SeqListModify(SeqList* pq, int pos, SeqDataType x){ assert(pq); assert(pq->size>pos); //两次断延 pq->a[pos] = x; //直接将下标为pos的元素改为x}
好,现在我们就将所有的接口全部写完了。
我们再来玩玩看:
在mock.c中打入:
运行结果:
我们可以看到,我们成功了。
好啦,
本章的内容,我们就到这里啦,
关注我@jxwd,订阅专栏《完全自学数据结构与算法和C++》,
就能看到我后期出的视频和文章啦~~~~~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/125326.html
摘要:前言实时音视频,正处在时代的风口上。音视频的应用越来越广泛,特别是移动端的音视频应用,包括短视频音视频直播音视频通话等移动端的音视频开发需求也会非常大。作为一名移动开发者,学习和了解音视频开发也是非常必要的。 ...
摘要:即服务提供者目前正在处理的请求数一个请求对应一条连接最少,表明该服务提供者效率高,单位时间内可处理更多的请求。此时应优先将请求分配给该服务提供者。初始情况下,所有服务提供者活跃数均为。 1.简介 LoadBalance 中文意思为负载均衡,它的职责是将网络请求,或者其他形式的负载均摊到不同的机器上。避免集群中部分服务器压力过大,而另一些服务器比较空闲的情况。通过负载均衡,可以让每台服务...
摘要:摘要今天我带来的分享是系统观测工具,有所关联但不涉及自身的这样一个话题。所以今天我想向大家介绍的是四部分内容慢的诊断思系统观测工具介绍脚本集使用举例使用方法限制第一部分,我们向大家介绍一下常规的诊断慢的思路,也是业界的常规思路。 本文根据黄炎在2018年8月3日在【2018 MySQL技术交流大会 · 上海站】现场演讲内容整理而成。 showImg(https://segmentfau...
摘要:因此,对音视频人才的需求也从小众变成了大众,这更多的是大家对未来市场的预期导致的结果。做个勤奋向上的人,加紧学习,抓住中心,宁精勿杂,宁专勿多。 前言 如今音视频的...
摘要:深入研究捕获外部变量和实现原理掘金前言是语言的扩充功能,而在和中引入了这个新功能。是由和两位大神在对的开发过程中中所有变换操作底层实现分析上掘金前言在上篇文章中,详细分析了是创建和订阅的详细过程。 深入研究Block捕获外部变量和__block实现原理 - 掘金 前言 Blocks是C语言的扩充功能,而Apple 在OS X Snow Leopard 和 iOS 4中引入了这个新功能B...
阅读 3310·2023-01-11 11:02
阅读 3876·2023-01-11 11:02
阅读 2715·2023-01-11 11:02
阅读 4892·2023-01-11 11:02
阅读 4396·2023-01-11 11:02
阅读 5105·2023-01-11 11:02
阅读 4888·2023-01-11 11:02
阅读 3362·2023-01-11 11:02