【数据结构】详解顺序表

目录

一、线性表

二、顺序表

1.顺序表的概念

2.顺序表的分类

(1)静态顺序表

(2)动态顺序表

3.顺序表的接口实现

三、顺序表的应用

四、总结

---

一、线性表

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

本篇文章主要是介绍线性表的其中一种——顺序表。

二、顺序表

1.顺序表的概念

顺序表是用一段物理地址连续的内存空间依次存储数据的线性结构。一般采用数组存储。在数组上完成顺序表的增删查改。更准确的说，线性表是逻辑层面的概念，顺序表是物理层面的概念，顺序表就是用数组实现的线性表。

2.顺序表的分类

(1)静态顺序表

用定长数组实现。

#define MAX  100
typedef int SLDataType;
 
typedef struct SeqList
{
    SLDataType a[MAX];//定长数组
    int size;
}SL;

(2)动态顺序表

用动态开辟的数组实现。

#define InitMax 5
typedef int SLDataType;
 
typedef struct SeqList
{
    SLDataType* a;//指向动态开辟的内存
    int size;
    int capacity;//容量
}SL;

3.顺序表的接口实现

  设计函数实现对顺序表的初始化、增 (头插、尾插、指定下标）删（头删、尾删、指定下标）查改。（以动态顺序表为例）

头文件SeqList.h:主要内容包括头文件的包含，结构体定义和接口函数的声明。

//SeqList.h
#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
typedef int SLDataType;//typedef用于基本数据类型取别名，便于顺序表中数组元素类型的多样化
 
typedef struct SeqList
{
	SLDataType* a;//指向动态内存开辟的内存
	int size;
	int capacity;//容量
}SeqList;
 
// 基本增删查改接口
 
// 顺序表初始化
void SeqListInit(SeqList* psl);
 
// 顺序表打印
void SeqListPrint(SeqList* psl);
 
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
 
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
 
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
 
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
 
// 顺序表头删
void SeqListPopFront(SeqList* psl);
 
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
 
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
 
// 顺序表销毁
void SeqListDestory(SeqList* psl);

 源文件SeqList.c:主要内容为函数接口的实现。

1.SeqListInit()函数

函数功能：实现顺序表的初始化。将结构体成员变量置为0(指针置为NULL)。

2.SeqListPrint()函数

函数功能：实现顺序表内容的打印。用for循环打印，一共打印psl->size个；打印的数据是结构体成员变量数组的元素。

3.CheckCapacity()函数（头插、尾插函数都需要先调用该函数，再进行插入操作）

函数功能：通过判断psl->size和psl->capacity的大小关系来检查数组是否已经存满数据。如果两个数大小相等，将容量扩大到原来的2倍(如果容量大小为0则置为4）。将容量扩大后用realloc函数扩大结构体数组的空间，操作结束后记得判断realloc的返回值，为空则扩容失败，函数直接结束。

4.SeqListPushFront()函数

函数功能：头插一个数到结构体成员数组中。先调用CheckCapacity()函数检查容量是否足够(不足够会扩容)，然后从最后一个元素psl->a[psl->size - 1]开始，每个元素依次向后挪一位，挪完后将第一个元素赋值为要插入的值。最后psl->size加一。

5.SeqListPopFront()函数

函数功能：删除结构体成员数组的第一个元素。先断言一下实现顺序表的结构体指针，避免指针为空。然后从第二个元素开始依次向前挪一位，挪完后psl->size减一。

6.SeqListPushBack()函数

函数功能：尾插一个数到结构体成员数组中。先检查容量。然后将数组的下标为psl->size的元素赋值为要插入的值，然后psl->size加一。（注意：数组元素个数为psl->size，原本的数组的最后一个元素下标为psl->size-1）

7.SeqListPopBack()函数

函数功能：删除结构体成员变量数组的最后一个元素。先断言，避免结构体指针为空。然后直接psl->size减一。

8.SeqListFind()函数

函数功能：查找结构体数组中是否有与x相等的元素，如有，返回下标，如无，返回-1。遍历数组，判断是否有与x相等的元素。

9.SeqListInsert()函数

函数功能：将数x插入结构体成员数组的指定下标pos处。先断言结构体指针，确保指针不为空。然后断言pos的范围，pos>=0 并且pos <= psl->size。然后从最后一个元素开始，一直到下标为pos的元素，依次向后挪一个，然后将x赋值给psl->a[pos]。psl->size加一。

10.SeqListErase()函数

函数功能：将结构体成员数组下标为pos处的元素删除。先断言结构体指针，避免为空指针。断言pos的范围，pos>= 0 并且pos< psl->size。然后从下标为pos+1的元素开始，一直到最后一个元素，依次向前挪一个，然后psl->size减一。

11.SeqListDestroy()函数

函数功能：用free函数释放动态申请的内存空间，将指针置空，将psl->size和psl->capacity置为0。

//SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
 
// 基本增删查改接口
 
// 顺序表初始化
void SeqListInit(SeqList* psl)
{
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
 
// 顺序表打印
void SeqListPrint(SeqList* psl)
{
	for (int i = 0;i < psl->size;i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
 
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl)
{
	if (psl->size == psl->capacity)//容量满了，需要扩容
	{
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//如果原容量==0，则置为4，不为0，则扩大为原来的两倍
		//动态申请内存空间，大小为新容量*单个元素的大小，，因为可能要多次扩容，所以必须使用realloc。
		SeqList* tmp = (SeqList*)realloc(psl->a,sizeof(SLDataType) * newcapacity);
		if (tmp != NULL)//动态申请成功
		{
			psl->a = tmp;
			psl->capacity = newcapacity;
		}
		else//动态申请失败
		{
			printf("realloc failed\n");
			return;
		}
	}
}
 
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	CheckCapacity(psl);//检查容量
	for (int i = psl->size - 1;i >= 0;i--)
	{
		psl->a[i + 1] = psl->a[i];//从最后一位依次向后挪一位
	}
	psl->a[0] = x;
	psl->size++;//插入一个顺序表元素后，其psl->size的值等于下一个元素的下标
}
 
// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);//断言
 
	for (int i = 0;i < psl->size - 1;i++)
	{
		psl->a[i] = psl->a[i + 1];//从第二个元素开始，依次向前挪一位
	}
	psl->size--;
}
 
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	CheckCapacity(psl);//检查容量
	psl->a[psl->size] = x;
	psl->size++;//插入一个顺序表元素后，其psl->size的值等于下一个元素的下标
}
 
// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	psl->a[psl->size - 1] = 0;
	psl->size--;
}
 
 
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{
	for (int i = 0;i < psl->size;i++)
	{
		if (psl->a[i] == x)
			return i;//返回对应元素第一次出现的下标
	}
	return -1;//没找到，返回-1
}
 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	for (int i = psl->size - 1;i >= pos;i--)
	{
		psl->a[i + 1] = psl->a[i];//从最后一个元素开始，到下标为pos的元素为止，依次向后挪一位
	}
	psl->a[pos] = x;
	psl->size++;
}
 
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	for (int i = pos;i < psl->size - 1;i++)
	{
		psl->a[i] = psl->a[i + 1];//从下标为pos+1的元素开始，依次向前挪一位
	}
	psl->size--;
}
 
// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
	free(psl->a);//释放动态申请的内存空间
	psl->a = NULL;//置空指针
	psl->size = 0;
	psl->capacity = 0;
}

//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
 
int main()
{
	SeqList sl;
	SeqListInit(&sl);
	//测试头插函数    成功
	SeqListPushFront(&sl, 1);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 3);
	SeqListPushFront(&sl, 4);
	SeqListPushFront(&sl, 5);
	SeqListPushFront(&sl, 6);
	//SeqListPrint(&sl);//6 5 4 3 2 1
 
	//测试头删函数    成功
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	//SeqListPrint(&sl);//2 1
 
	//测试尾插函数   成功
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushBack(&sl, 5);
	SeqListPushBack(&sl, 6);
	SeqListPushBack(&sl, 7);
	//SeqListPrint(&sl);//2 1 2 3 4 5 6 7
 
	//测试尾删函数  成功
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	SeqListPopBack(&sl);
	//SeqListPrint(&sl);//2 1 2
 
	//测试查找函数   成功
	//printf("%d\n", SeqListFind(&sl, 1));//1   找到了，下标为1
	//printf("%d\n", SeqListFind(&sl, 2));//0   找到了，下标为0
	//printf("%d\n", SeqListFind(&sl, 3));//-1  没找到
 
	//测试在pos位置插入x的函数  成功
	SeqListInsert(&sl, 2, 1);//2 1 1 2
	SeqListInsert(&sl, 2, 2);//2 1 2 1 2
	//SeqListPrint(&sl);//2 1 2 1 2
 
	//测试删除pos位置的值的函数  成功
	SeqListErase(&sl, 0);//1 2 1 2
	SeqListErase(&sl, 2);//1 2 2
	//SeqListPrint(&sl);//1 2 2
 
	SeqListDestory(&sl);
	//SeqListPrint(&sl);
	return 0;
}

三、顺序表的应用

1.通讯录的实现

2.原地移除元素：https://leetcode-cn.com/problems/remove-element/

3.合并两个有序数组：https://leetcode-cn.com/problems/merge-sorted-array/

(上述两题的解题思路都可以使用双指针，后续博客会总结一些与双指针解法有关的题)

四、总结

1.书写函数较多的代码时，比较好的一个习惯是，写一个测一个，可以有效避免写完之后代码报错但由于代码量过大无从下手的问题。

2.动态申请的空间一定要记得正确释放，避免造成内存泄漏。

谢谢各位的支持！