顺序表(更新版)——“数据结构与算法”

这篇具有很好参考价值的文章主要介绍了顺序表(更新版)——“数据结构与算法”。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

各位CSDN的uu们你们好呀,今天小雅兰又来更新新专栏啦,其实之前我就已经写过了顺序表的内容,只是之前的内容不是最新版的顺序表,现在,我来更新一下最新版的顺序表,下面,就让我们进入更新版的顺序表的世界吧


顺序表和小雅兰之前写的三子棋、扫雷、通讯录一样,分为三个文件:

https://xiaoyalan.blog.csdn.net/article/details/128705747?spm=1001.2014.3001.5502

https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502

https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502

https://xiaoyalan.blog.csdn.net/article/details/129788167?spm=1001.2014.3001.5502

https://xiaoyalan.blog.csdn.net/article/details/129896970?spm=1001.2014.3001.5502

test.c——测试代码功能

SeqList.c——顺序表的实现

SeqList.h——顺序表的声明

 https://xiaoyalan.blog.csdn.net/article/details/129380414?spm=1001.2014.3001.5502

这是小雅兰之前写的顺序表的知识,有兴趣的可以去看看


我们写的是一个动态版的顺序表: 

typedef struct SeqList
{
	SLDataType* a;
	int size;//存储的有效数据的个数
	int capacity;//容量
}SL;

把struct SeqList这个结构体重命名为SL

typedef int SLDataType;

 把int重命名为SLDataType

写成这样的形式是因为:如果以后想要修改类型,那就直接改int就可以了,如果不这样写, ​​​​​​要改很多个地方,就很麻烦

顺序表的初始化:

//初始化
void SLInit(SL* ps1)
{
	ps1->a = malloc(sizeof(SLDataType) * 4);
	if (ps1 == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps1->size = 0;
	ps1->capacity = 4;
}

动态开辟出4个SLDataType类型的大小的空间

 顺序表的销毁:也就是把空间还给操作系统

//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1)
{
	free(ps1->a);
	ps1->a = NULL;
	ps1->size = 0;
	ps1->capacity = 0;
}

打印顺序表的内容:

//打印
void SLPrint(SL* ps1)
{
	int i = 0;
	for (i = 0; i < ps1->size; i++)
	{
		printf("%d ", ps1->a[i]);
	}
	printf("\n");
}

尾插:

ps1->a[ps1->size] = x;
ps1->size++;

在这里,我们需要想一个问题:在尾插的过程中,如果空间不够了该怎么办呢???所以在这里,我们还需要一个检查容量的函数,如果容量不够就扩容

//检查容量,容量不够就扩容
void SLCheckCapacity(SL* ps1)
{
	if (ps1->size == ps1->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);
		//扩上一个二倍大小的容量
		//这个数值可以自己设定,扩多了不好,扩少了也不好
		//所以扩上二倍是最合理的选择
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps1->a = tmp;
		ps1->capacity = ps1->capacity * 2;
	}
}
//尾插
void SLPushBack(SL* ps1, SLDataType x)
{
	SLCheckCapacity(ps1);
	ps1->a[ps1->size] = x;
	ps1->size++;
}

下面,我们来测试一下尾插的功能,看是否成功

int main()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPushBack(&s, 7);
	SLPushBack(&s, 8);
	SLPushBack(&s, 9);
	SLPushBack(&s, 10);
	SLPrint(&s);
	SLDestroy(&s);
	return 0;
}

顺序表(更新版)——“数据结构与算法”

 结果发现,尾插的功能非常成功!!!

头插:

需要从后往前挪动数据!!!

顺序表(更新版)——“数据结构与算法”

 若是从前往后挪动数据,就会覆盖,这是绝对不行的

//头插
void SLPushFront(SL* ps1, SLDataType x)
{
	SLCheckCapacity(ps1);
	//挪动数据
	int end = ps1->size - 1;
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];//把数据往后挪
		end--;
	}
	ps1->a[0] = x;
	ps1->size++;
}

来测试一下头插的功能:

//头插测试
void TestSeqList2()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPushFront(&s, 7);
	SLPushFront(&s, 8);
	SLPushFront(&s, 9);
	SLPrint(&s);
	SLDestroy(&s);
}

 顺序表(更新版)——“数据结构与算法”

 尾删:

顺序表(更新版)——“数据结构与算法”

 直接把size--就可以了

//尾删
void SLPopBack(SL* ps1)
{
	ps1->size--;
}

 来测试一下尾删的功能:

//尾删测试
void TestSeqList3()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPushFront(&s, 7);
	SLPushFront(&s, 8);
	SLPushFront(&s, 9);
	SLPrint(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);
	SLDestroy(&s);
}

顺序表(更新版)——“数据结构与算法”

但是这个尾删仍然有点问题,需要检查一下:

//尾删
void SLPopBack(SL* ps1)
{
	//温柔的检查
	if (ps1->size == 0)
	{
		return;
	}
	ps1->size--;
}
//尾删
void SLPopBack(SL* ps1)
{
    //暴力的检查
	assert(ps1->size > 0);
	ps1->size--;
}

 头删:

顺序表(更新版)——“数据结构与算法”

//头删
void SLPopFront(SL* ps1)
{
	//暴力检查
	assert(ps1->size > 0);
	int start = 0;
	while (start < ps1->size - 1)
	{
		ps1->a[start] = ps1->a[start + 1];
		start++;
	}
	ps1->size--;
}

来测试一下头删的功能:

//头删测试
void TestSeqList4()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPushFront(&s, 7);
	SLPushFront(&s, 8);
	SLPushFront(&s, 9);
	SLPrint(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLDestroy(&s);
}

 顺序表(更新版)——“数据结构与算法”

在中间位置插入数据:

//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{
	SLCheckCapacity(ps1);
	int end = ps1->size - 1;
	while (end >= pos)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[pos] = x;
	ps1->size++;
}

顺序表(更新版)——“数据结构与算法”

写了这个函数的功能之后,我们就可以把之前写的头插和尾插修改一下:

//尾插
void SLPushBack(SL* ps1, SLDataType x)
{
   SLInsert(ps1, ps1->size, x);
}
//头插
void SLPushFront(SL* ps1, SLDataType x)
{
   SLInsert(ps1, 0, x);
}

但是,这个在中间插入数据的代码还是有点问题;

//中间插数据测试
void TestSeqList5()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPushFront(&s, 7);
	SLPushFront(&s, 8);
	SLPushFront(&s, 9);
	SLPrint(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLInsert(&s, 2, 30);
	SLPrint(&s);
	SLInsert(&s, 20, 300);
	SLPrint(&s);
	SLDestroy(&s);
}

顺序表(更新版)——“数据结构与算法”

从此运行结果可知:越界是不会报错的!!!但是它的的确确越界了!!!

所以把代码改进为:

//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps1->size);
	SLCheckCapacity(ps1);
	int end = ps1->size - 1;
	while (end >= pos)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[pos] = x;
	ps1->size++;
}

在中间位置删除数据:

//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos)
{
	assert(pos >= 0 && pos < ps1->size);
	assert(ps1->size > 0);//可有可无
	int start = pos + 1;
	while (start <= pos + 1)
	{
		ps1->a[start - 1] = ps1->a[start];
		start++;
	}
	ps1->size--;
}

同样,有了这个功能之后,可以把头删和尾删修改一下:

//头删
void SLPopFront(SL* ps1)
{
   SLErase(ps1, 0);
}
//尾删
void SLPopBack(SL* ps1)
{
   SLErase(ps1, ps1->size - 1);
}

测试一下从中间删除数据的功能:

//中间删数据测试
void TestSeqList6()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPushFront(&s, 7);
	SLPushFront(&s, 8);
	SLPushFront(&s, 9);
	SLPrint(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLInsert(&s, 2, 30);
	SLPrint(&s);
	SLErase(&s, 3);
	SLPrint(&s);
	SLDestroy(&s);
}

 顺序表(更新版)——“数据结构与算法”

 查找:

//查找
//找到了返回下标,找不到返回-1
int SLFind(SL* ps1, SLDataType x)
{
	int i = 0;
	for (i = 0; i < ps1->size; i++)
	{
		if (ps1->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

修改:

//修改
void SLModify(SL* ps1, int pos, SLDataType x)
{
	assert(pos >= 0 && pos < ps1->size);
	ps1->a[pos] = x;
}

下面,浅浅附上一波源代码:

SeqList.c的内容

#include"SeqList.h"
//初始化
void SLInit(SL* ps1)
{
	assert(ps1);
	ps1->a = malloc(sizeof(SLDataType) * 4);
	if (ps1 == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps1->size = 0;
	ps1->capacity = 4;
}
//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1)
{
	assert(ps1);
	free(ps1->a);
	ps1->a = NULL;
	ps1->size = 0;
	ps1->capacity = 0;
}
//打印
void SLPrint(SL* ps1)
{
	assert(ps1);
	int i = 0;
	for (i = 0; i < ps1->size; i++)
	{
		printf("%d ", ps1->a[i]);
	}
	printf("\n");
}
//检查容量,容量不够就扩容
void SLCheckCapacity(SL* ps1)
{
	assert(ps1);
	if (ps1->size == ps1->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);
		//扩上一个二倍大小的容量
		//这个数值可以自己设定,扩多了不好,扩少了也不好
		//所以扩上二倍是最合理的选择
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps1->a = tmp;
		ps1->capacity = ps1->capacity * 2;
	}
}
//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{
	assert(ps1);
	assert(pos >= 0 && pos <= ps1->size);
	SLCheckCapacity(ps1);
	int end = ps1->size - 1;
	while (end >= pos)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[pos] = x;
	ps1->size++;
}
//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos)
{
	assert(ps1);
	assert(pos >= 0 && pos < ps1->size);
	assert(ps1->size > 0);//可有可无
	int start = pos + 1;
	while (start <= pos + 1)
	{
		ps1->a[start - 1] = ps1->a[start];
		start++;
	}
	ps1->size--;
}
//尾插
void SLPushBack(SL* ps1, SLDataType x)
{
	assert(ps1);
	/*SLCheckCapacity(ps1);
	ps1->a[ps1->size] = x;
	ps1->size++;*/
	SLInsert(ps1, ps1->size, x);
}
//头插
void SLPushFront(SL* ps1, SLDataType x)
{
	assert(ps1);
	//SLCheckCapacity(ps1);
	挪动数据
	//int end = ps1->size - 1;
	//while (end >= 0)
	//{
	//	ps1->a[end + 1] = ps1->a[end];//把数据往后挪
	//	end--;
	//}
	//ps1->a[0] = x;
	//ps1->size++;
	SLInsert(ps1, 0, x);
}
//尾删
void SLPopBack(SL* ps1)
{
	assert(ps1);
	温柔的检查
	//if (ps1->size == 0)
	//{
	//	return;
	//}
	//ps1->size--;
	//暴力的检查
	/*assert(ps1->size > 0);
	ps1->size--;*/
	SLErase(ps1, ps1->size - 1);
}
//头删
void SLPopFront(SL* ps1)
{
	assert(ps1);
	//暴力检查
	assert(ps1->size > 0);
	int start = 0;
	while (start < ps1->size - 1)
	{
		ps1->a[start] = ps1->a[start + 1];
		start++;
	}
	ps1->size--;
	//SLErase(ps1, 0);
}
//查找
//找到了返回下标,找不到返回-1
int SLFind(SL* ps1, SLDataType x)
{
	assert(ps1);
	int i = 0;
	for (i = 0; i < ps1->size; i++)
	{
		if (ps1->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//修改
void SLModify(SL* ps1, int pos, SLDataType x)
{
	assert(ps1);
	assert(pos >= 0 && pos < ps1->size);
	ps1->a[pos] = x;
}

SeqList.h的内容

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;//存储的有效数据的个数
	int capacity;//容量
}SL;
//初始化
void SLInit(SL* ps1);
//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1);
//打印
void SLPrint(SL* ps1);
//尾插
void SLPushBack(SL* ps1,SLDataType x);
//尾删
void SLPopBack(SL* ps1);
//头插
void SLPushFront(SL* ps1, SLDataType x);
//头删
void SLPopFront(SL* ps1);
//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x);
//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos);
//查找
//找到了返回下标,找不到返回-1
int SLFind(SL* ps1, SLDataType x);
//修改
void SLModify(SL* ps1, int pos, SLDataType x);

test.c的内容

void menu()
{
	printf("***********************************************************\n");
	printf("1、尾插数据             2、尾删数据\n");
	printf("\n");
	printf("3、头插数据             4、头删数据\n");
	printf("\n");
	printf("5、在任意位置插入数据(位置3插入20)\n");
	printf("\n");
	printf("6、在任意位置删除数据              \n");
	printf("\n");
	printf("7、查找某个数据的位置,并删除它     \n");
	printf("\n");
	printf("8、删除顺序表中有的 某个数据        \n");
	printf("\n");
	printf("9、打印数据                       \n");
	printf("\n");
	printf("-1、退出                          \n");
	printf("\n");
	printf("***********************************************************\n");

}

int main()
{
	printf("*************  欢迎大家来到动态顺序表的测试  **************\n");
	int option = 0;
	SL s;
	SLInit(&s);
	do
	{
		menu();
		printf("请输入你的操作:>");
		scanf_s("%d", &option);
		int sum = 0;
		int x = 0;
		int y = 0;
		int z = 0;
		int pos = 0;
		int w = 0;
		switch (option)
		{
		case 1:
			printf("请依次输入你要尾插的数据:,以-1结束\n");
			scanf_s("%d", &sum);
			while (sum != -1)
			{
				SLPushBack(&s, sum);    // 1.尾插
				scanf_s("%d", &sum);
			}
			break;
		case 2:
			SLPopBack(&s);             // 2.尾删
			break;
		case 3:
			scanf_s("%d", &x);
			SLPushFront(&s, x);       // 3.头插
			break;
		case 4:
			SLPopFront(&s);           // 4.头删
			break;
		case 5:
			SLInsert(&s, 3, 20);     // 5.在任意位置插入数据
			break;
		case 6:
			SLErase(&s, 3);          // 6.在任意位置删除数据
			break;
		case 7:
			printf("请输入要删除序列的中的某个数字\n");
			scanf_s("%d", &z);
			y = SLFind(&s, z);        // 7.查找某个数字的位置,并且删除它
			printf("%d的位置在%d处: \n", z, y);
			if (y != -1)
			{
				SLErase(&s, y);
			}
			break;
		case 8:
			printf("请输入要删除序列的中的数字\n");  //8.删除顺序表中 所有的 某个数据 
			scanf_s("%d", &w);
			pos = SLFind(&s, w, 0);
			while (pos != -1)
			{
				SLErase(&s, pos);
				pos = SLFind(&s, w, pos);
			}
			break;
		case 9:
			SLPrint(&s);
			break;
		default:
			if (option == -1)
			{
				exit(0);  // 退出程序 
			}
			else
			{
				printf("输入错误,请重新输入\n");
			}
			break;

		}
	} while (option != -1);   // 退出程序
	SLDestroy(&s);
	return 0;
}

好啦,小雅兰今天的顺序表的更新版的内容就到这里啦,继续加油刷题和学习算法噢!!!

顺序表(更新版)——“数据结构与算法”文章来源地址https://www.toymoban.com/news/detail-422783.html

到了这里,关于顺序表(更新版)——“数据结构与算法”的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)
  • 【数据结构与算法】之顺序表及其实现!

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(35)
  • 数据结构与算法 --顺序表的创建

    1. 顺序表(Sequence List)是一种线性表的实现方式,通过连续的内存空间存储元素,按照顺序排列。 顺序表的特点包括: 元素在内存中的存储是连续的,通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(50)
  • 【数据结构】:实现顺序表各种基本运算的算法

    领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。 编写一个程序sqlist.cpp,实现顺序表的各种基本运算和整体建表算法(假设顺序表的元素类型ElemType为char),并在此基础上设计一个主程序,完成如下功能: 初始化顺序表L 依次插入a,b,c,d,e元素 输出顺序表L 输出顺

    2024年02月07日
    浏览(46)
  • 【数据结构与算法】掌握顺序栈:从入门到实践

       🌱博客主页:青竹雾色间. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 顺序栈的实现 初始化栈 判断栈空 判断栈满 入(进)栈 出栈 获取栈顶元素 示例代码 顺序栈的应用前景 当你学习数据结构和算法时,顺序栈(Sequential

    2024年02月08日
    浏览(67)
  • 数据结构与算法-头歌【1】顺序线性表--课上练

      本意是整理和复习,理解不深或者有错误的评论区提出即可。 只有第一关的代码里面有结构体的定义,其余我只放了功能函数。 任务描述 本关要求按照完成顺序表数据类型定义,并初始化一个顺序线性表。 编程要求 顺序线性表数据结构定义如下: 本关的编程任务是补全

    2023年04月25日
    浏览(45)
  • 数据结构与算法之查找: 顺序查找 (Javascript版)

    顺序查找 思路 遍历数组 找到跟目标值相等元素,就返回它的下标 没有找到,返回-1 算法实现 总结 非常低效,算是入门搜索 时间复杂度:O(n) 对于数组结构或链表结构而言,没什么太多可说的

    2024年02月05日
    浏览(49)
  • 【数据结构与算法】:手搓顺序表(Python篇)

    一、顺序表的概念 顺序表是一种线性的数据结构,其中数据元素按照特定的顺序依次存储在连续的内存空间中。它由一系列元素组成,每个元素都与唯一的索引(或者叫下标)相关联,索引从 0 开始递增。 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结

    2024年04月28日
    浏览(34)
  • 【数据结构与算法】二、线性表的顺序表示【硬核】

    图书表的顺序存储结构类型定义: 在调用函数的过程中,当形参为引用类型时,实参和形参占用了相同的空间 2.4.1 线性表的基本操作: 2.4.2 线性表L的初始化 2.4.3 销毁和清空线性表L 2.4.4 求线性表L的长度以及判断线性表L是否为空 2.4.5 顺序表的取值(根据位置i获取相应位置

    2023年04月26日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包