顺序表——“数据结构与算法”

各位CSDN的uu们你们好呀，今天小雅兰的内容是数据结构与算法里面的顺序表啦，在我看来，数据结构总体上是一个抽象的东西，关键还是要多写代码，下面，就让我们进入顺序表的世界吧

线性表

顺序表

线性表

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

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

 顺序表

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

顺序表就是数组，但是在数组的基础上，它还要求数据是从头开始连续存储的，不能跳跃间隔 

顺序表一般可以分为：

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

#define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#include"SeqList.h"
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType arr[N];//定长数组
	size_t size;//表示数组中存储了多少数据
}SL;

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

#define _CRT_SECURE_NO_WARNINGS 1
#define N 7
#include"SeqList.h"
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* arr;//指向动态开辟的数组
	size_t size;//表示数组中存储了多少数据
	size_t capicity;//数组实际能存储数据的空间容量是多大
}SL;

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。  

在这里，所有函数命名风格都是跟着STL走的，方便小雅兰日后的学习！！！ 

顺序表的初始化：

void SeqListInit(SL* ps)//顺序表的初始化
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

注意：在这里，不可以使用传值调用的方式，只能使用传址调用的方式

void SeqListInit(SL ps)//顺序表的初始化
{
	ps.arr = NULL;
	ps.size = ps.capacity = 0;
}

万万不能使用这样的方式初始化，因为：在函数传参的时候，形参是实参的一份临时拷贝，对形参的修改并不会影响实参

 顺序表的打印：

void SeqListPrint(SL* ps)//顺序表的打印
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

扩容：

void SeqListCheckCapacity(SL* ps)//检查空间，如果满了，进行扩容
{
	//如果没有空间或者空间不足，那么我们就扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

顺序表销毁：

void SeqListDestroy(SL* ps)//顺序表销毁
{
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

尾插：

void SeqListPushBack(SL* ps, SLDateType x)//尾插
{
	SeqListCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

尾删：

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

 头插：

void SeqListPushFront(SL* ps, SLDateType x)//头插
{
	SeqListCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

头删：

void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size > 0);
	//挪动数据
	int begin = 0;
	while (begin < ps->size-1)
	{
		ps->arr[begin] = ps->arr[begin+1];
		++begin;
	}
	ps->size--;
}
另一种写法： 
void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size > 0);
	//挪动数据
	int begin = 1;
	while (begin < ps->size)
	{
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;
	}
	ps->size--;
}

 顺序表查找：

//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

 指定pos下标位置插入：

// 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{
	温柔的写法
	//if (pos > ps->size || pos < 0)
	//{
	//	printf("pos invalid!\n");
	//}
	//粗暴的写法
	assert(pos <= ps->size || pos >= 0);
	SeqListCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

 然后，写出了这个函数的功能之后，我们发现：可以对之前写的头插和尾插搞一些事情，下面，我们开始搞事情！！！

头插和尾插：

void SeqListPushBack(SL* ps, SLDateType x)//尾插
{
	SeqListInsert(ps, ps->size, x);
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{
	SeqListInsert(ps, 0, x);
}

 删除pos位置的数据：

//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos)
{
	assert(pos < ps->size || pos >= 0);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;
	}
	ps->size--;
}

写出这个函数的功能之后，我们又可以搞事情啦！！！

头删和尾删：

void SeqListPopBack(SL* ps)//尾删
{
	SeqListErase(ps, 0);
}
void SeqListPopFront(SL* ps)//头删
{
	SeqListErase(ps, ps->size - 1);
}

菜单：

void menu()
{
	printf("#############################################\n");
	printf("\n");
	printf("###################1.头插#####################\n");
	printf("\n");
	printf("###################2.头删#####################\n");
	printf("\n");
	printf("###################3.尾插######################\n");
	printf("\n");
	printf("###################4.尾删######################\n");
	printf("\n");
	printf("###################5.打印#####################\n");
	printf("\n");
	printf("###################0.exit#####################\n");
	printf("\n");
	printf("##############################################\n");
}

其实，最好不要一上来就写菜单，先写单元测试，菜单不方便调试

 测试菜单函数：

void MenuTest()
{
	SL s1;
	SeqListInit(&s1);
	int input = 0;
	int x;
	while (input != -1)
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你要头插的数据，以-1结束：");
			while (x != -1)
			{
				SeqListPushFront(&s1, x);
				scanf("%d", &x);
			}
			break;
		case 2:
			SeqListPopFront(&s1);
			break;
		case 3:
			printf("请输入你要尾插的数据，以-1结束：");
			while (x != -1)
			{
				SeqListPushBack(&s1, x);
				scanf("%d", &x);
			}
			break;
		case 4:
			SeqListPopBack(&s1);
			break;
		case 5:
			SeqListPrint(&s1);
			break;
		case 0:
			printf("退出程序\n");
			break;
		default:
			printf("输入错误，请重新输入\n");
		}
	}
}

源代码如下：

SeqList.h的内容：

#pragma once
#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<assert.h>
#define N 7
typedef int SLDateType;
//顺序表的动态存储
typedef struct SeqList
{
	SLDateType* arr;//指向动态开辟的数组
	size_t size;//表示数组中存储了多少数据
	size_t capacity;//数组实际能存储数据的空间容量是多大
}SL;
//基本增删查改接口
void SeqListInit(SL* ps);//顺序表的初始化
void SeqListPrint(SL* ps);//顺序表的打印
void SeqListCheckCapacity(SL* ps);//检查空间，如果满了，进行扩容
void SeqListDestroy(SL* ps);//顺序表销毁
void SeqListPushBack(SL* ps, SLDateType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDateType x);//头插
void SeqListPopFront(SL* ps);//头删
//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x);
//顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x);
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos);

SeqList.c的内容：

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SL* ps)//顺序表的初始化
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
void SeqListPrint(SL* ps)//顺序表的打印
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
void SeqListCheckCapacity(SL* ps)//检查空间，如果满了，进行扩容
{
	//如果没有空间或者空间不足，那么我们就扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}
void SeqListDestroy(SL* ps)//顺序表销毁
{
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
void SeqListPushBack(SL* ps, SLDateType x)//尾插
{
	SeqListCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}
void SeqListPopBack(SL* ps)//尾删
{
	assert(ps->size > 0);
	ps->size--;
}
void SeqListPushFront(SL* ps, SLDateType x)//头插
{
	SeqListCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}
void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size > 0);
	//挪动数据
	int begin = 1;
	while (begin < ps->size)
	{
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;
	}
	ps->size--;
}
//顺序表查找
//找到了返回x位置的下标，没有找到返回-1
int SeqListFind(SL* ps, SLDateType x)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}
// 顺序表指定pos下标位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDateType x)
{
	温柔的写法
	//if (pos > ps->size || pos < 0)
	//{
	//	printf("pos invalid!\n");
	//}
	//粗暴的写法
	assert(pos <= ps->size || pos >= 0);
	SeqListCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}
//顺序表删除pos位置的数据
void SeqListErase(SL* ps, size_t pos)
{
	assert(pos < ps->size || pos >= 0);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;
	}
	ps->size--;
}

好啦，小雅兰今天的内容就到这里啦，数据结构的的确确是一个麻烦的东西，还要加油呀！！！

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/513.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【LeetCode】剑指 Offer（25）

【LeetCode】剑指 Offer（25）

目录 题目&#xff1a;剑指 Offer 49. 丑数 - 力扣&#xff08;Leetcode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 写在最后&#xff1a; 题目&#xff1a;剑指 Offer 49. 丑数 - 力扣&…
阅读更多...
【云原生】Linux进程控制(创建、终止、等待)

【云原生】Linux进程控制(创建、终止、等待)

✨个人主页&#xff1a; Yohifo &#x1f389;所属专栏&#xff1a; Linux学习之旅 &#x1f38a;每篇一句&#xff1a; 图片来源 &#x1f383;操作环境&#xff1a; CentOS 7.6 阿里云远程服务器 Good judgment comes from experience, and a lot of that comes from bad jud…
阅读更多...
MySQL对表操作

MySQL对表操作

目录 CRUD 增加(Create) 查询&#xff08;Retrieve&#xff09; 全列查询 指定列查询 查询字段为表达式 别名 去重&#xff1a;DISTINCT 排序&#xff1a;ORDER BY 条件查询&#xff1a;WHERE 逻辑运算符&#xff1a; 修改&#xff08;Update&#xff09; 删除&…
阅读更多...
「入门指南」轻松学习嵌入式 GPIO：从原理到应用一步到位

「入门指南」轻松学习嵌入式 GPIO：从原理到应用一步到位

嵌入式系统是指在其他系统中嵌入的计算机系统&#xff0c;通常由微处理器或微控制器、内存和其他支持电路组成。嵌入式系统的应用领域非常广泛&#xff0c;涉及从智能家居设备到汽车控制系统&#xff0c;再到飞机、医疗设备等各种设备。对于嵌入式系统的应用&#xff0c;GPIO是…
阅读更多...
我在字节当主管：百次面试结果，总结一个刷掉99%求职者的问题！

我在字节当主管：百次面试结果，总结一个刷掉99%求职者的问题！

我一个在大厂当主管的朋友&#xff0c;跟我说&#xff1a;“现在招性能测试太难了&#xff0c;当然不是说没人干&#xff0c;一开招聘信息就能收到一大把简历&#xff0c;其中不乏学历亮眼、背景出色、简历里各种高并发、大流量的项目经验的人才。问题在于&#xff0c;当你提出…
阅读更多...
【C++】模板初阶

【C++】模板初阶

文章目录泛型编程函数模板概念格式实例化匹配原则类模板定义格式实例化泛型编程 当我们的一个函数涉及到多个类型的处理时&#xff0c;我们就需要重载函数来实现&#xff0c;但是重载函数是存在一些局限性的。   重载函数仅仅是类型不同&#xff0c;代码的复用率较低&#xf…
阅读更多...
【AcWing】蓝桥杯备赛-深度优先搜索-dfs（2）

【AcWing】蓝桥杯备赛-深度优先搜索-dfs（2）

目录 写在前面&#xff1a; 题目&#xff1a;94. 递归实现排列型枚举 - AcWing题库 读题&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 数据范围&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; 代码&#xff1a; AC &…
阅读更多...
使用new bing简易教程

使用new bing简易教程

申请new bing 首先先申请new bing然后等待通过&#xff0c;如下图 申请完&#xff0c;用edge浏览器&#xff0c;若有科学方法&#xff0c;就能在右上角的聊天进行向AI提问 使用插件来进行直接访问New Bing 在edge浏览器中安装一个插件&#xff0c;地址为&#xff1a;Mod…
阅读更多...
HTML樱花飘落

HTML樱花飘落

樱花效果 FOR YOU GIRL 以梦为马&#xff0c;不负韶华 LOVE YOU FOREVER 实现代码 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html><head><meta http-equiv"…
阅读更多...
Windows逆向安全（一）之基础知识（二）

Windows逆向安全（一）之基础知识（二）

反汇编分析C语言 空函数反汇编 #include "stdafx.h"//空函数 void function(){}int main(int argc, char* argv[]) {//调用空函数function();return 0; }我们通过反汇编来分析这段空函数 函数外部 12: function(); 00401048 call ILT5(func…
阅读更多...
一款丧心病狂的API测试工具：Apifox！

一款丧心病狂的API测试工具：Apifox！

你好&#xff0c;我是测试开发工程师——凡哥。欢迎和我交流测试领域相关问题&#xff08;测试入门、技术、python交流都可以&#xff09; 我们平时在做接口测试的时候&#xff0c;对于一些常用的接口测试工具的使用应该都非常熟悉了&#xff1a; 接口文档&#xff1a;Swagge…
阅读更多...
2023年网络安全比赛--attack（新）数据包分析中职组（超详细）

2023年网络安全比赛--attack（新）数据包分析中职组（超详细）

一、竞赛时间 180分钟 共计3小时 任务环境说明： 1 分析attack.pcapng数据包文件，通过分析数据包attack.pcapng找出恶意用户第一次访问HTTP服务的数据包是第几号，将该号数作为Flag值提交； 2.继续查看数据包文件attack.pcapng，分析出恶意用户扫描了哪些端口，将全部的端口号…
阅读更多...
比df更好用的命令！

比df更好用的命令！

大家好&#xff0c;我是良许。 对于分析磁盘使用情况&#xff0c;有两个非常好用的命令&#xff1a;du 和 df 。简单来说&#xff0c;这两个命令的作用是这样的&#xff1a; du 命令&#xff1a;它是英文单词 disk usage 的简写&#xff0c;主要用于查看文件与目录占用多少磁…
阅读更多...
π-Day快乐：Python可视化π

π-Day快乐：Python可视化π

π-Day快乐&#xff1a;Python可视化π 今天是3.14&#xff0c;正好是圆周率 π\piπ 的前3位&#xff0c;因此数学界将这一天定为π\bold{\pi}π day。 π\piπ 可能是最著名的无理数了&#xff0c;人类对 π\piπ 的研究从未停止。目前人类借助计算机已经计算到 π\piπ 小数…
阅读更多...
考研408 王道计算机考研 (初试/复试) 网课笔记总结

考研408 王道计算机考研 (初试/复试) 网课笔记总结

计算机初试、复试笔记总结&#xff08;导航栏&#xff09;&#x1f4dd; 408 考研人&#xff0c;人狠话不多&#xff1a;3、2、1&#xff0c;上链接 &#xff01; 408 考研初试 - 备战期&#xff0c;专业课笔记&#xff0c;导航&#x1f6a5;&#x1f6a5;&#x1f6a5; &…
阅读更多...
编写Java哪个编译器好

编写Java哪个编译器好

现在能够编写Java代码的工具简直不要太多&#xff0c;各种各样五花八门&#xff0c;但目前效率最高的还是Intellij Idea。但这个工具对于完全零基础的小白来说&#xff0c;第一次用起来是比较复杂的&#xff0c;因为它的功能太多了。这就好比你要学开车&#xff0c;如果上来就给…
阅读更多...
量化(1):基础知识

量化(1):基础知识

1. Tops的含义 1TOPS代表处理器每秒可进行一万亿次（10^12）操作 2. 定点数 2.1 定点数的含义 大家都知道，数字既包括整数，又包括小数，如果想在计算机中，既能表示整数，也能表示小数，关键就在于这个小数点如何表示？ 计算机科学家们想出一种方法，即约定计算机中小数…
阅读更多...
MySQL：JDBC

MySQL：JDBC

什么是JDBC&#xff1f; JDBC( Java DataBase Connectivity ) 称为 Java数据库连接 &#xff0c;它是一种用于数据库访问的应用程序 API &#xff0c;由一组用Java语言编写的类和接口组成&#xff0c;有了JDBC就可以 用统一的语法对多种关系数据库进行访问&#xff0c;而不用担…
阅读更多...
Docker三剑客之swarm

Docker三剑客之swarm

一、什么是docker swarm Swarm是Docker公司推出的用来管理docker集群的平台&#xff0c;几乎全部用GO语言来完成的开发的&#xff0c;代码开源在https://github.com/docker/swarm&#xff0c; 它是将一群Docker宿主机变成一个单一的虚拟主机&#xff0c;Swarm使用标准的Docker…
阅读更多...
排序算法 - 冒泡排序

排序算法 - 冒泡排序

冒泡排序算法应该可以说是很经典的一种对数据进行排序的的算法了&#xff0c;甚至在很多的介绍算法的数据中&#xff0c;它可能还是放在最前面开始讲解的。 冒泡排序算法到底是咋样的呢&#xff1f;冒泡这个说法又是怎么得来的呢&#xff1f; 首先先理解一下冒泡算法的实现原理…
阅读更多...
最新文章

Copyright @ 2022~2023