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

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利用顺序表实现“杨辉三角”的思路及代码示例

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

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
web群集--nginx配置文件location匹配符的优先级顺序详解及验证

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配（Exact Match）2. 正则表达式匹配（Regex Match）3. 前缀匹配（Prefix Match） 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中，location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求，NGINX 提供了多种匹
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2