目录
一、数据结构
1.1概念
1.2总结
1.3为什么需要数据结构？
二、顺序表
1.顺序表的概念及结构
1.1线性表
2.顺序表分类
2.1顺序表和数组的区别
2.2顺序表的分类
2.2.1静态顺序表
2.2.1.1概念
2.2.1.2缺陷
2.2.2动态顺序表
三、动态顺序表的实现
3.1新建项目
3.2 SeqList.h
3.3SeqList.c
3.3.1初始化
3.3.2销毁
3.3.3打印
3.3.4扩容
3.3.4.1扩容原则选择
3.3.4.2扩容代码呈现
3.3.5尾插
3.3.6头插
3.3.7尾删
3.3.8头删
3.3.9指定位置之前插入数据
3.3.10指定位置之前删除数据
3.3.11查找
3.3.12 SeqList.c
一、数据结构
1.1概念
- 数据结构是计算机存储、组织数据的⽅式。
- 数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么⽅式构成，以及数据元素之间呈现的结构。
1.2总结
- 1）能够存储数据（如顺序表、链表等结构）
- 2）存储的数据能够⽅便查找
1.3为什么需要数据结构？
- 程序中如果不对数据进⾏管理，可能会导致数据丢失、操作数据困难、野指针等情况。 通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操作。
- 最基础的数据结构：数组。
- 【思考】有了数组，为什么还要学习其他的数据结构？
- 假定数组有10个空间，已经使⽤了5个，向数组中插⼊数据步骤： 求数组的⻓度，求数组的有效数据个数，向下标为数据有效个数的位置插⼊数据（注意：这⾥是 否要判断数组是否满了，满了还能继续插⼊吗）..... 假设数据量⾮常庞⼤，频繁的获取数组有效数据个数会影响程序执⾏效率。
- 结论：最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。
二、顺序表
1.顺序表的概念及结构
1.1线性表
- 线性表（linear list）是n个具有相同特性的数据元素的有限序列。
- 线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串..
- 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表分类
2.1顺序表和数组的区别
- 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
2.2顺序表的分类
2.2.1静态顺序表
2.2.1.1概念
- 使⽤定⻓数组存储元素
2.2.1.2缺陷
-
空间给少了不够⽤，给多了造成空间浪费
2.2.2动态顺序表
三、动态顺序表的实现
3.1新建项目
3.2 SeqList.h
//C语言
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;//不仅限于int类型 便于后续替换
//动态顺序表
typedef struct SeqList
{
SLDataType* arr; //存储数据的底层结构
int capacity; //记录顺序表的空间大小
int size; //记录顺便当前有效的数据个数
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//尾插/尾删/头插/头删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);3.3SeqList.c
3.3.1初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = 0;
ps->size = 0;
}3.3.2销毁
void SLDestroy(SL* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}3.3.3打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
3.3.4扩容
3.3.4.1扩容原则选择
- 一次扩充一个空间：插入一个元素还不会造成空间浪费 ✖ 程序执行效率低下
- 一次扩充固定个大小的空间（10、100）✖ 小了：造成频繁扩容，会造成程序运行低下；大了：造成空间浪费
- 成倍数的扩增（1.5倍、2倍）✅相对高效：数据插入的越多，扩容的大小越来越大即插入数据的数量与扩容大小成近似真相关
3.3.4.2扩容代码呈现
- 首先判断动态数组的元素个数（size）是否等于容量（capacity）。
- 若相等，则需要进行扩容操作。
- 计算新的容量大小，如果原容量为0，则新容量为4，否则新容量为原容量的两倍。
- 调用realloc函数重新分配内存空间，将原动态数组的元素拷贝到新的内存空间中。
- 如果内存分配失败（temp为NULL），则输出错误信息并退出程序。
- 如果内存分配成功，则将新的内存空间地址赋值给动态数组指针arr，同时更新容量为新的容量大小。
//扩容
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (temp == NULL)
{
perror("realloc fail!");//扩容失败
exit(1);//退出
}
//扩容成功
ps->arr = temp;
ps->capacity = newCapacity;
}
}3.3.5尾插
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);//断言，确保不为空
//空间不够直接插入
SLCheckCapacity(ps);
//空间足够直接插入
ps->arr[ps->size] = x;
ps->size++;
}3.3.6头插
//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
//旧数据挪动
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}3.3.7尾删
//尾删
void SLPopBack(SL* ps)
{
//顺序表为空
assert(ps);
assert(ps->size);
//顺序表不为空
ps->size--;
}
3.3.8头删
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}3.3.9指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->arr);
SLCheckCapacity(ps);
//pos及之后的数据挪动一位
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}3.3.10指定位置之前删除数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(ps >= 0 && pos < ps->size);
for (int i = pos;i < ps->size;i++)
{
ps->arr[i] = ps->arr[i + 1];
}
}3.3.11查找
int SLFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1; // 表示未找到
}3.3.12 SeqList.c
#include"SeqList.h"
//初始化和销毁
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = 0;
ps->size = 0;
}
void SLDestroy(SL* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//扩容
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (temp == NULL)
{
perror("realloc fail!");//扩容失败
exit(1);//退出
}
//扩容成功
ps->arr = temp;
ps->capacity = newCapacity;
}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);//断言，确保不为空
//空间不够直接插入
SLCheckCapacity(ps);
//空间足够直接插入
ps->arr[ps->size] = x;
ps->size++;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
//旧数据挪动
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
//顺序表为空
assert(ps);
assert(ps->size);
//顺序表不为空
ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->arr);
SLCheckCapacity(ps);
//pos及之后的数据挪动一位
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(ps >= 0 && pos < ps->size);
for (int i = pos;i < ps->size;i++)
{
ps->arr[i] = ps->arr[i + 1];
}
}
int SLFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1; // 表示未找到
}
