1. Toy模板网首页
  2. >Toy博客

『初阶数据结构 • C语言』⑧ - 动态顺序表详解（附完整源码）

1年前作者：花想云分类：Toy博客阅读(8)违法举报

这篇具有很好参考价值的文章主要介绍了『初阶数据结构 • C语言』⑧ - 动态顺序表详解（附完整源码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

本章内容

写在前面

1.静态与动态是指什么？

2.动态顺序表结构的定义

3.动态顺序表的函数接口实现

4.动态顺序表的问题及思考

5.关于顺序表的OJ题

6.OJ答案及解析

1.移除元素

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

​3.合并两个有序数组

7.动态顺序表完整源码

1.SeqList.h

2.SeqList.c

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构 

 文章来源地址https://www.toymoban.com/news/detail-600506.html

写在前面

上一章我们学习了静态顺序表的增删查改，并认识了静态顺序表的存储结构与静态顺序表的在不同场景下的优劣。静态顺序表与动态顺序表都叫做顺序表，只不过我们平时口头所提的顺序表指的是动态顺序表。静态顺序表的局限性太高，无法应对各种复杂的情况所以我们几乎不用它。本章我们就来学习动态顺序表的实现。

1.静态与动态是指什么？

静态顺序表：顺序表的大小固定，存储的数据个数有限。

#define N 5
typedef int SLDataType;

//静态顺序表
typedef struct SeqList
{
	SLDataType a[N];//定长数组
	int size;//记录存储多少个有效数据
}SeqList;

动态顺序表：运用动态内存管理，可按需调整顺序表的大小。

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//记录有多少个有效数据
	int capacity;//记录顺序表的容量大小
}SeqList;

2.动态顺序表结构的定义

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//记录有多少个有效数据
	int capacity;//记录顺序表的容量大小
}SeqList;

3.动态顺序表的函数接口实现

//初始化顺序表
void SLInit(SeqList* ps);
//释放空间
void SLDestroy(SeqList* ps);
//检查顺序表是否已满
void CheakCapacity(SeqList* ps);
//动态顺序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//动态顺序表的尾删
void SLPopBack(SeqList* ps);
//动态顺序表的头插
void SLPushFront(SeqList* ps, SLDataType data);
//动态顺序表的头删
void SLPopFront(SeqList* ps);
//pos位置插入数据
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置删除数据
void SLErase(SeqList* ps, int pos);
//查找数据
int SLFind(SeqList* ps, SLDataType data, int begin);
//判断数组是否已满
bool IsFull(SeqList* ps);
//打印存储的数据
void SLPrint(SeqList* ps);

以下是各个接口的实现：

void SLInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void SLDestroy(SeqList* ps)
{
	assert(ps);
	//若ps->a不为NULL，则释放空间
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}
void CheakCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//若是第一次扩容，则大小为4；
		//若不是第一次，则每次扩容为之前容量的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//检查是否做到扩容
	printf("扩容成功,现在的容量为:%d\n", ps->capacity);
}
void SLPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//插入数据
	ps->a[ps->size] = data;
	ps->size++;
}
void SLPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[0] = data;
	ps->size++;
}
void SLPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SLInsert(SeqList* ps, int pos, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[pos] = data;
	ps->size++;
}
void SLErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
int SLFind(SeqList* ps, SLDataType data, int begin)
{
	assert(ps);
	assert(begin < ps->size);
	for (int i = begin; i < ps->size; i++)
	{
		if (ps->a[i] == data)
		{
			return i;
		}
	}
	return -1;
}

void SLPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

4.动态顺序表的问题及思考

动态顺序表与静态顺序表的差别仅仅在与一个容量是固定的，一个可以按需扩容。

动态顺序表看似灵活性有所提高但仍存在着空间浪费，特别是扩容次数越多，越容易造成空间浪费。那么有没有其他的数据结构可以解决这个问题呢？答案是肯定的。这个神奇的数据结构叫做链表，它是一种基于节点的数据结构。下一章我们就会见到它。

动态顺序表和静态顺序表都称为顺序表，它们的性能是相同的。关于顺序表的性能优劣我已经在上一章介绍过了，点击小卡片即可跳转。

静态顺序表详解http://t.csdn.cn/zwU7I

5.关于顺序表的OJ题

1.移除元素

原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。 

移除元素https://leetcode.cn/problems/remove-element/

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

删除有序数组中的重复项https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

3.合并两个有序数组

合并两个有序数组https://leetcode.cn/problems/merge-sorted-array/

6.OJ答案及解析

1.移除元素

题目要求不能开辟新的数组，所以我们的做法是遇到等于val的元素时，将数组末尾的元素依次倒着覆盖掉等于val的元素。

代码实现;

int removeElement(int* nums, int numsSize, int val){
    int i=0;
    while(i<numsSize)
    {
        while(val==nums[i]&&i<numsSize)
        {
           nums[i]=nums[numsSize-1];
           numsSize--;
        }
        i++;
    }
    return numsSize;

}

以数组nums={3,2,5,6,3,5},val=3为例。

第一步，检查索引为0处的值是否等于val；

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

 第二步，将索引为5处的值拷贝到索引为0处；动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

 第三步，检查索引为1处的值；动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

第四步，检查索引为2处的值；动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

 第五步，检查索引为3处的值；动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

 第六步，检查索引为4处的值；

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

 第七步，将索引为4处的值拷贝到索引为4处；

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

此时i已经大于numsSize，循环结束。 

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

本题我采用的是双指针的方式，p1来记录当前位置，p2来寻找与p1处的值不相同的元素。

代码实现：

int removeDuplicates(int* nums, int numsSize){
    int* p1=nums;
    int* p2=nums+1;
    int i=0;
    int returnSize=1;//至少有一个元素
    for(i=0;i<numsSize-1;i++)
    {
        if(*p1!=*(p2+i))
        {
            *(++p1)=*(p2+i);
            returnSize++;
        }
    }
    return returnSize;
}

以数组nums={0,0,1,1,1,2,2,3,3,4}为例。

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

3.合并两个有序数组

这道题目我采用的是双指针的方式。p1指向nums1，p2指向nums2。另外需要额外开辟一个数组arr，当合并完成之后再将arr里的内容拷贝到nums1中。

代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=0;
    int j=0;
    int arr[200]={0};
    int* p1=nums1;
    int* p2=nums2;
    int k=0;//记录arr数组里元素的个数
    //检查数组是否为空
    if(nums2Size==0)
        return;
    //将nums1或nums2任何一个数组拷贝完成之后就结束
    while(i<nums1Size-nums2Size&&j<nums2Size)
    {
        if(p1[i]<p2[j])
        {
            arr[k]=p1[i];
            i++;
        }
        else
        {
            arr[k]=p2[j];
            j++;
        }
        k++;
    }
    //如果nums1先结束，将nums2中剩余的元素全部拷贝到arr
    if(i==nums1Size-nums2Size)
    {
        for(;j<nums2Size;j++)
        {
            arr[k++]=p2[j];
        }
    }
    //如果nums2先结束，将nums1中剩余的元素全部拷贝到arr
    if(j==nums2Size)
    {
        for(;i<nums1Size-nums2Size;i++)
        {
            arr[k++]=p1[i];
        }
    }
    //将arr中的元素拷贝回nums1
    for(k=0;k<nums1Size;k++)
    {
        nums1[k]=arr[k];
    }
}

7.动态顺序表完整源码

1.SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//记录有多少个有效数据
	int capacity;//记录顺序表的容量大小
}SeqList;

//初始化顺序表
void SLInit(SeqList* ps);
//释放空间
void SLDestroy(SeqList* ps);
//检查顺序表是否已满
void CheakCapacity(SeqList* ps);
//动态顺序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//动态顺序表的尾删
void SLPopBack(SeqList* ps);
//动态顺序表的头插
void SLPushFront(SeqList* ps, SLDataType data);
//动态顺序表的头删
void SLPopFront(SeqList* ps);
//pos位置插入数据
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置删除数据
void SLErase(SeqList* ps, int pos);
//查找数据
int SLFind(SeqList* ps, SLDataType data, int begin);
//判断数组是否已满
bool IsFull(SeqList* ps);
//打印存储的数据
void SLPrint(SeqList* ps);

2.SeqList.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"SeqList.h"

void SLInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLDestroy(SeqList* ps)
{
	assert(ps);
	//若ps->a不为NULL，则释放空间
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

void CheakCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		//若是第一次扩容，则大小为4；
		//若不是第一次，则每次扩容为之前容量的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//检查是否做到扩容
	printf("扩容成功,现在的容量为:%d\n", ps->capacity);
}

void SLPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//插入数据
	ps->a[ps->size] = data;
	ps->size++;
}

void SLPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[0] = data;
	ps->size++;
}

void SLPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SLInsert(SeqList* ps, int pos, SLDataType data)
{
	assert(ps);
	CheakCapacity(ps);
	//挪动数据
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	//插入数据
	ps->a[pos] = data;
	ps->size++;
}

void SLErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	//挪动数据
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

int SLFind(SeqList* ps, SLDataType data, int begin)
{
	assert(ps);
	assert(begin < ps->size);
	for (int i = begin; i < ps->size; i++)
	{
		if (ps->a[i] == data)
		{
			return i;
		}
	}
	return -1;
}

void SLPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

动态顺序表,新星计划免费学习专栏·数据结构与算法,c++,c语言,开发语言,数据结构

 

到了这里，关于『初阶数据结构 • C语言』⑧ - 动态顺序表详解（附完整源码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包赞助服务器费用

相关文章

  • 【数据结构初阶】二、 线性表里的顺序表（C语言实现顺序表）

    【数据结构初阶】二、 线性表里的顺序表（C语言实现顺序表）

    ========================================================================= 相关代码gitee自取 ： C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 ： 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月08日
    浏览(10)
  • 初阶数据结构之---顺序表和链表（C语言）

    初阶数据结构之---顺序表和链表（C语言）

    线性表： 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构，也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时，通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(42)
  • 【数据结构初阶】五、线性表中的栈（C语言 -- 顺序表实现栈）

    【数据结构初阶】五、线性表中的栈（C语言 -- 顺序表实现栈）

    ========================================================================= 相关代码gitee自取 ： C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 ： 【数据结构初阶】四、线性表里的链表（带头+双向+循环 链表 -- C语言实现）_高高的胖子的博客

    2024年02月08日
    浏览(25)
  • 【数据结构初阶】七、非线性表里的二叉树（堆的实现 -- C语言顺序结构）

    【数据结构初阶】七、非线性表里的二叉树（堆的实现 -- C语言顺序结构）

    ========================================================================= 相关代码gitee自取 ： C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 ： 【数据结构初阶】六、线性表中的队列（链式结构实现队列）-CSDN博客  ===========================

    2024年02月08日
    浏览(11)
  • 详解初阶数据结构之顺序表（SeqList）——单文件文件实现SeqList的增删查改

    详解初阶数据结构之顺序表（SeqList）——单文件文件实现SeqList的增删查改

    目录 一、线性表 二、顺序表 2.1概念及结构 2.2接口实现 2.3动态顺序表的创建 2.3动态顺序表的初始化 2.3.1传值初始化 2.3.2传址初始化 2.4动态顺序表的清空 2.5动态顺序表的扩容 2.6动态顺序表内容的打印 三、动态顺序表的使用 3.1尾插尾删 3.1.1尾插 3.1.2尾删 3.2头插头删 3.2.1头插

    2024年02月09日
    浏览(12)
  • 【数据结构专栏】动态扩容顺序栈详解

    【数据结构专栏】动态扩容顺序栈详解

      💌 博客内容：顺序栈的原理详解 😀 作  者：陈大大陈 🚀 个人简介：一个正在努力学技术的准前段，专注基础和实战分享 ，欢迎私信！ 💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘 目录 顺序栈的定义 结构体定义

    2023年04月09日
    浏览(11)
  • 【数据结构】顺序表的动态分配(步骤代码详解）

    【数据结构】顺序表的动态分配(步骤代码详解）

    🎈个人主页：豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏：数据结构 🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！ 在计算机科学中，数据结构是组织和存储数据的方式，它决定了数据如何被存储、检索和操作。

    2024年04月12日
    浏览(9)
  • C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    本篇讲述了顺序表的相关知识，以及动态顺序表的代码实现。 顺序表和链表一般情况下都会叫他们线性表。 线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性

    2024年02月07日
    浏览(10)
  • 数据结构（C语言）——顺序表详解

    数据结构（C语言）——顺序表详解

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

    2024年04月16日
    浏览(12)
  • [C语言][数据结构][动态内存空间的开辟]顺序表的实现!

    [C语言][数据结构][动态内存空间的开辟]顺序表的实现!

    目录 零.必备知识 a.顺序表的底层是数组. b.数组在内存中是连续存放的. c.动态内存空间的开辟(malloc,calloc,realloc). 一.顺序表的定义与实现          1.1 顺序表的定义          1.2 顺序表的初始化          1.3 顺序表的销毁          1.4 顺序表容量的检查与调整

    2024年04月09日
    浏览(14)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包