马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
各人好！这里是摆子，本日给各人带来的是C语言数据布局开端-次序表专题，紧张先容了数据布局和动态次序表的实现，快来看看吧！记得一键三连哦！
1.数据布局的概念
1.1什么是数据布局？
数据布局是盘算机存储、构造数据的⽅式。
分开看，由“数据”和“布局”两词组合而成。比方农户养羊🐑，每一只羊都是一个数据，但是面对巨大的羊群，想要找到草原上名叫“咩咩”的⽺很难，但是从⽺圈⾥找到1号⽺就很简朴，⽺圈如许的布局有用将⽺群构造起来。
数据布局反映数据的内部构成，即数据由那部门构成，以什么⽅式构成，以及数据元素之间出现的布局。
总结：
1）可以大概存储数据（如次序表、链表等布局）
2）存储的数据可以大概⽅便查找
1.2为什么须要数据布局？
正如上文所说，若没有妥善的管理方式，要想在草原上找到一只叫“麦麦”的羊很难。
同理，步调中如果不对数据进⾏管理，大概会导致数据丢失、使用数据困难、野指针等情况。通过数据布局，可以大概有用将数据构造和管理在⼀起。按照我们的⽅式恣意对数据进⾏增编削查等使用。
大概你们已经想到了，数组就是最根本的数据布局。
1.3有了数组，为什么还要学习其他的数据布局？
假设数据量⾮常庞⼤，频仍的获取数组有用数据个数会影响步调执⾏服从。
结论：最根本的数据布局可以大概提供的使用已经不能完全满⾜复杂算法实现。
做个类比：平常餐馆和米其林。都有一个炒土豆丝，平常餐馆起的菜名叫“炒土豆丝”，而米其林起的名字叫“豪华金丝”。他们所用的质料有区别么？显然没有，区别是米其林会通过精致的摆盘，让菜变得看起来更加高档。
数组就是平常餐馆，其他更复杂的数据布局就是米其林，后者提供了更多更复杂的使用，来让管理变得方便，办理复杂算法。
2.次序表的概念和布局
2.1线性表的概念
线性表指的是具有类似特性的数据布局的聚集。
线性表是⼀种在现实中⼴泛使⽤的数据布局，常⻅的线性表：次序表、链表、栈、队列、字符串… 比方：球类分为足球，篮球，排球等。
2.2两者关联
线性表指的是具有类似特性的数据布局的聚集。
1.物理布局：不肯定一连
2.逻辑布局：一连
次序表是线性表的一种。
1.物理布局：一连
2.逻辑布局：一连
3.次序表的分类
次序表的底层布局是数组，对数组的封装，实现了常⽤的增编削查等接⼝。
次序表分为：静态次序表和动态次序表。
3.1静态次序表
概念：使用定长数组存储元素。
界说：
//静态次序表的界说
struct SeqList
{
int arr[N];//定长数组
int size;//有用数据个数
};
3.2动态次序表
概念：按需申请空间。
界说：
typedef int SLDataType;
//动态次序表
typedef struct SeqList
{
SLDataType* arr;
int size;//有用数据个数
int capacity;//空间巨细
}SL;
3.3哪个更好呢？
静态次序表：数组巨细给小了，空间不敷用；数组巨细给大了，空间浪费；
动态次序表：按需申请空间，不浪费，够用。
因此，动态次序表更好啦！
4.动态次序表的实现
4.1界说次序表布局
4.2初始化/烧毁
注意：初始化时，函数传参要传地点
烧毁：
注意：开释空间后，还要置为空！
4.3尾插
尾插是封装的第一个功能，此中也有许多坑，将这个把握好了，后边写剩下的功能就如履平地了。一起来看看怎样实现 尾插 吧！
代码表明：
1.断言查抄 ：
2.空间查抄与扩容：
3.所得知识
4.代码优化
通过将扩容逻辑封装到 SLCheckCapacity 函数中，SLPushBack 函数的逻辑更加清楚，且 SLCheckCapacity 可以在其他地方复用。- void SLCheckCapacity(SL*ps)
- {
- //插入数据之前先判断空间够不够
- if (ps->size == ps->capacity)
- {
- //申请空间
- //malloc calloc realloc 增容realloc ,增容通常是成倍数的增加，一般2，3倍
- //三目表达式 真or假 真：默认给4 假：2倍扩容
- int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
- SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
- if (tmp == NULL)
- {
- perror("realloc fail!");
- exit(1);
- }
- //空间申请成功
- ps->arr = tmp;
- ps->capacity = newCapacity;
- }
- }
养成好风俗，每写好一个功能就立马测试一下，不要堆积测试，末了一堆报错，岂不是炸了吗。
发现当插入空的时间，报错。反推完满代码，插入之前应该查抄确保传入的指针ps不为NULL。即1.断言查抄。
4.3头插
扩容逻辑已封装为void SLCheckCapacity(SL*ps)函数，插入数据前，直接套用即可
插入数据前，判断是否为NULL;
插入数据后，记得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];//arr[1]=arr[0]
- }
- 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->arr[size-2]=ps->arr[size-1]
- }
- ps->size--;
- }
SeqList.h- #pragma once
- //定义顺序表结构
- #define N 100
- #include<stdio.h>
- #include<stdlib.h>//动态申请内存的头文件
- #include<assert.h>
- ////静态顺序表
- //struct SeqList
- //{
- // int arr[N];//定长数组
- // int size;//有效数据个数
- //};
- typedef int SLDataType;
- //动态顺序表
- typedef struct SeqList
- {
- SLDataType* arr;
- int size;//有效数据个数
- int capacity;//空间大小
- }SL;//2.
- //typedef struct SeqList SL;//1.
- //顺序表初始化
- void SLInit(SL *ps);
- //顺序表销毁
- void SLDestroy(SL*ps);
- void SLPrint(SL s);
- //头部插⼊删除 / 尾部插⼊删除
- void SLPushBack(SL* ps, SLDataType x);
- void SLPushFront(SL* ps, SLDataType x);
- void SLPopBack(SL* ps);
- void SLPopFront(SL* ps);
- //指定位置之前插⼊/删除数据
- void SLInsert(SL* ps, int pos, SLDataType x);
- void SLErase(SL* ps, int pos);
- int SLFind(SL* ps, SLDataType x);
- #include "SeqList.h"//次序表初始化void SLInit(SL *ps){ ps->arr = NULL; ps->size = ps->capacity= 0;}//次序表的烧毁void SLDestroy(SL* ps){ if (ps->arr) { free(ps->arr); } ps->arr = NULL; ps->size = ps->capacity = 0;}void SLCheckCapacity(SL*ps)
- {
- //插入数据之前先判断空间够不够
- if (ps->size == ps->capacity)
- {
- //申请空间
- //malloc calloc realloc 增容realloc ,增容通常是成倍数的增加，一般2，3倍
- //三目表达式 真or假 真：默认给4 假：2倍扩容
- int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
- SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
- if (tmp == NULL)
- {
- perror("realloc fail!");
- exit(1);
- }
- //空间申请成功
- ps->arr = tmp;
- ps->capacity = newCapacity;
- }
- }
- //尾插void SLPushBack(SL* ps, SLDataType x){ assert(ps);//等价于assert(ps!=NULL) //ps->arr[ps->size] = x; //++ps->size; //插入数据之前先判断空间够不敷 if (ps->size == ps->capacity) { //申请空间 //malloc calloc realloc 动态增容realloc ,增容通常是成倍数的增长，一样平常2，3倍 //三目表达式 真or假 真：默认给4 假：2倍扩容 realloc:申请失败返回null int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间 SLDataType * tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间 if (tmp == NULL) { perror("realloc fail!"); exit(1); } //空间申请乐成 ps->arr = tmp; ps->capacity = newCapacity; } ps->arr[ps->size++] = x;}//头插
- 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];//arr[1]=arr[0]
- }
- ps->arr[0] = x; //插
- ps->size++;
- }
- //打印void SLPrint(SL s){ for (int i = 0; i < s.size; i++) { printf("%d ", s.arr[i]); } printf("\n");}//尾删
- 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->arr[size-2]=ps->arr[size-1]
- }
- ps->size--;
- }
- #include"SeqList.h"
- void SLTest01()
- {
- SL s1;
- SLInit(&s1);//传地址
- //增删差改操作
- //测试尾插
- SLPushBack(&s1,1);
- SLPushBack(&s1, 2);
- SLPushBack(&s1, 3);
- SLPushBack(&s1, 4);
- //SLPushBack(NULL, 5);//assert(ps)
- SLPrint(s1);
- SLPushFront(&s1, 5);
- SLPushFront(&s1, 6);
- //测试头删
- SLPopFront(&s1);
- SLPrint(s1);
- SLPopFront(&s1);
- SLPrint(s1);
- SLDestroy(&s1);
- }
- int main()
- {
- SLTest01();
- return 0;
- }
|
发表于 2025-10-22 08:16:32