首页 > 其他分享 >【数据结构】线性表之《顺序表》超详细实现

【数据结构】线性表之《顺序表》超详细实现

时间：2024-06-17 16:01:31浏览次数：20  
标签：ps arr 顺序 线性表 int assert SL 数据结构 size

顺序表

前言：相信大家在学完C语言后，对于指针，结构体以及动态内存管理有了一定的见解，那么数据结构像是检验真理的唯一标椎，它考察了你掌握这三种语法的程度，如果掌握的不是很理想的友友们，建议看看鄙人主页总结的文章，好啦，数据结构之旅就正式开始啦。

一.数据结构

数据结构：计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

1.逻辑结构

逻辑结构：数据对象中数据元素之间的相互关系。
逻辑结构分为：集合结构，线性结构，树形结构和图形结构。

2.物理结构

物理结构：数据的逻辑结构在计算机中的存储形式。
物理结构分为：顺序存储结构和链式存储结构。

二.顺序表的分类

顺序表实际属于线性表这个大家族，那么什么是线性表呢？

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

1.静态顺序表

#define MAXSIZE 100     //静态顺序表的容量
typedef int SLDataType; //增强程序的可维护性

typedef struct SeqList
{
	SLDataType arr[MAXSIZE];//定长数组
	int size;               //有效的数据个数
}SeqList;

也许有人会问：这个静态顺序表说的这么神秘，本质上不就是一个数组吗？

答：没错，顺序表的低层就是数组，逻辑结构与物理结构都是连续的。不过顺序表对数组进行了封装，提供了大量常用的接口（所谓接口就是调用函数），方便完成数据进行增，删，查，改等一系列的操作。

静态顺序表的缺点：程序一但运行，数组的大小就确定了，不能被修改。数组大小给小了，空间就不够用；数组大小给大了，空间就白白的浪费掉了；

为了方便对静态顺序表进行扩容，于是，动态顺序表便应运而生。

2.动态顺序表

typedef int SLDataType;//增强程序的可维护性

typedef struct SeqList
{
	SLDataType* arr; //动态的，可以扩容
	int size;        //有效的数据个数
	int capacity;    //容量
}SL;

动态顺序表：通过堆区的动态内存管理控制顺序表空间的大小，即容量。

以下介绍的是基于动态顺序表的实现。

三.顺序表的实现

1.创建顺序表

创建一个顺序表结构，包含指向这块空间的起始地址，顺序表中存储数据的个数以及顺序表的最大容量。

typedef int SLDataType;//增强程序的可维护性，改变数据类型，只需改变int即可

typedef struct SeqList
{
	SLDataType* arr; //指向顺序表的起始位置，方便扩容
	int size;        //顺序表的有效的数据个数
	int capacity;    //顺序表的容量大小
}SL;//类型的重命名
//等价于typedef struct SeqList SL;

2.初始化顺序表

一般初始化我们都习惯赋值为0，指针赋值为NULL。

void SeqListInit(SL* ps)
{
	assert(ps);//断言操作，等价于assert(ps != NULL);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

3.判断是否扩容

当我们想要增加数据的时候，会遇到容量不够用的问题。所以在此之前，应该检查容量与有效数据之间的关系，判断是否要扩容，接着插入数据。

void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)//顺序表已满，进行扩容操作
	{
		//判断顺序表容量是否为0，若为0，开辟储存4个数据大小的空间，若不为0，则容量翻倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//开辟空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)//开辟失败
		{
			perror("realloc fail!");
			exit(1);//强行退出程序（表示遇到异常情况）
		}
		ps->arr = tmp;//开辟成功，修改指针
		ps->capacity = newcapacity;//修改容量
	}
}

注意：若传入realloc的指针为空指针(NULL)，则realloc函数等价于malloc函数。

4.打印顺序表

循环遍历顺序表数据即可。

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

5.插入操作

1.头插

头插的思想：将数据整体向后挪动一位。注意：为了防止覆盖原先的数据，采用从后向前挪动。再进行头部插入，最后有效数据个数+1。

void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//检查容量

	int end = ps->size;
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end - 1];//将数据整体向后挪动一位。
		end--;
	}
	ps->arr[0] = x;//头插
	ps->size++;//有效数据个数+1

	//等价于在下标为0处插入：SeqListInsert(ps, 0, x);
}

2.尾插

尾插的思想：直接在尾部插入，有效数据个数+1即可。

void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//检查容量

	ps->arr[ps->size++] = x;//尾插：采用后置++

	//等价于在下标为ps->size处插入：SeqListInsert(ps, ps->size, x);
}

3.按照下标插入

按照下标插入的思想：与头插的思想相同，只不过是要挪动数据的起始位置不同而已。

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//判断下标的合法性
	SeqListCheckCapacity(ps);

	int end = ps->size;
	while (end > pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

6.删除操作

1.头删

头删的思想：不是真正意义上的删除数据，而是将头部之后的数据整体向前挪动一位，覆盖头部数据，达到与头删相同的效果，最后有效数据个数-1。注意：为了防止覆盖原先的数据，采用从前向后挪动，这里与头插不同。

void SeqListPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);//前提：顺序表存在数据

	int start = 0;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;//有效数据个数-1

	//等价于在下标为0处删除：SeqListErase(ps, 0);
}

2.尾删

尾删的思想：有效数据个数-1即可。

void SeqListPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);//前提：顺序表存在数据

	ps->size--;//有效数据个数-1

	//等价于在下标为ps->size - 1处删除：SeqListErase(ps, ps->size - 1);
}

3.按照下标删除

按照下标删除的思想：与头删的思想相同，只不过是要挪动数据的起始位置不同而已。

void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);//前提：顺序表存在数据
	assert(pos >= 0 && pos < ps->size);//判断下标的合法性

	int start = pos;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;
}

7.查找数据

查找的思想：遍历数据，找到了返回下标，未找到返回-1即可。

int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到该数据，返回下标
		}
	}
	return -1;//未找到，返回-1
}

8.修改数据

修改的思想：利用下标确定位置，直接修改就行。较为简单。

void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->arr[pos] = x;
}

9.清空顺序表

清空的思想：将有效数据个数与容量赋值为0。

void SeqListClear(SL* ps)
{
	assert(ps);

	ps->size = 0;
	ps->capacity = 0;
}

10.销毁顺序表

销毁的思想：由于空间是利用动态内存函数 realloc 在堆区开辟的，所以要及时释放，避免内存泄漏。

void SeqListDestory(SL* ps)
{
	assert(ps);

	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;//置为NULL，防止野指针
	SeqListClear(ps);//清空顺序表
}

四.模块化源代码

1.SeqList.h

//#pragma once：防止头文件被重复包含
#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int SLDataType;//增强程序的可维护性

typedef struct SeqList
{
	SLDataType* arr; //动态的，可以扩容
	int size;        //有效的数据个数
	int capacity;    //容量
}SL;

void SeqListInit(SL* ps);//顺序表初始化

void SeqListCheckCapacity(SL* ps);//检查顺序表的容量

void SeqListPrint(SL* ps);//打印顺序表

void SeqListPushBack(SL* ps, SLDataType x);//顺序表尾部插入

void SeqListPushFront(SL* ps, SLDataType x);//顺序表头部插入

void SeqListPopBack(SL* ps);//顺序表尾部删除

void SeqListPopFront(SL* ps);//顺序表头部删除

void SeqListInsert(SL* ps, int pos, SLDataType x);//顺序表按照位置（下标）插入

void SeqListErase(SL* ps, int pos);//顺序表按照位置（下标）删除

int SeqListFind(SL* ps, SLDataType x);//顺序表查找元素值，返回下标

void SeqListModify(SL* ps, int pos, SLDataType x);//顺序表按位置（下标）修改

void SeqListClear(SL* ps);//清空顺序表

void SeqListDestory(SL* ps);//销毁顺序表

#endif

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void SeqListInit(SL* ps)
{
	assert(ps);//等价于assert(ps != NULL);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//扩容
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//强行退出程序（表示遇到异常情况）
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

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

void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);

	ps->arr[ps->size++] = x;

	//SeqListInsert(ps, ps->size, x);
}

void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);

	int end = ps->size;
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;

	//SeqListInsert(ps, 0, x);
}

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

	ps->size--;

	//SeqListErase(ps, ps->size - 1);
}

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

	int start = 0;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;

	//SeqListErase(ps, 0);
}

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SeqListCheckCapacity(ps);

	int end = ps->size;
	while (end > pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	assert(pos >= 0 && pos < ps->size);

	int start = pos;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;
}

int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->arr[pos] = x;
}

void SeqListClear(SL* ps)
{
	assert(ps);

	ps->size = 0;
	ps->capacity = 0;
}

void SeqListDestory(SL* ps)
{
	assert(ps);

	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	SeqListClear(ps);
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

enum//匿名枚举
{
	EXIT,
	PUSHBACK,
	PUSHFRONT,
	POPBACK,
	POPFRONT,
	INSERT,
	ERASE,
	FIND,
	MODIFY,
	PRINT,
	CLEAR
};

void Menu()
{
	printf("*************顺序表************\n");
	printf("****1.尾插           2.头插****\n");
	printf("****3.尾删           4.头删****\n");
	printf("****5.插入           6.删除****\n");
	printf("****7.查找           8.修改****\n");
	printf("****9.打印          10.清空****\n");
	printf("****0.退出               ******\n");
	printf("*******************************\n");
}

int main()
{
	SL sl;
	SeqListInit(&sl);
	int select = 0;   //菜单选项
	SLDataType value; //插入的值
	int pos = 0;      //插入或删除的下标
	do
	{
		Menu();
		printf("请选择您的操作：");
		scanf("%d", &select);
		switch (select)
		{
		case EXIT:
			printf("退出顺序表!");
			break;
		case PUSHBACK:
			printf("请输入您要尾插的值(输入-1代表结束)：");
			while ((scanf("%d", &value), value != -1)) //逗号表达式
			{
				SeqListPushBack(&sl, value);
			}
			break;
		case PUSHFRONT:
			printf("请输入您要头插的值(输入-1代表结束)：");
			do
			{
				scanf("%d", &value);
				if (value != -1)
				{
					SeqListPushFront(&sl, value);
				}
			} while (value != -1);
			break;
		case POPBACK:
			SeqListPopBack(&sl);
			break;
		case POPFRONT:
			SeqListPopFront(&sl);
			break;
		case INSERT:
			printf("请输入要插入的《下标》与《值》：");
			scanf("%d %d", &pos, &value);
			SeqListInsert(&sl, pos, value);
			break;
		case ERASE:
			printf("请输入要删除的《下标》：");
			scanf("%d", &pos);
			SeqListErase(&sl, pos);
			break;
		case FIND:
			printf("请输入要查找的《值》：");
			scanf("%d", &value);
			int ret = SeqListFind(&sl, value);
			if (ret != -1)
			{
				printf("找到了下标为：%d\n", ret);
			}
			else
			{
				printf("找不到!");
			}
			break;
		case MODIFY:
			printf("请输入要修改的《下标》以及修改后的《值》:");
			scanf("%d %d", &pos, &value);
			SeqListModify(&sl, pos, value);
			break;
		case PRINT:
			SeqListPrint(&sl);
			break;
		case CLEAR:
			SeqListClear(&sl);
			break;
		default:
			printf("您输入的值错误，请重新选择!\n");
			break;
		}
	} while (select);
	SeqListDestory(&sl);
	return 0;
}

五.顺序表必做OJ题

  1. 原地移除元素
  2. 合并两个有序数组

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！

标签：ps,arr,顺序,线性表,int,assert,SL,数据结构,size
From： https://blog.csdn.net/2203_76003626/article/details/139577067

相关文章

  • Redis是一个高性能的键值对数据库，它支持多种数据结构，如字符串、列表、集合、有序集合
    Redis是一个高性能的键值对数据库，它支持多种数据结构，如字符串、列表、集合、有序集合和哈希表。以下是一些Redis命令的实践示例，帮助你了解如何使用Redis。连接Redis服务器首先，使用redis-cli命令连接到Redis服务器：redis-cli-h<hostname>-p<port>基本命令PING：检查Redis......
  • Java基础：B树、B+树和红黑树的数据结构，三者区别
    B树（B-Tree）数据结构节点结构：每个节点包含多个键值和子节点指针。阶（Degree）：B树的阶定义了每个节点的最小和最大键值数。对于阶为(m)的B树：每个节点最多有(m-1)个键值和(m)个子节点。每个节点（除了根节点）至少有(\lceilm/2\rceil-1)个键值和(\lceilm/......
  • （pdf）数据结构与算法分析 Java语言描述=Data Structures and Algorithm Analysis in Jav
    书：pan.baidu.com/s/1tGbGhhQ3Ez1SIkqdEREsjQ?pwd=eqp0提取码：eqp0数组：作为最基本的数据结构，用于存储固定大小的同类型元素集合。链表：动态数据结构，允许在任意位置插入和删除元素。栈：后进先出（LIFO）的数据结构，常用于函数调用和表达式求值。队列：先进先出（FIFO）的数据结构，常用于任务调......
  • （书和笔记）学习JavaScript数据结构与算法（第3版） ([巴西] 洛伊安妮 • 格罗纳)
    书：pan.baidu.com/s/199LHxxIlMixw3gYSY8tyPw?pwd=ywxg提取码：ywxg数据结构与算法基础：介绍了数据结构与算法的基本概念、重要性以及它们在JavaScript中的应用。数组：深入讲解了数组的定义、操作、常用方法及其在JavaScript中的应用，包括多维数组的构建与访问。栈：详细阐述了栈的概......
  • （书和笔记）学习JavaScript数据结构与算法第二版
    书：pan.baidu.com/s/199LHxxIlMixw3gYSY8tyPw?pwd=ywxg提取码：ywxgJavaScript与数据结构基础：介绍了JavaScript语言的基本特性和数据结构的定义，为后续内容打下基础。数组及其操作：讲解了数组的定义、特性以及常见的操作方法，如增删改查等。栈与队列：详细阐述了栈（后进先出）和队列（先进......
  • 图文+实战，轻松学会数据结构【数组】
    作者：周棋洛，大二计算机在校生......
  • 【Kafka专栏 05】一条消息的完整生命周期：Kafka如何保证消息的顺序消费
    作者名称：夏之以寒作者简介：专注于Java和大数据领域，致力于探索技术的边界，分享前沿的实践和洞见文章专栏：夏之以寒-kafka专栏专栏介绍：本专栏旨在以浅显易懂的方式介绍Kafka的基本概念、核心组件和使用场景，一步步构建起消息队列和流处理的知识体系，无论是对分布式系统感兴趣，还......
  • C语言数据结构实现-双向链表
    前面学习了如何创建一个双向链表，本节学习有关双向链表的一些基本操作，即如何在双向链表中添加、删除、查找或更改数据元素。本节知识基于已熟练掌握双向链表创建过程的基础上，我们继续上节所创建的双向链表来学习本节内容，创建好的双向链表如图1所示：双向链表添加节点根据数据添......
  • 大话考研数据结构：第3篇 数据结构的基本概念（下）
    1数据结构        数据结构（datastructure）是指相互之间存在一种或多种特定关系的数据元素的集合。现实世界中，任何的数据元素并非孤立存在的，它们之间存在千丝万缕的某种关系，它们的这种称之为“结构”。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的......
  • 【数据结构】遍历二叉树（递归思想）--＞赋源码
    欢迎来到我的Blog，点击关注哦......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99