【数据结构与算法】线性表

【数据结构与算法】线性表 - 顺序表

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
在这里插入图片描述

2.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

顺序表一般可以分为：

静态顺序表：使用定长数组存储元素。
动态顺序表：使用动态开辟的数组存储。

静态顺序表只适用于确定知道需要存多少数据的场景，静态顺序表的定长数组，长度N定大了，空间开多了浪费，开少了不够用。所以基本都是使用动态顺序表，根据需要动态的分配空间大小。

3.顺序表的优缺点

缺点：增删改速度慢。

中间 / 头部的插入删除，时间复杂度为O(N)。
增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
增容一般是呈1.5或2倍的增长，势必会有一定的空间浪费。

优点：有数组索引，查询速度快。

4.实现（C语言）

4.1 头文件 seqList.h

#pragma once

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

// 初始大小
#define STD_SIZE 4

// 顺序表数据类型
typedef int seqListDataType;

// 顺序表
typedef struct SeqList 
{
	seqListDataType* list;
	int size; // 有效数据个数
	int cap; // 顺序表容量
} SeqList;

// 初始化，销毁
void init(SeqList* psl);
void destroy(SeqList* psl);

// 扩容
void checkResize(SeqList* psl);

// 头插头删，尾插尾删
void addFront(SeqList* psl, seqListDataType ele);
void removeFront(SeqList* psl);
void addBack(SeqList* psl, seqListDataType ele);
void removeBack(SeqList* psl);

// 指定位置[0-size+1）插入，[0~size）删除
void insert(SeqList* psl, int pos, seqListDataType ele);
void erase(SeqList* psl, int pos);

4.2 实现 seqList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "seqlist.h"

// 初始化
void init(SeqList* psl)
{
	assert(psl);
	psl->list = NULL;
	psl->size = 0;
	psl->cap = 0;
}

// 销毁
void destroy(SeqList* psl)
{
	assert(psl && psl->list);
	free(psl->list);
	psl->list = NULL;
	psl->size = 0;
	psl->cap = 0;
}

// 检查容量并扩容
static void checkResize(SeqList* psl)
{
	if (psl->size == psl->cap) 
	{
		int newCap = psl->size == 0 ? STD_SIZE : psl->cap * 2;
		seqListDataType* tmpList = realloc(psl->list, newCap * sizeof(seqListDataType));
		if (tmpList != NULL)
		{
			psl->list = tmpList;
			psl->cap = newCap;
			// 只将扩容的内存置0
			memset((psl->list) + psl->size, 0, psl->size * sizeof(seqListDataType));
		}
		else
		{
			perror("checkCap(SqList* psl) realloc error");
		}
	}
} 

// 头插
void addFront(SeqList* psl, seqListDataType data)
{
	assert(psl);
	checkResize(psl);
	// 所有元素往后挪1位
	for (int i = psl->size - 1; i >= 0; i--)
	{
		psl->list[i + 1] = psl->list[i];
	}
	psl->list[0] = data;
	psl->size++;
}

// 头删
void removeFront(SeqList* psl)
{
	assert(psl && psl->size > 0);
	// 第2个元素开始，所有元素往前挪1位
	for (int i = 1; i < psl->size; i++)
	{
		psl->list[i - 1] = psl->list[i];
	}
	psl->list[psl->size - 1] = 0;
	psl->size--;
}

// 尾插
void addBack(SeqList* psl, seqListDataType data)
{
	assert(psl);
	checkResize(psl);
	psl->list[psl->size] = data;
	psl->size++;
}

// 尾删
void removeBack(SeqList* psl)
{
	assert(psl && psl->size > 0);
	psl->list[psl->size - 1] = 0;
	psl->size--;
}

// 指定位置[0-size+1）插入
void insert(SeqList* psl, int pos, seqListDataType ele)
{	
	assert(psl);
	checkResize(psl);
	assert(pos >= 0 && pos < psl->size + 1);
	// 从插入位置开始，所有元素向后挪动1位
	for (int i = psl->size - 1; i >= pos; i--)
	{
		psl->list[i + 1] = psl->list[i];
	}
	psl->list[pos] = ele;
	psl->size++;
}

// 指定位置[0~size）删除
void erase(SeqList* psl, int pos)
{
	assert(psl && pos >= 0 && pos < psl->size);
	// 从删除位置开始，所有元素往前移动1位
	for (int i = pos; i < psl->size; i++)
	{
		psl->list[i] = psl->list[i + 1];
	}
	psl->list[psl->size - 1] = 0;
	psl->size--;
}