C语言-顺序表

  • 开发
  • 18

在这里插入图片描述

🎯引言

欢迎来到HanLop博客的C语言数据结构初阶系列。在这个系列中，我们将深入探讨各种基本的数据结构和算法，帮助您打下坚实的编程基础。本次我将为你讲解。顺序表（也称为数组）是一种线性表，因其简单易用而广泛应用于各类编程任务中。在本篇文章中，我们将介绍顺序表的基本概念、顺序表的创建和操作方法，以及其优缺点。通过一些实际的代码示例，您将更好地掌握顺序表在C语言中的应用，从而为后续学习其他数据结构打下坚实的基础。

👓顺序表

1.线性表

线性表的概念

线性表是数据结构中最基本、最常用的一种结构，由n个数据元素组成一个有限序列。线性表中的数据元素之间存在一对一的线性关系，即每个元素都有唯一的前驱和后继（除了第一个和最后一个元素）。常见的线性表有:顺序表、链表、栈、队列…

线性表的基本特点:

  1. 线性关系：每个元素有且仅有一个直接前驱和一个直接后继（第一个元素除外没有前驱，最后一个元素除外没有后继）。

  2. 唯一性：每个元素在表中的位置是唯一的。

  3. 相同类型：线性表中的所有元素都是相同的数据类型。

逻辑结构

线性表的逻辑结构是指线性表中元素之间的关系。线性表中的元素具有一对一的线性关系，即每个元素都有唯一的前驱和后继（第一个元素除外没有前驱，最后一个元素除外没有后继）。这种逻辑结构决定了线性表的基本操作和特点。

物理结构

线性表的物理结构是指线性表在计算机内存中的存储方式。主要有两种存储方式：

  1. 顺序存储结构（顺序表，数组）：
    • 元素依次存储在一段连续的内存空间中。
    • 优点：可以通过索引快速访问元素，查找效率高。
    • 缺点：插入和删除操作效率较低，因为需要移动大量元素。
  2. 链式存储结构（链表）：
    • 元素存储在任意的内存位置，元素之间通过指针连接。
    • 优点：插入和删除操作效率较高，不需要移动元素，只需改变指针。
    • 缺点：查找效率较低，因为需要从头遍历到所需位置。

2.顺序表

2.1概念

  • 定义：顺序表是由一组连续的存储单元组成的线性表，元素之间的逻辑顺序与物理存储位置相对应。
  • 特点：
    • 元素类型相同，存储在一块连续的内存空间中。
    • 支持通过索引快速访问元素。
    • 插入和删除操作需要移动大量元素，效率较低。
  • 适用场景：适合于元素数量固定且需要频繁进行查找操作的场景。

2.2结构

顺序表的物理结构如下：

存储结构：使用一段连续的内存空间存储元素，可以通过下标来访问各个元素。(底层本质上数组,对数组进行封装后成了顺序表)

基本操作：

  1. 插入操作：

    • 定义：在顺序表的指定位置插入一个新的元素。

    • 步骤：如果插入位置不在表尾，需要将插入位置后的元素依次后移一位，然后将新元素插入到指定位置。

    • 时间复杂度：最坏情况下是O(n)，因为可能需要移动表尾的所有元素。

  2. 删除操作：

    • 定义：删除顺序表中指定位置的元素。

    • 步骤：将删除位置后的元素依次前移一位，覆盖被删除的元素位置。

    • 时间复杂度：最坏情况下是O(n)，因为可能需要移动表尾的所有元素。

  3. 修改操作：

    • 定义：修改顺序表中指定位置的元素值。

    • 步骤：直接通过索引定位到指定位置，修改元素的值。

    • 时间复杂度：O(1)，因为修改操作是直接定位到位置进行修改。

  4. 查找操作：

    • 定义：查找顺序表中指定元素或元素位置。

    • 步骤：通过顺序表的索引直接访问指定位置的元素，或者遍历整个表查找特定元素。

    • 时间复杂度：最坏情况下是O(n)，因为可能需要遍历整个表来查找元素。

2.3分类

2.3.1静态顺序表：
  • 定义：静态顺序表是在程序运行前就确定了大小，内存空间是静态分配的，不可动态改变大小。
  • 特点：数组长度在创建时固定，不能动态增加或减少。
  • 优点：访问速度快，不需要额外的空间管理。
  • 缺点：浪费内存空间，不能适应动态变化的数据需求。
//静态顺序表
typedef int SLDateType;
#define N 10
typedef struct SeqList
{
	SLDateType a[N];
	int size;
}SeqList;
2.3.2动态顺序表：
  • 定义：动态顺序表是在程序运行时根据需要动态分配内存空间的顺序表。
  • 特点：可以动态地增加或减少数组的长度。
  • 优点：节约内存空间，适应动态变化的数据需求。
  • 缺点：可能导致频繁的内存分配和拷贝，影响性能。
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}SeqList;

2.4动态顺序表的实现

2.4.1SeqList.h文件
//SeqList.h文件的代码
#include <stdio.h>//标准输入输出库，提供了标准的输入输出函数。
#include <stdlib.h>//标准库，提供了动态内存分配、随机数生成、程序控制等函数。
#include <assert.h>//断言库，用于在程序中插入检查点，确保某个条件为真，如果条件为假则终止程序执行。


//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}SeqList;

//顺序表初始化
void SeqListInit(SeqList* p);
//顺表打印
void SeqListPrint(SeqList* p);
//顺序表的销毁
void SeqListDestory(SeqList* p);


//顺序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
//顺序表增容
void CheckCapacity(SeqList* p);
//顺序表头插
void SeqListPushFront(SeqList* p, SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* p);

//在pos位置插入数字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
//删除pos位置的数字
void SeqListErase(SeqList* p,int pos);
//找到指定的数字位置,返回下标
int SeqListFind(SeqList* p, SLDateType x);

代码解析:

动态顺序表结构体定义

typedef int SLDateType;
typedef struct SeqList
{
    SLDateType* a;  // 指向动态数组的指针
    int size;       // 当前动态顺序表中元素的个数
    int capacity;   // 当前动态顺序表的容量
} SeqList;
  • SLDateType：定义动态顺序表中存储的元素类型为 int。
  • struct SeqList：定义了动态顺序表的结构体，包含：
    • SLDateType* a：指向动态数组的指针，用于存储顺序表中的元素。
    • int size：当前动态顺序表中元素的个数。
    • int capacity：当前动态顺序表的容量，即可以存储的最大元素个数。

函数声明

// 顺序表初始化
void SeqListInit(SeqList* p);
// 顺序表打印
void SeqListPrint(SeqList* p);
// 顺序表的销毁
void SeqListDestory(SeqList* p);

// 顺序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
// 顺序表增容
void CheckCapacity(SeqList* p);
// 顺序表头插
void SeqListPushFront(SeqList* p, SLDateType x);
// 顺序表尾删
void SeqListPopBack(SeqList* p);

// 在pos位置插入数字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
// 删除pos位置的数字
void SeqListErase(SeqList* p, int pos);
// 找到指定的数字位置,返回下标
int SeqListFind(SeqList* p, SLDateType x);

这些函数声明定义了动态顺序表的基本操作：

  • SeqListInit：初始化动态顺序表。
  • SeqListPrint：打印动态顺序表中的元素。
  • SeqListDestory：销毁动态顺序表，释放内存。
  • SeqListPushBack：尾部插入元素。
  • CheckCapacity：检查并增加动态顺序表的容量。
  • SeqListPushFront：头部插入元素。
  • SeqListPopBack：尾部删除元素。
  • SeqListInsert：在指定位置插入元素。
  • SeqListErase：删除指定位置的元素。
  • SeqListFind：查找指定元素并返回其位置。

这些函数声明提供了对动态顺序表进行初始化、增删改查等基本操作的接口，具体的实现应该在对应的 SeqList.c 文件中完成。

2.4.2SeqList.c文件
//SeqList.c文件
//这里引入了头文件 SeqList.h，其中定义了动态顺序表的结构体 SeqList 和函数声明。
#include "SeqList.h"
//顺序表的初始化
void SeqListInit(SeqList* p)
{
	assert(p);
	p->a = NULL;
	p->size = p->capacity = 0;
}


//顺序表的销毁
void SeqListDestory(SeqList* p)
{
	assert(p);

	free(p->a);
	p->a = NULL;
	p->size = p->capacity = 0;
}

//顺序表打印
void SeqListPrint(SeqList* p)
{
	assert(p);
	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		printf("%d ", p->a[i]);
	}

	printf("\n");
}

//检查并增加动态顺序表的容量。
void CheckCapacity(SeqList* p)
{
	assert(p);
	int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;

	if (p->capacity == p->size)
	{
		p->capacity = newcapacity;
		SLDateType* tmp = (SLDateType*)
			realloc(p->a, p->capacity * sizeof(SLDateType));

		if (tmp != NULL)
		{
			p->a = tmp;
		}
		else
		{
			exit(1);
		}
	}
}

//顺序表尾插
void SeqListPushBack(SeqList* p, SLDateType x)
{
	assert(p);
	CheckCapacity(p);

	p->a[p->size] = x;
	p->size++;
}

//顺序表头插
void SeqListPushFront(SeqList* p, SLDateType x)
{
	assert(p);
	CheckCapacity(p);

	int i = 0;
	for (i = p->size; i > 0; i--)
	{
		p->a[i] = p->a[i-1];
	}

	p->a[0] = x;

	p->size++;
}

//顺序表尾删
void SeqListPopBack(SeqList* p)
{
	assert(p);
	assert(p->size);
	p->size--;

}

//顺序表头删
void SeqListPopFront(SeqList* p)
{
	assert(p);
	assert(p->size);
	int i = 0;
	for (i = 0; i < p->size-1; i++)
	{
		p->a[i] = p->a[i + 1];
	}
	p->size--;
}

//在pos位置插入数字
void SeqListInsert(SeqList* p, int pos, SLDateType x)
{
	assert(p != NULL);
	assert(pos >= 0 && pos <= p->size);

	//检查是否需要增容
	CheckCapacity(p);

	for (int i = p->size-1; i > pos-1 ; --i)
	{
		p->a[i + 1] = p->a[i];//p->a[pos+1]=p->a[pos]
	}
	p->a[pos] = x;

	p->size++;
}

//删除pos位置的数字
void SeqListErase(SeqList* p, int pos)
{
	assert(p != NULL);
	assert(pos >= 0 && pos < p->size);

	for (int i = pos; i < p->size-1; i++)
	{
		p->a[i] = p->a[i + 1];//p->a[size-2]=p->a[size-1]
	}

	p->size--;
}

//找到指定的数字位置,返回下标
int SeqListFind(SeqList* p, SLDateType x)
{
	assert(p != NULL);

	for (size_t i = 0; i < p->size; i++)
	{
		if (p->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

代码解析:

初始化函数 SeqListInit

void SeqListInit(SeqList* p)
{
    assert(p);
    p->a = NULL;
    p->size = p->capacity = 0;
}
  • 功能：初始化动态顺序表。
  • 说明：将动态顺序表指针 p 所指向的顺序表 a 设置为 NULL，并将 size（元素个数）和 capacity（容量）都设置为 0。使用断言 assert(p) 确保传入的指针 p 不为空。

销毁函数 SeqListDestory

void SeqListDestory(SeqList* p)
{
    assert(p);

    free(p->a);
    p->a = NULL;
    p->size = p->capacity = 0;
}
  • 功能：销毁动态顺序表。
  • 说明：释放动态顺序表 a 所指向的内存空间，将 a 置为 NULL，并将 size 和 capacity 置为 0。同样使用断言 assert(p) 确保传入的指针 p 不为空。

打印函数 SeqListPrint

void SeqListPrint(SeqList* p)
{
    assert(p);
    int i = 0;
    for (i = 0; i < p->size; i++)
    {
        printf("%d ", p->a[i]);
    }
    printf("\n");
}
  • 功能：打印动态顺序表中的元素。
  • 说明：遍历顺序表 a 中的每个元素，依次打印出来。使用断言 assert(p) 确保传入的指针 p 不为空。

增容函数 CheckCapacity

void CheckCapacity(SeqList* p)
{
    assert(p);
    int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;

    if (p->capacity == p->size)
    {
        p->capacity = newcapacity;
        SLDateType* tmp = (SLDateType*)
            realloc(p->a, p->capacity * sizeof(SLDateType));

        if (tmp != NULL)
        {
            p->a = tmp;
        }
        else
        {
            exit(1);
        }
    }
}
  • 功能：检查并增加动态顺序表的容量。
  • 说明：
    • 如果当前顺序表 a 的容量 capacity 等于当前元素个数 size，则表示需要增加容量。
    • 计算新的容量 newcapacity，如果当前容量为 0，则设置为 4，否则扩大为原来的两倍。
    • 使用 realloc 函数重新分配 a 的内存空间，将新的容量分配给 a。如果分配失败，程序退出。
    • 使用断言 assert(p) 确保传入的指针 p 不为空。

尾部插入函数 SeqListPushBack

void SeqListPushBack(SeqList* p, SLDateType x)
{
    assert(p);
    CheckCapacity(p);

    p->a[p->size] = x;
    p->size++;
}
  • 功能：在动态顺序表尾部插入元素 x。
  • 说明：首先调用 CheckCapacity 函数检查并增加容量。然后将元素 x 插入到顺序表 a 的末尾，并更新 size。

头部插入函数 SeqListPushFront

void SeqListPushFront(SeqList* p, SLDateType x)
{
    assert(p);
    CheckCapacity(p);

    int i = 0;
    //元素从后往前依次往后移动一位 注:不能从前往后 因为前面的元素往后移动会覆盖掉后面的元素
    for (i = p->size; i > 0; i--)
    {
        p->a[i] = p->a[i-1];
    }

    p->a[0] = x;
    p->size++;
}
  • 功能：在动态顺序表头部插入元素 x。
  • 说明：首先调用 CheckCapacity 函数检查并增加容量。然后将顺序表 a 中的所有元素后移一位，为新元素腾出空间，最后将 x 插入到顺序表 a 的第一个位置，并更新 size。

尾部删除函数 SeqListPopBack

void SeqListPopBack(SeqList* p)
{
    assert(p);
    assert(p->size > 0);

    p->size--;
}
  • 功能：从动态顺序表尾部删除元素。
  • 说明：首先使用断言 assert(p) 确保顺序表不为空，然后将 size 减一，表示删除尾部的元素。

头部删除函数 SeqListPopFront

void SeqListPopFront(SeqList* p)
{
    assert(p);
    assert(p->size > 0);

    int i = 0;
    //元素从前往后依次向前移动一位 
    for (i = 0; i < p->size-1; i++)
    {
        p->a[i] = p->a[i + 1];
    }
    p->size--;
}
  • 功能：从动态顺序表头部删除元素。
  • 说明：首先使用断言 assert(p) 确保顺序表不为空，然后将顺序表 a 中的所有元素前移一位，覆盖掉第一个元素，最后将 size 减一，表示删除头部的元素。

插入函数 SeqListInsert

void SeqListInsert(SeqList* p, int pos, SLDateType x)
{
    assert(p != NULL);
    assert(pos >= 0 && pos <= p->size);

    CheckCapacity(p);
	
    //元素从后往前依次向后移动一位 
    for (int i = p->size-1; i >= pos; --i)
    {
        p->a[i + 1] = p->a[i];
    }
    p->a[pos] = x;

    p->size++;
}
  • 功能：在指定位置 pos 插入元素 x。
  • 说明：
    • 首先使用断言确保顺序表和位置参数有效。
    • 调用 CheckCapacity 函数检查并增加容量。
    • 将插入位置 pos 后的所有元素依次后移一位，为新元素 x 腾出空间。
    • 将元素 x 插入到指定位置 pos，并更新 size。

删除函数 SeqListErase

void SeqListErase(SeqList* p, int pos)
{
    assert(p != NULL);
    assert(pos >= 0 && pos < p->size);
	
    //元素从前往后依次向前移动一位 
    for (int i = pos; i < p->size-1; i++)
    {
        p->a[i] = p->a[i + 1];
    }

    p->size--;
}
  • 功能：删除指定位置 pos 的元素。
  • 说明：
    • 首先使用断言确保顺序表和位置参数有效。
    • 将指定位置 pos 后的所有元素依次前移一位，覆盖掉要删除的元素。
    • 最后将 size 减一，表示删除了一个元素。

查找函数 SeqListFind

int SeqListFind(SeqList* p, SLDateType x)
{
    assert(p != NULL);

    for (size_t i = 0; i < p->size; i++)
    {
        if (p->a[i] == x)
        {
            return i;
        }
    }

    return -1;
}
  • 功能：查找顺序表中值为 x 的元素，返回其位置索引。
  • 说明：
    • 使用断言确保顺序表有效。
    • 遍历顺序表 a 中的所有元素，找到第一个值等于 x 的元素，返回其位置索引。
    • 如果未找到，返回 -1 表示未找到。

🥇结语

通过本篇文章，我们详细介绍了顺序表这一重要的数据结构及其在C语言中的实现与应用。我们探讨了顺序表的基本概念、操作方法以及优缺点，并通过实例代码展示了如何在实际编程中使用顺序表。掌握顺序表不仅有助于理解其他更复杂的数据结构，还能提高代码编写和优化能力。希望本文能为您的编程之旅提供有益的指导。请继续关注HanLop博客，下一篇文章我们将探讨另一种常见的数据结构——链表，敬请期待！

阅读全部

相关推荐

  2. 顺序表(C语言)

    2024-07-11 21:10:04       29 阅读

  4. 顺序表（C语言）

    2024-07-11 21:10:04       18 阅读

  8. 顺序表 （C语言版）

    2024-07-11 21:10:04       26 阅读

  9. 【C/C++】C语言实现顺序表

    2024-07-11 21:10:04       29 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-11 21:10:04       67 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-11 21:10:04       72 阅读

  9. 在Django里面运行非项目文件

    2024-07-11 21:10:04       58 阅读

  19. Python语言-面向对象

    2024-07-11 21:10:04       69 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-11 21:10:04       64 阅读

热门阅读

  5. Linux基础: 三. 相对路径和绝对路径

    2024-07-11 21:10:04       25 阅读

  6. Lemo 的 AGI 应用实战博文导航

    2024-07-11 21:10:04       19 阅读

  8. 音视频开发——FFmpeg 实现MP4转FLV文件 C语言实现

    2024-07-11 21:10:04       20 阅读

  9. Android 列表视频滑动自动播放—滑动过程自动播放(实现思路)

    2024-07-11 21:10:04       19 阅读

  10. Facebook机器人技术：社交互动与内容发布的智能化

    2024-07-11 21:10:04       22 阅读

  13. 【Spring】springSecurity中WebSecurityConfigurerAdapter类中configure方法（5版本以下）

    2024-07-11 21:10:04       20 阅读

  14. 【C#】遍历文件夹及其子文件夹指定后缀文件

    2024-07-11 21:10:04       19 阅读

  15. C语言从头学33——内存管理（一）

    2024-07-11 21:10:04       23 阅读

  19. Qt 的Q_PROPERTY关键字

    2024-07-11 21:10:04       20 阅读

  20. C++ 入门08：运算符重载

    2024-07-11 21:10:04       24 阅读

  21. [AI 大模型] 百度 文心一言

    2024-07-11 21:10:04       21 阅读

  24. 架构面试-场景题-单点登录(SSO)怎么实现的

    2024-07-11 21:10:04       24 阅读

  27. 深入理解Spring Boot中的事件驱动架构

    2024-07-11 21:10:04       21 阅读

  28. DDD架构面试问题

    2024-07-11 21:10:04       21 阅读