首页 > 资讯 > 后端开发 > 其他教程 >C语言顺序表的基本结构与实现思路详解

439

分享到

C语言顺序表的基本结构与实现思路详解

C语言顺序表 C语言顺序表的创建 2023-02-13 15:02:38 439人浏览独家记忆

摘要

目录一、顺序表的概念与结构1、线性表的解释2、顺序表概念解释二、顺序表的思路及代码实现详解1.静态顺序表的实现2.动态顺序表思路及代码实现2.1 动态顺序表的整体思路2.2 定义结构

一、顺序表的概念与结构

1、线性表的解释

首先我们在这里引入线性表的概念。线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。

常见的线性表：顺序表、链表、栈、队列、字符串……

线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数据和链式结构的形式存储。

顺序表就是线性表的一种，我们在这里详细解释一下顺序表的实现，后续我们会更新链表等内容。

2、顺序表概念解释

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

而顺序表一般可分为：

静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。

二、顺序表的思路及代码实现详解

1.静态顺序表的实现

我们先想出来一个静态表整体的模板思路：

定义一个结构体，该结构体包含一个可以存放数据的数组和记录数组中有效数字的变量。
初始化结构体。
打印结构体。
头插。
尾插。
头删。
尾删。
任意位置插入。
任意位置删除。

这里需要有一点注意的是，我们在定义结构体中的数组时，我们可以用typedef进行变量名简化，这也方便我们后期更改存储类型的时候直接更改typedef处就行。同时我们会想到数组的大小需要define定义一个宏，这样大大提高了代码后期的可维护性。

但是我们仔细想一下，假如我们存储的数据满了，我们想要继续存储的话还要找到源码进行更改大小。每次存储满了，都要更改。那是不是太麻烦了，且效率很低。这时候我们就联想到了动态的顺序表，可以自动开辟空间，从而大大提高效率。

这里我就给出大家静态顺序表定义及接口的代码，不再详细解释接口的实现了。我们这里详细解释一下动态顺序表的解释。静态顺序表接口的实现与动态顺序表接口实现大同小异，可参考动态顺序表接口的详解。

代码如下：

#define MAX_SIZE 10
typedef int SQDataType;
typedef struct SeqList
{
	SQDataType a[MAX_SIZE];
	int size;
}SL;
//typedef struct SeqList SL;
typedef struct SeqList SL;
//初始化结构体
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFrint(SL* ps, SQDataType x);
//头删
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意删
void SeqListErase(SL* ps, int pos);

2.动态顺序表思路及代码实现

2.1 动态顺序表的整体思路

动态顺序表的思路与静态大致相同，但也有所不同，我来给大家详细解释一下。我们先看动态顺序表的整体思路模板：

定义一个结构体，该结构体包含一个可以存放数据的动态数组和记录数组中有效数据的变量，两外还需要一个变量记录当前数组的大小。
初始化结构体。
打印结构体。
检查数组容量
头插。
尾插。
头删。
尾删。
任意位置插入。
任意位置删除。
释放动态数组空间

我们上面提到了动态的数组，需要用malloc或realloc动态开辟空间。由于是动态开辟的，我们这里多了一项释放动态开辟的空间。注意，记录数组的有效数据和数组大小并不相同。有效数据是已经存储的数据个数，而数组大小是指最能够存储数组的个数。我们为什么要记录数组的大小呢？这里是用来判断是否存储满了，满了话要开辟空间。

我们来详细看一下每个接口的实现。

2.2 定义结构体的实现

在定义结构体时，我们可以用typedef进行数组类型简化，同时方便我们后期更改存储类型的时候直接更改typedef处即可。同时我们也用typedef进行结构体类型简化，方便我们以后编辑代码。我们来看一下代码的实现：

typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;

通过上面的代码我们可以发现，当我们不想存储int型数据时，我们只需把‘typedef int SQDataType’改为‘typedef doubleSQDataType’即可。极大的提高了代码的维护性。

2.3 初始化结构体

我们初始化结构体时，可以先将数组置空，我们后期插入数据时可再开辟空间。同时当然有效数据和数组大小都要初始化成零。我们看代码的实现。

void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

我们这里是改变了结构体的内容，所以需要传地址，用指针变量来接收。

2.4 结构体打印

结构体打印方便我们观察对动态数组的操作。打印的时数组的有效数据的内容。我们来看代码的实现。

void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("\n");
}

2.5 检查数组容量

我们仔细想一想，是不是在插入每个数据之前都要检查数组是否已经满了。如果满了，则需要增容。如果没有满，就插入数据即可。在这里我们需要实现头插、尾插、任意插入三个接口，所以我们就把检查数组容量单独分装一个函数，这样提高代码的简洁性。我们看一下代码的实现。

void sqlCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

当我们检查增容时，我们还要判断一下之前的数组大小是否为零，如果是零的话，我们要给其赋一个值。因为我们刚开始初始化数组的时候把数组指针置空了。在动态顺序表中我们增容一般会扩大到原来的2倍。

2.6 头插

在插入之前要判断数组是否已经满了。头插的思想就是把数组的内容整体后移一位，我们把要插入的数据放在第一位。我们结合着代码一起理解。

void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

2.7 尾插

同样，在插入之前要判断数组是否已经满了。尾插的思想很简单。就是直接在数组尾部插入一个数据即可。我们看一下代码的实现。

void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.8 头删

删除时我们也有要注意的一点，就是检查数组中是否有元素给我们删除。头删的思想就是除去数组的第一个元素，我们将后面的元素整体向前移动一位，将第一位给覆盖了。我们来看代码。

void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

2.9 尾删

同样，在尾删之前，我们要检查数组中是否有元素给我们删除。尾删的思想十分简单，就是把数组的有效数据减一即可。我们看一下代码的实现。

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}

2.10 任意删除

在任意删除时，我们首先要判断删除的位置是否合理，不能违背顺序表的规则。同样，在尾删之前，我们要检查数组中是否有元素给我们删除。任意删除就是我们指出删除位置的下标进行删除。当然，我们想要删除数组中指定元素时，我们可以先查出元素下标在进行删除。这个相对来说较复杂一点，我们结合着代码理解一下。

//查找位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

2.11 任意插入

在任意插入时时，我们也要判断插入的位置是否合理，不能违背顺序表的规则。插入时，我们不能忘记检查数组是否满了。任意插入的思想与任意删除的思想基本相同。任意插入的思想就是在我们指出删除位置的下标进行插入。我们看一下代码实现。

void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SQLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

2.12 空间释放

由于我们的数组是动态开辟的，所以当我们不用时，我们要及时释放掉动态开辟的空间，避免内存泄漏。同时我们要把数组指针再次置空，避免产生野指针。我们看代码实现。

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

三、顺序表代码整合

由于代码量相对来说有一点多，所以我们就将函数的声明的定义分开，这样有利于提高代码的可读性，同时会保持一个良好的思路，且方便编写代码。

我们将函数的声明放在单独的一个SeqList.h的头文件，函数的实现放在一个单独的SeqList.c源文件，函数的主方法及调用放在另一个单独的test.c源文件。

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;
//初始化结构体
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFrint(SL* ps, SQDataType x);
//头删
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意删
void SeqListErase(SL* ps, int pos);
//销毁空间
void SeqListDestory(SL* ps);

SeqList.c

#include"SeqList.h"
//初始化结构体
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//打印
void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("\n");
}
//查容增容
void SQLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}
//头插
void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
//头删
void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
//查找位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//任意插——在下标为pos的位置插入数据
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SQLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
//任意删——删除下标为pos的数据
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}
//销毁空间
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

test.c

#include"SeqList.h"
void test()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushFrint(&s1, 1);
	SeqListPushFrint(&s1, 2);
	SeqListPushFrint(&s1, 3);
	SeqListPushFrint(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPrint(s1);
	SeqListPopFrint(&s1);
	SeqListPrint(s1);
	int pos = SeqListFind(s1, 1);
	SeqListInsert(&s1, pos, 10);
	SeqListInsert(&s1, 0, 20);
	SeqListPrint(s1);
	SeqListErase(&s1, 0);
	SeqListPrint(s1);
	SeqListDestory(&s1);
}
int main()
{
	test();
	return 0;
}

到此这篇关于C语言顺序表的基本结构与实现思路详解的文章就介绍到这了,更多相关C语言顺序表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言顺序表的基本结构与实现思路详解

本文链接: https://www.lsjlt.com/news/195830.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

C语言顺序表的基本结构与实现思路详解

目录一、顺序表的概念与结构1、线性表的解释2、顺序表概念解释二、顺序表的思路及代码实现详解1.静态顺序表的实现2.动态顺序表思路及代码实现2.1 动态顺序表的整体思路2.2 定义结构...

99+

2023-02-13

C语言顺序表 C语言顺序表的创建
C语言实现顺序表的基本操作的示例详解

目录一、认识顺序表1.线性表2.顺序表的概念及结构二、顺序表的基本操作（接口实现）1.初始化顺序表2.打印顺序表3.尾插4.尾删5.扩容6.头插7.头删8.任意位置插入9.任意位置删...

99+

2022-11-13

C语言顺序表基本操作 C语言顺序表操作 C语言顺序表
C++实现数据结构的顺序表详解

目录前言：代码1.SeqList.h2.SeqList.cpp3.test.cpp总结前言： hello，大家好，这篇文章博主来分享一下C++实现数据结构中的顺序表的代码。希望对大...

99+

2022-11-12
C语言堆与二叉树的顺序结构与实现

目录一. 二叉树的顺序结构二. 堆的概念及结构三. 堆的实现四. 堆排序(具有缺陷型)一. 二叉树的顺序结构普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全...

99+

2022-11-13
C语言实现串的顺序存储表示与基本操作

本文实例为大家分享了C语言实现串的顺序存储表示与基本操作代码，供大家参考，具体内容如下 1、串的三种存储表示串，即：字符串。要注意的是，C语言中是没有字符串数据类型的，而将其作为一...

99+

2022-11-12
C语言实现动态顺序表详解

目录什么是顺序表?1. 定义顺序表结构体：2. 初始化顺序表：3. 销毁顺序表：4. 打印顺序表：5. 判断容量+扩容：6. 头插数据：7. 尾插数据：8. 指定下标位置插入...

99+

2022-11-12
C语言数据结构之数组模拟实现顺序表流程详解

目录线性表和顺序表线性表顺序表静态顺序表动态顺序表代码已经放在Gitee上，需要可以小伙伴可以去看看用C语言数组模拟实现顺序表 Gitee 线性表和顺序表线性表线性表（line...

99+

2022-11-12
C语言数据结构顺序表的进阶讲解

目录前言一、顺序表的构造VS功能1.顺序表的构造2.接口实现（功能）二、功能具体分析1.初始化2.销毁3.检查size与capacity是否溢出4.尾增功能（实现）5.打印三、实现具...

99+

2022-11-13
C语言实现顺序表的全操作详解

目录线性表顺序表顺序表接口实现1.顺序表初始化2.顺序表空间增容3.顺序表打印4.尾插数据5.尾删数据6.头插数据7.头删数据8.在pos下标处插入数据9.删除pos下标处数据10....

99+

2022-11-13
C语言实现顺序表的基本操作指南(注释很详细)

目录创建一个结构体用于存放顺序表相关数据初始化顺序表插入元素先检查容量是否够用删除元素元素修改查找元素排序元素元素反转源码SeqList.ctest.cSeqList.h总结创建一个...

99+

2022-11-12
详解C语言内核中的链表与结构体

Windows内核中是无法使用vector容器等数据结构的，当我们需要保存一个结构体数组时，就需要使用内核中提供的专用链表结构LIST_ENTRY通过一些列链表操作函数对结构体进行装...

99+

2022-11-13
C语言实现单链表的基本功能详解

1.首先简单了解一下链表的概念: 要注意的是链表是一个结构体实现的一种线性表,它只能从前往后,不可以从后往前(因为next只保存下一个节点的地址).在实现单链表的操作时,需要用指针...

99+

2022-11-12
C语言实现线性表的基本操作详解

目录前言一、实训名称二、实训目的三、实训要求四、实现效果五、顺序存储代码实现六、链式存储代码实现前言这里使用的工具是DEV C++ 可以借鉴一下一、实训名称线性表的基本操作二...

99+

2022-11-12
C语言数据结构堆的基本操作实现

目录1.基本函数实现a.代码1(向下调整)b.代码2(向上调整)c.代码3(交换）2.建堆 3.插入数据4. 删除数据5.获取堆顶的数据6.堆的数据个数7.判空8.打印9.销毁10....

99+

2022-11-12
C语言深入浅出讲解顺序表的实现

目录1.线性表2.顺序表2.1 概念及结构2.2 提供接口2.3 接口实现今天起开始编写数据结构中的各种数据结构及算法的实现，说到顺序表，我们首先得了解下线性表。 1.线性表线性表...

99+

2022-11-13
C语言中单链表(不带头结点)基本操作的实现详解

目录一、单链表的概念二、单链表的基本操作1.创建单个结点2.创建具有n个结点的链表3.打印单链表4.尾插5.尾删6.头插7.头删8.查找某个结点9.在某个结点后面插入10.在某个结点...

99+

2022-11-16

C语言单链表操作 C语言单链表
新手向超详细的C语言实现动态顺序表

目录一、各个函数接口的实现 1.1 不太好‘'李姐‘'的“容量检测函数” 1.2 在任意位置插入的函数"坑！" 1.3 在任意位置删除数据的函数 1.4 其余简单的接口函数二、顺序...

99+

2022-11-12
C语言数据结构顺序表中的增删改(尾插尾删)教程示例详解

目录初始化尾插格局打开尾删初始化在初步认识顺序表这一结构后，我们就可以继续深入探究这是我之前在.h文件中创建的结构体 typedef int type; typedef struc...

99+

2022-11-13
C语言数据结构顺序表中的增删改(头插头删)教程示例详解

目录头插操作头删操作小结头插操作继上一章内容（C语言数据结构顺序表中的增删改教程示例详解），继续讲讲顺序表的基础操作。和尾插不一样，尾插出手阔绰直接的开空间，咱头插能开吗？好像没...

99+

2022-11-13
怎么使用Python仿照C语言来实现线性表的顺序存储结构

今天小编给大家分享一下怎么使用Python仿照C语言来实现线性表的顺序存储结构的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。...

99+

2023-06-16