IT小白

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】——顺序表介绍（独家介绍，小白必看！！）

作者：IT小白 | 2024-05-06 09:26:13

踩

顺序表

重点和易错点都用彩笔标记出来了，放心食用！！

数据结构分为线性表和非线性表，今天我们要学习的顺序表就是线性表中的一个小类。那么，何为线性表，线性表是指n个具有相同性质的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列、字符串等等。注意，线性表的物理结构不一定是线性的，它在逻辑结构上一定是线性的（这个很好理解，等我们学完顺序表和单链表这对黄金搭档，就明白这句话的含义了）

今天我们重点讲解顺序表，顺序表是线性表，顺序表在逻辑结构和物理结构上都是线性的。

1、概念及结构

顺序表（SeqList）：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构（连续存储数据，不能跳跃）。

一般我们用数组存储顺序表，在数组上完成数据的增删查改。

顺序表分为两种类型：


//静态顺序表
#define N 7
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType array[N];  //定长数组
	size_t size;                  //有效数据长度，size_t是无符号整形
}SeqList;
 
//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* array;  //指向动态开辟的数组
	size_t size;  //数据中存储的数据
	size_t capacity;   //数组的容量
}SeqList;

我建议用动态顺序表，比起静态顺序表，动态的更加好调整顺序表的大小。接下来，我也会以动态顺序表为例，介绍如何实现动态顺序表的增删查改。

2、接口实现

2.1 功能要求

我们要实现以下功能


//顺序表初始化
void SeqListInit(SeqList* psl);  //psl  p指针，sl顺序表
//检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl,SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos,SLDateType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//打印顺序表
void PrintSL(SeqList* psl);
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x);

2.2 功能实现

2.2.1 打印顺序表

这里提一嘴，我建议在每写一个功能就测试一下，千万不要把大部分功能写完再统一测试，那样你的Bug可能会99+（别问我为什么知道）。


//打印顺序表
void SeqListPrint(SeqList* psl)
{
	assert(psl);
	for(int i=0;i<psl->size;i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf('\n');
}

2.2.2 顺序表初始化

链表初始化没什么好说的，我直接上代码了。


void SeqListInit(SeqList*psl)
{
  assert(psl);   //断言psl是不是空指针
  psl->array=NULL;
  psl->size=psl->capacity=0;
}

2.2.3 检查顺序表的空间，增容

思路讲解：

判断顺序表空间是否满了，也就是判断是否需要增容就是要看psl->size==psl->capacity?增容：不增容。
用条件运算符来确定增容后的新空间的大小，如果是仍未存储数据的新链表，则先让链表的容量为4（这个数值可以随便设置）；如果已经存储了数据，但容量不够了，我们就让链表的空间每次增加一倍，也就是变成原来的两倍（可能有人会疑惑，为什么是两倍，其实这个也是为了减少数据的浪费，变成2倍比较保守）。
在扩容时用realloc，当realloc的第一个参数为0时，其效果等同于malloc，用realloc可以完美实现最初开辟空间和增容的功能。
检查tmp是否为空，也就是检查是否成功开辟了新的空间，非空则把tmp赋值给psl->array，最后千万不要忘记更改capacity的值。


//检查容量，增容
void CheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		size_t newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);
		//这里用realloc非常好
		SLDateType* tmp = (SLDateType*)realloc(psl->array, psl->capacity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc：");
			return;
		}
		psl->array = tmp;
		psl->capacity = newcapacity;
	}
}

2.2.4 顺序表尾插

这里就需要注意在尾插前检查容量，并且不要忘记psl->size++。


//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x)
{
	assert(psl);
	CheckCapacity(psl);
	psl->array[psl->size] = x;
	//别忘记让psl->size+1
	psl->size++;
}

2.2.5 顺序表尾删

注意：不管是进行头删还是进行尾删，我们都要检查psl->size是否大于0，我也提供了两种检查的方式，选其一即可。


//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	//千万不要忘记检查psl->size是否大于0
	//检查方式一：温柔的检查
	/*if (psl->size == 0)
		return;*/
	//检查方式二：暴力的检查
	assert(psl->size>0);
	psl->size--;
}

2.2.6 顺序表头插

这个也没什么好说的，直接上代码。


void SeqListPushFront(SeqList*psl, SLDateType x)
{
	assert(psl);
	CheckCapacity(psl);
	for (int i = psl->size;i>0; i++)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[0] = x;
	psl->size++;
}

2.2.7 顺序表头删

删除数据不要忘记暴力检查psl->size。


//顺序表头删
void SeqListPopFront(SeqList*psl)
{
	assert(psl);
	//暴力检查
	assert(psl->size);
	for (int i = 0; i < psl->size - 1; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}

2.2.8 顺序表查找

找到了，返回值为数组下标；未找到，返回值为-1。


//顺序表查找(返回下标,找不到就返回-1)
int SeqListFind(SeqList* psl, SLDateType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

2.2.9 在pos位置插入值

这个功能在实现的过程中一不小心就出问题，注意注意！！！！


//顺序表在pos位置插入x（pos为下标值）
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
	assert(psl);
	assert(pos<=psl->size);//注意：pos是可以等于psl->size，此时就相当于尾插
	CheckCapacity(psl);
    //写法一：
	for (int i = psl->size-1; i >= pos; i--)
	{
		psl->array[i + 1] = psl->array[i];
	}
    //写法二：
    size_t end=psl->size-1;
    while(end)
    {
        psl->array[end+1]=psl->array[end];
        end--;
    }
	psl->array[pos] = x;
	psl->size++;
}

当在下标为0的位置上插入一个数据时，i从psl->size-1到0，i进行i--操作，此时i=-1，再执行i>=pos操作，此时会停止循环吗？答案是不会，大家可以去调试，确实不会让循环停下。

那为什么呢？因为pos为size_t的类型，size_t为无符号整形-，当int（有符号整形）和size_t（无符号整形）比较大小时，int型的数据会发生算数转换，转换成unsigned int型，此时为负数的i就变成了很大的数字，自然而然比0大，因此会进入死循环。

那怎么解决呢？

针对写法一的解决办法：


for (int i = psl->size; i > pos; i--)
{
	psl->array[i] = psl->array[i-1];
}

此时，避免了i==0的情况，保证i始终大于0，这样i--就不会出现问题了。

针对写法二的解决方法：


size_t end=psl->size;
while(end)
{
    psl->array[end]=psl->array[end-1];
    end--;
}

有人肯定会不理解，为什么非让pos为size_t类型，如果让pos变成int型，只需要保证pos大于等于0就可以了，size_t显得好像更麻烦一些。其实，我们把pos写成size_t是因为库也是这样写的，我们严格根据库的声明来实现，以后当我们涉及到的问题更加复杂时，用size_t做接口肯定比int更好。

2.2.10 顺序表删除pos的位置

这里注意好循环时i的上下限就可以了。


//顺序表删除pos的位置
void SeqListErase(SeqList*psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
	for (int i = pos;i<psl->size-1;i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}

2.2.11 修改pos位置的值


//修改顺序表的值
void SeqListModify(SeqList*psl, size_t pos,SLDateType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->array[pos] = x;
}

2.2.12 销毁顺序表


//销毁顺序表
void SeqListDestory(SeqList*psl)
{
	assert(psl);
	free(psl->array);
	psl->array = NULL;
	psl->size = psl->capacity = 0;
}

3、总代码

SeqList.h


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
静态版本
//#define N 7
//typedef struct SeqList
//{
//	SLDateType array[N];   //静态数组
//	size_t size;   //有效数据个数
//}SeqList;
//动态版本
typedef struct SeqList
{
	SLDateType* array;   //指向动态开辟的数组
	size_t size;   //有效数据个数
	size_t capacity;  //容量空间的大小
}SeqList;
 
//基本增删查改接口
//顺序表初始化
void SeqListInit(SeqList* psl);  //psl  p指针，sl顺序表
//检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl,SLDateType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos,SLDateType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//打印顺序表
void PrintSL(SeqList* psl);
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x);

SeqList.c


#include"SeqList.h"
//打印顺序表
void PrintSL(const SeqList* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf("\n");
}
//初始化顺序表
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->array = NULL;
	psl->size = psl->capacity = 0;
}
//检查容量，增容
void CheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		size_t newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);
		//这里用realloc非常好，当realloc的第一个参数为0时，其效果等同于malloc
		//用realloc可以完美实现最初开辟空间和增容的功能
 
		//一定要注意：是newcapacity，而不是psl->capacity
		SLDateType* tmp = (SLDateType*)realloc(psl->array, newcapacity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc：");
			return;
		}
		psl->array = tmp;
		psl->capacity = newcapacity;
	}
}
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x)
{
	assert(psl);
	CheckCapacity(psl);
	psl->array[psl->size] = x;
	//也可以用SeqListInsert（psl，psl->size,x),但经常用上面的方法，可读性更强
	//可别忘了让psl->size加1
	psl->size++;
}
 
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x)
{
	assert(psl);
	CheckCapacity(psl);
	for (int i = psl->size; i > 0; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[0] = x;
	//也可以用SeqListInsert（psl，0,x),但经常用上面的方法，可读性更强
	psl->size++;
}
 
//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	//千万不要忘记检查size是否大于0
	//温柔地检查SL中的size是否大于0
	/*if (psl->size == 0)
	{
		return;
	}*/
	//暴力的检查
	assert(psl->size > 0);
	psl->size--;
}
 
//顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	for (int i = 0; i < (psl->size - 1); i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}
//顺序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}
 
//顺序表在pos位置插入x（pos指的是下标）
void SeqListInsert(SeqList* psl,size_t pos,SLDateType x)
{
	assert(psl);
	CheckCapacity(psl);
	assert(pos <= psl->size);//size_t是无符号整形，所以不需要担心pos小于0
	//而pos等于psl->size，此时就不是插在中间了，而是尾插了。
	//易错：pos=0
	for (int i = psl->size; i >pos; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[pos] = x;
	psl->size++;
}
 
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos<psl->size);
	for (int i = pos; i < psl->size; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}
//顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array = NULL;
	psl->capacity = psl->size = 0;
}
//修改顺序表
void SLModify(SeqList* psl, size_t pos, SLDateType x)
{
	assert(psl);
	assert(psl < psl->size);
	psl->array[pos] = x;
}

test.c

test.c可以自己写，记得引用头文件就可以。


#include"SeqList.h"
int main()
{
	SeqList SL;
	SeqListInit(&SL);
	SeqListPushBack(&SL, 5);
	SeqListPushBack(&SL, 2);
	SeqListPushFront(&SL, 0);
	PrintSL(&SL);
	SeqListInsert(&SL, 2, 3);
	PrintSL(&SL);
	SeqListInsert(&SL, 2, 3);
	PrintSL(&SL);
	return 0;
}

这是数据结构第二篇文章了，数据结构有些小难♂，但别担心，快关注我跟我一起坚持学习吧！(*^▽^*)

如果喜欢我的文章就给我点个赞再走吧！下次见！拜拜 ┏(＾0＾)┛

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/543574