【数据结构与算法篇】动态顺序表及相关OJ算法题

【数据结构与算法篇】动态顺序表及相关OJ算法题

🥕个人主页:开敲🍉

🔥所属专栏:数据结构与算法🍅

目录

【数据结构与算法篇】动态顺序表及相关OJ算法题

1. 动态顺序表的实现

    1.1 SeqList.h 头文件声明

      1.2 SeqList.c 源文件定义

    1.3 Test.c 源文件测试

2. OJ算法题

     1. 27. 移除元素 - 力扣(LeetCode)

      2. 88. 合并两个有序数组 - 力扣(LeetCode)

1. 动态顺序表的实现

    1.1 SeqList.h 头文件声明

//SeqList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef int SQDataType;

typedef struct
{
    SQDataType* arr;
    int size;
    int capacity;
}SL;

SL sl;


//初始化
void SeqListInit(SL* sl);

//打印
void SeqListPrint(SL* sl);


//增  删  查  改

//尾插
void SeqListPushBack(SL* sl);

//头插
void SeqListPushHead(SL* sl);

//随机插入
void SeqListPushRand(SL* sl);

//尾删
void SeqListPopBack(SL* sl);

//头删
void SeqListPopHead(SL* sl);

//随机删除
void SeqListPopRand(SL* sl);


//查找
void SeqListFind(SL* sl);


//更改
void SeqListChange(SL* sl);

      1.2 SeqList.c 源文件定义

#define _CRT_SECURE_NO_WARNINGS 1


#include "SeqList.h"

//初始化
void SeqListInit(SL* sl)
{
    sl->arr = sl->arr = (SQDataType*)malloc(sizeof(SQDataType));
    sl->size = 0;
    sl->capacity = 1;
}

//打印
void SeqListPrint(SL* sl)
{
    int i = 0;
    for (i = 0; i < sl->size; i++)
    {
        printf("%d ", sl->arr[i]);
    }
    printf("\n");
}

//尾插
void SeqListPushBack(SL* sl,int n)
{
    //扩容
    while (sl->size >= sl->capacity)
    {
        SQDataType* ptr = (SQDataType*)realloc(sl->arr, sizeof(SQDataType) * (sl->capacity) * 2);
        if (ptr == NULL)
        {
            perror("realloc");
            return;
        }
        else
        {
            sl->arr = ptr;
        }
        sl->capacity *= 2;
    }
    sl->arr[sl->size] = n;
    sl->size++;
}


//头插
void SeqListPushHead(SL* sl)
{
    int num = sl->size;
    int input = 0;
    printf("请输入要插入的数据: ");
    scanf("%d", &input);
    //扩容
    while (sl->size >= sl->capacity)
    {
        SQDataType* ptr = (SQDataType*)realloc(sl->arr, sizeof(SQDataType) * (sl->capacity) * 2);
        if (ptr == NULL)
        {
            perror("realloc");
            return;
        }
        else
        {
            sl->arr = ptr;
        }
        sl->capacity *= 2;
    }
    while (num)
    {
        sl->arr[num] = sl->arr[num - 1];
        num--;
    }
    sl->arr[0] = input;
    sl->size++;
}

//随机插入
void SeqListPushRand(SL* sl)
{
    int input = 0;
    int flag = 0;
    printf("请输入要插入的数据:");
    scanf("%d", &input);
    printf("请输入要插入的位置:");
    scanf("%d", &flag);
    //扩容
    while (sl->size >= sl->capacity)
    {
        SQDataType* ptr = (SQDataType*)realloc(sl->arr, sizeof(SQDataType) * (sl->capacity) * 2);
        if (ptr == NULL)
        {
            perror("realloc");
            return;
        }
        else
        {
            sl->arr = ptr;
        }
        sl->capacity *= 2;
    }
    SQDataType* pf = &(sl->arr[flag - 1]);
    SQDataType* pf1 = &(sl->arr[sl->size - 1]);
    while (pf1 >= pf)
    {
        *(pf1 + 1) = *pf1;
        pf1--;
    }
    *pf = input;
    sl->size++;
}

//尾删
void SeqListPopBack(SL* sl)
{
    sl->size--;
}


//头删
void SeqListPopHead(SL* sl)
{
    if (sl->size)
    {
        int num = 0;
        while (num < sl->size)
        {
            sl->arr[num] = sl->arr[num + 1];
            num++;
        }
    }
}

//随机删除
void SeqListPopRand(SL* sl)
{
    int del = 0;
    printf("请输入要删除的位置:");
    scanf("%d", &del);
    while (del > sl->size)
    {
        printf("该位置无可删除的数据,请重新输入:");
        scanf("%d", &del);
    }
    SQDataType* pf = &(sl->arr[del - 1]);
    SQDataType* pf1 = pf + 1;
    while (pf1 <= &(sl->arr[sl->size - 1]))
    {
        *(pf1 - 1) = *pf1;
        pf1++;
    }
    sl->size--;
}


//查找
void SeqListFind(SL* sl)
{
    SQDataType* pf = sl->arr;
    int find = 0;
    printf("请输入要查找的位置:");
    scanf("%d", &find);
    while (find > sl->size)
    {
        printf("查询失败,该位置无内容,请重新输入:");
        scanf("%d", &find);
    }
    if (find <= sl->size)
    {
        printf("查询成功,该位置内容为:%d\n", sl->arr[find - 1]);
    }

}


//更改
void SeqListChange(SL* sl)
{
    int change = 0;
    int flag = 0;
    printf("请输入要更改的位置:");
    scanf("%d", &flag);
    while (flag > sl->size)
    {
        printf("该位置无数据可更改,请重新输入:");
        scanf("%d", &flag);
    }
    printf("请输入想要更换为的数据:");
    scanf("%d", &change);
    SQDataType* pf = &(sl->arr[flag - 1]);
    *pf = change;
}

    1.3 Test.c 源文件测试

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void menu()
{
    printf("**********************************************\n");
    printf("**********************************************\n");
    printf("*********** 1. endadd   2. beginadd **********\n");
    printf("*********** 3. randadd  4. endel    **********\n");
    printf("*********** 5. begindel 6. randdel  **********\n");
    printf("*********** 7. find     8. change   **********\n");
    printf("***********        0. exit          **********\n");
    printf("**********************************************\n");
    printf("**********************************************\n");
    printf("请输入要进行的操作:");
}


enum SQ
{
    Exit,
    endadd,
    beginadd,
    randadd,
    enddel,
    begindel,
    randdel,
    find,
    change
}sq;


int main()
{
    SeqListInit(&sl);
    int i = 0;
    int option = 0;
    int input = 0;
    int add = 0;
    do
    {
        menu();
        scanf("%d", &i);
        input = (enum SQ)i;
        switch (input)
        {
        case endadd:
            printf("请输入要插入的数据,以-1结束:");
            do
            {
                scanf("%d", &option);
                if (option != -1)
                {
                    SeqListPushBack(&sl, option);
                }
            } while (option != -1);
            SeqListPrint(&sl);
            break;
        case beginadd:
            SeqListPushHead(&sl);
            SeqListPrint(&sl);
            break;
        case randadd:
            SeqListPushRand(&sl);
            SeqListPrint(&sl);
            break;
        case enddel:
            SeqListPopBack(&sl);
            SeqListPrint(&sl);
            break;
        case begindel:
            SeqListPopHead(&sl);
            SeqListPrint(&sl);
            break;
        case randdel:
            SeqListPopRand(&sl);
            SeqListPrint(&sl);
            break;
        case find:
            SeqListFind(&sl);
            break;
        case change:
            SeqListChange(&sl);
            SeqListPrint(&sl);
            break;
        case Exit:
            printf("退出程序\n");
            break;
        default:
            printf("输入非法,请重新输入:");
            scanf("%d", &input);
            break;
        }
    } while (input);
    return 0;
}

2. OJ算法题

     1. 27. 移除元素 - 力扣(LeetCode)

  这题的最优解是双指针解法:时间复杂度O(N),空间复杂度O(1)。解法:

int removeElement(int* nums, int numsSize, int val)

{

    int left = 0;    //左指针,用于保存不等于val的数据

    int right = 0;  //右指针,用于排除等于val的值,并把不等于val的值赋值给左指针

    for(right = 0;right<numsSize;right++)  //右指针遍历

    {

        if(nums[right]!=val)  //如果右指针数据不等于val,右指针的数据复制给左指针

        {

            nums[left] = nums[right];

            left++;    //左右指针都++

        }

               //否则,如果右指针的数据等于val,左指针不动,右指针++

    }

    return left;         //最后数组中元素的个数就等于left的大小

}

      2. 88. 合并两个有序数组 - 力扣(LeetCode)

    这题的思路是用第三个数组来将数组1、2中的内容从小到大排放,然后再按个放进数组1中:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)

{

    int i = 0;  

    int j = 0;  //数组3的下标

    int pf1 = 0;  //数组1的指针

    int pf2 = 0;  //数组2的指针

    int nums3[m+n];  //用于存放数据的数组3

    while(pf1<m||pf2t<n)

    {

        if(pf1==m)  //如果数组1的内容已经全部放进数组3,则直接将数组2中的内容放进数组3

        {

            nums3[j++] = nums2[pf2++];

        }

        else if(pf2==n)  //如果数组2的内容已经全部放进数组3,则直接将数组1中的内容放进数组3

        {

            nums3[j++] = nums1[pf1++];

        }

        else if(nums1[pf1]<nums2[pf2])  //比较两数组中数据的大小,小的先放进数组3

        {

            nums3[j++] = nums1[pf1++];

        }

        else  

        {

            nums3[j++] = nums2[pf2++];

        }

    }

    for(i = 0;i<j;i++)

    {

        nums1[i] = nums3[i];  //将数组3的内容放回数组1中

    }

}

                                                        创作不易,点个赞呗,蟹蟹啦~

           

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/292190.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【进程IO】详细讲解文件描述符fd

文章目录 前言什么叫文件描述符FILE与fd的关系 再次理解文件为什么要有文件的方法列表呢&#xff1f; 进程和struct file的关系再次理解open操作 前言 C语言的关于文件操作的各种函数实际上是对系统调用的封装。那么从进程的角度看&#xff0c;一个文件到底是如何被描述的呢&a…

【Java数据结构】关于栈的操作出栈,压栈,中缀表达式,后缀表达式,逆波兰表达式详解

&#x1f525;个人主页&#xff1a;努力学编程’ &#x1f525;内容管理&#xff1a;java数据结构 上一篇文章我们讲过了java数据结构的链表&#xff0c;对于链表我们使用了它的一些基本操作&#xff0c;完成了扑克牌小游戏的操作&#xff0c;如果你感兴趣的话&#xff0c;点…

了解 LoadRunner 性能测试软件及其基础使用

目录 一、了解LoadRunner 1、什么是Loadrunner&#xff1f; 2、Loadrunner包括什么组件&#xff1f; &#xff08;1&#xff09;前台组件 &#xff08;2&#xff09;后台组件 二、LoadRunner三大组件 1、VuGen&#xff08;虚拟用户脚本生成器&#xff09; &#xff08;…

Vue + .NetCore前后端分离,不一样的快速发开框架

摘要&#xff1a; 随着前端技术的快速发展&#xff0c;Vue.NetCore框架已成为前后端分离开发中的热门选择。本文将深入探讨Vue.NetCore前后端分离的快速开发框架&#xff0c;以及它如何助力开发人员提高效率、降低开发复杂度。文章将从基础功能、核心优势、适用范围、依赖环境等…

linux基础命令篇:Linux基础命令讲解——文件浏览(cat、less、head、tail和grep)

Linux基础命令讲解——文件浏览&#xff08;cat、less、head、tail和grep&#xff09; 本文详细介绍Linux中的cat、less、head、tail和grep命令&#xff0c;这些命令在日常工作中非常实用&#xff0c;以下是关于这些命令的详细介绍&#xff1a; 1. cat命令&#xff1a;用于查看…

JDK8的下载安装与环境变量配置教程

前言 官网下载&#xff1a;Java Archive Downloads - Java SE 8u211 and later 现在应该没人用32位的系统了吧&#xff0c;直接下载Windows x64 Installer jdk-8u391-windows-x64.exe 一、安装JDK 1. 打开jdk-8u391-windows-x64.exe 2. 直接下一步 3. 这个地方不要动他&…

鸿蒙OS开发实例:【瀑布流式图片浏览】

介绍 瀑布流式展示图片文字&#xff0c;在当前产品设计中已非常常见&#xff0c;本篇将介绍关于WaterFlow的图片浏览场景&#xff0c;顺便集成Video控件&#xff0c;以提高实践的趣味性 准备 请参照[官方指导]&#xff0c;创建一个Demo工程&#xff0c;选择Stage模型熟读Har…

构建操作可靠的数据流系统

文章目录 前言数据流动遇到的困难先从简单开始可靠性延迟丢失 性能性能损失性能——分层重试 可扩展性总结 前言 在流式架构中&#xff0c;任何对非功能性需求的漏洞都可能导致严重后果。如果数据工程师没有将可伸缩性、可靠性和可操作性等非功能性需求作为首要考虑因素来构建…

单例设计模式(3)

单例模式&#xff08;3&#xff09; 实现集群环境下的分布式单例类 如何理解单例模式中的唯一性&#xff1f; 单例模式创建的对象是进程唯一的。以springboot应用程序为例&#xff0c;他是一个进程&#xff0c;可能包含多个线程&#xff0c;单例代表在这个进程的某个类是唯一…

mybatis标签解析教程

mybatis标签解析 标签结构 我们在mapper的xml文件中&#xff0c;使用动态SQL&#xff0c;那么这些标签<where>、<if>、<set>、<ForEach>、<Choose>、<Trim> 等是怎么解析的呢&#xff1f;我们先看包的结构 包结构中&#xff0c;script…

【Qt】:多种方式编辑hello world

多种方式编辑hello world 一.QLabel二.对象树三.使用单行编辑框四.使用按钮 (小技巧&#xff1a;1.可以使用F4来进行头文件和对应cpp文件的切换&#xff1b;2.写完一个函数的声名之后,按下altenter,就可以自动的在对应的cpp 文件中添加函数的定义了.) 一.QLabel 注意这里是QSt…

第九届蓝桥杯大赛个人赛省赛(软件类)真题C 语言 A 组-分数

solution1 直观上的分数处理 #include <iostream> using namespace std; int main() {printf("1048575/524288");return 0; }#include<stdio.h> #include<math.h> typedef long long ll; struct fraction{ll up, down; }; ll gcd(ll a, ll b){if…

相册清理大师-手机重复照片整理、垃圾清理软件

相册清理大师是一款超级简单实用的照片视频整理工具。通过便捷的操作手势&#xff0c;帮助你极速整理相册中的照片和视频、释放手机存储空间。 【功能简介】 向上滑动&#xff1a;删除不要的照片 向左滑动&#xff1a;切换下一张照片 向右滑动&#xff1a;返回上一张照片 整理分…

【2023】kafka在linux和docker安装(kafka-1)

目录&#x1f4bb; 一、linux安装kafka1. 安装jdk2. 上传解压到/usr/local目录下3、使用kafka 二、docker安装kafka1. 下载2. 安装zookeeper3. 安装kafka 一、linux安装kafka 环境主机 mac m2、虚拟机Ubuntu22.04.4 1. 安装jdk yum install -y java-1.8.0-openjdk.x86_64下载k…

电商系统秒杀三 秒杀兜底方案之熔断降级

一 秒杀场景介绍 1.1 秒杀场景的特点 1、秒杀具有瞬时高并发的特点&#xff0c;秒杀请求在时间上高度集中于某一特定的时间点&#xff08;秒杀开始那一秒&#xff09;&#xff0c;这样一来&#xff0c;就会导致一个特别高的流量峰值&#xff0c;它对资源的消耗是瞬时的。 2、…

LATTICE进阶篇DDR2--(1)获取官网DDR2例程并仿真

前言 本章主要讲述如何从官网下载DDR2的DEMO例程&#xff0c;并将例程的仿真运行起来。 官网的DEMO在Diamond工程里是没有调用任何任何IP核的&#xff0c;只是在仿真的时候调用了CORE文件夹下的IP核源文件进行仿真&#xff0c;该DEMO工程主要是拿来产生仿真波形&#xff0c;对…

算法学习——LeetCode力扣图论篇2

算法学习——LeetCode力扣图论篇2 1020. 飞地的数量 1020. 飞地的数量 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个大小为 m x n 的二进制矩阵 grid &#xff0c;其中 0 表示一个海洋单元格、1 表示一个陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相…

这回轮到鸿蒙禁用安卓了!!!

1月18日&#xff0c;鸿蒙生态千帆仪式上&#xff0c;华为正式宣布了HarmonyOS NEXT&#xff08;下简称鸿蒙星河版或纯血鸿蒙&#xff09;开发者预览已向开发者开放申请&#xff0c;纯血鸿蒙开始走向普及阶段。伴随着不再兼容安卓的纯血鸿蒙铺开&#xff0c;鸿蒙走进了运营属于自…

本地虚拟机服务器修改站点根目录并使用域名访问的简单示例

说明&#xff1a;本文提及效果是使用vmware虚拟机&#xff0c;镜像文件是Rocky8.6 一、配置文件路径 1. /etc/httpd/conf/httpd.conf #主配置文件 2. /etc/httpd/conf.d/*.conf #调用配置文件 调用配置文件的使用&#xff1a; vim /etc/httpd/conf.d/webpage.conf 因为在主配…

python opencv之提取轮廓并拟合圆

图片存储地址为&#xff1a;C:\Users\Pictures\test.png&#xff0c;该图像图片背景是黑色的&#xff0c;目标区域是亮的&#xff0c;目标区域是两段圆弧和两段曲线构成的封闭区域&#xff0c;其中两段圆弧属于同一个圆&#xff0c;但在目标区域的相对位置&#xff0c;也就是不…