首页 > 其他分享 >顺序表专题

顺序表专题

时间：2024-04-07 23:30:32浏览次数：21  
标签：ps arr 专题 void SL 顺序 sl size

欧克，今天就让我们小小来看个顺序表吧！

在这里插入图片描述

目录

顺序表

1、顺序表的概念及结构

1.1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。
线性表指的是具有部分相同特性的⼀类数据结构的集合

2、顺序表分类

顺序表和数组的区别
顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口，由于数组在物理结构与逻辑结构上是连续的，所以顺序表也是如此

静态顺序表

概念：使用定长数组存储元素
在这里插入图片描述
静态顺序表的缺陷：空间给少了不够用，给多了造成空间浪费

动态顺序表 ---- 按需申请

在这里插入图片描述

3.动态顺序表的实现

完成这个动态顺序表，我们需要创建3个文件，一个头文件— 让人一看就能知道有什么内容（类似书籍的目录），两个源文件 — 一个用于实现动态顺序表的功能，一个用于测试代码
在这里插入图片描述
这里我对头文件命名为SeqList.h，顺序表实现源文件为SeqList.c，测试文件为test.c
首先，我们需要定义一个结构体
在这里插入图片描述

结构体定义好后，我们就要开始实现动态顺序表的内容了！具体实现内容如下：

//顺序表的初始化
void SLInit(SL* ps);
//顺序表内存空间的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置删除
void SLErase(SL* ps, int pos);
//查找元素
int SLFind(SL* ps, SLDataType x);

1.顺序表的初始化

SeqList.c
void SLInit(SL* ps)
{
	ps->arr= NULL;
	ps->capacity = 0;
	ps->size = 0;
}
test.c
int main()
{
	SL sl;
	SLInit(&sl);
	return 0;
}

注意：这里应该用传址调用
在这里插入图片描述

2.顺序表的销毁

这里先把销毁这一个先给实现了，比较容易哈哈

void SLDestroy(SL* ps)
{
	if (ps->arr)//等价于ps->arr!=NULL（NULL的ASCII码值为0）
	{
		free(ps->arr);//将动态开辟的空间进行销毁
	}
	ps->arr = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

下面就是重头戏了！看过来！！

3.顺序表尾插

在这里插入图片描述

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//判断ps是否为空指针
	if (ps->size == ps->capacity)
	{
	//一开始capacity可能为0，所以在为0情况先为其开辟4个空间，若不为0，则对其按2倍或3倍的倍数进行扩容
	int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//三目表达式
	//定义一个新的指针来接收realloc的返回值，因为当我们扩容失败的时候，realloc会返回空指针NULL，这样就没必要进行下去了
	SLDataType* tmp = realloc(ps->arr, newCapacity * sizeof(SLDataType));
	if (tmp == NULL)
	{
		perror("realloc");
		return 1;
	}
	//到了此处说明空间申请成功
	ps->arr = tmp;
	ps->capacity = newCapacity;
}
	ps->arr[ps->size] = x;//尾插操作
	ps->size++;//尾插完后记得使size（有效数据个数+1）
}

在这里插入图片描述

4.头插

在这里插入图片描述
那么，既然头插也需要判断空间大小是否足够，是否需要扩容，那我们是不是可以将判断是否扩容这一模块封装成一个函数，减少代码量，如下是尾插与扩容分开

//扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//一开始capacity可能为0，所以在为0情况先为其开辟4个空间，若不为0，则对其按2倍或3倍的倍数进行扩容
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			//exit(1);//直接退出程序，不再继续执行
			return 1;
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);//调用该函数判断是否需要进行扩容
	ps->arr[ps->size] = x;
	ps->size++;
}

现在，就让我们来写头插吧！

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);//记得判断是否为空指针
	SLCheckCapacity(ps);//判断是否需要进行扩容
	//将数据都向后移动一位，需从最后一个元素开始移动
	for (int i = ps->size; i > 0; i--)//书写for循环的时候不知判断条件可以先写下面最后判断完再写
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]
	}
	ps->arr[0] = x;//将下标为0的位置赋予我们想要的值
	ps->size++;//有效数据个数+1
}

尾插、头插讲完后，就需要去实现我们的尾删和头删了！

5.尾删

void SLPopBack(SL* ps)
{
	assert(ps);//等价于assert(ps!=NULL)
	//顺序表不能为空，所以我们需要判断有效数据大小是否大于0，否则也没数据给他删
	assert(ps->size);
	ps->size--;//尾删实际上就是把有效数据个数-1即可，直接把下标为size-1的元素丢掉
}

是不是很简单啊

6.头删

在这里插入图片描述

void SLPopFront(SL* ps)
{
	assert(ps);//判断是否为空指针
	assert(ps->size);//顺序表不能为空
	//把下标为1开始的每个元素纷纷向前移动一位，从前面开始移动
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
	}
	ps->size--;//有效数据大小-1
}

实现完头插、尾插、头删、尾删之后，就到了我们插队上场了，哈哈！

7.指定位置插入

顾名思义：想插哪插哪（当然，是在有效数据大小范围内的）
)
在这里插入图片描述

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);//判断是否为空指针
	assert(pos >= 0 && pos <= ps->size);//判断pos是否超出范围
	SLCheckCapacity(ps);//判断空间大小是否需要扩容
	//将下标为pos开始的所有数据纷纷向后移动，需从后面开始先移动
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos]
	}
	ps->arr[pos] = x;//将指定位置赋予我们想要的值
	ps->size++;//有效数据大小+1
}

8.指定位置删除

在这里插入图片描述

void SLErase(SL* ps, int pos)
{
	assert(ps);//判断是否为空指针
	assert(pos >= 0 && pos < ps->size);//判断pos是否超出范围
	//将pos后面的数据向前移动一位，需要从pos后一个元素开始移动
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
	}
	ps->size--;//有效数据大小-1
}

9.查找指定元素

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);//判断是否为空指针
	for (int i = 0; i < ps->size; i++)//遍历顺序表，查看有无我们要查找的数值，有则返回下标，无则返回一个不相干的数，比如-1，数组没有下标为-1的吧
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//最后通过在test.c接收的值判断即可

10.打印顺序表

哈哈，差点忘了还有他

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

这就不用多说什么了吧，简简单单的打印！

test.c

下面是test.c源文件的测试代码，记得，写完一个功能最好就调试一次，看是否有错误，不然等你写完一切再检查，出了一堆报错的话你就会晕了，这里不方便展示就不展示了

#include"SeqList.h"
int main()
{
	SL sl;
	//尾插测试
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	
	//头插测试
	// 
	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);
	//SLPushFront(&sl, 3);
	//SLPushFront(&sl, 4);
	//SLPushFront(&sl, 5);
	//尾删测试
	// 
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//头删测试
	// 
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//指定位置插入测试
	// 
	//SLInsert(&sl, 5, 6);
	//SLInsert(&sl, 0, 6);
	//SLInsert(&sl, 3, 6);
	//指定位置删除
	// 
	//SLErase(&sl, 4);
	//SLErase(&sl, 0);
	//SLErase(&sl, 3);
	//查找元素
	int ret = SLFind(&sl, 5);
	if (ret == -1)
		printf("找不到呢\n");
	else
		printf("找到了，它的下标为%d\n", ret);
	
	//打印
	SLPrint(&sl);
	SLDestroy(&sl);
	return 0;

}

总营地

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据的个数
	int capacity;//空间大小
}SL;
//顺序表的初始化
void SLInit(SL* ps);
//顺序表内存空间的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插?删除 / 尾部插?删除
//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//指定位置之前插?/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置删除
void SLErase(SL* ps, int pos);
//查找元素
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"
//顺序表的初始化
void SLInit(SL* ps)
{
	ps->arr= NULL;
	ps->capacity = 0;
	ps->size = 0;
}
//顺序表内存空间的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)//等价于ps->arr!=NULL（NULL的ASCII码值为0）
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
//顺序表的打印
void SLPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
//扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//一开始capacity可能为0，所以在为0情况先为其开辟4个空间，若不为0，则对其按2倍或3倍的倍数进行扩容
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			//exit(1);//直接退出程序，不再继续执行
			return 1;
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//头部插入删除 / 尾部插入删除
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//将数据都向后移动一位，需从最后一个元素开始移动
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]
	}
	ps->arr[0] = x;
	ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
	assert(ps);//等价于assert(ps!=NULL)
	//顺序表不能为空
	assert(ps->size);
	ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//把下标为1开始的每个元素纷纷向前移动一位，从前面开始移动
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
	}
	ps->size--;
}
//指定位置之前插?/删除数据
//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	//将下标为pos开始的所有数据纷纷向后移动，需从后面开始先移动
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos]
	}
	ps->arr[pos] = x;
	ps->size++;
}
//指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//将pos后面的数据向前移动一位，需要从pos后一个元素开始移动
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
	}
	ps->size--;
}
//查找元素
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

test.c

#include"SeqList.h"
int main()
{
	SL sl;
	//尾插测试
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	
	//头插测试
	// 
	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);
	//SLPushFront(&sl, 3);
	//SLPushFront(&sl, 4);
	//SLPushFront(&sl, 5);
	//尾删测试
	// 
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//头删测试
	// 
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//SLPopFront(&sl);
	//指定位置插入测试
	// 
	//SLInsert(&sl, 5, 6);
	//SLInsert(&sl, 0, 6);
	//SLInsert(&sl, 3, 6);
	//指定位置删除
	// 
	//SLErase(&sl, 4);
	//SLErase(&sl, 0);
	//SLErase(&sl, 3);
	//查找元素
	int ret = SLFind(&sl, 5);
	if (ret == -1)
		printf("找不到呢\n");
	else
		printf("找到了，它的下标为%d\n", ret);
	
	//打印
	SLPrint(&sl);
	SLDestroy(&sl);
	return 0;

}
到这里，顺序表就基本结束了，希望你有所收获！！

在这里插入图片描述

标签：ps,arr,专题,void,SL,顺序,sl,size
From： https://blog.csdn.net/2401_82669614/article/details/137477962

相关文章

  • 【思维专练】专题训练 1
    前言思维训练1，几乎没有什么算法，枚举or搜索or二分CF1681DRequiredLength\(\mathtt{TAGS}\)：暴搜+剪枝前置函数下文中称：\(len(x)\)为\(x\)十进制下的位数。First.为什么是搜索开始看到这道题想到了贪心：每次找出最大的一个数乘上去。但是很显然：可以先乘一......
  • 通讯录----顺序表版本
    1.通讯录的实现逻辑对于通讯录，我们做的无非就是初始化，销毁。添加联系人数据，修改联系人数据，删除联系人数据，查找联系人数据，展示联系人数据；这个不就和我们的顺序表的逻辑如出一辙吗，顺序表实现的功能不就是数据的初始化，修改，删除（头删和尾删），添加（头插和尾插），顺序表的打印，这些我们是可......
  • 数据结构之顺序表
    目录一、顺序表源代码1.1SeqList.h1.2SeqList.c二、顺序表的应用2.1Contact.h2.2Contact.c2.3SeqList.h2.4SeqList.c2.5main.c一、顺序表源代码顺序表的底层实现为数组，源代码以整形数据为例，使用C语言编写1.1SeqList.htypedefintSLDataType;//动态顺......
  • 【专题】2023新消费品牌的中国范式报告PDF合集分享（附原数据表）
    原文链接：https://tecdat.cn/?p=34074原文出处：拓端数据部落公众号近年来，随着中国消费升级的趋势，新兴消费品牌在市场上逐渐崭露头角。这些品牌以挑战者的身份进入市场，通过创新的供应链、产品和营销策略，以用户为核心满足新的消费需求，实现了短期内的强劲增长和销售规模的快速扩张。......
  • 【专题】2024年3月电商行业报告合集汇总PDF分享（附原数据表）
    原文链接：https://tecdat.cn/?p=35663原文出处：拓端数据部落公众号随着数字技术的飞速发展，电商行业正经历着前所未有的变革。本报告合集汇总旨在梳理2024年3月电商领域的最新动态和发展趋势。我们将从行业趋势与细分领域研究入手，深入探讨3C数码商用品、母婴营养品以及AI数字人产......
  • 蓝桥杯，省赛，动态规划专题，青蛙，更小的数，松散子序列，接龙数列
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e5+9;doublex[N],a[N],b[N];doubledp[N][5];intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>x[i];for(inti=1;i<=n-1;i++)cin>>a[i]>>b[i......
  • 顺序栈功能函数（包括判断回文、数值转化、括号匹配）
    一，具体代码#include<iostream>#include<stdlib.h>usingnamespacestd;#defineOK1#defineERROR0#defineMAXSIZE100typedefintElemType;typedefintStatus;typedefstruct {   ElemType*elem;   inttop;}Sqstack;StatusInitStack(Sqstack......
  • 顺序栈和链栈的部分功能完整代码
    一、顺序栈代码#include<iostream>#include<stdlib.h>usingnamespacestd;#defineOK1#defineERROR0#defineMAXSIZE100typedefintElemType;typedefintStatus;typedefstruct {   ElemType*elem;   inttop;}Sqstack;StatusInitStack(Sqsta......
  • 动态规划专题
    动态规划专题A.HelpingPeople神仙概率题容易发现给定的区间限制满足树形关系，考虑建树。个人认为最难理解的一点是，期望最大值并不是简单相加，所以直接设期望DP是很难做的。设$a[i]$表示原来第\(i\)个人的钱数，$dp[i][j]$表示第\(i\)个节点最大钱数小于等于$max{......
  • 1600. 王位继承顺序
    题面核心思想纯模拟！没反应过来是前序遍历~privateMap<String,List<String>>children;表示一个人的孩子当调用getInheritanceOrder时通过map搜索答案，由于孩子也有可能有孩子，无限套娃，所以通过递归搜索建立答案。建立答案的时候也不用考虑是否死亡，我们搜索完成后在去删除......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99