首页 > 其他分享 >数据结构之顺序表的相关知识点及应用

数据结构之顺序表的相关知识点及应用

时间：2024-04-06 15:00:16浏览次数：12  
标签：知识点 arr 顺序 ps int SL 数据结构 size

 个人主页（找往期文章包括但不限于本期文章中不懂的知识点）：我要学编程(ಥ_ಥ)-CSDN博客

目录

顺序表的概念及结构

顺序表的分类

顺序表的实现 

在顺序表中增加数据 

在顺序表中删除数据 

在顺序表中查找数据 

顺序表源码

 

顺序表的概念及结构

在了解顺序表之前，得先知道一个东西：线性表。线性表（linear list）是n个具有相同特性的数据元素的有限序列。简单理解就是：线性表指的是具有部分相同特性的一类数据结构的集合。例如：蔬菜分为绿叶类、瓜类、菌菇类。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。 如何理解逻辑结构和物理结构？我们去超市买东西的时候，去付款时要排队，假设有很多人，也就意味着我们需要排成一条对去付款。这是在逻辑上就是一条线性的（我们下意识认为，是理想的），但是实际上在站队时不一定是线性的（现实情况）。但是顺序表在逻辑结构和物理结构上都是线性的。这是因为顺序表的底层实现逻辑是数组。我们知道数组在内存上是连续存放的（实际情况）。

注意：顺序表的底层虽然是数组，但是却是在数组的基础之上对数组进行了封装，实现了增删查改的一些功能。

顺序表的分类

我们知道数组有两种：一种是定长数组，也就是空间大小不可变化，是固定的；还有一种是变长数组，这个变长数组是我们用动态内存开辟函数申请来的（注意区分C99中引入的变长数组）。

根据数组的不同，顺序表也分为两种：静态顺序表（大小不可变），动态顺序表（大小可变）。

顺序表的实现 

这两种顺序表一比较，肯定是第二种的优势明显一些，同样在项目中，动态顺序表的应用远远大于静态顺序表。下面我们就来学习动态顺序表的实现。

首先创建三个文件：SeqList.h  —— 顺序表的头文件  SeqList.c  —— 顺序表的实现  test.c——>测试顺序表

顺序表的创建：

typedef struct SeqList
{
	SLDataType* arr;//数组指针
	int size;//记录当前有效的空间大小
	int capacity;//记录当前总空间大小
}SL;//由于struct SeqList太长，比较麻烦，因此就重新定义

由于数组的类型是暂定为int，后续如果要改动的话，不是很方便，因此也是重定义。

typedef int SLDataType;//数组不一定是int类型

顺序表创建完了之后，就得开始实现它的基本功能：增 删 查 改。

在实现上面那些基本功能之前，我们肯定得把这个顺序表进行初始化。 

//初始化顺序表
void InitSeqList(SL* ps)//由于要改变顺序表，所以传地址
{
	ps->arr = NULL;//没为数组分配内存空间
	ps->capacity = 0;
	ps->size = 0;
}

在顺序表中增加数据 

接下来就开始实现增加数据，这个增加稍微有所不同：是在指定的位置增加数据。

我们先来实现两种特殊的情况：头插和尾插。头插是在顺序表的第一个位置（数组下标为0的位置）插入（增加）数据；尾插是在顺序表的有效数据的末尾插入（增加）数据。

首先，来实现头插：（数据从后往前覆盖）

//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给BASE(4)个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}

注意：在比较大型的项目中，我们写一些功能代码时，一定要去检查功能是否完整。比如：这里我们写这个头插功能的代码时，写完之后一定要去打印结果，看看是否满足我们的要求。 

头插写完就开始写尾插了。

//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->capacity == ps->size)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)//还没分配空间
		{
			newcapacity = BASE;
		}
		else
		{
			newcapacity = 2 * ps->capacity;
		}
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		tmp = NULL;
		ps->capacity = newcapacity;
	}
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}

通过观察上面两个代码，我们会发现那个判断是否需要增容的部分是一样的，因此我们就可以把这个判断是否需要增容的部分写成一个函数（可以只判断，也可以把增容的部分也写进去）。

那么上面的代码就可以简化成下面的样子。 

//判断是否需要增容（如果需要，则直接自动增容）
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给4个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}


//在顺序表的头部插入数据
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];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}


//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}

两种特殊的插入写完之后，就得开始写指定插入，就是说在指定的位置插入数据。 （和头插一样，从后往前覆盖）

//在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//arr[2] = arr[1]; 
	}
	ps->arr[pos] = x;
	ps->size++;
}

在顺序表中删除数据 

接下来就是删除数据。同样删除数据也根据上面的方式来先实现特殊方式：头删和尾删。 

注意删除数据时，一定要判断是否有数据。

先来看头删。（数据从前往后覆盖）

void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size);//看看有没有数据
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

尾删就比较简单了。 

void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);
	//ps->arr[size-1] = 0; //这一步可有可无
	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;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到
}

上面就是顺序表的全部逻辑以及实现。

顺序表源码

下面是顺序表的源码：

SeqList.c

#include "SeqList.h"

//初始化顺序表
void InitSeqList(SL* ps)
{
	ps->arr = NULL;//没为数组分配内存空间
	ps->capacity = 0;
	ps->size = 0;
}


//销毁顺序表
void SLDestroy(SL* ps)
{
	if (ps->arr)//有可能我们还没有使用（为空）
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}


//打印顺序表
void SLPrint(const SL* 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)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给4个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}


//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);//ps是一个指针（没有&，因此也是一个值）
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}


//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}


//在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//arr[2] = arr[1]; 
	}
	ps->arr[pos] = x;
	ps->size++;
}


//删除顺序表头部的数据
void SLPopFront(SL* ps)
{
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}


//删除顺序表尾部的数据
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//ps->arr[size-1] = 0; //这一步可有可无
	ps->size--;
}


//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}


//在顺序表中查找数据
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到
}

SeqList.h 

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

#define BASE 4

typedef int SLDataType;//数组不一定是int类型

typedef struct SeqList
{
	SLDataType* arr;//数组指针（）
	int size;//记录当前有效的空间大小
	int capacity;//记录当前总空间大小
}SL;


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

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

void SLPrint(const SL* ps);//打印顺序表的数据

void SLPushFront(SL* ps, SLDataType x);//在顺序表的头部插入数据

void SLPushBack(SL* ps, SLDataType x);//在顺序表的末尾插入数据

void SLInsert(SL* ps, int pos, SLDataType x);//在指定位置插入数据

void SLPopFront(SL* ps);//删除顺序表头部的数据

void SLPopBack(SL* ps);//删除顺序表尾部的数据

void SLErase(SL* ps, int pos);//删除指定位置的数据

int SLFind(SL* ps, SLDataType x);//在顺序表中查找数据

好啦！本期数据结构顺序表的学习就到此为止啦！我们下一期再一起学习吧！ 

标签：知识点,arr,顺序,ps,int,SL,数据结构,size
From： https://blog.csdn.net/2301_80854132/article/details/137356385

相关文章

  • （数据结构——比特）算法的时间复杂度和空间复杂度
    目录1.算法效率如何衡量一个算法的好坏算法的复杂度复杂度在校招中的考察2.时间复杂度时间复杂度的概念 请计算一下Func1中++count语句总共执行了多少次？Func1执行的基本操作次数： 大O的渐进表示法推导大O阶方法：使用大O的渐进表示法以后，Func1的时间复杂度为： 另......
  • 【数据结构】时间和空间复杂度
    摘要：时间和空间复杂度是评估算法效率的两个重要指标，它们分别关注算法在执行过程中所消耗的时间和空间资源。本文将介绍时间和空间复杂度的概念、计算方法以及它们在算法设计与分析中的重要性，以及如何在实际应用中平衡时间和空间复杂度，以达到最佳的算法性能。1.引言在计......
  • 数据结构篇：跳跃表与B+树的对比与优劣分析
       本文旨在探讨跳跃表的特性及其在实际应用场景中的作用，同时对其与B+树进行比较，以帮助更好地理解和运用这两种数据结构。跳跃表什么是跳跃表（skiplist）        跳跃表是一种基于跳跃链表的有序数据结构，它是一种多层链表，每一层都是一个有序的链表。表的每一层......
  • C++数据结构——顺序表
    C++数据结构——顺序表以下代码可以作为一个顺序表的模板，从顺序表的初始化创建到增删改查，都有详细的过程，供学习参考。#include<iostream>#include<stdio.h>usingnamespacestd;#defineelemTypeintstructSequentialList{elemType*elements;intsiz......
  • 顺序表的实现
    在顺序表的实现中我们不会再像之前通讯录一样写菜单来调试了，而是用test函数来直接调用接口调试，因为菜单调试起来过于繁琐，而我们在写数据结构的时候是需要很多次调试函数功能的。所有接口#pragmaonce#include<stdio.h>#include<assert.h>#include<stdlib.h>#defineN......
  • 数据结构 第六章（图）【下】
    写在前面：本系列笔记主要以《数据结构（C语言版）》为参考（本章部分图片来源于王道），结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言，如有错误欢迎指出。视频链接：第01周a--前言_哔哩哔哩_bilibili四、图的应用1、最小生成树（1）在一个连通网的所有生成树......
  • 数据结构 第五章（树和二叉树）【下】
    写在前面：本系列笔记主要以《数据结构（C语言版）》为参考（本章部分图片以及知识点整理来源于王道），结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言，如有错误欢迎指出。视频链接：第01周a--前言_哔哩哔哩_bilibili哈夫曼树部分的代码参考了一位小伙伴分享的......
  • 【MySQL系列】--SQL 执行顺序
    不想往后翻直接告诉我结论,好的:)FROM：获取第一张表，称为原表table1，获取第二张表，称为原表table2，将两张表做笛卡尔积，生成第一张中间表Temp1。ON：根据筛选条件，在Temp1上筛选符合条件的记录，生成中间表Temp2。JOIN：根据连接方式的不同，选择是否在Temp2的基础上添加外部行。左外......
  • 数据结构：二叉搜索树、平衡二叉树（AVL树）、红黑树、B树、B+树
    个人理解浅谈数据结构，应对八股文面试目录前言一、二叉搜索树（二叉排序树、二叉查找树、AVL树）（1）二叉树的特点：（2）二叉树的优缺点二、平衡二叉树（高度平衡树，最早的自平衡二叉树）（1）平衡二叉树的特点：（2）平衡二叉树的优缺点三、红黑树（1）红黑树的特点（2）红黑树的优缺点四、红黑树......
  • 数据结构：详解【树和二叉树】
    1.树的概念及结构（了解）1.1树的概念树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。1.2树的结构1.3树与非树：1.4树在实际中的运用（表示文件系统的目录树结构）2.......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99