【数据结构】顺序表---C语言版

这篇具有很好参考价值的文章主要介绍了【数据结构】顺序表---C语言版。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:

顺序表是一种常见的数据结构,今天就让我来带领大家一起学习一下吧!
不会再休息,一分一毫了,OK,let’s go!

一、线性表

  1. 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
    用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串
  2. 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的
    线性表在物理上存储时,通常以数组和链式结构的形式存储。

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

二、顺序表

1.顺序表的概念及结构:

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

2.顺序表的分类:

顺序表一般可以分为:

  1. 静态顺序表:使用定长数组存储元素。
//顺序表的静态存储
#define N 7
typedef int SLDataType;
 
typedef struct SeqList
{
	SLDataType array[N];//定长数组
	size_t size;//有效数据的个数
}SeqList;

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言
2. 动态顺序表:使用动态开辟的数组存储。

typedef struct SeqList
{
	SLDataType* array;//指向动态开辟的数组
	size_t size;//有效数据的个数
	size_t capacity;//容量
}SeqList;

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

3.顺序表缺陷:

  1. 顺序表缺陷:

(1)动态增容有性能消耗。

(2)当头部插入数据时,需要挪动数据

三、顺序表的代码实现:

1.头文件:

#pragma once

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

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* s;//顺序表的名称(头指针!)

	int size;//储存的有效个数!
	int capacity;//整块空间的大小!
}SL;


//初始化
void SLInit(SL* ps);
//销毁
void SLDestory(SL* ps);
//打印
void SLPrint(SL* ps);



//管理数据:增删查改

//尾插
void PushBack(SL* ps, SLDataType x);
//头插
void PushFront(SL* ps, SLDataType x);

//尾删
void PopBack(SL* ps);
//头删
void PopFront(SL* ps);

//判断是否扩容
void SLCheckCapacity(SL* ps);

//在pos位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);

2.函数文件:

#define _CRT_SECURE_NO_WARNINGS 1 
#include <stdio.h>
#include "SeqList.h"

//初始化函数
void SLInit(SL* ps)
{
	assert(ps);

	//创建空间
	ps->s = (SLDataType*)malloc(sizeof(SLDataType)*4);
	if (ps->s == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	ps->size = 0;
	ps->capacity = 4;
}

//销毁函数
void SLDestory(SL* ps)
{
	free(ps);

	ps->s = NULL;
	ps->size = ps->capacity = 0;
}

//打印函数
void SLPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->s[i]);
	}
	printf("\n");
}


//判断是否扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		//需要扩容
		SLDataType* tmp = (SLDataType*)realloc(ps->s, sizeof(SLDataType) * ps->capacity * 2);//扩大了原来容量的二倍。

		//SLDataType* tmp = (SLDataType*)realloc(ps->s, 2 * ps->capacity);标准的错误写法!
		//如果空间不够用,要对一些元素进行扩容。我们扩容的标准:就是为这些元素申请它 自身大小 整数倍 的空间!所以说为什么要sizeof(数据类型),然后再乘以扩大的容量的倍数
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->s = tmp;
		ps->capacity *= 2;
	}
	
}

//尾插
void PushBack(SL* ps, SLDataType x)
{
	//检查容量
	SLCheckCapacity(ps);

	ps->s[ps->size] = x;
	ps->size++;
}

//尾删
void PopBack(SL* ps)
{
	assert(ps);

	ps->size--;

}

//头插(利用一个end指针从后往前拷贝!)
void PushFront(SL* ps, SLDataType x)
{
	assert(ps);

	//检查容量
	SLCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->s[end+1] = ps->s[end];
		end--;
	}
	ps->s[0] = x;
	ps->size++;
}


//头删
void PopFront(SL* ps)
{
	assert(ps);

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


//在pos位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)

{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	SLCheckCapacity( ps);

	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->s[end+1] = ps->s[end];
		end--;
	}
	ps->s[pos] = x;
	ps->size++;
}

3.测试文件:

#define _CRT_SECURE_NO_WARNINGS 1 
#include <stdio.h>
#include "SeqList.h"



void test1()
{
	SL s1;
	SLInit(&s1);

	PushFront(&s1, 1);
	PushFront(&s1, 2);
	PushFront(&s1, 3);
	PushFront(&s1, 4);
	PushFront(&s1, 5);

	SLPrint(&s1);

	PopFront(&s1);
	PopFront(&s1);
	PopFront(&s1);

	SLPrint(&s1);

}


void test2()
{
	SL s2;

	SLInit(&s2);

	PushBack(&s2,1);
	PushBack(&s2,2);
	PushBack(&s2,3);
	PushBack(&s2,4);
	PushBack(&s2,5);

	SLPrint(&s2);

	PopBack(&s2);
	PopBack(&s2);
	PopBack(&s2);

	SLPrint(&s2);
}


void test3()
{
	SL s2;

	SLInit(&s2);

	PushBack(&s2, 1);
	PushBack(&s2, 2);
	PushBack(&s2, 3);
	PushBack(&s2, 4);
	PushBack(&s2, 5);

	SLPrint(&s2);

	SLInsert(&s2, 3, 6);//在下标为3的数据之前插入一个6

	SLPrint(&s2);
}

int main()
{

	//test1();//测试头插,头删

	//test2();//测试尾插 尾删

	test3();//测试在pos位置之前插入数据!
	return 0;

}

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

四、顺序表的相关OJ题:

(1)原地移除数组中所有的元素val:

1.题目描述:

1.原地移除数组中所有的元素val,要求时间复杂度为O(N),空间复杂度为O(1)。OJ链接:OJ链接
【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

2.思路表述:

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

3.代码实现:

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++];
        }
        else
        {
            src++;
        }
    }
    return dst;//返回的是:新数组的长度,因为最后一步出循环的时候,dst已经++了,所以说直接返回dst就行了
}

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

1.题目描述:

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

2.思路表述:

还使用双下标法:
【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

3.代码实现:

int removeDuplicates(int* nums, int numsSize) 
{
    int dst=1;
    int src=0;
    while(dst<numsSize)
    {
        if(nums[dst]!=nums[src])
        {
          //nums[++src]=nums[dst++];//这里的src一定要是前置++,先++,然后再赋值。
          
          src++;
          nums[src]=nums[dst];
          dst++;
        }
        else
        {
            
            dst++;
        }
    }
    return src+1;
}

(3)合并两个有序数组

1.题目描述:

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

2.思路表述:

使用3下标法
【数据结构】顺序表---C语言版,数据结构,c语言,开发语言

3.代码实现:

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--];
       }
   }
   //因为用nums1的初始长度是m+n,所以不会担心数组大小不够用。
   //下面这个循环是针对:比如说nums1中的所有数字都插到自己数组后面了,但是因为两个数组都是有序的,所以我只需要把nums2中的全部数字依次放到nums1前面就行了。
   while(end2>=0)
   {
       nums1[end--]=nums2[end2--];
   }
}

好了,今天的分享就到这里了
如果对你有帮助,记得点赞👍+关注哦!
我的主页还有其他文章,欢迎学习指点。关注我,让我们一起学习,一起成长吧!

【数据结构】顺序表---C语言版,数据结构,c语言,开发语言文章来源地址https://www.toymoban.com/news/detail-756864.html

到了这里,关于【数据结构】顺序表---C语言版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构(C语言)——顺序表详解

    数据结构是计算机存储和组织数据的方式。常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)等;而数据结构又可以通过逻辑结构与物理结构进行分类,逻辑结构是指数据元素之间的逻辑关系,也就是数据元

    2024年04月16日
    浏览(38)
  • 数据结构——顺序表(C语言版)

    顺序表是数据结构中最基本的一种线性表,它以一段连续的存储空间来存储数据元素,元素之间的顺序由它们在内存中的位置来决定。在C语言中,我们通常使用数组来实现顺序表。 目录 顺序表的结构定义 顺序表的基本操作 应用实例 顺序表的结构定义 首先,我们需要定义一

    2024年04月10日
    浏览(38)
  • 【数据结构|C语言版】顺序表

    各位小伙伴大家好!小编来给大家讲解一下数据结构中顺序表的相关知识。 【概念】数据结构是计算机存储、组织数据的⽅式。 数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合 数据结构反映数据的内部构成,即数据由那部分构成,以什么⽅式构成,以及数

    2024年04月16日
    浏览(32)
  • 数据结构c语言版:顺序表

        顺序表是一种 线性数据结构 ,它由一组连续的存储单元组成,用来存储具有相同数据类型的元素。顺序表中的元素按照逻辑顺序依次存放,并且可以通过索引来访问和修改元素。         两种:静态顺序表和动态顺序表。 静态顺序表: 静态顺序表使用 静态数组 来实现

    2024年02月02日
    浏览(41)
  • 顺序表—C语言实现数据结构

    本期带大家一起来用C语言代码实现顺序表🌈🌈🌈 顺序表是一段物理地址连续的存储单元,依次存储数据元素的线性结构。分为静态顺序表与动态顺序表。 🍊 🍋 🍒 静态顺序表 :使用定长数组用来存储数据 优点 :操作简单,代码实现容易 缺点 :定长数组很受限制,数

    2023年04月24日
    浏览(39)
  • 数据结构(c语言版) 顺序表

    2024年02月05日
    浏览(34)
  • 【数据结构】顺序表---C语言版

    顺序表是一种常见的数据结构,今天就让我来带领大家一起学习一下吧! 不会再休息,一分一毫了,OK,let’s go! 线性表(linear list)是n个具有 相同特性的数据元素 的有限序列。 线性表是一种在实际中广泛使 用的数据结构, 常见的线性表:顺序表、链表、栈、队列、字符

    2024年02月04日
    浏览(35)
  • 【数据结构】C语言实现顺序表

    顺序表是用顺序存储方式存放的线性表(可以理解为数组的存储方式),表中的元素在内存中彼此相邻。 静态存储:在定义时就确定了顺序表的大小,并且之后顺序表的大小不会改变(即使之后空间不够用了,也无法增加) 动态存储:线性表的大小可以根据需要更改(顺序

    2024年02月08日
    浏览(40)
  • 【数据结构|C语言版】顺序表应用

    上期回顾: 【数据结构|C语言版】顺序表 个人主页: C_GUIQU 各位小伙伴大家好!上期小编给大家讲解了数据结构中的顺序表,接下来讲讲顺序表该如何应用。 (1)能够保存联系人的姓名、年龄、性别、电话、住址 (2)添加联系人信息 (3)删除联系人信息 (4)修改联系人信

    2024年04月16日
    浏览(28)
  • 【数据结构】C语言实现顺序表(超级详细)

    目录 概念及结构 接口函数实现 顺序表的初始化 容量判断  顺序表尾插  顺序表尾删 顺序表头插 顺序表头删 顺序表查找 顺序表指定位置插入 顺序表指定位置删除 打印顺序表 销毁顺序表 顺序表完整代码 顺序表作为线性表的一种,它是用一段 物理地址连续的存储单元依次

    2024年04月10日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包