C语言数据结构之顺序表

目录

    • 1.线性表
    • 2.顺序表
      • 2.1顺序表相关概念及结构
      • 2.2增删查改等接口的实现
    • 3.数组相关例题

在这里插入图片描述

在这里插入图片描述

1.线性表

线性表（linear list）是n个具有相同特性（数据类型相同）的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的（ 在内存中的储存地址可能不是连续的，但是我们可以按它的储存顺序从顺序表的开头依次找到结尾，所以逻辑上是连续的 ） ，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

2.顺序表

2.1顺序表相关概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。结构与数组相同，在数组的基础上增加了对数据的增删查改。

顺序表一般可以分为：
1.静态顺序表：数组的长度是确定的，不可改变。

在这里插入图片描述

2.动态顺序表：使用动态开辟的数组存储数据，数组大小是可变的。

在这里插入图片描述

2.2增删查改等接口的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的数组大小N是确定的，不能改变，N如果定大了，空间开多了浪费，N定小了，空间开少了不够用。所以现实中基本都是使用动态顺序表，根据需要改变动态分配的空间大小，可以更加灵活地储存数据，所以下面我们实现动态顺序表。

test.c

#include "SeqList.h"

void menu()//功能菜单
{
	printf("******************************************\n");
	printf("**************    请选择    **************\n");
	printf("******  1.PushFront    2.PushBack  *******\n");
	printf("******  3.PopFront     4.PopBack   *******\n");
	printf("******  5.Insert       6.Del       *******\n");
	printf("******  7.Modify       8.FindSct   *******\n");
	printf("******  9.Print        0.Exit      *******\n");
	printf("******************************************\n");
}

int main()
{
	int input = 0;
	int value = 0;
	int pos = 0;
	SeqList sl;
	Init_SeqList(&sl);
	do
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入要头插的值>:");
			scanf("%d", &value);
			Push_Front_SeqList(&sl, value);
			break;
		case 2:
			printf("请输入要尾插的值>:");
			scanf("%d", &value);
			Push_Back_SeqList(&sl, value);
			break;
		case 3:
			Pop_Front_SeqList(&sl);
			break;
		case 4:
			Pop_Back_SeqList(&sl);
			break;
		case 5:
			printf("请输入你要插入的位置和要插入的值>:");
			scanf("%d %d", &pos, &value);
			Insert_SeqList(&sl, pos, value);
			break;
		case 6:
			printf("请输入要删除的值>:");
			scanf("%d", &value);
			Del_SeqList(&sl, value);
			break;
		case 7:
			printf("请输入你要修改的位置和修改的值:>");
			scanf("%d %d", &pos, &value);
			Modify_SeqList(&sl, pos, value);
			break;
		case 8:
			printf("请输入你要查找的值>:");
			scanf("%d", &value);
			int ret = Find_Sct_SeqList(&sl, value);
			if (ret == -1)
				printf("找不到该值\n");
			else
				printf("该值的下标为%d\n", ret);
			break;
		case 9:
			Print_SeqList(&sl);
			break;
		case 0:
			printf("退出成功\n");
			Destroy_SeqList(&sl);
		}
	} while (input);
	return 0;
}

SeqList.c

#include "SeqList.h"


//初始化顺序表
void Init_SeqList(SeqList* ptr)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	SLDataType* tmp = (SLDataType*)malloc(3 * sizeof(SLDataType));//先开3个数据的大小，不够再增
	
	if (tmp == NULL)//有可能动态数组开辟不成功
	{
		perror("Init_SeqList");
		exit(1);
	}
	else
		ptr->arr = tmp;

	ptr->size = 0;
	ptr->capacity = 3;
}


//销毁顺序表
void Destroy_SeqList(SeqList* ptr)//动态申请的空间使用完之后要释放，不然会造成内存泄漏
{
	free(ptr->arr);
	ptr->arr = NULL;
}


//检查数组大小
void Check_Capacity(SeqList* ptr)//数组大小不够则增容
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	if (ptr->size == ptr->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ptr->arr, 2 * ptr->capacity * sizeof(SLDataType));//每次增容都开辟两倍的数组大小
		
		if (tmp == NULL)//有可能动态数组开辟不成功
		{
			perror("Check_Capacity");
			exit(1);
		}
		else
			ptr->arr = tmp;

		ptr->capacity *= 2;//扩容后不要忘记把capacity修改
	}
}


//寻找某个数据的下标
int Find_Sct_SeqList(SeqList* ptr, SLDataType val)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	for (int i = 0; i < ptr->size; i++)
	{
		if (ptr->arr[i] == val)
		{
			return i;//找到val返回val的下标
		}
	}
	return -1;//找不到则返回-1，因为-1不是下标，方便区分找没找到
}


//在数据dst的前面插入数据src
void Insert_SeqList(SeqList* ptr, SLDataType dst,SLDataType src)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	Check_Capacity(ptr);//插入前要先检查空间够不够，不够则增容

	int sct = Find_Sct_SeqList(ptr, dst);
	if(sct == -1)//有可能要插入的值的位置是不存在的
	{
		printf("找不到该值\n");
		return;
	}

	for (int i = ptr->size - 1; i >= sct ; i--)//插入一个值，后面的值都要往后移动
	{
		ptr->arr[i+1] = ptr->arr[i];
	}

	ptr->arr[sct] = src;
	ptr->size++;//插入后不要忘了给数组大小加1
}


//头插一个数据
void Push_Front_SeqList(SeqList* ptr,SLDataType val)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	Check_Capacity(ptr);插入前要先检查空间够不够，不够则增容

	for (int i = ptr->size - 1; i >= 0; i--)
	{
		ptr->arr[i + 1] = ptr->arr[i];
	}

	ptr->arr[0] = val;
	ptr->size++;//插入后不要忘了给数组大小加1
}


//尾插一个数据
void Push_Back_SeqList(SeqList* ptr,SLDataType val)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	Check_Capacity(ptr);//插入前要先检查空间够不够，不够则增容

	ptr->arr[ptr->size] = val;
	ptr->size++;//插入后不要忘了给数组大小加1
}


//修改一个给定的数据
void Modify_SeqList(SeqList* ptr, SLDataType dst, SLDataType src)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	int sct = Find_Sct_SeqList(ptr, dst);
	
	if (sct == -1)//有可能要修改的值是不存在的
	{
		printf("找不到该值\n");
		return;
	}
	ptr->arr[sct] = src;
}


//删除一个给定的数据
void Del_SeqList(SeqList* ptr, SLDataType val)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	int sct = Find_Sct_SeqList(ptr, val);
	
	if (sct == -1)//有可能要删除的值是不存在的
	{
		printf("找不到该值\n");
		return;
	}
	for (int i = sct + 1; i < ptr->size; i++)
	{
		ptr->arr[i - 1] = ptr->arr[i];
	}
	ptr->size--;
}


//头删一个数据
void Pop_Front_SeqList(SeqList* ptr)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	if (ptr->size == 0)//数组内元素个数为0时不能再删了，否则会越界访问
	{
		return;
	}

	for (int i = 1; i < ptr->size; i++)
	{
		ptr->arr[i - 1] = ptr->arr[i];
	}
	ptr->size--;
}


//尾删一个数据
void Pop_Back_SeqList(SeqList* ptr)
{
	if (ptr->size == 0)//数组内元素个数为0时不能再删了，否则会越界访问
	{
		return;
	}

	assert(ptr);
	ptr->size--;//数组尾删就是不访问最后一个元素，将数组大小减1就可以了
}


//打印顺序表
void Print_SeqList(SeqList* ptr)
{
	assert(ptr);//防止ptr为空指针，空指针不能解引用

	for (int i = 0; i < ptr->size; i++)
	{
		printf("%d ",ptr->arr[i]);
	}
	printf("\n");
}

SeqList.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>

typedef int SLDataType; //将数据类型重命名为SLDataType，方便修改储存的数据类型

typedef struct SeqList
{
	SLDataType* arr; //动态开辟的数组
	size_t size;     //数组元素个数
	size_t capacity; //数组大小
}SeqList;

void Init_SeqList(SeqList* ptr);

void Insert_SeqList(SeqList* ptr, SLDataType dst, SLDataType src);

void Push_Front_SeqList(SeqList* ptr, SLDataType val);

void Push_Back_SeqList(SeqList* ptr, SLDataType val);

void Modify_SeqList(SeqList* ptr, SLDataType dst, SLDataType src);

void Del_SeqList(SeqList* ptr, SLDataType val);

void Pop_Front_SeqList(SeqList* ptr);

void Pop_Back_SeqList(SeqList* ptr);

int Find_Sct_SeqList(SeqList* ptr, SLDataType val);

void Print_SeqList(SeqList* ptr);

void Destroy_SeqList(SeqList* ptr);

3.数组相关例题

题目1：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 ：

输入：nums = [3, 2, 2, 3], val = 3
输出：2, nums = [2, 2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
例如，函数返回的新长度为 2 ，而 nums = [2, 2, 3, 3] 或 nums = [2, 2, 0, 0]，也会被视作正确答案。

参考解析：

void Swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 思路：用两个存下标的front和behind都先放在0的位置，front找不是val的值与behind交换，
// 这样就相当于把等于val的值往后放，不等于val的值往前放
// 最后数组的前n个数就是我们想要的删除所有val值之后的数组

int removeElement(int* nums, int numsSize, int val) 
{
    int front, behind;
    front = behind = 0;
    while (front < numsSize)
    {
        if (nums[front] == val)
        {
            front++;
        }
        else
        {
            if (front != behind)
                Swap(&nums[front], &nums[behind]);
            front++;
            behind++;
        }
    }
    return behind;//每找到一个不是val的值behind就++一次，所以behind的值就是新数组的长度
}

程序执行过程图：

在这里插入图片描述

题目2：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出：[1, 2, 2, 3, 5, 6]
解释：需要合并[1, 2, 3] 和[2, 5, 6] 。
合并结果是[1, 2, 2, 3, 5, 6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并[1] 和[] 。
合并结果是[1] 。

参考解析：

//解题思路:
//1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较
//将较大的元素往nums1末尾进行搬移
//2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1
//
//时间复杂度：O(m + n)
//空间复杂度 : O(1)

void Merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
	// end标记nums1的末尾，nums1和nums2中的元素从后往前往nums1中存放，应从end开始往前放，否则会存在数据覆盖
    int end1 = m - 1;
    int end2 = n - 1;
    int index = m + n - 1;


    // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移
    // 直到将num1或者num2中有效元素全部搬移完
    while (end1 >= 0 && end2 >= 0)
    {
        if (nums1[end1] > nums2[end2])
        {
            nums1[index--] = nums1[end1--];
        }
        else
        {
            nums1[index--] = nums2[end2--];
        }
    }


    // num2中的元素可能没有搬移完，将剩余的元素继续往nums1中搬移
    while (end2 >= 0)
    {
        nums1[index--] = nums2[end2--];
    }


    // num1中剩余元素没有搬移完 ---不用管了，因为num1中剩余的元素本来就在num1中
}

程序执行过程图：

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Github 2024-04-20 开源项目日报 Top10

Github 2024-04-20 开源项目日报 Top10

根据Github Trendings的统计，今日(2024-04-20统计)共有10个项目上榜。根据开发语言中项目的数量，汇总情况如下： 开发语言项目数量非开发语言项目2Python项目2Swift项目2HTML项目1CSS项目1Go项目1C项目1C++项目1Rust项目1编程面试大学：成为软件工程师的全面学习计划 创建周期…
阅读更多...
半导体材料（三）——P-N结和金属-半导体接触

半导体材料（三）——P-N结和金属-半导体接触

本篇为西安交通大学本科课程《电气材料基础》的笔记。 本篇为这一单元的第三篇笔记&#xff0c;上一篇传送门。 p-n结和金属-半导体接触 p-n结 无偏压开路状态 如图a所示&#xff0c;左边是n型掺杂&#xff0c;右边是p型掺杂&#xff0c;在n区和p区之间形成了一个不连续的…
阅读更多...
WARNING: No swap limit support——查看docker状态时提示警告

WARNING: No swap limit support——查看docker状态时提示警告

环境&#xff1a;Ubuntu 20.04 1、警告详情 执行命令 service docker status如下图 2、解决办法 2.1 修改文件 执行命令 vim /etc/default/grub在GRUB_CMDLINE_LINUX中追加cgroup_enablememory swapaccount1&#xff0c;如下&#xff1a; # If you change this file…
阅读更多...
【蓝桥杯嵌入式】蓝桥杯嵌入式第十四届省赛程序真题，真题分析与代码讲解

【蓝桥杯嵌入式】蓝桥杯嵌入式第十四届省赛程序真题，真题分析与代码讲解

&#x1f38a;【蓝桥杯嵌入式】专题正在持续更新中&#xff0c;原理图解析✨&#xff0c;各模块分析✨以及历年真题讲解✨都已更新完毕&#xff0c;欢迎大家前往订阅本专题&#x1f38f; &#x1f38f;【蓝桥杯嵌入式】蓝桥杯第十届省赛真题 &#x1f38f;【蓝桥杯嵌入式】蓝桥…
阅读更多...
攻防世界18.fileclude

攻防世界18.fileclude

18.fileclude include函数&#xff1a;包含并执行变量或者文件。 if&#xff1a;是if语句用来判断。 isset&#xff1a;判断变量是否存在&#xff0c;值是否为NULL。 $_GET&#xff1a;接收表单提交数据&#xff0c;并把数据附加到url链接当中。 逻辑运算符&&&#xff…
阅读更多...
【提示学习论文】BlackVIP: Black-Box Visual Prompting for Robust Transfer Learning论文原理

【提示学习论文】BlackVIP: Black-Box Visual Prompting for Robust Transfer Learning论文原理

BlackVIP: Black-Box Visual Prompting for Robust Transfer Learning BlackVIP:稳健迁移学习的黑盒视觉提示 问题 黑盒白盒&#xff1f; 黑盒和白盒的概念与对预训练模型内部参数的了解程度相关。黑盒指的是对预训练模型的参数和结构缺乏详细了解&#xff0c;通常只能通过使…
阅读更多...
NAT基本配置

NAT基本配置

配置IP完成及缺省的路由如下&#xff1b; 此时R1pingISP是ping不通的&#xff0c;因为缺省是可以将数据传给R3&#xff0c;但是R3传不回去&#xff0c;知道目标IP地址但因其是私有内部IP&#xff0c;而自己的是公有IP&#xff0c;所以传不过去&#xff0c;此时就需要R2这个边界…
阅读更多...
2024 发布Maven项目到中央仓库

2024 发布Maven项目到中央仓库

注册sonatype账号 Maven中央仓库并不支持直接发布jar包&#xff0c;sonatype是其指定的第三方仓库之一&#xff0c;发布到此的项目会被定时同步到中央仓库 官方教程地址&#xff1a;https://central.sonatype.org/register/central-portal/ 访问网址&#xff1a;https://centra…
阅读更多...
文件操作和IO

文件操作和IO

1.认识文件 我们先来认识狭义上的⽂件(file)。针对硬盘这种持久化存储的I/O设备&#xff0c;当我们想要进⾏数据保存时&#xff0c;往往不是保存成⼀个整体&#xff0c;⽽是独⽴成⼀个个的单位进⾏保存&#xff0c;这个独⽴的单位就被抽象成⽂件的概念&#xff0c;就类似办公桌…
阅读更多...
# 从浅入深 学习 SpringCloud 微服务架构（三）注册中心 Eureka（2）

# 从浅入深 学习 SpringCloud 微服务架构（三）注册中心 Eureka（2）

从浅入深 学习 SpringCloud 微服务架构&#xff08;三&#xff09;注册中心 Eureka&#xff08;2&#xff09; 段子手168 1、搭建 EurekaServer 注册中心&#xff0c;使用 Eureka 的步骤&#xff1a; 1&#xff09;搭建 EurekaServer 创建工程&#xff0c;导入依赖坐标&…
阅读更多...
Python-VBA函数之旅-globals函数

Python-VBA函数之旅-globals函数

目录 一、globals函数的常见应用场景&#xff1a; 二、globals函数与locals函数对比分析&#xff1a; 1、globals函数&#xff1a; 1-1、Python&#xff1a; 1-2、VBA&#xff1a; 2、推荐阅读&#xff1a; 个人主页&#xff1a;https://blog.csdn.net/ygb_1024?spm101…
阅读更多...
基于springboot+vue+Mysql的广场舞团管理系统

基于springboot+vue+Mysql的广场舞团管理系统

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…
阅读更多...
牛客小白月赛91

牛客小白月赛91

A.Bingbong的化学世界 链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 &#x1f319;“上…
阅读更多...
AndroidStudio右下角显示内存使用情况

AndroidStudio右下角显示内存使用情况

目录 一.具体效果 二.4.0以下版本 三.4.0以上版本 四.增加内存配置 一.具体效果 二.4.0以下版本 1.打开 Android Studio. 2.进入设置界面。点击 Android Studio 左上角的“File”&#xff0c;然后选择“Settings” 3.在设置界面中&#xff0c;选择“Appearance & Beha…
阅读更多...
关于图像YUV格式分类和排布方式的全学习

关于图像YUV格式分类和排布方式的全学习

【学习笔记】关于图像YUV格式分类和排布方式的全学习_yuv图像-CSDN博客 下图是将多个yuv420p图像(A和B)&#xff0c;拼接成一个画面的思路 A大小:416*64 B大小:416*208 将A和B合并到一个416*416的尺寸上&#xff0c;代码如下 //整合char * ptd;ptd (char * ) malloc (416*41…
阅读更多...
手把手教你实现 C 语言的函数多参默认值 「下」

手把手教你实现 C 语言的函数多参默认值 「下」

以下内容为本人的学习笔记&#xff0c;如需要转载&#xff0c;请声明原文链接 微信公众号「ENG八戒」https://mp.weixin.qq.com/s/ifnDcV7AKrh6eVihVK9l5A 本文上接《手把手教你实现 C 语言的函数多参默认值 上》&#xff0c;下文提及的一些概念来源于上文&#xff0c;为方便阅…
阅读更多...
使用LLM-API开发应用-DataWhale笔记

使用LLM-API开发应用-DataWhale笔记

调用API 先使用一个例子 from openai import OpenAI ​ client OpenAI(# This is the default and can be omittedapi_keyos.environ.get("OPENAI_API_KEY"), //这个在环境env中 ) ​ completion client.chat.completions.create(# 调用模型&#xff1a;ChatGPT-…
阅读更多...
【目标检测】YOLO系列-YOLOv1 理论基础 通俗易懂

【目标检测】YOLO系列-YOLOv1 理论基础 通俗易懂

为方便大家理解YOLO的原理&#xff0c;这里将YOLOv1的部分内容基础内容进行用比较直白的话和例子进行阐述&#xff0c;为后续大家学习YOLO作为铺垫。 1、模型所干的活 工作中&#xff0c;大家经常将 Word 文档 上传到某转换器&#xff0c;然后转换输出为PDF文档。目标检测中我…
阅读更多...
单点登录实现：一次登录，到处运行

单点登录实现：一次登录，到处运行

单点登录&#xff1a;一次登录&#xff0c;到处运行 举个场景&#xff0c;假设我们的系统被切割为N个部分&#xff1a;商城、论坛、直播、社交…… 如果用户每访问一个模块都要登录一次&#xff0c;那么用户将会疯掉&#xff0c; 为了优化用户体验&#xff0c;我们急需一套机制…
阅读更多...
组件安全（Solr、Shiro、Log4j、Jackson、FastJson、XStream）

组件安全（Solr、Shiro、Log4j、Jackson、FastJson、XStream）

Solr 主要基于HTTP和 Apache Lucene 实现的全文搜索服务器。 特征&#xff1a;图标识别 端口&#xff1a;8393 CVE-2019-0193&#xff08;远程命令执行漏洞&#xff09; 漏洞版本&#xff1a;Apache Solr < 8.2.0 利用条件&#xff1a; Apache Solr 的 DataImportHandler 启…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站