【C/C++】静态顺序表详解（附完整源码）

news/2024/5/20 6:27:22 标签: c语言, 数据结构, 顺序表

本章内容

1.什么是线性表

2.什么是顺序表 

3.静态顺序表结构的定义

4.静态顺序表的函数接口实现

5.静态顺序表的问题及思考

1.什么是线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

2.什么是顺序表 

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

顺序表一般可以分为：

1.静态顺序表：使用定长数组存储元素。

2.动态顺序表：使用动态开辟的数组存储元素。

3.静态顺序表结构的定义

#define N 100
typedef int SLDataType;

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

4.静态顺序表的函数接口实现

//初始化顺序表
void SLInit(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->size = 0;
}
bool IsFull(SeqList* ps)
{
	assert(ps);
	if (ps->size == N)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void SLPushBack(SeqList* ps,SLDataType data)
{
	assert(ps);
	assert(!IsFull(ps));
	//插入数据
	ps->a[ps->size] = data;
	ps->size++;
}
void SLPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}
void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	assert(!IsFull(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);
	assert(!IsFull(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");
}

5.静态顺序表的问题及思考

1.静态顺序表的局限性

静态顺序表只适用于确定知道需要存多少数据的场景。如果数据量未知，N的值太大，造成空间浪费；N的值太小，数据存储不下。

2.接口函数的参数为什么要用结构体指针？

因为尾插、尾删与初始化需要改变结构的内容，若不用结构体指针，形参的改变无法影响实参，则导致无法完成任务；剩下的两个是为了统一与美观。

3.顺序表增删查改的时间复杂度

①顺序表的优势

顺序表的优势是尾插与尾删，为什么呢？

顺序表底层逻辑结构与数组相同，都是在内存上取一连串连续的空间来存储数据。既然这些空间是连续的，那么就意味着我们只需要记住这一连串空间的起始位置，若需要访问与起始位置只相差距离为5的位置时，我们只要在起始位置的地址上加5就可以一步到位。

尾插与尾删最重要的一步就是如何找到尾巴。然而数组几乎可以一步做到这一点，我们知道数组的起始位置，而且用size记录着数组有效长度，那么找尾可以说是及其简单，一步到位。

所以顺序表的尾插与尾删时间复杂度为O(1)。

②顺序表的劣势

与尾插尾删相比，顺序表最大的劣势就是头插与头删。

数组的空间开辟好之后，数组的起始位置已经固定了。我们不能想着将起始位置往前挪一格，然后留出来一个空位置进行插入；同样的也不能将起始位置往后挪一个就完成头删。

正确的头插与头删：

头插：从索引为0的位置开始，将所有数据向后平移一格，然后插入数据。

头删：从索引为1的位置开始，将所有数据向前平移一格，此时索引为0的位置的数据被索引为1的位置的数据覆盖掉了。

头插与头删关键的步骤是平移数据，因此头插与头删的时间复杂度为O(N)。

有关于数组更多详细的讲解，请参考这篇文章：

数据结构为何重要（数组）icon-default.png?t=MBR7http://t.csdn.cn/NB1Uw

6.完整源码

SeqList.h文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#define N 5
typedef int SLDataType;

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

//初始化顺序表
void SLInit(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);

SeqList.c文件

#define _CRT_SECURE_NO_DEPRECATE 1
#include"SeqList.h"

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

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

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

void SLPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	assert(!IsFull(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);
	assert(!IsFull(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");
}

bool IsFull(SeqList* ps)
{
	assert(ps);
	if (ps->size == N)
	{
		return true;
	}
	else
	{
		return false;
	}
}


http://www.niftyadmin.cn/n/26397.html

相关文章

Vue打印功能

Vue打印功能

这里介绍一个插件&#xff08;vue-print-nb&#xff09;&#xff0c;蛮好用的&#xff0c;用起来很方便&#xff0c;所以想记录一下 npm官方&#xff1a; https://www.npmjs.com/package/vue-print-nb 安装 V2版本 npm install vue-print-nb --save V3版本 npm install…
阅读更多...
SCI投稿：MDPI旗下期刊Mathematics投稿经历

SCI投稿：MDPI旗下期刊Mathematics投稿经历

最近写了篇论文&#xff0c;由于国内期刊现状&#xff08;懂的都懂&#xff09;&#xff0c;打算投国外的期刊&#xff0c;看来看去选择投MDPI旗下的Mathematics。手稿经过一轮大修之后顺利收到了Accepted&#xff0c;过程还是比较顺利的&#xff0c;记录一下投稿过程。 论文撰…
阅读更多...
C++【多线程】

C++【多线程】

文章目录一、什么是线程二、创建线程pthread_createpthread_join三、线程退出pthread_exitpthread_cancel线程idpthread_self四、进程对于共享资源的访问__thread五、分离线程pthread_detach六、线程互斥加锁保护互斥锁 &#xff08;全局&#xff09;pthread_mutex_tpthread_mu…
阅读更多...
Hi3861鸿蒙物联网项目实战：智慧农业

Hi3861鸿蒙物联网项目实战：智慧农业

华清远见FS-Hi3861开发套件&#xff0c;支持HarmonyOS 3.0系统。开发板主控Hi3861芯片内置WiFi功能&#xff0c;开发板板载资源丰富&#xff0c;包括传感器、执行器、NFC、显示屏等&#xff0c;同时还配套丰富的拓展模块。开发板配套丰富的学习资料&#xff0c;包括全套开发教程…
阅读更多...
前缀和差分算法

前缀和差分算法

前缀和&差分算法前言前缀和应用场景算法描述代码实现差分应用场景算法描述代码实现补充前言 2023.1.9 重学了前缀和与差分算法&#xff0c;特此写一篇小博客。 前缀和 应用场景 多次求区间和 算法描述 ΣΣΣf[i]a[i]f[i−1] a[i]f[i-1]a[i]f[i−1] 非常的好理解&…
阅读更多...
Java开发规范

Java开发规范

文章目录后端1、新增2、更新3、删除4、查询5、文件业务数据库表设计后端 1、新增 主键ID填充类型&#xff0c;创建时间、更新时间、创建用户&#xff0c;更新用户。建议 每个对象都应该保证有这些数据。参数校验问题。新增接口的参数对象&#xff0c;应该按每个字段的约束&am…
阅读更多...
【STM32学习】SysTick定时器（嘀嗒定时器）

【STM32学习】SysTick定时器（嘀嗒定时器）

SysTick定时器一、参考资料二、时钟源选择与定时时间计算1、时钟源选择2、定时时间计算三、SysTick_Handler中断服务函数一、参考资料 嘀嗒定时器&#xff1a;时钟源、寄存器 二、时钟源选择与定时时间计算 结合正点原子的代码进行说明&#xff1a; 1、时钟源选择 从上图可以发…
阅读更多...
xilinx srio ip学习笔记之再识srio

xilinx srio ip学习笔记之再识srio

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 xilinx srio ip学习笔记之再识srio前言SRIO的理解IP核的理解前言 这段时间&#xff0c;随着对SRIO的学习&#xff0c;又有了更深的一点认识&#xff0c;不像一开始这么慌张了…
阅读更多...
最新文章

Copyright @ 2022~2023