速通数据结构第二站 顺序表

2024-03-26 06:20
文章标签 数据结构 顺序 速通 第二站

本文主要是介绍速通数据结构第二站 顺序表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

速通数据结构与算法系列

1 速通数据结构与算法第一站 复杂度        http://t.csdnimg.cn/sxEGF

感谢佬们支持！

目录

系列文章目录

  • 前言
  • 一、顺序表
  •       0 结构体
  •       1 接口声明
  •       2 初始化和销毁
  •       3 扩容函数
  •       4 打印和判空
  •       5 尾插
  •       6 尾删
  •       7 头插
  •       8 头删
  •       9 查找
  •      10insert （指定位置下一个插入）
  •      11erase  （删除指定位置）
  •      12完整代码
  • 二、顺序表OJ
  •       1 移除元素
  •       2 删除有序数组中的重复项
  •       3 合并两个有序数组
  • 总结

前言

           我们要接触到的第一种数据结构类型是线性表，线性表的定义是n个具有相同特性的数据元素的有限序列。常见的有：顺序表，链表，栈，队列，字符串……

线性表的逻辑结构是线性的，即一条连续的直线，但是其物理结构不一定是连续的，在物理上一般为数组和链式。

在这里我们要先区分一个概念：逻辑结构和物理结构

逻辑结构是一个抽象的结构，是我们研究某种东西时为了便于理解的一种归纳的思想

而物理结构则是真实的存储结构

举个例子来看，磁盘是什么结构？我们拿到一个磁盘会发现它是扇形的，他存储单元是一个个扇区，倘若我们把这些扇形一个个拉直，最后得到一条线，所以它的逻辑结构就是线性表

--》

一、顺序表

顺序表是用一段物理连续存储单元依次存储数据元素的线性结构，一般采用数组存储，利用数组来完成增删查改操作。

我们来浅浅实现一波，先创3个文件：test.c  sqlist.c   sqlist.h

在sqlist.h下……

为了达到C语言版的所谓泛型，模板，我们设一个宏

typedef int SLDataType;

我们先来写它的结构体

结构体


typedef struct sqlist
{SLDataType* a;//数据个数int size;//容量int capacity;
}SL;

注意：在STL的实现中，vector的结构体成员（成员变量）有3个，int* start,int* end,int* endofstorage三个指针（迭代器，此处先暂且认为是int*类型），对应关系为

start=_a;
finish=_a+_size;
endofstorage=_a+capacity;

这样设计的好处就是，当我们swap（vector1,vector2）时；成本将非常低，因为只需交换3个指针而已。

为了方便我们之后STL的学习，我们接口的命名风格都按STL的来

我们在seqlist.h中包一下需要用到的头文件，

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

接口声明

并声明如下接口

//打印函数
void SeqListPrint(SL* ps);//扩容函数
void BuyListNode(SL* ps);//初始化
void SeqListInit(SL* ps);//销毁
void SeqListDestroy(SL* ps);//判空
bool SeqListCheckCapacity(SL* ps);//尾插
void SeqListPushBack(SL* ps, SLDataType x);//尾删
void SeqListPopBack(SL* ps);//头插
void SeqListPushFront(SL* ps, SLDataType x);//头删
void SeqListPopFront(SL* ps);//查找 找到了返回下标，没找到返回-1 
int SeqListFind(SL* ps, SLDataType x);//指定pos位置后插
void SeqListInsert(SL* ps, SLDataType x, int pos);//指定pos位置删
void SeqListErase(SL* ps, int pos);

初始化和销毁

考虑到动态内存泄漏的问题，我们先来实现初始化及其销毁函数

要做的事很简单，初始化时指针置空，size和capacity给个0即可

(其中要注意判空ps，因为我们不知道不知道传入的ps是否为空)

//初始化
void SeqListInit(SL* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->size = 0;
}//销毁
void SeqListDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a=NULL;ps->capacity = ps->size = 0;}

扩容函数

为了便于调用，我们封装出一个扩容函数来

由于刚开始容量为0，我们第一次给4，之后进行二倍扩容

（二倍扩容采用的是SGI STL的扩容策略）

//扩容函数
void BuyListNode(SL* ps)
{assert(ps);//0就给4，不是就给capacity2倍int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//扩容失败if (NULL == tmp){printf("realloc fail");exit(-1);}//扩容成功ps->a = tmp;ps->capacity = newcapacity;
}

我们简单地来测试一下

SL sl;SeqListInit(&sl);SeqListDestroy(&sl);

（确实挺不错的）

打印和判空

下来我们再写个简单的打印和判空

打印就简单了，遍历打印；判空的逻辑就是size是否等于0

//打印函数
void SeqListPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}
}
//判空
bool SeqListCheckCapacity(SL* ps)
{assert(ps);return ps->size == 0;
}

 接下来就该是顺序表核心的插入删除操作了

尾插

我们先来进行尾插，尾插简单，在数组的最后插就行了，顺便更新一下size

注意：在插之前，我们先要考虑是否需要扩容的问题

void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);//考虑扩容if (ps->capacity == ps->size){BuyListNode(ps);}//插ps->a[ps->size] = x;ps->size++;
}

另外 我们知道，此时的扩容并非在数组后面直接扩容，而是再开一块空间，并将原来的数据拷过来，并释放原空间，在STL的学习中会有所谓迭代器失效的问题，因为之前的空间没了

所以指向之前空间的迭代器就会失效，我们不能用了，但是在C语言中，这种场景则不太容易碰到。

尾删

尾删就更简单了，我们直接--size即可，但是我们需要断言一下size>0

//尾删
void SeqListPopBack(SL* ps)
{assert(ps);//断言一下size，size要大于0assert(ps->size > 0);ps->size--;}

显然，我们发现，尾插，尾删的时间复杂度都是O（1）的。

我们来测试一下尾插和尾删

SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPrint(&sl);printf("\n");SeqListPopBack(&sl);SeqListPushBack(&sl, 5);SeqListPrint(&sl);

 

（没问题）

下来就是有点麻烦的头插和头删了

头插

头插的逻辑是这样的，我们需要讲数组往后挪一格，再在第一个位置做插入

-》

其中这个挪就有意思了，是从前往后挪还是从后往前挪呢?

当然是从后往前挪，不然会覆盖数据

//头插
void SeqListPushFront(SL* ps, SLDataType x)
{assert(ps);//考虑扩容if (ps->capacity == ps->size){BuyListNode(ps);}//插//从后往前挪数据int len = ps->size-1;while (len>=0){ps->a[len+1] = ps->a[len];--len;}ps->a[0] = x;ps->size++;}

头删

头删也需要挪动数据，不过和头插恰好相反，他需要从前往后开始挪

//头删
void SeqListPopFront(SL* ps)
{assert(ps);//挪数据int len = 0;while (len <= ps->size - 1){ps->a[len] = ps->a[len + 1];++len;}ps->size--;
}

显然，头插和头删的时间复杂度都是O（n），所以精明的STL并没有单独提供头插头删操作

我们再来简单的测试一下

SL s2;SeqListInit(&s2);SeqListPushFront(&s2, 1);SeqListPushFront(&s2, 2);SeqListPushFront(&s2, 3);SeqListPushFront(&s2, 4);SeqListPrint(&s2);printf("\n");SeqListPopFront(&s2);

（同样没有任何问题）

查找

下来我们写一下查找

查找的逻辑很简单，遍历数组，找到了返回下标，没找到返回-1

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

 查找是为之后的两个函数服务的：insert 和erase

因为在实际运用时，我们一般都是先找到某个元素，再插入/删除

我们写的是删除指定位置和在指定位置的下一个插入

（STL提供的是删除指定位置和指定位置前一个插入）

 写过了之前的头删，写这个insert就简单了

insert

我们依然需要从后往前插的方式，而且在之前需要判断一下pos的合法性

//指定pos位置后插
void SeqListInsert(SL* ps, SLDataType x, int pos)
{assert(pos>=0&&pos <= ps->size);//考虑扩容if (ps->capacity == ps->size){BuyListNode(ps);}//挪动数据int len = ps->size;while (len-pos+1){ps->a[len + 1] = ps->a[len];--len;}ps->a[pos + 1] = x;++ps->size;
}

erase同理

erase 

//指定pos位置删
void SeqListErase(SL* ps,  int pos)
{assert(pos>=0&&pos <= ps->size);//pos+1往前挪int len = ps->size-1;while (len-pos){ps->a[len-1] = ps->a[len];len--;}--ps->size;
}

我们再来简单的测试一下

SL s3;SeqListInit(&s3);SeqListPushBack(&s3, 1);SeqListPushBack(&s3, 2);SeqListPushBack(&s3, 3);SeqListPushBack(&s3, 4);SeqListPushBack(&s3, 5);SeqListPrint(&s3);printf("\n");int pos=SeqListFind(&s3,4);printf("%d\n", pos);//SeqListInsert(&s3, 7, pos);SeqListPrint(&s3);printf("\n");SeqListInsert(&s3, 8, pos);SeqListInsert(&s3, 9, pos);SeqListErase(&s3, pos);SeqListPrint(&s3);

 

12 完整代码

 sqlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int SLDataType;typedef struct sqlist
{SLDataType* a;//数据个数int size;//容量int capacity;
}SL;//打印函数
void SeqListPrint(SL* ps);//扩容函数
void BuyListNode(SL* ps);//初始化
void SeqListInit(SL* ps);//销毁
void SeqListDestroy(SL* ps);//判空
bool SeqListCheckCapacity(SL* ps);//尾插
void SeqListPushBack(SL* ps, SLDataType x);//尾删
void SeqListPopBack(SL* ps);//头插
void SeqListPushFront(SL* ps, SLDataType x);//头删
void SeqListPopFront(SL* ps);//查找 找到了返回下标，没找到返回-1 
int SeqListFind(SL* ps, SLDataType x);//指定pos位置后插
void SeqListInsert(SL* ps, SLDataType x, int pos);//指定pos位置删
void SeqListErase(SL* ps, int pos);

sqlist.c

#include "seqlist.h"//初始化
void SeqListInit(SL* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->size = 0;
}//销毁
void SeqListDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;}//扩容函数
void BuyListNode(SL* ps)
{assert(ps);//0就给4，不是就给capacity2倍int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//扩容失败if (NULL == tmp){printf("realloc fail");exit(-1);}//扩容成功ps->a = tmp;ps->capacity = newcapacity;
}//打印函数
void SeqListPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}
}void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);//考虑扩容if (ps->capacity == ps->size){BuyListNode(ps);}//插ps->a[ps->size] = x;ps->size++;
}//尾删
void SeqListPopBack(SL* ps)
{assert(ps);//断言一下size，size要大于0assert(ps->size > 0);ps->size--;}//头插
void SeqListPushFront(SL* ps, SLDataType x)
{assert(ps);//考虑扩容if (ps->capacity == ps->size){BuyListNode(ps);}//插//从后往前挪数据int len = ps->size - 1;while (len >= 0){ps->a[len + 1] = ps->a[len];--len;}ps->a[0] = x;ps->size++;}//头删
void SeqListPopFront(SL* ps)
{assert(ps);//挪数据int len = 0;while (len <= ps->size - 1){ps->a[len] = ps->a[len + 1];++len;}ps->size--;}//查找 找到了返回下标，没找到返回-1 
int SeqListFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; ++i){if (x == ps->a[i]){return i;}}return -1;}//指定pos位置后插
void SeqListInsert(SL* ps, SLDataType x, int pos)
{assert(pos >= 0 && pos <= ps->size);//考虑扩容if (ps->capacity == ps->size){BuyListNode(ps);}//挪动数据int len = ps->size;printf("%d\n", len);while (len - pos + 1){ps->a[len + 1] = ps->a[len];--len;}ps->a[pos + 1] = x;++ps->size;
}//指定pos位置删
void SeqListErase(SL* ps, int pos)
{assert(pos >= 0 && pos <= ps->size);//pos+1往前挪int len = ps->size - 1;while (len - pos){ps->a[len - 1] = ps->a[len];len--;}--ps->size;
}

test.c(测试代码)

#include "seqlist.h"void test1()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPrint(&sl);printf("\n");SeqListPopBack(&sl);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListDestroy(&sl);}void test2()
{SL s2;SeqListInit(&s2);SeqListPushFront(&s2, 1);SeqListPushFront(&s2, 2);SeqListPushFront(&s2, 3);SeqListPushFront(&s2, 4);SeqListPrint(&s2);printf("\n");SeqListPopFront(&s2);SeqListPrint(&s2);SeqListDestroy(&s2);}void test3()
{SL s3;SeqListInit(&s3);SeqListPushBack(&s3, 1);SeqListPushBack(&s3, 2);SeqListPushBack(&s3, 3);SeqListPushBack(&s3, 4);SeqListPushBack(&s3, 5);SeqListPrint(&s3);printf("\n");int pos=SeqListFind(&s3,4);SeqListInsert(&s3, 7, pos);SeqListPrint(&s3);printf("\n");SeqListInsert(&s3, 8, pos);SeqListInsert(&s3, 9, pos);SeqListErase(&s3, pos);SeqListPrint(&s3);}int main()
{test3();return 0;
}

二、顺序表OJ

学完了顺序表的实现，我们可以写一些有关顺序表的OJ题

1 移除元素

题目链接： . - 力扣（LeetCode）

这个题就是简单的双指针，我们可以定义两个变量， src用来遍历数组，dst用来存放不是val的值，并标记移除元素后的新长度

由于它要的是新长度，所以我们不用真的删除那些元素。

int removeElement(int* nums, int numsSize, int val)
{int src = 0;int dst = 0;while (src < numsSize){if (nums[src] != val){nums[dst] = nums[src];++dst;++src;}else{++src;}}return dst;
}

关于双指针这类算法，后续我们会进行系统的学习和刷题哦~

2 删除有序数组中的重复项

题目链接：  . - 力扣（LeetCode）

由于要求原地删除，所以我们不能再搞一个数组，把不重复的元素push_back进去

这道题我们依旧采用双指针来做

但是我们需要三个指针，两个cur,next用来遍历，一个dst用来记录不重复元素的个数

我们的逻辑是这样，如果cur和next指向值相同的数就让next++，指向值不相同的数时

用dst下标记录cur指向的值，再让dst++，让cur去next的位置，再让next++

如图所示

-》

-》

（此时第一个下标就记录了0这个元素）

但是还有个问题：到了要结束的时候，此时cur，next指向的元素不同，next++就跳出了循环

所以最后一个元素我们在循环结束后要再补充至dst下标上

由此可得代码如下

int removeDuplicates(int* nums, int numsSize)
{int cur = 0;int next = 1;int dst = 0;//考虑为空if (numsSize == 0){return 0;}while (next < numsSize){if (nums[next] == nums[prev]){next++;}else{nums[dst++] = nums[prev];prev = next;next++;}}nums[dst++]=nums[prev];return dst;
}

3 合并两个有序数组

题目链接 ： . - 力扣（LeetCode）

显然，我们的任务是把nums2的拷入nums1中，

两个数组一个给一个指针int i=0,int j=0，遍历数组找小的；再标记一个dst指针，将较小者插入nums[dst++];

当两个数组有一个走完了另一个数组的元素再依次拷入剩下的位置即可。

啊但是！

当你画了图模拟一遍之后就会发现，如果我们从前往后开始会有覆盖的可能

如图，当nums2的2和nums1的3比较时，由于2<3,显然2要到3的位置，所以这个3就会被覆盖

那怎么办呢？

以我们刚才头插头删的经验来看，从前往后会覆盖，那我们就从后往前

所以我的指针变为int end1=m-1,int end2=n-1,int end=m+n-1。比较的时候也是比较大的

所以代码如下

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1=m-1;int end2=n-1;int end=m+n-1;while (end1>=0 && end2>=0){if (nums1[end1] > nums2[end2]){nums1[end--] = nums1[end1--];}else{nums1[end--] = nums2[end2--];}}//有一个走完了while (end2>=0){nums1[end--] = nums2[end2--];}
}

总结

 做总结，这篇博客我们学习了了顺序表，顺序表的优势是由于有下标，可以随机访问，尾插尾删效率高。下篇博客我们要学习可能有些些许难得链表，如果你的指针有些遗忘了，建议去复习一下指针哦~

水平有限，还请各位大佬指正。如果觉得对你有帮助的话，还请三连关注一波。希望大家都能拿到心仪的offer哦。

每日gitee侠：今天你交gitee了嘛

这篇关于速通数据结构第二站 顺序表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/847538。

相关文章

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》：本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时，需要提供方将Map类型的数据序列化为co
阅读更多...
MySQL中SQL的执行顺序详解

MySQL中SQL的执行顺序详解

《MySQL中SQL的执行顺序详解》：本文主要介绍MySQL中SQL的执行顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql中SQL的执行顺序SQL执行顺序MySQL的执行顺序SELECT语句定义SELECT语句执行顺序总结MySQL中SQL的执行顺序
阅读更多...
SpringBoot中配置文件的加载顺序解读

SpringBoot中配置文件的加载顺序解读

《SpringBoot中配置文件的加载顺序解读》：本文主要介绍SpringBoot中配置文件的加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot配置文件的加载顺序1、命令⾏参数2、Java系统属性3、操作系统环境变量5、项目【外部】的ap
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...
Python中顺序结构和循环结构示例代码

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2