包装材料网站建设,介绍个人网站的ppt怎么做,相城苏州网站建设,做漫画在线观看网站前言 我们在对C语言有一定的了解之后#xff0c;我们就可以开始数据结构的学习了#xff0c;数据结构多用指针、结构体、动态内存开辟等知识#xff0c;若对这些知识还不太了解的朋友#xff0c;就需要加深其理解了#xff0c;那么废话不多说#xff0c;我们正式开始本节… 前言 我们在对C语言有一定的了解之后我们就可以开始数据结构的学习了数据结构多用指针、结构体、动态内存开辟等知识若对这些知识还不太了解的朋友就需要加深其理解了那么废话不多说我们正式开始本节的学习
什么是数据结构
数据结构是由数据 和 结构 两个词相组合得到的
那么什么是数据呢
例如常见的数字1、2、3、4、5等手机通讯录里面保存的联系人信息号码、名字等、浏览器网页里面的信息这些都统称为数据
什么是结构呢
当我们需要使用大量同一类型的数据时我们手动的定义大量独立的变量对程序来说可读性很差我们往往可以借助数组等这些数据结构将大量的数据组织在一起所以结构也可以理解为组织数据的方式
举个通俗易懂的例子我们如果想要在一大片草场上寻找一名叫 多莉 的羊难度会很大但是我们要在羊圈中找到 多莉 就会很简单羊圈就好像一个结构而羊就好似数据 概念数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系 的数据元素的集合。数据结构反映数据的内部构成即数据由那部分构成以什么⽅式构成以及数据元素之间呈现的结构
其中在数据结构中最基础的数据结构就是数组
顺序表
顺序表是线性表的一种其中线性表是具有相同特征的数据结构的集合
线性表的特征
1.物理结构不一定连续数据间的地址不一定是连续的
2.逻辑结构是连续的
顺序表在物理结构和逻辑结构层面上都是连续的
顺序表的底层就是数组顺序表是在数组的基础上进行维护、封装
可能有人就会产生疑问既然都有数组了数组也可以实现数据的增加、删除、查询、修改功能那么顺序表的存在又有什么意义呢
当我们想修改、插入或者删除数组中的某个数据时我们首先需要通过循环来查找数组之中已有元素的个数再进行数据的修改、插入或者删除我们每次进行操作的时候都需要进行循环的处理这样就会很浪费时间和空间此时顺序表的存在就有意义了
顺序表的底层虽然是数组但是数组提供了很多现成的办法来处理数据相比直接使用数组会更加的简洁高效
顺序表分类
1.静态顺序表
struct Seqlist
{int arr[100];int size;//记录顺序表当前有效数据的个数};
静态顺序表的底层是一个定长的数组在代码的编译阶段我们就确认了数组的大小
2.动态顺序表
//动态顺序表
struct Seqlist
{int* arr;int size;//有效的数据个数int capacity;//记录空间大小
};
那么动态顺序表和静态顺序表二者相比较谁更好呢
对于静态顺序表而言。若是数组大小给小了则会导致空间不够用的问题可能导致数据的丢失若是数组大小给大了则会导致空间的浪费
所以动态顺序表更好因为它更加灵活
我们在实现顺序表时我们通常把它分成两个文件
头文件顺序表的结构声明实现顺序表的方法头文件实现的是类似于书的目录的功能
源文件实现顺序表的方法
同时我们在实现顺序表的时候还需要多创建一个文件用于检测其功能是否正常
//动态顺序表
struct Seqlist
{int* arr;int size;//有效数据的个数int capacity;//空间大小
};
我们先在头文件中定义顺序表结构体考虑到我们存入顺序表中的数据类型不一定为 int 类型还有可能是 char 类型的数据所以我们可以定义一下用定义表示当前顺序表中存储数据的类型具体操作如下
typedef int SLDataType;//动态顺序表
struct Seqlist
{SLDataType* arr;int size;//有效数据的个数int capacity;//空间大小
};
我们可以重命名一下结构体类型来简化代码
//动态顺序表
typedef struct Seqlist
{SLDataType* arr;int size;//有效数据的个数int capacity;//空间大小
}SL;
下面我们就来实现一下顺序表的各种功能
顺序表的初始化
在源文件中初始化前我们需要在头文件中声明一下
void SLInit(SL ps);此时我们就可以在源文件中初始化
#includeSeqlist.h
void SLInit(SL s)
{s.arr NULL;s.size s.capacity 0;}
由于我们不知道初始化是否成功我们就可以在测试文件中通过打印各个成员的值通过在屏幕上面打印的值在观察出初始化是否成功
我们按照我们的常规理解来写出如下代码
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqlist.hvoid SLTest01()
{SL s1;SLInit(s1);}int main()
{SLTest01();return 0;
}
当我们在运行程序的时候我们发现它报错了 这个报错非常的奇怪编译器说我们使用了未初始化的局部变量 s1而我们现在所做的操作不正是要初始化吗这样不是自相矛盾吗
我们仔细分析一下就可以发现问题
我们传入的 sl 是形式参数我们采取的是传值操作由于 sl 本来就是没有初始化的变量无法进行传值操作要想解决这个问题我们需要使用传址操作现在我们就来改一下代码
#includeSeqlist.h
void SLInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;}
void SLInit(SL* ps);
此时我们的初始化代码就成功完成了
顺序表的销毁
因为数组的大小是动态开辟的需要使用到动态内存函数我们需要释放开辟的空间那么我们就需要采取如下的操作
顺序表的头部 插入 和 删除 顺序表的 尾部 插入 和 删除
顺序表的尾插
举个例子若数组里面只有四个数据
0123 0 1 2 3 4 5
此时 size 4 capacity 6我们想要在它的尾部插入 x 5
我们可以发现我们想要插入数据的地方的下标就是 size 的大小同时再插入数据之前我们需要先保证有空间允许去插入如果空间不够我们还需要去申请空间那么我们该怎么申请空间呢
首先空间的申请需要使用到 malloc calloc realloc 函数当申请的空间被使用完了我们还需要去增容那么我们要申请多大的空间呢一次增容又该增多大呢
申请空间的规则增容通常来说是成倍数的增加一般是两倍增容若空间是一个一个地去增加那么插入数据也得一个一个的去插入这样会非常的麻烦若要频繁的增容程序运行的效率就会大大降低若一次进行大量的增容就会造成空间的浪费。所以采取两倍两倍的增容是最合理的
4 -------- 8 -------- 16 -------- 32 -------- 64
通过以上几个注意事项我们可以写出代码
//尾插
void SLPushBack(SL* ps, SLDataType x)
{if (ps NULL){return;}//插入数据前看空间够不够if (ps-capacity ps-size){//申请空间//判断capacity是否为0int newCapaciy ps-capacity 0 ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, ps-newCapacity * sizeof(SLDataType));if (tmp NULL){perror(realloc fail!);exit(1);//直接退出程序不再继续执行}//空间申请成功ps-arr tmp;ps-capacity newCapaciy;}ps-arr[ps-size] x;ps-size;//或者写作 ps-arr[ps-size] x;ps-size;}
注意我们在增容的时候需要临时创建一个变量用于存储增容后的指针若是直接将 其赋给 arr倘若空间申请失败原数据内容也会丢失导致不可逆的错误
我们在 test.c 中测试一下这个代码
#includeSeqlist.hvoid SLTest01()
{SL s1;SLInit(s1);//测试尾插代码SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushBack(s1, 5);//.....SLDestory(s1);}int main()
{SLTest01();return 0;
}
这样我们的尾插操作就完成了
顺序表的头插
举个例子
0123 0 1 2 3 4size
在开始进行头插之前。我们同样的需要判断插入数据的空间够不够不够的话我们需要增容。
头插需要在下标为0的地方插入数据但是原数组下标为0的地方已经有了数据这时我们应该怎么插入数据呢
我们此时需要把原顺序表中的数据统一向后挪动一位
0123
若我们此时需要插入一个数据 x 6
由于我们在进行头插和尾插之前都需要判断空间是否足够此时我们就可以把判断空间的代码单独封装成一个函数
void SLCheckCapacity(SL* ps)
{//插入数据前看空间够不够if (ps-capacity ps-size){//申请空间//判断capacity是否为0int newCapaciy ps-capacity 0 ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapaciy * sizeof(SLDataType));if (tmp NULL){perror(realloc fail!);exit(1);//直接退出程序不再继续执行}//空间申请成功ps-arr tmp;ps-capacity newCapaciy;}
}
在数据挪动的时候我们可以发现数组中的最后一个元素经过挪动后需要到达下标为 size 处
所以由此我们可以写出头插的代码
//头插
void SLPushFront(SL* ps, SLDataType x)
{if (ps NULL){return;}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;}我们再在 test.c 文件里面测试一下
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqlist.hvoid SLTest01()
{SL s1;SLInit(s1);//测试尾插代码SLPushFront(s1, 1);SLPushFront(s1, 2);SLPushFront(s1, 3);SLPushFront(s1, 4);SLPushFront(s1, 5);//.....SLDestory(s1);}int main()
{SLTest01();return 0;
}
我们运行调试可以发现头插功能成功实现
由于每次都运行调试比较麻烦我们来定义一个函数用于打印顺序表中的元素
//打印
void SLPrint(SL s)
{for (int i 0; i s.size; i){printf(%d , s.arr[i]);}printf(\n);
}
顺序表的尾部删除
0123
我们首先需要判断顺序表是否为空为空的话就不能执行删除操作
我们可以知道每次删除完数据以后数组里面的数据就会减少一个所以 size--
此时我们就能够很轻松地写出尾部删除的代码
//尾部删除
void SLPopBack(SL* ps)
{if (ps NULL){return;}if (ps-size 0){return;}--ps-size;}
我们来测试一下
void SLTest01()
{SL s1;SLInit(s1);测试尾插代码SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPrint(s1);SLPopBack(s1);SLPrint(s1);//.....SLDestory(s1);}int main()
{SLTest01();return 0;
} 顺序表的头部删除
我们在删除完数据以后需要把顺序表里原有的顺序整体向前挪动一位
根据这个我们可以写出代码如下
//头部删除
void SLPopFront(SL* ps)
{if (ps NULL){return;}if (ps-size 0){return;}//数据整体前挪for (int i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}我们测试一下
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqlist.hvoid SLTest01()
{SL s1;SLInit(s1);测试尾插代码SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPrint(s1);SLPopFront(s1);SLPrint(s1);//.....SLDestory(s1);}int main()
{SLTest01();return 0;
} 代码运行成功
顺序表代码合并
头文件
#pragma once
#include stdio.h
#include stdlib.htypedef int SLDataType;//动态顺序表
typedef struct Seqlist
{SLDataType* arr;int size;//有效数据的个数int capacity;//空间大小
}SL;//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestory(SL* ps);
//顺序表的头部 插入 和 删除 顺序表的 尾部 插入 和 删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);void SLPopBack(SL* ps);
void SLPopFront(SL* ps);//顺序表的打印
void SLPrint(SL s);
源文件
#define _CRT_SECURE_NO_WARNINGS 1
//静态顺序表
//struct Seqlist
//{
// int arr[100];
// int size;//记录顺序表当前有效数据的个数
//
//
//};//动态顺序表
//struct Seqlist
//{
// int* arr;
// int size;//有效的数据个数
// int capacity;//记录空间大小
//};#includeSeqlist.h
void SLInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;}//顺序表的销毁
void SLDestory(SL* ps)
{if (ps-arr){free(ps-arr);}ps-arr NULL;ps-size ps-capacity 0;
}void SLCheckCapacity(SL* ps)
{//插入数据前看空间够不够if (ps-capacity ps-size){//申请空间//判断capacity是否为0int newCapaciy ps-capacity 0 ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapaciy * sizeof(SLDataType));if (tmp NULL){perror(realloc fail!);exit(1);//直接退出程序不再继续执行}//空间申请成功ps-arr tmp;ps-capacity newCapaciy;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{if (ps NULL){return;}SLCheckCapacity(ps);ps-arr[ps-size] x;ps-size;//或者写作 ps-arr[ps-size] x;}//头插
void SLPushFront(SL* ps, SLDataType x)
{if (ps NULL){return;}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)
{if (ps NULL){return;}if (ps-size 0){return;}--ps-size;}
//头部删除
void SLPopFront(SL* ps)
{if (ps NULL){return;}if (ps-size 0){return;}//数据整体前挪for (int i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqlist.hvoid SLTest01()
{SL s1;SLInit(s1);测试尾插代码SLPushBack(s1, 1);SLPushBack(s1, 2);SLPushBack(s1, 3);SLPushBack(s1, 4);SLPrint(s1);SLPopBack(s1);SLPrint(s1);//.....SLDestory(s1);}int main()
{SLTest01();return 0;
}
结尾
顺序表代码的实现整体难度不是很大但是要求我们在编写代码的时候要考虑仔细若是有疏忽就很容易出现错误。因为顺序表的内容很多我就将顺序表封装成了两节本节我们讲解的是顺序表的基本内容下一节为大家带来顺序表更高级的内容实现顺序表删除、插入指定位置的数据。谢谢您的浏览
