当前位置： 首页 > article >正文

【数据结构】顺序表解析及实战运用

article 2024/11/15 15:32:18

目录

线性表

顺序表

概念及结构

静态顺序表

动态顺序表

接口实现

初始化与销毁顺序表

检查容量（扩容函数）

打印顺序表

尾部插入和尾部删除

头部插入与头部删除

查找数据

指定下标位置插入

删除指定下标位置的数据

顺序表优缺点

优点

缺点

顺序表实战运用

删除有序数组中的重复项

合并两个有序数组

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表就是数组,但是再数组的基础上,它还要求数据是从头开始连续存储的,不能跳跃间隔。

静态顺序表

#pragma once

#define N 1000
typedef int SLDataType;

//静态顺序表
typedef struct SeqList
{
    SLDataType a[N];
    int size;//表示数组中存储了多少个数据

}SL;

//接口函数
void SeqListInit(SL* ps, SLDataType x);

//静态特点：如果满了就不让插入 缺点：给多少的合适呢？这个很难确定
//N给小了不够用，N给大了浪费
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListpushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps, SLDataType x);

动态顺序表

#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;//表示数组中存储了多少个数据（有效数据个数）
    int capacity;//数组实际能存数据的空间容量是多大（能存储的数据个数）
}SL;

//接口函数
void SeqListInit(SL* ps);//初始化
void SeqListCheckCapacity(SL* ps);//检查容量（扩容）
void SeqListDestroy(SL* ps);
//销毁顺序表，释放空间
void SeqListPushBack(SL* ps, SLDataType x);
//尾插
void SeqListPopBack(SL* ps);
//尾删
void SeqListpushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);
//头删
void SeqListPrint(SL* ps);//打印顺序表
//找到了返回x位置下标，没有找到返回-1
int SeqListFind(SL* ps, SLDataType x);
//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除pos下标位置的数据
void SeqListErase(SL* ps, int pos);

接口实现

初始化与销毁顺序表

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

void SeqListDestroy(SL* ps)//顺序表不用了，销毁，释放空间
{
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}

检查容量（扩容函数）

void SeqListCheckCapacity(SL* ps)//检查容量，扩容
{
    //如果没有空间或者空间不足，我们就扩容
    if (ps->size == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果为0，则给4，如果不是0，则扩大二倍
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
        if (tmp == NULL)//扩容失败
        {
            printf("realloc fail\n");
            exit(-1);//系统函数，退出程序，正常退出是返回0，这里是退出程序并返回-1，说明是异常退出
        }
        //扩容成功
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
}

打印顺序表

void SeqListPrint(SL* ps)//打印一下顺序表内容
{
    for (int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

尾部插入和尾部删除

void SeqListPushBack(SL* ps, SLDataType x)//尾插，从尾部插入
{
    SeqListCheckCapacity(ps);
    //从尾部插入
    ps->a[ps->size] = x;
    ps->size++;
}

void SeqListPopBack(SL* ps)//尾部删除
{
    assert(ps->size > 0);    //防止多次调用导致size小于0出现非法访问的情况
    //ps->a[ps->size - 1] = 0;    //可加可不加
    ps->size--;
}

头部插入与头部删除

void SeqListpushFront(SL* ps, SLDataType x)//头插
{
    SeqListCheckCapacity(ps);
    //挪动数据，从后往前，依次向后挪动一个位置
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    ps->a[0] = x;
    ps->size++;
}

void SeqListPopFront(SL* ps)//头删 
{
    assert(ps->size > 0);
    int begin = 1;//从数组第二个位置开始依次往前移动覆盖
    while (begin < ps->size)
    {
        ps->a[begin - 1] = ps->a[begin];
        begin++;
    }
    ps->size--;
}

查找数据

//查找
int SeqListFind(SL* ps, SLDataType x)
{
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        if (x == ps->a[i])
            return i;
    }
    return -1;
}

指定下标位置插入

//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
    assert(pos >= 0 && pos <= ps->size);//防止pos插入位置非法
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    //挪动数据
    while (pos <= end)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

删除指定下标位置的数据

//删除pos下标位置的数据
void SeqListErase(SL* ps, int pos)
{
    assert(pos >= 0 && pos < ps->size);

    int begin = pos + 1;
    while (begin < ps->size)
    {
        ps->a[begin - 1] = ps->a[begin];
        begin++;
    }
    ps->size--;
}

顺序表优缺点

优点

        支持随机访问。

缺点

        1.空间不够了需要增容，而增容是需要付出代价的。

        2.为了避免频繁扩容，我们满了基本都是扩大2倍，可能会导致一定的空间浪费。

        3.顺序表要求数据从开始位置连续存储，那么我们在头部或者中间位置插入删除数据就需要挪动数据，效率不高。

        （针对顺序表的缺陷，就设计出了链表）

顺序表实战运用

删除有序数组中的重复项

解题思路：

定义三个指针，dst，i，j。使j++、向后移动，判断i和j指向的数据是否相等测定重复数据的范围，j++直到i和j指向的数据不相等，就让nums[dst] = nums[i]，然后i = j，将i移动到j的位置上，dst+1指向下一个需要改变的位置，然后j++继续向后移动测定重复数据的范围。这样dst就可以一个一个将去重后的数据放到数组中。（需要注意j++越界）

代码如下：

//去重
int removeDuplicates(int* nums, int numsSize)//返回数据个数
{
    if (numsSize == 0)//防止空数组
        return 0;

    int i = 0, j = 0;
    int dst = 0;
    while (j < numsSize)
    {
        if (nums[i] != nums[j])
        {
            nums[dst] = nums[i];
            i = j;
            j++;
        }
        else
        {
            j++;
        }
    }
    //当j++越界后会导致直接跳出循环，最后一个去重后的数据还需要录入
    nums[dst] = nums[i];
    dst++;

    return dst;
}

合并两个有序数组

思路：

两个指针将两个数组从最后一个开始进行相互比较，大的放进左边大数组的最后一个位置，然后将该已经放入数组的指针向前移动一个位置，然后再进行比较。

大的放进数组中，再将指针前移。

依次向前就可以把两个数组合并。如果是左侧大数组的指针先向左走到头，那么只需要将右侧数组中剩余的元素拷贝到左侧未放入新数据的位置就可以了。

代码实现：

void merge(int* nums1, int muns1Size, int m, int* nums2, int nums2Size, int n)
{
    int left = m - 1, right = n - 1;
    int end = m + n - 1;

    while (right >= 0 && left >= 0)
    {
        if (nums1[left] > nums2[right])
        {
            nums1[end] = nums1[left];
            end--;
            left--;
        }
        else
        {
            nums1[end] = nums2[right];
            end--;
            right--;
        }
    }
    if (left < 0)
    {
        while (right >= 0)
        {
            nums1[end] = nums2[right];
            end--;
            right--;
        }
    }
}

（全文完）


http://www.kler.cn/a/394566.html

相关文章：

  • SQL 注入详解：原理、危害与防范措施
  • 985研一学习日记 - 2024.11.14
  • 阿里云centos7.9服务器磁盘挂载，切换服务路径
  • 深度学习中的感受野：从基础概念到多层次特征提取
  • npm list @types/node 命令用于列出当前项目中 @types/node 包及其依赖关系
  • 陪诊问诊APP开发实战：基于互联网医院系统源码的搭建详解
  • 【Redis实战篇】利用布隆过滤器解决缓存穿透问题
  • 力扣题目解析--合并两个链表
  • SystemVerilog学习笔记（十一）：接口
  • 相机光学（四十）——2x2 Adjacent Pixel Binning
  • 小程序开发者工具的network选项卡中有某域名的接口请求，但是在charles中抓不到该接口
  • Python图像识别详解
  • STL学习-排序算法
  • Python-requests模块详解！
  • 威联通Docker Compose搭建NAS媒体库资源工具NAS Tools
  • C++单例模式实现
  • CSS盒子的定位＞ （中篇）#绝对定位#附练习
  • JAVA开源项目 微服务在线教育系统 计算机毕业设计
  • 【Linux上部署Dify】从本地到云端：在Linux上部署Dify并实现公网访问的流程
  • Go语言进阶之Context控制并发
  • STM32F1学习——I2C通信
  • 第5章: 图像变换与仿射操作
  • vue3+vite+js env引入
  • 湾区聚力 开源启智 | 2024 CCF中国开源大会暨第五届OpenI/O启智开发者大会闪耀深圳
  • Scroll 生态全面启动为 Pencils Protocol 赋能，DAPP 将迎强势腾飞
  • 【MySQL】SQL语言