当前位置:   article > 正文

数据结构——线性表之顺序表的基本操作讲解_线性表顺序结构的基本操作

线性表顺序结构的基本操作

目录

目录

一线性表

1.线性表定义        

2.常见的线性表:

 3.线性表存储结构       

二.顺序表

1.定义:

2.分类:

3.顺序表的初始化

4.顺序表的释放

5.顺序表的数据添加

6.数据的删除

 头部删除:

7.数据的查找——返回该数字的下标位置

 8.在指定位置插入数据

 9.在指定位置删除数据

10.数据的修改:

test.c测试文件代码:

SeqList.c文件代码:

SeqList.h代码:



一线性表

1.线性表定义        

        线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

2.常见的线性表:

顺序表、链表、栈、队列、字符串等

 3.线性表存储结构       

        线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。 

 如图,上述两个就是线性表中两个重要的分类:顺序表和链表。而今天我要说的就是顺序表。


二.顺序表

1.定义:

        用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般采用数组存储。而顺序表就是在数组上完成数据的增删查改等步骤。

2.分类:

顺序表分为静态顺序表和动态顺序表两类:

        A.静态的顺序表:大小固定,只适用于知道要存多少个数据,所以采用使用定长数组进行存储;

  1. #define N 10
  2. typedef int SLDataType;//类型重定义
  3. struct SeqList {
  4. //int a[N];
  5. SLDataType a[N];
  6. int size;//存储数据的个数
  7. };

 注:使用静态顺序并不方便,假如开1000个空间,只用到100个,那么剩下的990个空间被浪费;

        开1000个空间时,要存储1001个数据,会出现不够的情况,所以静态顺序表的使用总是达不到令人满意的结果。


        

        B.动态顺序表:使用动态开辟的数组进行存储,数组的大小随着数据的增加而增加,不会造成浪费,基本上都是有多少用多少;程序的灵活性更高;也不会出现分配不足的问题。

  1. //动态顺序表的创建——malloc、calloc,realloc等动态开辟的空间
  2. typedef int SLDataType;//类型重定义
  3. typedef struct SeqList {
  4. SLDataType* a;//指针
  5. int size;//当前存储的个数
  6. int capacity;//整体容量的大小
  7. }SL;//将动态顺序表的结构体类型简写化为SL

        动态开辟需要用到三个成员:1是指针用于指向动态开辟的堆区空间;2.是当前数组中存储的数据个数;3.是当前数组的最大容量。动态开辟最大的特点是能随时扩容,当存储数据的个数达到数组的最大容量时,表示数组已经满了,这时就可以自动扩容,为下一个数据的存储增加空间!十分方便 所以一般在数据结构中我们常使用动态顺序表。 

 

3.顺序表的初始化

        创建好顺序表的模型后,接下来我来讲一讲顺序表的初始化

        顺序表的初始化就是对刚刚创建好的结构体SL中的成员做数据分配:

在Test.c(这个.c文件主要用于进行测试)中:创建结构体变量s,通过取出变量s的地址作为实参去关联函数形参。

  1. void TestSLInit() {
  2. SL s;
  3. SLInit(&s);//初始化
  4. }
  5. int main(){
  6. TestSLInit();
  7. return 0;
  8. }

在SeqList.c(这个.c文件主要用于进行函数的实现)中 :

  1. //初始化函数
  2. void SLInit(SL* psl) {
  3. assert(psl);//断言库函数(判断指针psl是否为空)
  4. psl-> size = 0;
  5. psl-> capacity = 0;
  6. psl->a = NULL;
  7. }

        注: 在主函数中使用了传址调用,学习C语言的时候,大家都知道传值调用的过程中,形参只是实参的一份临时拷贝,形参的改变不能影响实参。实参是结构体的变量,代表着顺序表,想要对其进行数据的增删改查扽操作,需要传地址才能改变顺序表。

        注2:在初始化中,数据的个数与容量都设为0,而指针a先置为空指针,在之后的增加数据时会改变。

4.顺序表的释放

既然是动态开辟的数组,那么程序结束时就需要手动释放这块内存空间,否则会造成内存泄漏。

        free后,这块空间被交还给操作系统,但指针仍保留着这块空间的地址,因此指针a会变成野指针,很危险,需要手动置为空,此外size和capacity也得重新置为0 。

5.顺序表的数据添加

        创建好顺序表的开始与结束函数后,接下来就要对顺序表进行数据的添加了.

        需要注意的是数据的添加分为头部添加、尾部添加。一般常使用尾部添加方式。

        在数据的添加过程中,需要去检查数组(顺序表),看其容量是否能够允许数据被添加进来!因此我创建了一个独立函数去检查,而检查的条件就是当前存储的个数是否等于容量的上限。若是等于,则还需要看容量是否为0,若为0,则表明是第一次开辟空间;若不为0,则表明是容量满了需要扩容,针对这两种情况,我使用三目操作表达式去编写代码。

  1. // 检查空间,如果满了,进行增容
  2. static void CheckCapacity(SL* psl) {
  3. //1.检查
  4. if (psl->size == psl->capacity) {
  5. int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  6. SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
  7. if (tmp == NULL) {
  8. perror("realloc filed\n");
  9. return -1;
  10. }
  11. psl->a = tmp;
  12. psl->capacity = newcapacity;
  13. }
  14. }

        扩容的时候可以使用malloc、calloc、realloc等3种库函数<stdlib.h>去开辟,我使用的是realloc既可以开辟空间,又可以做扩容操作。

        一个重大结论:动态开辟是系统根据堆区内存空间的空闲位置去开辟的,就是说堆区中哪块空间空闲,就会在那个位置存放,基于此扩容 操作会有三种情况:

         原地扩容的好处就是扩展内存就直接原有内存之后直接追加空间,原来空间的数据不发生变化。


        异地扩容:也就是第一次开辟空间的后面无法再继续扩容,那么系统会自动寻找另一块能够放下扩容后的新地址,那么原有的空间会被系统回收 。


扩容失败表示堆区空间已满,无法继续为其增加空间。 


尾部插入代码:

SLPushBack函数的作用就是,在数组的尾部插入一个个数据,每添加一个数据,就使存储个数+1。

调试结果:


 头部插入代码:

 头部添加的关键在于:需要将所有数据往后挪一个单位,为数组首元素留下一个空位,并且使指针指向首元素位置添加数据。

调试结果:


6.数据的删除

分为头部删除、尾部删除。一般常使用尾部删除方式。

尾部删除:

 调试结果:

 

 尾部的删除相当简单,令size-1即可。


 头部删除:

结果对比: 

 


7.数据的查找——返回该数字的下标位置

代码:

         在查找函数中,我使用了顺序查找的方式,将数组从下标0到最后依次遍历。大家可能会问,顺序遍历的时间复杂度为O(N),用二分查找会不会更好?二分查找算法的时间复杂度虽然是O(log2(N)),比O(N)更好,但使用二分查找的前提是该数列为有序数组,而排序的复杂度就很高了,代价大,所以还是老实用顺序遍历好。

         之前顺序表中剩余的元素为30,1,2,3 ,查找的数字为30,则系统会在顺序表中寻找该数字,并返回该数字的下标位置,若是没找到则返回-1。


 8.在指定位置插入数据

 SLInsert函数的作用:通过在数组下标位置pos前插入元素x。在右图中第一个语句表示在数组的下标位置2前插入数据999;第二个语句表示在数组下标位置0前插入数据666。

该函数的实现原理:

调试结果:


 9.在指定位置删除数据

调试结果:

 函数实现原理:在数组中,使指针指向pos位置处,使用循环,从前往后将 后一个值赋给前一个值。从而将begin指向的数据值被后一个数据值所覆盖,完成删除。


10.数据的修改:

以上就是对顺序表增删查改的基本步骤了,接下来我会发出所有代码:

test.c测试文件代码:

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"SeqList.h"
  3. void TestSLInit() {
  4. SL s;
  5. SLInit(&s);//初始化
  6. //尾部插入
  7. SLPushBack(&s, 1);
  8. SLPushBack(&s, 2);
  9. SLPushBack(&s, 3);
  10. SLPushBack(&s, 4);
  11. SLPushBack(&s, 5);
  12. SLPushBack(&s, 6);
  13. //头部插入
  14. SLPushFront(&s, 30);
  15. SLPushFront(&s, 20);
  16. SLPushFront(&s, 10);
  17. //尾部删除
  18. SLPopBack(&s);//删除数组最后一个元素
  19. SLPopBack(&s);//删除数组最后一个元素
  20. SLPopBack(&s);//删除数组最后一个元素
  21. //头部删除
  22. SLPopFront(&s);//删除数组首元素
  23. SLPopFront(&s);
  24. //查找
  25. /*int ret = SearchSL(&s, 30);
  26. printf("%d\n", ret);*/
  27. //在指定位置插入数据
  28. SLInsert(&s, 2, 999);
  29. SLInsert(&s, 0, 666);
  30. SLprint(&s);
  31. SLDestory(&s);//释放动态空间你重置
  32. }
  33. void TestSLInit2() {
  34. SL s2;
  35. SLInit(&s2);//初始化
  36. //尾部插入
  37. SLPushBack(&s2, 1);
  38. SLPushBack(&s2, 2);
  39. SLPushBack(&s2, 3);
  40. SLPushFront(&s2, 999);
  41. //在指定位置删除数据
  42. SLprint(&s2);
  43. SLErase(&s2, 0);
  44. SLprint(&s2);
  45. SLDestory(&s2);
  46. //可以自己输入想要删除的下标位置代码
  47. /*int x = 0;
  48. scanf("%d", &x);
  49. int pos = SearchSL(&s2, x);
  50. if (pos != -1) {
  51. SLErase(&s2, pos);
  52. }*/
  53. SLprint(&s2);
  54. }
  55. int main() {
  56. //TestSLInit();
  57. TestSLInit2();
  58. return 0;
  59. }

SeqList.c文件代码:

  1. #include"SeqList.h"
  2. //初始化函数
  3. void SLInit(SL* psl) {
  4. assert(psl);
  5. psl-> size = 0;
  6. psl-> capacity = 0;
  7. psl->a = NULL;
  8. }
  9. //销毁动态内存
  10. void SLDestory(SL* psl) {
  11. assert(psl);
  12. free(psl->a);
  13. psl->a = NULL;
  14. psl->size = psl->capacity = 0;
  15. }
  16. // 检查空间,如果满了,进行增容
  17. void CheckCapacity(SL* psl) {
  18. assert(psl);
  19. //1.检查
  20. if (psl->size == psl->capacity) {
  21. int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  22. SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
  23. if (tmp == NULL) {
  24. perror("realloc filed\n");
  25. return;
  26. }
  27. psl->a = tmp;
  28. psl->capacity = newcapacity;
  29. }
  30. }
  31. //尾部插入
  32. void SLPushBack(SL* psl, SLDataType x) {
  33. assert(psl);
  34. //1.检查
  35. CheckCapacity(psl);
  36. //2.在尾部插入数据
  37. psl->a[psl->size] = x;
  38. psl->size++;
  39. }
  40. void SLprint(SL* psl) {
  41. int i = 0;
  42. for (i = 0; i <psl->size; i++) {
  43. printf("%d ", psl->a[i]);
  44. }
  45. printf("\n");
  46. }
  47. //头插
  48. void SLPushFront(SL* psl, SLDataType x) {
  49. assert(psl);
  50. //1.检查
  51. CheckCapacity(psl);
  52. //2.将所有数据往后挪,以便在头部插入数据
  53. int end = psl->size - 1;
  54. while (end >= 0) {
  55. psl->a[end + 1] = psl->a[end];//所有位置往后挪
  56. end--;
  57. }
  58. //3.插入数据
  59. psl->a[0] = x;
  60. psl->size++;
  61. }
  62. //尾部删除
  63. void SLPopBack(SL* psl) {
  64. assert(psl);
  65. //温柔的检查
  66. if (psl->size == 0) {
  67. return;
  68. }
  69. //暴力的检查
  70. //assert(psl->size > 0);//选择其中一种即可
  71. psl->size--;
  72. }
  73. //头部删除
  74. void SLPopFront(SL* psl) {
  75. assert(psl);
  76. //温柔的检查
  77. if (psl->size == 0) {
  78. return;
  79. }
  80. //暴力的检查
  81. //assert(psl->size > 0);//选择其中一种即可
  82. //从前往后(第二个元素的值赋值给第一个元素,第三个元素的
  83. //值赋给第二个,以此类推,直到begin<(psl->Size-1)停止
  84. int begin = 0;
  85. while (begin<psl->size-1) {//size是指向数组最后一个位置的
  86. //下一个位置,所以-1(可以理解为数组下标)
  87. psl->a[begin] =psl->a[begin+1];
  88. begin++;
  89. }
  90. psl->size--;
  91. }
  92. //查找——返回的是该数的下标位置
  93. int SearchSL(SL* psl, SLDataType x) {
  94. assert(psl);
  95. int i = 0;
  96. for (i = 0; i < psl->size; i++) {
  97. if (psl->a[i] == x) {
  98. return i;
  99. }
  100. }
  101. return -1;
  102. }
  103. //指定某一个数组下标位置进行插入数据
  104. void SLInsert(SL* psl, int pos, SLDataType x) {
  105. assert(psl);
  106. assert(pos <= psl->size);
  107. int end = psl->size - 1;
  108. while (end >= pos) {
  109. psl->a[end + 1] = psl->a[end];
  110. end--;
  111. }
  112. psl->a[pos] = x;
  113. psl->size++;
  114. }
  115. //指定某一个数组下标位置删除数据
  116. void SLErase(SL* psl, size_t pos) {
  117. assert(psl);
  118. assert(pos < psl->size);
  119. size_t begin = pos;
  120. while (begin < psl->size - 1)
  121. {
  122. psl->a[begin] = psl->a[begin + 1];
  123. begin++;
  124. }
  125. psl->size--;
  126. }

SeqList.h代码:

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. //静态顺序表的创建——数组(定长数组)大小写死了,只适用于直到要存多少个数据采用
  6. //#define N 10
  7. //typedef int SLDataType;//类型重定义,因为int类型写死了,可以重定义int类型
  8. //struct SeqList {
  9. // //int a[N];
  10. // SLDataType a[N];
  11. // int size;//存储数据的个数
  12. //};
  13. //一般写顺序表都是写动态版本的,静态版本的不怎么用!!!
  14. //动态顺序表的创建——malloc、calloc,realloc等动态开辟的空间
  15. typedef int SLDataType;
  16. typedef struct SeqList {
  17. SLDataType* a;
  18. int size;//当前存储的个数
  19. int capacity;//整体容量的大小
  20. }SL;//将动态顺序表的结构体类型简写化为SL
  21. //初始化函数
  22. void SLInit(SL* psl);
  23. //释放空间
  24. void SLDestory(SL* psl);
  25. //尾部插入——一般用法
  26. void SLPushBack(SL* psl, SLDataType x);
  27. //打印
  28. void SLprint(SL* psl);
  29. //头部插入
  30. void SLPushFront(SL* psl, SLDataType x);
  31. //尾部删除
  32. void SLPopBack(SL* psl);
  33. //头部删除
  34. void SLPopFront(SL* psl);
  35. //查找
  36. int SearchSL(SL* psl, SLDataType x);
  37. //指定某一个数组下标位置进行插入数据
  38. void SLInsert(SL* psl, int pos, SLDataType x);
  39. 指定某一个数组下标位置删除数据
  40. void SLErase(SL* psl, size_t pos);

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/765987
推荐阅读
相关标签
  

闽ICP备14008679号