首页 计算机科学 数据结构笔记

该系列为本人的学习笔记，主要由本人整理书写而成。部分内容来自教材、视频课程等，不能保证完全原创性。

萌新的学习笔记，写错了恳请斧正。

# 数据结构

数据结构，顾名思义，就是计算机存储和管理数据的方式，是存在一种或多种关系的数据的集合。数据结构和算法都是程序设计的重要部分。比方说，数组就是一种最基础数据结构。

# 线性表

线性表是一类数据结构，其特点是 “逻辑线性”，也就是说里面的数据在逻辑上是按一定顺序先后排成一列的，不会有一些分叉什么的。当然，在逻辑上是线性的不代表其在物理结构（在内存中的实际分布结构）上也是线性的，可以每一个数据存在各自的位置，只要有办法能找到其逻辑相邻的数据就行。常见的线性表有：顺序表、链表、栈、队列、字符串等等。

# 顺序表（SeqList，简写 SL）

顺序表是线性表的一种，是一种基于数组的数据结构。但是其实质是对数组的封装，实现对其增删改查等操作的接口。

一般来说，实现顺序表我们会定义一个结构体，其成员为存放数据的数组和一个存放目前数据总量的整型常量。

# 静态顺序表

静态顺序表使用定长数组管理数据，由于其空间的固定性，我们一般不会使用。

typedef int SLDataType;
#define N 10
 
typedef struct SeqList
{
    SLDataType data[N];
    int size;
} SL;
# 动态顺序表

动态顺序表则为数组动态分配空间，按需申请所需空间，较为灵活。

typedef int SLDataType;
#define N 10
 
typedef struct SeqList
{
    SLDataType* data;
    int size;
    int capacity;
} SL;

其中，为指针 data 动态开辟空间模拟数组用于保存数据；size 用于保存已有数据个数；capacity 则用于保存目前动态开辟的空间大小。

# 动态顺序表的实现
# 头文件

下面是定义动态顺序表和声明其常用函数的头文件：

SeqList.h
// 定义顺序表结构、要实现的接口 / 方法
#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLDataType;
 
// 静态顺序表
//#define N 100
//struct SeqList
//{
//	SLDataType arr[N];
//	int size;
//};
 
// 动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int capacity;	// 记录顺序表空间大小
	int size;		// 记录顺序表当前有效数据个数
} SL;
 
// 初始化与销毁
// 初始化
void SLInit(SL* psl);
// 销毁
void SLDestory(SL* psl);
// 打印顺序表
void SLPrint(SL* psl);
 
// 扩容顺序表
void SLCheckCapacity(SL* psl);
 
// 头部 / 尾部插入与删除
// 头部插入
void SLPushBack(SL* psl, SLDataType x);
// 头部删除
void SLPopBack(SL* psl);
// 尾部插入
void SLPushFront(SL* psl, SLDataType x);
// 尾部删除
void SLPopFront(SL* psl);
 
// 任意位置插入与删除
// 任意位置插入
void SLInsert(SL* psl, int pos, SLDataType x);
// 任意位置删除
void SLRemove(SL* psl, int pos);
 
// 查找
// 查找某个元素对应的下标
int SLFind(SL* psl, SLDataType x);
// 查找某个下标对应的元素
SLDataType SLFindByPos(SL* psl, int pos);
 
// 修改
// 修改某个下标对应的元素
void SLModifyByPos(SL* psl, int pos, SLDataType x);
 
// 根据下标交换两个元素
void SLSwapByPos(SL* psl, int pos1, int pos2);
# 源文件

下面是实现这些接口的源文件：

SeqList.c
// 实现定义的接口 / 方法
 
#include "SeqList.h"
 
// 初始化与销毁
// 初始化
void SLInit(SL* psl)
{
	// 断言
	assert(psl);
	psl->arr = NULL;
	psl->size = psl->capacity = 0;
}
// 销毁
void SLDestory(SL* psl)
{
	// 断言
	assert(psl);
	free(psl->arr);
	psl->arr = NULL;
	psl->size = psl->capacity = 0;
}
 
// 打印顺序表
void SLPrint(SL* psl)
{
	// 断言
	assert(psl);
	for (int i = 0; i < psl->size; ++i)
	{
		printf("%d ", psl->arr[i]);
	}
	printf("\n");
}
 
// 扩容顺序表
void SLCheckCapacity(SL* psl)
{
	// 空间不够，扩容
	if (psl->capacity == psl->size)
	{
		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->arr, sizeof(SLDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("扩容失败，程序终止！\n");
			exit(EXIT_FAILURE);
		}
		// 扩容成功
		psl->arr = tmp;
		psl->capacity = newCapacity;
	}
}
 
// 插入与删除
// 尾部插入
void SLPushBack(SL* psl, SLDataType x)
{
	// 断言
	assert(psl);
	// 空间不够，扩容
	SLCheckCapacity(psl);
	// 空间足够，插入
	psl->arr[psl->size++] = x;
}
// 尾部删除
void SLPopBack(SL* psl)
{
	// 断言
	assert(psl);
	// 顺序表为空，无法删除
	if (!psl->size)
	{
		printf("顺序表为空，无法删除！\n");
		return;
	}
	// 顺序表不为空，删除
	--psl->size;
}
// 头部插入
void SLPushFront(SL* psl, SLDataType x)
{
	// 断言
	assert(psl);
	// 空间不够，扩容
	SLCheckCapacity(psl);
	// 空间足够，插入
	for (int i = psl->size; i > 0; --i)
	{
		psl->arr[i] = psl->arr[i - 1];
	}
	psl->arr[0] = x;
	++psl->size;
}
// 头部删除
void SLPopFront(SL* psl)
{
	// 断言
	assert(psl);
	// 顺序表为空，无法删除
	if (!psl->size)
	{
		printf("顺序表为空，无法删除！\n");
		return;
	}
	// 顺序表不为空，删除
	for (int i = 0; i < psl->size - 1; ++i)
	{
		psl->arr[i] = psl->arr[i + 1];
	}
	--psl->size;
}
 
// 任意位置插入与删除
// 任意位置插入
void SLInsert(SL* psl, int pos, SLDataType x)
{
	// 断言
	assert(psl);
	// 位置不合法，插入失败
	if (pos < 0 || pos > psl->size)
	{
		printf("插入位置不合法，插入失败！\n");
		return;
	}
	// 位置合法，插入
	// 空间不够，扩容
	SLCheckCapacity(psl);
	// 空间足够，插入
	for (int i = psl->size; i > pos; --i)
	{
		psl->arr[i] = psl->arr[i - 1];
	}
	psl->arr[pos] = x;
	++psl->size;
}
// 任意位置删除
void SLRemove(SL* psl, int pos)
{
	// 断言
	assert(psl);
	// 位置不合法，删除失败
	if (pos < 0 || pos >= psl->size)
	{
		printf("删除位置不合法，删除失败！\n");
		return;
	}
	// 位置合法，删除
	for (int i = pos; i < psl->size - 1; ++i)
	{
		psl->arr[i] = psl->arr[i + 1];
	}
	--psl->size;
}
 
// 查找
// 查找某个元素对应的下标
int SLFind(SL* psl, SLDataType x)
{
	// 断言
	assert(psl);
	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}
// 查找某个下标对应的元素
SLDataType SLFindByPos(SL* psl, int pos)
{
	// 断言
	assert(psl);
	// 位置不合法，查找失败
	if (pos < 0 || pos >= psl->size)
	{
		printf("查找位置不合法，查找失败！\n");
		return -1;
	}
	// 位置合法，查找
	return psl->arr[pos];
}
 
// 修改
// 修改某个下标对应的元素
void SLModifyByPos(SL* psl, int pos, SLDataType x)
{
	// 断言
	assert(psl);
	// 位置不合法，修改失败
	if (pos < 0 || pos >= psl->size)
	{
		printf("修改位置不合法，修改失败！\n");
		return;
	}
	// 位置合法，修改
	psl->arr[pos] = x;
}
 
// 根据下标交换两个元素
void SLSwapByPos(SL* psl, int pos1, int pos2)
{
	// 断言
	assert(psl);
	// 位置不合法，交换失败
	if (pos1 < 0 || pos1 >= psl->size || pos2 < 0 || pos2 >= psl->size)
	{
		printf("交换位置不合法，交换失败！\n");
		return;
	}
	// 位置合法，交换
	SLDataType tmp = psl->arr[pos1];
	psl->arr[pos1] = psl->arr[pos2];
	psl->arr[pos2] = tmp;
}

其中大部分的函数其实很简单很好理解，主要需要注意插入数据时需要判断插入数据时顺序表是否有足够的空间，如果没有则需要扩容。

为了更高效，非 0 空间扩容时我们一般采取空间按比例重新分配的方法。“做乘法而不是做加法”。