动态顺序表

标签：ps 顺序 SeqList SLDataType base 动态 void size

顺序表(动态)

顺序表分为静态和动态，静态的顺序表和动态顺序表相关接口的实现差别不大，因此不在赘述。

头文件定义

类型定义

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

//#define N 10
#define INIT_CAPACITY 4  // 给顺序表一个初始大小

typedef int SLDataType;	//定义顺序表数据类型

静态顺序表   开少了不够用   开多了浪费
//typedef struct SeqList {
//	SLDataType arr[N];
//	int size;
//};

//动态顺序表   动态扩容   开辟内存在堆区       没必要用柔性数组
typedef struct SeqList {
	SLDataType* base;	//动态数组的基地址
	int size;		//有效数据个数		size是    最后一个元素的下一个位置的下标
	int capacity;	//空间容量
}SeqList;

此处阐释静态顺序表的劣势。
静态顺序表开辟的空间是固定的，开辟空间过少，不够存储，开辟空间过多，造成空间的浪费。因此在实际使用的过程中，使用动态顺序表居多。

使用指针管理顺序表的地址，利用C语言的malloc函数和realloc函数以及指针来实现顺序表的动态扩容。

关于size的理解：

base[size] 可以直接访问到数组最后一个元素的下一个位置。
size-1 是数组最后一个元素的下标

源文件实现

#include "SeqList.h"

//传入assert的值为真时， 通过   为假  报错， 并在终端中显示错误所在行

初始化

断言结构体指针不能为空
开辟空间，将空间地址赋值给ps->base
判断是否开辟成功
赋初值
- 数组数据初始个数为 0
- 数组容量初始化为 INIT_CAPACITY

void SLInit(SeqList* ps) {
	assert(ps);
	ps->base = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->base == NULL) {
		perror("malloc failed");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

销毁

断言指针为非空
释放结构体指针指向的堆区数组
将指针置空，防止悬空指针的问题
将当前大小和总容积都设置为0

void SLDestroy(SeqList* ps) {
	assert(ps);
	free(ps->base);
	ps->base = NULL;
	ps->capacity = ps->size = 0;
	
}

扩容

一个一个插的时候，会到size == capacity的临界点，因此只需检查临界点

断言指针非空
判断该数组是否满了(ps->size == ps->capacity)
满了之后需要扩容，使用realloc函数 SLDataType* newSpace = (SLDataType*)realloc(ps->base, sizeof(SLDataType) * ps->capacity * 2)
- C++的STL中，扩容一般是扩容至当前容量的2倍， realloc函数(第二个参数为新空间的总大小，而不是要增加的大小，单位是字节)扩容会有两种情况
  - 原地扩容，在原空间的基础上增加容量
  - 异地扩容，开辟一块新的大小的空间，将原数据拷贝至新的空间中，同时释放原空间。
  - 为防止异地扩容，需要接受新空间的地址，将其赋值给指向原空间的指针。
最后 ps->capacity *= 2

void checkCapacity(SeqList* ps) {
	assert(ps);
	//扩容
	// 一个一个插的时候，会到size == capacity的临界点， 因此只需检查临界点
	if (ps->size == ps->capacity) {
		//将容量扩至原来的两倍
		SLDataType* newSpace = (SLDataType*)realloc(ps->base, sizeof(SLDataType) * ps->capacity * 2);
		if (newSpace == NULL) {
			perror("realloc failed");
			return;
		}
		// realloc 函数 扩容会有两种情况  一种是开辟一个新的空间   另一种是在原空间的基础上扩容
		ps->base = newSpace;
		ps->capacity *= 2;
	}
}

尾插

断言指针非空
检查是否需要扩容
插入
- ps->base[size++] = data
也可以调用后面的在任意位置插入的函数，通过调整参数实现尾插

// 尾插与尾删
void SLPushBack(SeqList* ps, SLDataType data) {
	assert(ps);

	checkCapacity(ps);

	//插入数据
	ps->base[ps->size++] = data;

	//可以用任意位置插入代替尾插
	//SLInsert(ps, ps->size, data);
}

尾删

删除前需要确保数组的size > 0
删除，其实只需要将 size-- 即可，后续再写入时直接将原数据覆盖

void SLPopBack(SeqList* ps) {
	//size的值为 0 时， 就不能再缩小了
	//暴力检查
	assert(ps->size > 0);
	//温柔的检查
	if (ps->size == 0)
		return;

	ps->size--;

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

头插

插入N个数据的时间复杂度为O(N)

断言指针非空
头插入需要将数据一个一个挪动，为防止挪动时数据覆盖，需要从后往前挪动 end = size -1, size-1 是数组中最后一个元素的下标
插入前需要检查顺序表是否为满，如果满了需要扩容
依次向后挪动

while (end >= 0) {
		ps->base[end + 1] = ps->base[end];
		end--;
	}

挪动结束后赋值，使size–

void SLPushFront(SeqList* ps, SLDataType data){
	assert(ps);
	int end = ps->size - 1;
	checkCapacity(ps);	//检查顺序表是否为满的
	while (end >= 0) {
		ps->base[end + 1] = ps->base[end];
		end--;
	}
	ps->base[0] = data;
	ps->size++;
}

头删

断言指针非空
断言数组的大小大于0
将下标为 1 ~ size 的数据一次向左移动，覆盖即可
size–

void SLPopFront(SeqList* ps, SLDataType data) {
	assert(ps);
	assert(ps->size > 0);

	int begin = 1;
	while (begin < ps->size) {
		ps->base[begin - 1] = ps->base[begin];
		begin++;
	}
	ps->size--;
}

在任意位置插入

和头插的思路一样
- 头插的停止位置是在base[0]
- 任意位置插入的停止位置是在base[pos]
断言指针非空以及 pos >= 0 && pos <= ps->size

void SLInsert(SeqList* ps, int pos, SLDataType data) {
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	checkCapacity(ps);

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

删除任意位置的元素

和头删法类似
- 头删法的起始位置在base[0]
- 任意位置删除的起始位置在base[pos+1]
将右侧的元素向左移动

void SLErase(SeqList* ps, int pos) {
	assert(ps);
	assert(pos >= 0 && pos <= ps->size - 1);

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

查找顺序表(暴力查找)

int FindSL(SeqList* ps, SLDataType ele) {
	assert(ps);
	for (int i = 0; i < ps->size; i++) {
		if (ps->base[i] == ele)
			return i;
	}
	return -1;
}

遍历顺序表

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

顺序表的劣势

中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是两倍的增长，势必会有一定的空间浪费。
当存储的数据量过大时， relloc 函数扩容基本上都是异地扩容，时间开销很大。

标签：ps,顺序,SeqList,SLDataType,base,动态,void,size
From： https://blog.csdn.net/2301_80064645/article/details/144166141