C语言-顺序表

发布于:2024-07-11 ⋅ 阅读:(28) ⋅ 点赞:(0)

在这里插入图片描述

🎯引言

欢迎来到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,并将 sizecapacity 置为 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博客,下一篇文章我们将探讨另一种常见的数据结构——链表,敬请期待!