1. 数据结构相关概念
数据结构是由“数据”和“结构”两词组合而来。
什么是数据？常见的数值1、2、3、4…、教务系统⾥保存的用户信息（姓名、性别、年龄、学历等等）、网页眼可以看到的信息（文字、图片、视频等等），这些都是数据。
什么是结构？
当我们想要使⽤⼤量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独⽴的变量对于程序来说，可读性⾮常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的⽅式。
概念：数据结构是计算机存储、组织数据的⽅式。
数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么⽅式构成，以及数据元素之间呈现的结构。
总结：
- 能够存储数据（如顺序表、链表等结构）
- 存储的数据能够方便查找
2. 顺序表的概念及结构
2.1 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据构，常⻅的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.2顺序表分类
顺序表和数组的区别
- 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
静态顺序表
概念：使用定长数组存储元素
静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费动态顺序表
3. 动态顺序表的实现
3.1 创建顺序表
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* arr; //管理动态开辟的空间
int capacity; //记录顺序表的空间大小
int size; //记录顺表表当前有效元素的个数
}SL;
3.2 实现顺序表
初始化顺序表
//初始化顺序表
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
销毁顺序表
void SLDestory(SL* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->capacity = 0;
ps->size = 0;
}
检查是否需要扩容
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* ptr = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (ptr == NULL)
{
perror("realloc fail");
exit(1);//退出程序
}
//扩容成功
ps->arr = ptr;
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);
int i = 0;
for (i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
打印顺序表
void SLPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
尾删顺序表
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}
头删顺序表
void SLPopFornt(SL* ps)
{
assert(ps);
assert(ps->size);
int i = 0;
for (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->size);
SLCheckCapacity(ps);
int i = 0;
for (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(pos >= 0 && pos < ps->size);
int i = 0;
for (i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
查找数据
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
3.3 顺序表完整代码实现
SeqList.h
#pragma once//防止头文件被重复包含多次
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* arr; //管理动态开辟的空间
int capacity; //记录顺序表的空间大小
int size; //记录顺表表当前有效元素的个数
}SL;
//初始化顺序表
void SLInit(SL* ps);
//销毁顺序表
void SLDestory(SL* ps);
//尾插顺序表
void SLPushBack(SL* ps,SLDataType x);
//头插顺序表
void SLPushFront(SL* ps,SLDataType x);
//打印顺序表
void SLPrint(SL* ps);
//尾删顺序表
void SLPopBack(SL* ps);
//头删顺序表
void SLPopFornt(SL* ps);
//在任意位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//在任意位置删除数据
void SLErase(SL* ps, int pos);
//查找数据
int SLFind(SL* ps,SLDataType x);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS//消除警告
#include "SeqList.h"
//初始化顺序表
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//销毁顺序表
void SLDestory(SL* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->capacity = 0;
ps->size = 0;
}
void SLCheckCapacity(SL* ps)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
if (ps->capacity == ps->size)
{
SLDataType* ptr = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (ptr == NULL)
{
perror("realloc fail");
exit(1);
}
//扩容成功
ps->arr = ptr;
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);
int i = 0;
for (i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
//
void SLPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//尾删顺序表
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}
//头删顺序表
void SLPopFornt(SL* ps)
{
assert(ps);
assert(ps->size);
int i = 0;
for (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->size);
SLCheckCapacity(ps);
int i = 0;
for (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(pos >= 0 && pos < ps->size);
int i = 0;
for (i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//查找数据
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
int main()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(&sl);
int ret = SLFind(&sl, 2);
if (ret == -1)
{
printf("找不到\n");
}
else
{
printf("找到了,下标是%d\n",ret);
}
SLDestory(&sl);
return 0;
}
运行结果如图:
