【数据结构-初阶】详解线性表(1)---顺序表
🎈主页传送门:良木生香
🔥个人专栏:《C语言》 《数据结构-初阶》 《程序设计》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
上期回顾:上一篇文章中(有兴趣的小伙伴可以看看上一篇文章:【数据结构-初阶】详解算法复杂度：时间与空间复杂度),我们已经学习了判断一个算法程序好与坏的方法:时间复杂度与空间复杂度,那么现在我们继续向下面学习数据结构的新知识:线性表中的顺序表
在介绍顺序表之前,我们先来了解线性表的概念
1.线性表
线性表(liner list)是由n个具有相同特性的数据元素组成的有限序列,其在生活中的运用非常广泛,常见的线性表有:顺序表,链表,栈,队列、字符串......线性表在逻辑上是连续的,但是在物理上不一定连续,线性表在物理上进行存储时,通常以数组或者链表结构的形式进行存储.
下面我们就来看看线性表之一的顺序表~~~
2.顺序表
2.1.顺序表的概念
顺序表使用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组进行存储.言外之意就是,顺序表的底层是数组.
既然都说了顺序表的底层是数组,那么顺序表和数组的区别又是什么呢?直接用数组不就行了吗?这是因为:顺序表的底层是数组,对数组进行了封装,实现了数组具有增删查改的功能,使得我们在对数据进行操作时更加高效.我们可以通过下面这张图进行深入理解顺序表与数组的关系:
通过这张图,相信大家对顺序表与数组的关系就有所了解了吧,那么下面我们就正式进入到顺序表的学习中
2.2顺序表的分类
顺序表一般被我们分成两类,一类是静态顺序表,另一类是动态顺序表
2.2.1静态顺序表
静态顺序表从名字还是那个就不难猜出,这类顺序表是的长度是相对固定的,使用的是定长数进行元素的存储,下面是静态顺序表的结构:
typedef int Elemtype; #define N 10 typedef struct Sqlist { Elemtype arr[N]; //使用的是定长数组 int length; //这是记录当前数组中的有效数据个数 }Sqlist; 静态顺序表的开发与维护成本极低,但是有一个致命的缺陷就是,空间值N给小了不够用,大了浪费空间,不能实现"想要多少给多少"的功能,那么下面我们就来介绍他的孪生兄弟:动态顺序表
2.2.2动态顺序表
动态顺序表,顾名思义就是是可以实现内存的动态放缩,下面是动态顺序表的基本结构内容:
typedef int Elmetype; typedef struct Sqlist { Elemtype* data; //这里其实是数组(因为数组名就是数组首地址) int length; //当前顺序表中的有效元素个数 int size; //当前顺序表的总长度 }Sqlist;这样一来,对于动态顺序表而言,我们就能实现"想要多少给多少"的功能需求了,不会因为数组的固定长度而担忧了.
既然对明白了顺序表的基本结构,那我们现在就来对顺序表进行实现吧~~~
2.3顺序表的实现
在实现顺序表之前,我们要先将头文件写好:
#define _CRT_SECURE_NO_WARNINGS 520 #include<stdio.h> #include<stdlib.h> //为了使用malloc、realloc函数 #include<assert.h> //为了对指针进行断言操作 #include<windows.h> //为了使用Slepp()函数,纯属个人喜好 #define INIT_SIZE 100 //预分配空间 #define INSERT_SIZE 200 //空间不够时要增加的空间 //现在将整形变量重命名为 typedef int Elemtype; //为了便于以后修改数据类型 在对某个数据结构进行实现之前,我们都可以围绕四个大方向进行操作:增、删、查、改
2.3.1顺序表的初始化
不管对哪个数据结构,在进行操作之前都要记得对其进初始化哟~
void Init_Sqlist(Sqlist* pSqlist) { //为顺序表申请一个空间 Elemtype* data = (Elemtype*)malloc(INIT_SIZE * sizeof(int)); if (data == NULL) { printf("空间申请失败,同时顺序表初始化失败!\n"); return; } pSqlist->data = NULL; pSqlist->length = 0; pSqlist->size += INIT_SIZE; } 初始化是对顺序表结构当中的三个结构元素进行初始化:
1.为data数组申请一块事先预定好的空间大小,将data指针指向这块空间;
2.将表中的元素个数置为0;
3.将表长设置为预先设定好的长度INIT_SIZE
2.3.2顺序表的插入操作
在顺序表中，对于插入操作我们有三种类型：头部插入，尾部插入，指定位置插入
2.3.2.1头部插入
头部插入操作，实现的是一个陷进去的元素排在最后，最后进去的元素排在第一个的功能,可以通过下面的步骤进行实现:
1.先对传进来的结构体指针进行判空(这是一个重要的操作,基本上每个操作之前都会用到,所以后面都是默认进行此操作)
2.判断当前顺序表的有效元素个数是否超过或者等于表长,如果是,那就重新申请空间
3.将当前顺序表中的元素全部向后移动一位,为表头提供容纳下一个数据的位置
4.将表头赋值上新的元素,记得将元素个数length+1
下面是具体的代码:
void Push_Front(Sqlist* pSqlist,Elemtype num) { //想要在头部插入数据2,就要先判断这个顺序表现在是否溢出: //如果溢出,那就扩容 assert(pSqlist); if (pSqlist->length >= pSqlist->size) { Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype)); if (newbase == NULL) { printf("新空间申请失败,无法进行头部操作...\n"); return; } pSqlist->data = newbase; pSqlist->size = INSERT_SIZE; } for (int i = pSqlist->length-1; i >= 0; i--) { *(pSqlist->data + i + 1) = *(pSqlist->data + i); } *(pSqlist->data+0) = num; pSqlist->length++; } 这里要注意的是,我们在向后移动元素的时候,习惯上从最后一个元素开始,如果从第一个元素开始的话,会将后面的元素覆盖:
2.3.2.2尾部插入
尾部插入相对于头部插入就简单了许多,只需要在顺序表的最尾部进行插入即可,可按照下面的步骤进行,详细代码如下:
//现在是尾部的插入 void Push_Back(Sqlist* pSqlist,Elemtype num) { //依旧判断 assert(pSqlist); if (pSqlist->length >= pSqlist->size) { Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype)); if (newbase == NULL) { printf("空间申请失败,无法进行尾部操作...\n"); return; } pSqlist->data = newbase; pSqlist->size += INSERT_SIZE; } *(pSqlist->data + pSqlist->length) = num; pSqlist->length++; //一定要记得将顺序表中元素的个数进行+1操作,不然后面的操作会出问题!! } 2.3.2.3指定位置pos插入
指定位置其实就相当于高级一点的头部插入,步骤与头部插入差不多,只不过是将头部的下标改成pos值而已,这里直接上代码
void Push_pos(Sqlist* pSqlist, Elemtype num,int pos) { assert(pSqlist); //先检查pos值: if (pos<0 || pos > pSqlist->length) { printf("pos值不合法...\n"); return; } //再检查是否溢出 if (pSqlist->length >= pSqlist->size) { Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype)); if (newbase == NULL) { printf("申请空间失败,无法进行pos位置插入的相关操作...\n"); return; } } //将pos位置后面的元素向后面移动 for (int i = pSqlist->length - 1; i >= pos; i--) { *(pSqlist->data + i + 1) = *(pSqlist->data + i); } *(pSqlist->data + pos) = num; pSqlist->length++; }插入讲完了,那我们现在来讲讲删除操作
2.3.3顺序表的删除操作
删除操作与插入操作一样,也分为头部删除,尾部删除,指定位置pos删除
2.3.3.1头部删除
头部删除,不用想的太复杂,我们只需要将后面的数据元素向前移动一位,把第一个数据元素覆盖掉就行,再将有效数据个数进行-1操作即可,下面是代码:
void Pop_Front(Sqlist* pSqlist) { assert(pSqlist); for (int i = 0; i < pSqlist->length; i++) { *(pSqlist->data + i) = *(pSqlist->data + i + 1); } pSqlist->length--; }覆盖操作的话我们可以从第一个元素开始,将后面的数据元素往前"拉".
2.3.3.2尾部删除
尾部删除比头部删除更加简单,因为pSqlist->length记录的是顺序表中有效的元素个数,我们只用将这个变量-1就行,不需要过多的操作:
void Pop_Back(Sqlist* pSqlist) { pSqlist->length--; } 这样我们就完成了尾部删除的操作
2.3.3.3指定位置pos删除
指定位置pos删除与头部删除相似,是将pos位置之后的数据元素全部向前移动一位,再将pSqlist->length-1即可
//现在是pos位置删除 void Pop_pos(Sqlist* pSqlist, int pos) { assert(pSqlist); for (int i = pos; i < pSqlist->length; i++) { *(pSqlist->data + i-1) = *(pSqlist->data + i); } pSqlist->length--; }在这里我们为了与现实逻辑一样,我们就认为输入的pos是从1开始,但实际上在顺序表中,是从0开始,所以在这里我们要将pos-1,让下标逻辑与顺序表中相同
2.3.4顺序表的查找
想要在顺序表中实现查找某个元素的功能,我们常用的就是遍历,当然,如果这个顺序表是有序的话,那我们可以使用二分查找法,这样会快很多,先买你是普通遍历查找的代码:
//现在是查找元素 void Search_elem(Sqlist* pSqlist,Elemtype num) { int flag = 0; for (int i = 0; i < pSqlist->length; i++) { if (*(pSqlist->data + i) == num) { printf("找到了\n"); flag = 1; break; } } if(flag ==0) { printf("找不到哦\n"); } } 想要输出这个元素在顺序表中的位置,只用将i的值一起输出即可
2.3.5顺序表的修改
我们来到了最后一个操作---修改,对于这个操作我们要传入你想要修改的位置pos以及修改之后的数据值,要先判断pos值是否合理,再将pos位置的值直接修改即可,代码如下:
//现在是修改元素 void Change_num(Sqlist* pSqlist,Elemtype num,int pos) { assert(pSqlist); if (pos<0 || pos>pSqlist->length) { printf("pos不合法,无法查找\n"); return; } *(pSqlist->data + pos) = num; Sleep(1000); printf("pos位置的值已经修改成%d\n",num); Sleep(2000); }2.3.6顺序表的打印
打印顺序表,我们只用将顺序表进行遍历,输出每个元素的值即可
//现在是打印顺序表函数 void my_printf(Sqlist* pSqlist) { assert(pSqlist); for (int i = 0; i < pSqlist->length; i++) { printf("%d ", *(pSqlist->data + i)); } }2.3.7顺序表的销毁操作
在进行完一系列操作之后,我们要将顺序表手动进行销毁,不要让他一直占用内存空间.我们只用将指向数组的指针data置为空即可:
void Destory_Sqlist(Sqlist* pSqlist) { assert(pSqlist); free(pSqlist->data); pSqlist->data = NULL; }以上就是实现顺序表基本功能的全部代码了,但还是缺少主函数,下面我就进行个汇总吧,有兴趣的小伙伴可以看看,嘿嘿~~~
3.代码总和
#define _CRT_SECURE_NO_WARNINGS 520 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<windows.h> #define INIT_SIZE 100 #define INSERT_SIZE 200 //现在将整形变量重命名为 typedef int Elemtype; //现在定义顺序表结构体 typedef struct SqList { Elemtype* data; int length; int size; }Sqlist; //现在对顺序表进行初始化: void Init_Sqlist(Sqlist* pSqlist) { //为顺序表申请一个空间 Elemtype* data = (Elemtype*)malloc(INIT_SIZE * sizeof(int)); if (data == NULL) { printf("空间申请失败,同时顺序表初始化失败!\n"); return; } pSqlist->data = NULL; pSqlist->length = 0; pSqlist->size += INIT_SIZE; } //对顺序表有以下操作:插入,删除,查找,修改 //插入:头插,尾插,pos位置 //删除:头删,尾删,pos位置 //查找: //修改 //现在对顺序表进行增加操作:头插 void Push_Front(Sqlist* pSqlist,Elemtype num) { //想要在头部插入数据2,就要先判断这个顺序表现在是否溢出: //如果溢出,那就扩容 assert(pSqlist); if (pSqlist->length >= pSqlist->size) { Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype)); if (newbase == NULL) { printf("新空间申请失败,无法进行头部操作...\n"); return; } pSqlist->data = newbase; pSqlist->size = INSERT_SIZE; } for (int i = pSqlist->length-1; i >= 0; i--) { *(pSqlist->data + i + 1) = *(pSqlist->data + i); } *(pSqlist->data+0) = num; pSqlist->length++; } //现在是尾部的插入 void Push_Back(Sqlist* pSqlist,Elemtype num) { //依旧判断 assert(pSqlist); if (pSqlist->length >= pSqlist->size) { Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype)); if (newbase == NULL) { printf("空间申请失败,无法进行尾部操作...\n"); return; } pSqlist->data = newbase; pSqlist->size += INSERT_SIZE; } *(pSqlist->data + pSqlist->length) = num; pSqlist->length++; } //现在是pos位置的插入: void Push_pos(Sqlist* pSqlist, Elemtype num,int pos) { assert(pSqlist); //先检查pos值: if (pos<0 || pos > pSqlist->length) { printf("pos值不合法...\n"); return; } //再检查是否溢出 if (pSqlist->length >= pSqlist->size) { Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype)); if (newbase == NULL) { printf("申请空间失败,无法进行pos位置插入的相关操作...\n"); return; } } //将pos位置后面的元素向后面移动 for (int i = pSqlist->length - 1; i >= pos; i--) { *(pSqlist->data + i + 1) = *(pSqlist->data + i); } *(pSqlist->data + pos) = num; pSqlist->length++; } //现在是删除操作:头删 void Pop_Front(Sqlist* pSqlist) { assert(pSqlist); for (int i = 0; i < pSqlist->length; i++) { *(pSqlist->data + i) = *(pSqlist->data + i + 1); } pSqlist->length--; } //现在是尾删 void Pop_Back(Sqlist* pSqlist) { pSqlist->length--; } //现在是pos位置删除 void Pop_pos(Sqlist* pSqlist, int pos) { assert(pSqlist); for (int i = pos; i < pSqlist->length; i++) { *(pSqlist->data + i-1) = *(pSqlist->data + i); } pSqlist->length--; } //现在是查找元素 void Search_elem(Sqlist* pSqlist,Elemtype num) { int flag = 0; for (int i = 0; i < pSqlist->length; i++) { if (*(pSqlist->data + i) == num) { printf("找到了\n"); flag = 1; break; } } if(flag ==0) { printf("找不到哦\n"); } } //现在是修改元素 void Change_num(Sqlist* pSqlist,Elemtype num,int pos) { assert(pSqlist); if (pos<0 || pos>pSqlist->length) { printf("pos不合法,无法查找\n"); return; } *(pSqlist->data + pos) = num; Sleep(1000); printf("pos位置的值已经修改成%d\n",num); Sleep(2000); } //现在是打印顺序表函数 void my_printf(Sqlist* pSqlist) { assert(pSqlist); for (int i = 0; i < pSqlist->length; i++) { printf("%d ", *(pSqlist->data + i)); } } void Destory_Sqlist(Sqlist* pSqlist) { assert(pSqlist); free(pSqlist->data); pSqlist->data = NULL; } //现在是打印菜单函数 void printf_menu() { printf("=============================\n"); printf("你可以进行以下操作:\n"); printf("1.头插 2.尾插 3.pos位置插\n"); printf("4.头删 5.尾删 6.pos位置删\n"); printf("7.查找元素 8.修改元素\n"); printf("=============================\n"); printf("\n"); } //现在是主函数 int main() { Sqlist L; Sqlist* pSqlist = &L; Init_Sqlist(pSqlist); int choose = 0; do { system("cls"); printf_menu(); printf("当前的顺序表为:\n"); my_printf(pSqlist); printf("\n"); printf("请输入你的选择(按-1结束程序):\n"); //int choose = 0; scanf("%d", &choose); if (choose == -1) { break; } switch(choose) { case 1: { printf("请输入你想输入的元素个数:\n"); int num_num = 0; scanf("%d", &num_num); printf("请输入你想要插入的元素:\n"); Elemtype num; for (int i = 0; i < num_num; i++) { scanf("%d", &num); Push_Front(pSqlist, num); } Sleep(1000); printf("插入成功!!!\n"); Sleep(2000); break; } case 2: { printf("请输入你想输入的元素个数:\n"); int num_num = 0; scanf("%d", &num_num); printf("请输入你想要插入的元素:\n"); Elemtype num; for (int i = 0; i < num_num; i++) { scanf("%d", &num); Push_Back(pSqlist, num); } Sleep(1000); printf("插入成功!!!\n"); Sleep(2000); break; } case 3:{ printf("请输入你想要输入的位置:\n"); int pos = 0; scanf("%d", &pos); printf("请输入你想要输入的元素:\n"); Elemtype num = 0; scanf("%d", &num); Push_pos(pSqlist, num, pos); Sleep(1000); printf("插入成功!!!\n"); Sleep(2000); break; } case 4: { Pop_Front(pSqlist); Sleep(1000); printf("删除成功!!!\n"); Sleep(2000); break; } case 5: { Pop_Back(pSqlist); Sleep(1000); printf("删除成功!!!\n"); Sleep(2000); break; } case 6: { printf("请输入你想要删除的位置:\n"); int pos = 0; scanf("%d", &pos); Pop_pos(pSqlist, pos); Sleep(1000); printf("删除成功!!!\n"); Sleep(2000); break; } case 7: { printf("请输入你想要查找的元素:\n"); Elemtype num; scanf('%d', &num); Search_elem(pSqlist, num); Sleep(1000); printf("查找完成!!!\n"); Sleep(2000); break; } case 8: { printf("请输入你想要修改的位置:\n"); int pos = 0; scanf("%d", &pos); printf("请输入你想要修改成的元素:\n"); Elemtype num = 0; scanf("%d", &num); Change_num(pSqlist, num, pos); Sleep(1000); printf("修改成功!!!\n"); Sleep(2000); break; } default: { printf("choose的值不合法,请重新输入!!!\n"); break; } } }while (choose != -1); //最后释放内存 Destory_Sqlist(pSqlist); return 0; }以上就是我对线性表之一的顺序表的全部分享内容了,有不对的地方希望大佬们指出来~~~
文章是自己写的哈，有啥描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读。
