目录
一、数据结构前言
1. 数据结构：数据和数据间的组织方式
2. 程序（数据和函数组成） = 数据结构 + 算法
3. 时间复杂度
概念：一个算法程序的某一语句的执行次数（而不是该算法的运行时间）；
时间复杂度是一个函数 T (n) ，为方便一般使用大O表示法标准：渐进时间复杂度 O (f (n))；
常见算法时间复杂度：
- 递归算法时间复杂度 = 单次调用时间复杂地+总递归次数
- 冒泡排序时间复杂度 = O(n^2)
- 二分查找时间复杂度 = O(log(n))
- 递归求斐波那契数时间复杂素 = O(2^n)
4. 空间复杂度
概念：一个算法运行时临时占用的空间大小（即运行后新开辟的空间）；
空间复杂度是一个函数 S (n) ，为方便一般使用大O表示法标准：渐进空间复杂度 O (f (n))；
常见复杂度性能
二、顺序表
- 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组
上完成数据的增删查改。
1.顺序表的两种开辟方式（顺序表的数据结构）
静态顺序表
直接将数据放在定长数组
//顺序表的静态储存
#define N 7
struct SeqList
{
int array[N]; //定长数组
size_t size; //有效数据个数
}
动态顺序表
在堆上动态开辟数组并返回起始位置指针
//顺序表的动态储存
struct SeqList
{
int *array; //一个指针当作数组的起始位置
size_t size; //有效数据个数
size_t capicticy; //堆上开辟空间大小
}
2.顺序表的常用函数
1）初始化动态顺序表
在堆上开辟自定义长度的顺序表，默认最小开辟三个元素
void SeqListInit(SeqList* ps, int initCapacity)
{
assert(ps); //检测传入地址是否合法
initCapacity = initCapacity <= 0 ? 3 : initCapacity; //检测第二个参数 若非法默认开辟三个空间
ps->array = (DataType*)malloc(initCapacity * sizeof(DataType));
if (NULL == ps->array)
{
assert(0); //通过assert显示错误原因
return;
}
ps->capacity = initCapacity;
ps->size = 0;
}
2）释放顺序表
动态顺序表由于是在堆上开辟，调用结束后需要释放，避免内存溢出
void SeqListDestroy(SeqList* ps)
{
assert(ps);
if (ps->array)
{
free(ps->array); //链表内存上连续开辟，整体释放
ps->array = NULL;
ps->capacity = 0;
ps->size = 0;
}
}
3）顺序表的尾插与头插
a. 顺序表插入前必须先检查空间是否足够，自定义空间检测函数
static void ChecKCapacity(SeqList* ps)
b. 头插需将后面所有元素向后依次移动
c. 故尾插时间复杂度为O(1)，头插时间复杂度为O(N)
d. 插入操作后记得对数组有效大小加1
// 尾插
void SeqListPushBack(SeqList* ps, DataType data)
{
assert(ps);
//1.检测空间是否足够
ChecKCapacity(ps);
//2.最后一个元素插入data
ps->array[ps->size] = data;
ps->size++;
}
// 头插
void SeqListPushFront(SeqList* ps, DataType data)
{
assert(ps);
//1.检测空间是否足够
ChecKCapacity(ps);
//2.将所有元素整体向后移一位
for (int i = ps->size - 1; i >= 0; i--)
{
ps->array[i + 1] = ps->array[i];
}
//3.插入元素
ps->array[0] = data;
ps->size++;
}
4）顺序表空间检测函数
a. 定义为static静态函数，使其只在本文件程序有效
b. 若空间不足，每次开辟的新空间为原来两倍 (这里使用左移<<操作符扩大2倍)
c. 注意新空间开辟后，要释放原来堆空间
static void ChecKCapacity(SeqList* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
//开辟新空间
int newCapacity = (ps->capacity << 1); //左移一位就是两倍大小
DataType* temp = (DataType*)malloc(newCapacity * sizeof(DataType));
if (NULL == temp)
{
assert(0);
return;
}
//原空间值拷贝到新空间
for (int i = 0; i < ps->size; i++)
{
temp[i] = ps->array[i];
}
//释放原堆空间
free(ps->array);
ps->array = temp;
ps->capacity = newCapacity;
}
}
5）顺序表的尾删与头删
a. 顺序表删除前必须先判断是否对空链表进行操作，若为空表直接跳出
b. 头删需将后面所有元素向前依次移动
c. 故头插时间复杂度为O(1)，尾插时间复杂度为O(N)
d. 删除操作后记得对数组有效大小减1
// 尾删
void SeqListPopBack(SeqList* ps)
{
assert(ps);
//1.检测链表是否有元素
if (SeqListEmpty(ps))
{
printf("ERROR:顺序表无内容\n");
return;
}
//2.删除
ps->size--; //只改变合法元素个数即可，无需将空间释放
}
// 头删
void SeqListPopFront(SeqList* ps)
{
assert(ps);
//1.检测链表是否有元素
if (SeqListEmpty(ps))
{
printf("ERROR:顺序表无内容\n");
return;
}
//2.将所有元素整体向前移一位
for (int i = 0; i < ps->size; i++)
{
ps->array[i] = ps->array[i + 1];
}
ps->size--;
}
6）顺序表的指定位置插入与删除
插入与删除前先判断pos位置是否在数组有效长度内
// 在顺序表的pos位置插入元素data
// 注意：pos的范围必须在[0, ps->size]
void SeqListInsert(SeqList* ps, int pos, DataType data) //pos为下标从0开始
{
assert(ps);
//1.位置检测
if (pos<0 || pos>ps->size)
{
printf("ERROR:插入位置超出范围\n");
return;
}
//2.容量检测
ChecKCapacity(ps);
//3.pos后元素后移一位
for (int i = ps->size; i >= pos; i--)
{
ps->array[i + 1] = ps->array[i];
}
//4.插入元素
ps->array[pos] = data;
ps->size++;
}
// 顺序表删除pos位置的值
// 注意：pos的范围必须在[0, ps->size)
void SeqListErase(SeqList* ps, int pos) //pos为下标从0开始
{
assert(ps);
//1.位置检测
if (pos<0 || pos>ps->size)
{
printf("ERROR:插入位置超出范围\n");
return;
}
//2.pos和其后元素向前移一位
for (int i = pos; i < ps->size; i++)
{
ps->array[i] = ps->array[i + 1];
}
ps->size--;
}
7）顺序表的其他函数
// 9.有效元素个数
int SeqListSize(SeqList* ps)
{
assert(ps);
return ps->size;
}
// 10.空间总的大小
int SeqListCapacity(SeqList* ps)
{
assert(ps);
return ps->capacity;
}
// 11.查找元素位置
int SeqListFind(SeqList* ps, DataType data)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (data == ps->array[i])
{
return i;
}
}
return -1;
}
// 12.检测顺序表是否为空
int SeqListEmpty(SeqList* ps)
{
assert(ps);
return 0 == ps->size; //若为空，等式为真，返回值为1
}
// 13.获取顺序表中的第一个元素
DataType SeqListFront(SeqList* ps)
{
assert(ps);
return ps->array[0];
}
// 14.获取顺序表中最后一个元素
DataType SeqListBack(SeqList* ps)
{
assert(ps);
return ps->array[ps->size];
}
// 15.获取顺序表中任意位置的元素
DataType SeqListGet(SeqList* ps, int pos)
{
assert(ps);
return ps->array[pos];
}
3.顺序表总结
1）顺序表由于在内存连续开辟，故找任意位置数据时可直接找到
2）顺序表的头插与头删需循环移动数据，时间复杂度高
3）顺序表扩容需将原数据遍历拷贝值新空间，消耗大
4）顺序表会造成空间浪费，因为空间是提前开辟好的
源代码
头文件
//头文件 用来声明调用函数
#pragma once
#include<stdio.h>
#include<Windows.h>
#include<malloc.h>
#include<assert.h>
#pragma warning(disable:4996)
/*
// 1.静态顺序表：顺序表中的元素存储在一段固定的数组中
#define MAXSIZE 100
struct SeqList
{
int array[MAXSIZE];
int size;
};
*/
// 2.动态顺序表: 底层的空间从堆上动态申请出来的
typedef int DataType;
typedef struct SeqList
{
DataType* array; // 指向存储元素空间的起始位置
int capacity; // 表示空间总的大小
int size; // 有效元素的个数
}SeqList;
// typedef struct SeqList SeqList;
// 1.初始化动态顺序表
void SeqListInit(SeqList* ps, int initCapacity);
// 2.释放链表
void SeqListDestroy(SeqList* ps);
// 3.尾插
void SeqListPushBack(SeqList* ps, DataType data);
// 4.尾删
void SeqListPopBack(SeqList* ps);
// 5.头插
void SeqListPushFront(SeqList* ps, DataType data);
// 6.头删
void SeqListPopFront(SeqList* ps);
// 7.在顺序表的pos位置插入元素data
// 注意：pos的范围必须在[0, ps->size]
void SeqListInsert(SeqList* ps, int pos, DataType data);
// 8.顺序表删除pos位置的值
// 注意：pos的范围必须在[0, ps->size)
void SeqListErase(SeqList* ps, int pos);
// 9.有效元素个数
int SeqListSize(SeqList* ps);
// 10.空间总的大小
int SeqListCapacity(SeqList* ps);
// 11.查找元素位置
int SeqListFind(SeqList* ps, DataType data);
// 12.检测顺序表是否为空
int SeqListEmpty(SeqList* ps);
// 13.获取顺序表中的第一个元素
DataType SeqListFront(SeqList* ps);
// 14.获取顺序表中最后一个元素
DataType SeqListBack(SeqList* ps);
// 15.获取顺序表中任意位置的元素
DataType SeqListGet(SeqList* ps, int pos);
///
// 测试顺序表
void TestSeqList();
函数文件
#include "seqlist.h"
// 检测顺序表空间
static void ChecKCapacity(SeqList* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
//开辟新空间
int newCapacity = (ps->capacity << 1); //左移一位就是两倍大小
DataType* temp = (DataType*)malloc(newCapacity * sizeof(DataType));
if (NULL == temp)
{
assert(0);
return;
}
//原空间值拷贝到新空间
for (int i = 0; i < ps->size; i++)
{
temp[i] = ps->array[i];
}
//释放原堆空间
free(ps->array);
ps->array = temp;
ps->capacity = newCapacity;
}
}
// 打印函数
static void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->array[i]);
}
printf("\n");
}
///
// 1.初始化动态顺序表
void SeqListInit(SeqList* ps, int initCapacity)
{
assert(ps); //检测传入地址是否合法
initCapacity = initCapacity <= 0 ? 3 : initCapacity; //检测第二个参数 若非法默认开辟三个空间
ps->array = (DataType*)malloc(initCapacity * sizeof(DataType));
if (NULL == ps->array)
{
assert(0); //通过assert显示错误原因
return;
}
ps->capacity = initCapacity;
ps->size = 0;
}
// 2.释放顺序表
void SeqListDestroy(SeqList* ps)
{
assert(ps);
if (ps->array)
{
free(ps->array); //链表内存上连续开辟，整体释放
ps->array = NULL;
ps->capacity = 0;
ps->size = 0;
}
}
// 3.尾插
void SeqListPushBack(SeqList* ps, DataType data)
{
assert(ps);
//1.检测空间是否足够
ChecKCapacity(ps);
//2.最后一个元素插入data
ps->array[ps->size] = data;
ps->size++;
}
// 4.尾删
void SeqListPopBack(SeqList* ps)
{
assert(ps);
//1.检测链表是否有元素
if (SeqListEmpty(ps))
{
printf("ERROR:顺序表无内容\n");
return;
}
//2.删除
ps->size--; //只改变合法元素个数即可，无需将空间释放
}
// 5.头插
void SeqListPushFront(SeqList* ps, DataType data)
{
assert(ps);
//1.检测空间是否足够
ChecKCapacity(ps);
//2.将所有元素整体向后移一位
for (int i = ps->size - 1; i >= 0; i--)
{
ps->array[i + 1] = ps->array[i];
}
//3.插入元素
ps->array[0] = data;
ps->size++;
}
// 6.头删
void SeqListPopFront(SeqList* ps)
{
assert(ps);
//1.检测链表是否有元素
if (SeqListEmpty(ps))
{
printf("ERROR:顺序表无内容\n");
return;
}
//2.将所有元素整体向前移一位
for (int i = 0; i < ps->size; i++)
{
ps->array[i] = ps->array[i + 1];
}
ps->size--;
}
// 7.在顺序表的pos位置插入元素data
// 注意：pos的范围必须在[0, ps->size]
void SeqListInsert(SeqList* ps, int pos, DataType data) //pos为下标从0开始
{
assert(ps);
//1.位置检测
if (pos<0 || pos>ps->size)
{
printf("ERROR:插入位置超出范围\n");
return;
}
//2.容量检测
ChecKCapacity(ps);
//3.pos后元素后移一位
for (int i = ps->size; i >= pos; i--)
{
ps->array[i + 1] = ps->array[i];
}
//4.插入元素
ps->array[pos] = data;
ps->size++;
}
// 8.顺序表删除pos位置的值
// 注意：pos的范围必须在[0, ps->size)
void SeqListErase(SeqList* ps, int pos) //pos为下标从0开始
{
assert(ps);
//1.位置检测
if (pos<0 || pos>ps->size)
{
printf("ERROR:插入位置超出范围\n");
return;
}
//2.pos和其后元素向前移一位
for (int i = pos; i < ps->size; i++)
{
ps->array[i] = ps->array[i + 1];
}
ps->size--;
}
// 9.有效元素个数
int SeqListSize(SeqList* ps)
{
assert(ps);
return ps->size;
}
// 10.空间总的大小
int SeqListCapacity(SeqList* ps)
{
assert(ps);
return ps->capacity;
}
// 11.查找元素位置
int SeqListFind(SeqList* ps, DataType data)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (data == ps->array[i])
{
return i;
}
}
return -1;
}
// 12.检测顺序表是否为空
int SeqListEmpty(SeqList* ps)
{
assert(ps);
return 0 == ps->size; //若为空，等式为真，返回值为1
}
// 13.获取顺序表中的第一个元素
DataType SeqListFront(SeqList* ps)
{
assert(ps);
return ps->array[0];
}
// 14.获取顺序表中最后一个元素
DataType SeqListBack(SeqList* ps)
{
assert(ps);
return ps->array[ps->size];
}
// 15.获取顺序表中任意位置的元素
DataType SeqListGet(SeqList* ps, int pos)
{
assert(ps);
return ps->array[pos];
}
///
//测试函数1
static void Test1()
{
SeqList s;
SeqListInit(&s, 3); //注意这里参数传的是地址
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPushBack(&s, 5);
SeqListPushBack(&s, 6);
SeqListPrint(&s);
SeqListErase(&s, 4);
SeqListPushFront(&s, 0);
SeqListPrint(&s);
printf("顺序表有效数字：%d\n", SeqListSize(&s));
printf("顺序表开辟空间：%d\n", SeqListCapacity(&s));
printf("顺序表中数字5的下标：%d\n", SeqListFind(&s, 5));
SeqListDestroy(&s);
}
//测试顺序表
void TestSeqList()
{
Test1();
}
主函数文件
#include "seqlist.h"
int main()
{
TestSeqList();
system("pause");
return 0;
}