【数据布局】动态次序表的实现
1.什么是数据布局数据布局就是把数据元素按照肯定的关系构造起来的聚集，用来构造和存储数据。通过数据布局，可以大概有用的将数据构造和管理在一起，按照我们的方式恣意对数据举行增删查改等利用。
2.数据布局的分类
数据布局大概可分为逻辑布局和物理布局两大类 。
2.1逻辑布局
逻辑布局：是从具体标题中抽象出来的模子，是抽象意义的布局。
[*]聚集布局：布局中数据元素除了同属于一个聚集外，它们之间没有任何关系
[*]线性布局：布局中数据元素之间存在逐一对应的关系
[*]树形布局：布局中数据元素之间存在一对多的条理关系
[*]图形布局：布局中数据元素是多对多的关系
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMGJhYWFjZjQ3ZTc1NDUxMWEzNzBhMzY5M2M4ODNkNDAucG5n
2.2物理布局
物理布局：逻辑布局在盘算机中真正的表现方式（又称映像）。
常见的物理布局（存储布局）有次序存储，链式存储，索引存储，以及散列存储。
[*]次序存储布局：把数据元素放到地点一连的内存单元内里，其数据间的逻辑关系和物理关系是划一的，好比我们常用的数组就是次序存储布局。
[*]链式存储布局：是把数据元素存放在恣意的存储单元内里，这组存储单元可以是一连的，也可以是不一连的。此时，数据间的物理关系不能反映其逻辑关系。以是每一数据元素均利用一个结点来存储，不光必要存储数据元素，而且还要存储数据元素之间的逻辑关系（将结点分为两部分，一部分存储数据元素自己，称为数据域；一部分存储下一个结点的地点，称为指针域。）
[*]索引存储布局：在索引存储布局中，不光必要存储全部数据元素（称为主数据表），还必要创建附加的索引表。每个数据元素都由一个唯一的关键字来标识，由该关键字和对应的数据元素的地点构成一个索引项，存入索引表。
[*]散列（哈希）存储布局：散列存储布局是指依据数据元素的关键字，通过事先筹划好的哈希函数盘算出一个值，再将其作为该数据的存储地点。
2.3总结
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYmE2YTk3MTFhMjE3NGY5MmJhY2MzMDA0YmY5NDNhMzIucG5n
最根本的数据布局：数组。
有了数组，为什么还要学习其他的数据布局？
假定命组有10个空间，已经利用了5个，向数组中插入数据步调：
求数组的有用数据个数，向下标为数据有用个数的位置插入数据。（留意：这里要判定数组是否满了）
假设数据量非常巨大，频仍的获取数组有用数据个数会影响步调实验服从。
结论：最根本的数据布局可以大概提供的利用已经不能完全满足复杂算法实现。
3.线性表
线性表（linear list）指的是具有部分雷同特性的一类数据布局的聚集。
线性表的逻辑布局属于线性布局，采取次序存储布局为次序表，采取链式存储布局为线性链表。次序表在C语言中一样平常利用数组去实现，链表利用布局体去实现。
3.1次序表
次序表的底层布局是数组，通过对数组的封装，实现了常用的增编削查等接口。
3.2次序表的分类
静态次序表
概念：利用定长数组存储元素
//静态顺序表
typedef int SLDATATYPE;
#define N 100
typedef struct SeqList
{
SLDATATYPE arr;//定长数组
int size;//顺序表当前有效数据个数
}SL;静态次序表缺陷：静态次序表的长度是固定的，因此数组满了必要手动更改N，空间给少了不敷用，给多了造成空间浪费。
动态次序表
//动态顺序表——按需申请可增容
typedef int SLDATATYPE;
typedef struct SeqList
{
SLDATATYPE* arr;//指向动态开辟的数组
int size;//顺序表当前有效数据个数
int capacity;//记录当前空间大小
}SL;
3.3动态次序表的实现
3.3.1次序表的初始化
void SLInit(SL *ps)//注意：这里不可以写成void SLInit(SL ps)
//会报错：使用了未初始化的局部变量！这是值传递，对形参的修改不影响实参。要传地址
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}3.3.2次序表的烧毁
顺序表的销毁
void SLDestory(SL* ps)
{
if (ps->arr)
{
free(ps->arr);//先释放空间，然后置空
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}3.3.3次序表的插入
尾插
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNTE1MjlhODhmZmQ2NGM1NzljMzBiYzcwZGNhNzljYzgucG5n
留意：插入数据之前先看空间够不敷。初始化后空间容量为0，插入数据之前先申请空间，也大概空间满了，有用数据个数即是空间容量了，也要申请空间。
容量查抄函数
void SLCheckCapacity(SL*ps)
{
//插入数据之前先看空间够不够
if (ps->capacity == ps->size)
{
//申请空间
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目表达式
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//要申请多大空间
//若要频繁的增容，则会造成程序的运行效率大大降低,增容通常来说是成倍数的增加，一般是2或者3倍
//realloc申请空间失败返回空指针,所以再造一个临时的指针tmp
if (tmp == NULL)
{
perror("realloc");
exit(1);//直接退出程序
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newcapacity;
}
}尾插实现
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr = x;//增加一个数据，有效数据个数+1
/*ps->arr = x;
++ps->size;*/
}
头插
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjM5Zjk0NTZhNDlmNDI0ZDkzM2U2ZDk5YjNiMTE0YjIucG5n
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
//先让顺序表中已有的数据整体往后挪动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr = ps->arr;//最后一次ps->arr=ps->arr
}
ps->arr = x;
ps->size++;
}
3.3.4次序表的删除
尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//判断顺序表是否为空，为空不能执行删除操作
//顺序表不为空
--ps->size;
}留意：被删除的数据空间不必要置为0，没故意义，下次访问这块空间时，新的数据会覆盖掉。也不能开释空间，由于free只能从开发的空间的首地点处开释，不能开释其他地方的空间。
头删
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMDY5MjRhODMyMzE0NGQzODhkMGIyZWFhYTg3MTYxZTgucG5n
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//数据整体往前挪动一位
for (int i = 0; i < ps->size-1; i++)
{
ps->arr = ps->arr;//最后一次ps->arr = ps->arr
}
ps->size--;
}
3.3.5在指定位置插入数据
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMzI4ZTExMTMzNTVkNGNmZGFmMDZhOTBlODgzOGI0YTIucG5n
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
//让pos及之后的数据整体向后挪动一位
for (int i = ps->size; i > pos; i--)
{
ps->arr = ps->arr;//最后一次ps->arr=ps->arr
}
ps->arr = x;
ps->size++;
}3.3.6删除指定位置的数据
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZGQ5NGFhNzQwNzZmNDk1NTgzMGY1YWJkN2YzMTFjZDcucG5n
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size-1; i++)
{
ps->arr = ps->arr;//最后一次ps->arr=ps->arr
}
ps->size--;
}3.3.7次序表的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr ==x)
{
//找到了！
return i;
}
}
//没有找到！
return -1;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金
页:
[1]