玩转顺序表理解核心概念 实现增删查改功能阅读本文需要C语言基础掌握指针、结构体、动态内存分配与断言。顺序表概念讲解线性表线性表的定义线性表是最基本、最简单、也是最常用的一种数据结构。线性表*linear list*是数据结构的一种一个线性表是n个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系即除了第一个和最后一个数据元素之外其它数据元素都是首尾相接的注意这句话只适用大部分线性表而不是全部。比如循环链表逻辑层次上也是一种线性表存储层次上属于链式存储但是把最后一个数据元素的尾指针指向了首位结点。定义很抽象简单来说就像是相同类型的数据排成一路纵队不可以出现并排或分叉就像一条直线一样。只要满足逻辑结构是线性的这个条件就可以称其为线性表线性表包括顺序表、链表、栈、队列等。顺序表与数组顺序表的逻辑结构与物理结构顺序表的逻辑结构是线性的顺序表符合线性表的定义所以它的逻辑结构是线性的。顺序表的物理结构也是线性的顺序表的底层是由数组实现的数组是将相同类型的数据按地址从低到高的顺序连续存储在内存上所以数组的物理结构是线性的由此可知顺序表的物理结构也是线性的。数组的缺点顺序表的底层是由数组实现的那为什么不直接使用数组呢因为数组有以下两个缺点。数组大小固定无法改变这个缺点会让数组很不灵活因为你写程序时是没办法预测将来要存储多少数据数组创建的太小会存储不下过多的数据创建的太大会造成空间浪费。无法知晓数组里面存储多少有效数据增删查改操作全都依赖于这个信息在讲解这些具体功能的时候你自然就理解了。顺序表是装修过的数组顺序表就是为了解决数组缺点而诞生的它通过以下两个方式解决。在堆上创建数组以int arr[5] {0};这种方式创建数组本质是在栈上创建数组我们没办法像操作堆一样自由的操作栈这是数组大小无法改变的根本原因所以我们就可以直接在堆上创建数组以达到自由改变数组大小的目的。存储数组的必要信息我们可以将数组的有效数据个数用整型size存储在进行增删查改等操作后实时更新size然后将数组的地址与大小分别用指针arr与整型capacity存储之所以存储数组的地址和大小是因为在堆上创建数组虽然更自由但是也更加操心需要我们自己记住数组的大小与地址后续讲解具体的代码你就会理解为何这么做。顺序表分为静态顺序表与动态顺序表静态顺序表不太常用将不会详细讲解所以本文默认顺序表为动态顺序表。顺序表代码讲解定义顺序表结构体顺序表的三个必要信息分别是arr、size、capacity三个同属顺序表的不同的信息需要用结构体进行储存所以定义结构体代码如下。首先将int重命名为SLTDataType这是为了方便更改存储的数据类型在更改类型时只需更改这行代码中的int即可改变后续所有SLTDataType类型的含义。//存储数据类型---inttypedefintSLTDataType;动态顺序表结构体成员是那三个必要信息这里将struct SeqList重命名为SL是缩短名字方便使用。//动态顺序表typedefstructSeqList{SLTDataType*arr;//顺序表地址intsize;//有效数据个数intcapacity;//空间大小}SL;静态顺序表大小无法改变只需存储定长数组与有效数据个数。//静态顺序表typedefstructSeqList{SLTDataType arr[100];//定长数组intsize;//有效数据个数}SL;顺序表初始化如果在创建结构体变量之后不对它进行初始化那么结构体成员都会是随机值。//初始化顺序表voidSLInit(SL*pa){assert(pa);pa-arrNULL;pa-sizepa-capacity0;return;}assert(pa);是断言防止pa为空指针因为空指针解引用属于未定义行为会出错。pa-arr NULL;将顺序表指针初始化为NULL表示此时并未申请空间。pa-size pa-capacity 0;有效数据个数与空间大小均初始化为0。顺序表扩容扩容函数就是控制顺序表增大的功能函数这里也能体现出顺序表在堆上申请空间的具体方式。//检查并扩容顺序表容量voidSLCheckCapacity(SL*pa){assert(pa);//判断是否增容if(pa-sizepa-capacity){//2倍增容intnewcapacity(pa-capacity0)?4:(pa-capacity*2);SLTDataType*temp(SLTDataType*)realloc(pa-arr,newcapacity*sizeof(SLTDataType));//判断申请是否成功if(tempNULL){perror(realloc fail !);exit(1);}pa-arrtemp;pa-capacitynewcapacity;}return;}if (pa-size pa-capacity)当sizecapacity时顺序表的空间足够无需扩容。当sizecapacity时顺序表空间已满进行扩容操作。int newcapacity (pa-capacity 0) ? 4 : (pa-capacity * 2);频繁的扩容会降低程序的性能所以需要倍数扩容至于进行具体几倍扩容则需要你自己权衡倍数越大扩容的次数就越少但是空间的浪费也更多。如果是首次创建顺序表就直接申请4个单位的空间。SLTDataType* temp (SLTDataType*)realloc(pa-arr, newcapacity * sizeof(SLTDataType));用realloc函数申请空间一定不要用arr存储新地址因为一旦空间申请失败不仅没法扩容还会造成原先地址的丢失。newcapacity并不是指新空间的大小而是指新空间能存储的数据个数所以真正的空间大小是newcapacity * sizeof(SLTDataType)需要乘以单个数据的大小。如果申请失败就直接结束程序。//判断申请是否成功if(tempNULL){perror(realloc fail !);exit(1);}更新结构体里面的信息。pa-arrtemp;pa-capacitynewcapacity;顺序表尾部插入元素顺序表可以通过尾插函数在已有的有效元素序列尾部插入元素。//顺序表尾部插入元素voidSLPushBack(SL*pa,SLTDataType x){assert(pa);//增容SLCheckCapacity(pa);//在尾部插入pa-arr[pa-size]x;return;}assert(pa);断言防止传入空指针。既然是插入元素那一定要进行SLCheckCapacity(pa);扩容操作。pa-arr[pa-size] x;直接在顺序表size下标位置插入元素然后size更新结构体信息。顺序表尾部插入元素的时间复杂度为O(1)。顺序表头部插入元素顺序表可以通过头插函数在已有的有效元素序列的头部插入元素头插操作相较于尾插更复杂。//顺序表头部插入元素voidSLPushFront(SL*pa,SLTDataType x){assert(pa);//增容SLCheckCapacity(pa);//在头部插入for(intipa-size;i0;i--){pa-arr[i]pa-arr[i-1];}pa-arr[0]x;pa-size;return;}assert(pa);断言防止传入空指针。SLCheckCapacity(pa);进行扩容操作。for (int i pa-size; i 0; i--)在头部插入元素不能像尾插一样直接插入需要先将所有元素整体后移一位腾出首元素空间并且一定要先挪后面的元素再挪前面的元素。先挪动前面的元素再挪后面的元素以这种方法移动元素会将所有元素全部被a覆盖掉为了插入一个元素而丢掉几乎所有数据这代价未免有点太大了。先挪动后面的元素再挪前面的元素这才是正确的移动方法最后在首元素位置插入元素即可。pa-arr[0] x;pa-size;更新结构体信息。顺序表头部插入元素的时间复杂度为O(n)。顺序表尾部删除元素尾删的逻辑基本与尾插相同。//顺序表尾部删除元素voidSLPopBack(SL*pa){assert(papa-size);//在尾部删除pa-size--;return;}assert(pa pa-size);防止传入空指针并且要防止顺序表为空空顺序表没法删除数据。直接pa-size--;即可完成删除这是因为删除数据的本质不是把数据销毁而是允许它所在的空间被使用当我们再次插入数据时自然就把被删除的数据覆盖掉了。顺序表尾部删除元素的时间复杂度为O(1)。顺序表头部删除元素同样顺序表头删的逻辑与头插也很像但是有差别不要记混。//顺序表头部删除元素voidSLPopFront(SL*pa){assert(papa-size);//在头部删除for(inti0;ipa-size-1;i){pa-arr[i]pa-arr[i1];}pa-size--;return;}assert(pa pa-size);防止传入空指针并且要防止顺序表为空。for (int i 0; i pa-size - 1; i)在头部删除数据要将所有元素整体向前移动一位和头插不同的是要先挪前面的元素再挪后面的元素。先挪后面的元素再挪前面的元素先挪前面的元素再挪后面的元素头删挪动顺序与头插相反但是原因相同看图可以发现a也并没有被直接销毁而是被覆盖和尾插一样。通过这里可以发现删除数据的本质是允许它所在的空间被再次写入数据而不是将它所在空间的数据直接删除。pa-size--;更新顺序表结构体信息。顺序表头部删除元素的时间复杂度为O(n)。查找顺序表元素它的作用是查找顺序表内是否有我们要找的元素它一般与在顺序表指定位置插入元素功能配合使用。//查找元素返回下标intSLFind(SL*pa,SLTDataType x){assert(pa);//遍历寻找for(inti0;ipa-size;i){if(pa-arr[i]x){returni;}}return-1;}assert(pa);断言防止传入空指针。for (int i 0; i pa-size; i)遍历查找顺序表的所有元素。arr[i]目标元素时直接返回当前元素的下标。遍历所有元素后没有找到目标元素则返回-1代表没找到。查找顺序表元素的时间复杂度为O(n)。顺序表指定位置插入元素它的代码逻辑与头插基本相同。//在指定下标位置插入元素voidSLInsert(SL*pa,intpos,SLTDataType x){assert(pa(pos0pospa-size));//增容SLCheckCapacity(pa);//遍历后移for(intipa-size;ipos;i--){pa-arr[i]pa-arr[i-1];}pa-arr[pos]x;pa-size;return;}assert(pa (pos 0 pos pa-size));防止传入空指针并且要保证pos是顺序表的有效下标这就是为什么查找函数在找不到目标元素的时候返回-1因为查找函数的返回值一般直接作为指插函数的参数进行使用。SLCheckCapacity(pa);对顺序表进行扩容。for (int i pa-size; i pos; i--)和头插一个逻辑只不过空出的不再是首元素位置而是指定位置同样要先挪后面再挪前面如果你看懂了头插与头删的流程图自然就能够理解指插的逻辑。pa-arr[pos] x;pa-size;更新结构体信息。顺序表指定位置插入元素的时间复杂度为O(N)。销毁顺序表顺序表是在堆上申请空间创建的需要我们自己回收空间。//销毁顺序表voidSLDestroy(SL*pa){assert(pa);//销毁free(pa-arr);pa-arrNULL;pa-sizepa-capacity0;return;}assert(pa);防止传入空指针。free(pa-arr);回收顺序表空间。pa-arr NULL;pa-size pa-capacity 0;更新结构体信息。代码练习本文讲解的顺序表代码还有以下功能没有实现//在指定下标后插入元素voidSLInsertAfter(SL*pa,intpos,SLTDataType x);//删除指定下标位置元素voidSLErase(SL*pa,intpos);独立的去实现本文讲解的所有代码并画流程图。本文未讲解的两个函数代码逻辑与前面讲解过的代码逻辑基本相同容易踩的坑前面也有讲解如果你已经学会本文的内容那么这两个功能你就可以独立实现。总结函数名功能时间复杂度SLPushBack顺序表尾部插入元素O(1)SLPushFront顺序表头部插入元素O(n)SLPopBack顺序表尾部删除元素O(1)SLPopFront顺序表头部删除元素O(n)SLFind查找顺序表元素O(n)SLInsert顺序表指定位置插入元素O(n)完整源码已上传至 GitHubSean-Next/c-data-structure-learning
玩转顺序表理解核心概念 实现增删查改功能阅读本文需要C语言基础掌握指针、结构体、动态内存分配与断言。顺序表概念讲解线性表线性表的定义线性表是最基本、最简单、也是最常用的一种数据结构。线性表*linear list*是数据结构的一种一个线性表是n个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系即除了第一个和最后一个数据元素之外其它数据元素都是首尾相接的注意这句话只适用大部分线性表而不是全部。比如循环链表逻辑层次上也是一种线性表存储层次上属于链式存储但是把最后一个数据元素的尾指针指向了首位结点。定义很抽象简单来说就像是相同类型的数据排成一路纵队不可以出现并排或分叉就像一条直线一样。只要满足逻辑结构是线性的这个条件就可以称其为线性表线性表包括顺序表、链表、栈、队列等。顺序表与数组顺序表的逻辑结构与物理结构顺序表的逻辑结构是线性的顺序表符合线性表的定义所以它的逻辑结构是线性的。顺序表的物理结构也是线性的顺序表的底层是由数组实现的数组是将相同类型的数据按地址从低到高的顺序连续存储在内存上所以数组的物理结构是线性的由此可知顺序表的物理结构也是线性的。数组的缺点顺序表的底层是由数组实现的那为什么不直接使用数组呢因为数组有以下两个缺点。数组大小固定无法改变这个缺点会让数组很不灵活因为你写程序时是没办法预测将来要存储多少数据数组创建的太小会存储不下过多的数据创建的太大会造成空间浪费。无法知晓数组里面存储多少有效数据增删查改操作全都依赖于这个信息在讲解这些具体功能的时候你自然就理解了。顺序表是装修过的数组顺序表就是为了解决数组缺点而诞生的它通过以下两个方式解决。在堆上创建数组以int arr[5] {0};这种方式创建数组本质是在栈上创建数组我们没办法像操作堆一样自由的操作栈这是数组大小无法改变的根本原因所以我们就可以直接在堆上创建数组以达到自由改变数组大小的目的。存储数组的必要信息我们可以将数组的有效数据个数用整型size存储在进行增删查改等操作后实时更新size然后将数组的地址与大小分别用指针arr与整型capacity存储之所以存储数组的地址和大小是因为在堆上创建数组虽然更自由但是也更加操心需要我们自己记住数组的大小与地址后续讲解具体的代码你就会理解为何这么做。顺序表分为静态顺序表与动态顺序表静态顺序表不太常用将不会详细讲解所以本文默认顺序表为动态顺序表。顺序表代码讲解定义顺序表结构体顺序表的三个必要信息分别是arr、size、capacity三个同属顺序表的不同的信息需要用结构体进行储存所以定义结构体代码如下。首先将int重命名为SLTDataType这是为了方便更改存储的数据类型在更改类型时只需更改这行代码中的int即可改变后续所有SLTDataType类型的含义。//存储数据类型---inttypedefintSLTDataType;动态顺序表结构体成员是那三个必要信息这里将struct SeqList重命名为SL是缩短名字方便使用。//动态顺序表typedefstructSeqList{SLTDataType*arr;//顺序表地址intsize;//有效数据个数intcapacity;//空间大小}SL;静态顺序表大小无法改变只需存储定长数组与有效数据个数。//静态顺序表typedefstructSeqList{SLTDataType arr[100];//定长数组intsize;//有效数据个数}SL;顺序表初始化如果在创建结构体变量之后不对它进行初始化那么结构体成员都会是随机值。//初始化顺序表voidSLInit(SL*pa){assert(pa);pa-arrNULL;pa-sizepa-capacity0;return;}assert(pa);是断言防止pa为空指针因为空指针解引用属于未定义行为会出错。pa-arr NULL;将顺序表指针初始化为NULL表示此时并未申请空间。pa-size pa-capacity 0;有效数据个数与空间大小均初始化为0。顺序表扩容扩容函数就是控制顺序表增大的功能函数这里也能体现出顺序表在堆上申请空间的具体方式。//检查并扩容顺序表容量voidSLCheckCapacity(SL*pa){assert(pa);//判断是否增容if(pa-sizepa-capacity){//2倍增容intnewcapacity(pa-capacity0)?4:(pa-capacity*2);SLTDataType*temp(SLTDataType*)realloc(pa-arr,newcapacity*sizeof(SLTDataType));//判断申请是否成功if(tempNULL){perror(realloc fail !);exit(1);}pa-arrtemp;pa-capacitynewcapacity;}return;}if (pa-size pa-capacity)当sizecapacity时顺序表的空间足够无需扩容。当sizecapacity时顺序表空间已满进行扩容操作。int newcapacity (pa-capacity 0) ? 4 : (pa-capacity * 2);频繁的扩容会降低程序的性能所以需要倍数扩容至于进行具体几倍扩容则需要你自己权衡倍数越大扩容的次数就越少但是空间的浪费也更多。如果是首次创建顺序表就直接申请4个单位的空间。SLTDataType* temp (SLTDataType*)realloc(pa-arr, newcapacity * sizeof(SLTDataType));用realloc函数申请空间一定不要用arr存储新地址因为一旦空间申请失败不仅没法扩容还会造成原先地址的丢失。newcapacity并不是指新空间的大小而是指新空间能存储的数据个数所以真正的空间大小是newcapacity * sizeof(SLTDataType)需要乘以单个数据的大小。如果申请失败就直接结束程序。//判断申请是否成功if(tempNULL){perror(realloc fail !);exit(1);}更新结构体里面的信息。pa-arrtemp;pa-capacitynewcapacity;顺序表尾部插入元素顺序表可以通过尾插函数在已有的有效元素序列尾部插入元素。//顺序表尾部插入元素voidSLPushBack(SL*pa,SLTDataType x){assert(pa);//增容SLCheckCapacity(pa);//在尾部插入pa-arr[pa-size]x;return;}assert(pa);断言防止传入空指针。既然是插入元素那一定要进行SLCheckCapacity(pa);扩容操作。pa-arr[pa-size] x;直接在顺序表size下标位置插入元素然后size更新结构体信息。顺序表尾部插入元素的时间复杂度为O(1)。顺序表头部插入元素顺序表可以通过头插函数在已有的有效元素序列的头部插入元素头插操作相较于尾插更复杂。//顺序表头部插入元素voidSLPushFront(SL*pa,SLTDataType x){assert(pa);//增容SLCheckCapacity(pa);//在头部插入for(intipa-size;i0;i--){pa-arr[i]pa-arr[i-1];}pa-arr[0]x;pa-size;return;}assert(pa);断言防止传入空指针。SLCheckCapacity(pa);进行扩容操作。for (int i pa-size; i 0; i--)在头部插入元素不能像尾插一样直接插入需要先将所有元素整体后移一位腾出首元素空间并且一定要先挪后面的元素再挪前面的元素。先挪动前面的元素再挪后面的元素以这种方法移动元素会将所有元素全部被a覆盖掉为了插入一个元素而丢掉几乎所有数据这代价未免有点太大了。先挪动后面的元素再挪前面的元素这才是正确的移动方法最后在首元素位置插入元素即可。pa-arr[0] x;pa-size;更新结构体信息。顺序表头部插入元素的时间复杂度为O(n)。顺序表尾部删除元素尾删的逻辑基本与尾插相同。//顺序表尾部删除元素voidSLPopBack(SL*pa){assert(papa-size);//在尾部删除pa-size--;return;}assert(pa pa-size);防止传入空指针并且要防止顺序表为空空顺序表没法删除数据。直接pa-size--;即可完成删除这是因为删除数据的本质不是把数据销毁而是允许它所在的空间被使用当我们再次插入数据时自然就把被删除的数据覆盖掉了。顺序表尾部删除元素的时间复杂度为O(1)。顺序表头部删除元素同样顺序表头删的逻辑与头插也很像但是有差别不要记混。//顺序表头部删除元素voidSLPopFront(SL*pa){assert(papa-size);//在头部删除for(inti0;ipa-size-1;i){pa-arr[i]pa-arr[i1];}pa-size--;return;}assert(pa pa-size);防止传入空指针并且要防止顺序表为空。for (int i 0; i pa-size - 1; i)在头部删除数据要将所有元素整体向前移动一位和头插不同的是要先挪前面的元素再挪后面的元素。先挪后面的元素再挪前面的元素先挪前面的元素再挪后面的元素头删挪动顺序与头插相反但是原因相同看图可以发现a也并没有被直接销毁而是被覆盖和尾插一样。通过这里可以发现删除数据的本质是允许它所在的空间被再次写入数据而不是将它所在空间的数据直接删除。pa-size--;更新顺序表结构体信息。顺序表头部删除元素的时间复杂度为O(n)。查找顺序表元素它的作用是查找顺序表内是否有我们要找的元素它一般与在顺序表指定位置插入元素功能配合使用。//查找元素返回下标intSLFind(SL*pa,SLTDataType x){assert(pa);//遍历寻找for(inti0;ipa-size;i){if(pa-arr[i]x){returni;}}return-1;}assert(pa);断言防止传入空指针。for (int i 0; i pa-size; i)遍历查找顺序表的所有元素。arr[i]目标元素时直接返回当前元素的下标。遍历所有元素后没有找到目标元素则返回-1代表没找到。查找顺序表元素的时间复杂度为O(n)。顺序表指定位置插入元素它的代码逻辑与头插基本相同。//在指定下标位置插入元素voidSLInsert(SL*pa,intpos,SLTDataType x){assert(pa(pos0pospa-size));//增容SLCheckCapacity(pa);//遍历后移for(intipa-size;ipos;i--){pa-arr[i]pa-arr[i-1];}pa-arr[pos]x;pa-size;return;}assert(pa (pos 0 pos pa-size));防止传入空指针并且要保证pos是顺序表的有效下标这就是为什么查找函数在找不到目标元素的时候返回-1因为查找函数的返回值一般直接作为指插函数的参数进行使用。SLCheckCapacity(pa);对顺序表进行扩容。for (int i pa-size; i pos; i--)和头插一个逻辑只不过空出的不再是首元素位置而是指定位置同样要先挪后面再挪前面如果你看懂了头插与头删的流程图自然就能够理解指插的逻辑。pa-arr[pos] x;pa-size;更新结构体信息。顺序表指定位置插入元素的时间复杂度为O(N)。销毁顺序表顺序表是在堆上申请空间创建的需要我们自己回收空间。//销毁顺序表voidSLDestroy(SL*pa){assert(pa);//销毁free(pa-arr);pa-arrNULL;pa-sizepa-capacity0;return;}assert(pa);防止传入空指针。free(pa-arr);回收顺序表空间。pa-arr NULL;pa-size pa-capacity 0;更新结构体信息。代码练习本文讲解的顺序表代码还有以下功能没有实现//在指定下标后插入元素voidSLInsertAfter(SL*pa,intpos,SLTDataType x);//删除指定下标位置元素voidSLErase(SL*pa,intpos);独立的去实现本文讲解的所有代码并画流程图。本文未讲解的两个函数代码逻辑与前面讲解过的代码逻辑基本相同容易踩的坑前面也有讲解如果你已经学会本文的内容那么这两个功能你就可以独立实现。总结函数名功能时间复杂度SLPushBack顺序表尾部插入元素O(1)SLPushFront顺序表头部插入元素O(n)SLPopBack顺序表尾部删除元素O(1)SLPopFront顺序表头部删除元素O(n)SLFind查找顺序表元素O(n)SLInsert顺序表指定位置插入元素O(n)完整源码已上传至 GitHubSean-Next/c-data-structure-learning
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
