devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

《数据结构与算法》顺序表专题

作者：黑客灵魂 | 2024-08-14 10:35:05

赞

踩

《数据结构与算法》顺序表专题

必备基础知识：结构体、指针（一级指针、二级指针、指针传参）、结构体指针、动态内存管理

数据结构的相关概念

1 什么是数据结构

概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在⼀种或多种特定关系
的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么⽅式构成，以及数据元素之间呈现的结构。

总结：
1）能够存储数据（如顺序表、链表等结构）
2）存储的数据能够⽅便查找

eg：有两个牧场，A牧场是放养的羊，B牧场是每只羊都有各自的号码的羊，如果我们想找到叫“肖恩”的羊，在A牧场就无法快速的找到，而B牧场只需要找到“肖恩”的号码即可快速找到它。

顺序表

1 顺序表的概念及结构

1.1线性表

线性表（ linear list ）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的据结构，常见的线性表：顺序表、链表、栈、队列、字符串...                                                       
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
案例：蔬菜分为绿叶类、⽠类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合。

1.2 顺序表的分类

  ·  顺序表和数组的区别

    ·  顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接口

       举个例子

9afeb0d73f4e4eb89fab1b64eb5e38d9.png

   ·  顺序表分类

    ·  静态顺序表

  1. #define N 100
  2. typedef int SLDataType//等效替换int，可以实现一键替换想要的数据类型
  3.  
  4. struct SeqList
  5. {
  6.   SLDataType a[N];//数组的长度即空间的大小
  7.   int size;//有效数据个数
  8. }；

       静态顺序表的缺陷：给定的数组长度，若不够就会导致后续数据的保存失败（导致数据丢失，引发严重技术事故），但如果给多了就会导致空间的大量浪费。

    ·  动态顺序表（可增容）

  1. typedef int SLDataType;
  2.  
  3. typedef struct SeqList
  4. {
  5.   SLDataType* arr;//存储数据的底层结构
  6.   int capacity;//记录顺序表的空间大小
  7.   int size;//记录顺序表当前有效的数据个数
  8. }SL;
  9.  
  10. //typedef struct SeqList SL; //与以上代码相同的去定义SeqList结构体变量SL

 

2 动态顺序表的实现

SeqList.h  定义顺序表的结构，顺序表要实现的接口/方法

SeqList.c  具体实现顺序表里定义的接口/方法

test.c  测试动作：测试顺序表

2.1 初始化

错误示范

SeqList.h

void SLInit(SL s1);

 SeqList.c

  1. #include "SeqList.h"
  2.  
  3. void SLInit(SL* ps)
  4. {
  5.   s.arr = NULL;
  6.   s.size = s.capacity = 0;
  7. }

test.c

  1. #include "SeqList.h"
  2.  
  3. void slTest01()
  4. {
  5.   SL s1;
  6.   SLInit(s1);
  7. }
  8.  
  9. int main()
  10. {
  11.   s1Test01();
  12.   return 0;
  13. }

 错误：这里传的不是地址而是传的sl的值过去给s，形参只是实参的值的零食拷贝，而并不是sl本身，这样程序在运行时就会报错“使用了未初始化的局部变量sl”。

正确示范

SeqList.h

  1. //初始化
  2. void SLInit(SL* ps);

SeqList.c

  1. #include "SeqList.h"
  2.  
  3. void SLInit(SL* ps)
  4. {
  5.   ps->arr = NULL;
  6.   ps->size = ps->capacity = 0;
  7. }

test.c

  1. #include "SeqList.h"
  2.  
  3. void slTest01()
  4. {
  5.   SL s1;
  6.   SLInit(&s1);
  7. }
  8.  
  9. int main()
  10. {
  11.   s1Test01();
  12.   return 0;
  13. }

2.2 扩容

SeqList.h

void SLCheckCapacity(SL* ps);

SeqList.c

  1. void SLCheckCapacity(SL* ps)
  2. {
  3.   if(ps=>size == ps->capacity)
  4.   {
  5.     int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  6.     //判断capacity是否为零，因为初始化时capacity为零，如果不为零则扩容两倍
  7.     SLDataType* tmp = (SLDataType*)realloc(ps=>arr, newCapacity * sizeof(SLDataType));
  8.     //注意newCapacity的单位，要乘上数据类型的大小
  9.     //设一个零时变量tmp是为了防止realloc开辟空间失败导致地址丢失
  10.     if(tmp == NULL)
  11.     {
  12.       perror("realloc fail!");
  13.       exit(1);
  14.     }
  15.     //扩容成功
  16.     ps->arr = tmp;
  17.     ps->capacity = newCapacity;
  18.   }
  19. }

2.3 打印

SeqList.h

void SLPrint(SL* ps);  //这里可以传值也可以传地址,这里传地址是为了保持接口一致性

SeqList.c

  1. void SLPrint(SL* ps)
  2. {
  3.   for(int i = 0; i < ps->size; i++)
  4.   {
  5.     printf("%d", ps->arr[i]);
  6.   }
  7.   printf("\n");
  8. }

2.4 尾插

插入数据时很可能出现两种情况

  • 空间不够 -- 扩容再插入
  • 空间足够 -- 直接插入

SeqList.h

void SLPushBack(SL* ps, SLDataType x);

SeqList.c

  1. void SLPushBack(SL* ps, SLDataType x)
  2. {
  3.   //为了防止传的地址为NULL
  4.   //assert--粗暴的解决方式,如果等于NULL或者判断为假就会报错,程序无法继续运行下去
  5.   assert(ps);
  6.   //assert(ps != NULL);//等同于上一行
  7.   
  8.   //if判断--温柔的解决方式,如果等于NULL就就直接跳过而不插入
  9.   //if(ps == NULL)
  10.   //{
  11.   //  return;
  12.   //}
  13.   
  14.   //空间不够,扩容
  15.   SLCheckCapacity(ps);
  16.   
  17.   //空间足够,直接插入
  18.   ps->arr[ps->size++] = x;
  19. }

test.c

  1. //测试尾插
  2. SLPushBack(&sl, 1);
  3. SLPushBack(&sl, 2);
  4. SLPushBack(&sl, 3);
  5. SLPushBack(&sl, 4);
  6. SLPrint(&sl);
  7. SLPushBack(&sl, 5);
  8. SLPrint(&sl);

输出结果为

  1. 1 2 3 4
  2. 1 2 3 4 5

2.5 头插

SeqList.h

void SLPushFront(SL* ps, SLDataType x);

SeqList.c

  1. void SLPushFront(SL* ps, SLDataType x)
  2. {
  3.   assert(ps);
  4.  
  5.   //判断是否扩容
  6.   SLCheckCapacity(ps);
  7.  
  8.   //旧的数据往后挪一位
  9.   for(int i = ps->size; i > 0; i--) //i最后值为1
  10.   {
  11.     ps->arr[i] = ps->arr[i-1];  //最后一个循环为 ps->arr[1] = ps->arr[0]
  12.   }
  13.   ps->arr[0] = x;
  14.   ps->size++;
  15. }

test.c

  1. //测试头插
  2. SLPushBack(&sl, 1);
  3. SLPushBack(&sl, 2);
  4. SLPushBack(&sl, 3);
  5. SLPushBack(&sl, 4);
  6. SLPrint(&sl);
  7.  
  8. SLPuchFront(&sl, 5);
  9. SLPuchFront(&sl, 6);
  10. SLPuchFront(&sl, 7);
  11. SLPrint(&sl);

输出结果为

  1. 1 2 3 4
  2. 7 6 5 1 2 3 4

2.6 尾删

SeqList.h

void SLPopBack(SL* ps);

SeqList.c

  1. void SLPopBack(SL* ps)
  2. {
  3.   assert(ps);
  4.   assert(ps->size);  //判断顺序表是否为空,为空不能进行删除操作
  5.   
  6.   //顺序表不为空
  7.   ps->size--;  //这里属于是看不见就等于没有,这并不影响数据的查找,修改,插入
  8. }

test.c

  1. //测试尾删
  2. SLPushBack(&sl, 1);
  3. SLPushBack(&sl, 2);
  4. SLPushBack(&sl, 3);
  5. SLPushBack(&sl, 4);
  6. SLPrint(&sl);
  7.  
  8. SLPopBack(&sl);
  9. SLPopBack(&sl);
  10. SLPrint(&sl);

输出结过为

  1. 1 2 3 4
  2. 1 2

2.7 头删

SeqList.h

void SLPopFront(SL* ps);

SeqList.c

  1. void SLPopFront(SL* ps)
  2. {
  3.   assert(ps);
  4.   assert(ps->size);
  5.  
  6.   //不为空执行挪动操作
  7.   for(int i = 0; i < size-1; i++)  //i最后的值为size-2
  8.   {
  9.     ps->arr[i] = ps->arr[i+1];  //最后一次循环为 ps->arr[size-2] = ps->arr[size-1]
  10.   }
  11.   ps->size--;
  12. }

 test.c

  1. //测试头删
  2. SLPushBack(&sl, 1);
  3. SLPushBack(&sl, 2);
  4. SLPushBack(&sl, 3);
  5. SLPushBack(&sl, 4);
  6. SLPrint(&sl);
  7.  
  8. SLPopFront(&sl);
  9. SLPopFront(&sl);
  10. SLPrint(&sl);

 输出结果为

  1. 1 2 3 4
  2. 3 4

2.8 指定位置插入数据

SeqList.h

void SLInsert(SL* ps, int pos, SLDataType x);

SeqList.c

  1. void SLInsert(SL* ps, int pos, SLDataType x)
  2. {
  3.   assert(ps);
  4.   assert(pos >= 0 && pos <= ps->size);  //限制pos的大小，否则会出现插入失败的情况
  5.  
  6.   SLCheckCapacity(ps);
  7.  
  8.   //pos及之后的数据往后挪动一位，把pos空出来
  9.   for(int i = ps->size; i > pos; i--)
  10.   {
  11.     ps->arr[i] = ps->arr[i-1];  //最后一步ps->arr[pos+1] = ps->arr[pos]
  12.   }
  13.   ps->arr[pos] = x;
  14.   ps->size++;
  15. }

test.c

  1. //测试指定位置插入
  2. SLPushBack(&sl, 1);
  3. SLPushBack(&sl, 2);
  4. SLPushBack(&sl, 3);
  5. SLPushBack(&sl, 4);
  6. SLPrint(&sl);
  7.  
  8. SLInsert(&sl, 0, 100);
  9. SLPrint(&sl);
  10. SLInsert(&sl, 0, 100);
  11. SLPrint(&sl);
  12.  
  13. //SLInsert(&sl, 0, 100);  //如果代码中没有assert来检查pos的值，这里就会插入失败，插入的数据异常 
  14. //SLPrint(&sl);

输出结果为

  1. 1 2 3 4
  2. 100 1 2 3 4
  3. 100 1 2 3 4 200

2.9 删除指定位置数据

SeqList.h

void SLErase(SL* ps, int pos);

SeqList.c

  1. void SLErase(SL* ps, int pos)
  2. {
  3.   assert(ps);
  4.   assert(pos >= 0 && ps < ps->size);
  5.  
  6.   //pos以后的数据往前挪一位
  7.   for(int i = pos; i < ps->size-1; i++)
  8.   {
  9.     ps->arr[i] = ps->arr[i+1];  //最后一步ps->arr[i-2] = ps->arr[i-1]
  10.   }
  11.   ps->size--;
  12. }

test.c

  1. //测试指定位置删除
  2. SLPushBack(&sl, 1);
  3. SLPushBack(&sl, 2);
  4. SLPushBack(&sl, 3);
  5. SLPushBack(&sl, 4);
  6. SLPrint(&sl);
  7.  
  8. SLErase(&sl, 0);
  9. SLPrint(&sl);
  10. SLErase(&sl, sl.size - 1);
  11. SLPrint(&sl);

输出结果为

  1. 1 2 3 4
  2. 2 3 4
  3. 2 3

 2.10 查找数据

SeqList.h

int SLFind(SL* ps, SLDataType x);

 SeqList.c

  1. int SLFind(SL* ps, SLDataType x)
  2. {
  3.   assert(ps);  //加上断言对代码的健壮性更好
  4.   for(int i = 0; i < ps->size; i++)
  5.   {
  6.     if(ps->arr[i] == x)
  7.     {
  8.       return i;
  9.     }
  10.   }
  11.   return -1;
  12. }

test.c

 

  1. //测试查找
  2. SLPushBack(&sl, 1);
  3. SLPushBack(&sl, 2);
  4. SLPushBack(&sl, 3);
  5. SLPushBack(&sl, 4);
  6. SLPrint(&sl);
  7.  
  8.  
  9. int ret = SLFind(&Sl, 3);
  10. if(ret < 0)
  11. {
  12.   printf("数据不存在，查找失败！！"）;
  13. }
  14. else
  15. {
  16.   printf("数据找到了，在下标为%d的位置\n", ret);
  17. }
  18.  
  19. //int ret = SLFind(&Sl, 6);
  20. //if(ret < 0)
  21. //{
  22. //  printf("数据不存在，查找失败！！“）;
  23. //}
  24. //else
  25. //{
  26. //  printf("数据找到了，在下标为%d的位置！\n", ret);
  27. //}

输出结果为

  1. 1 2 3 4
  2. 数据找到了，在下标为2的位置
  3.  
  4. //数据不存在，查找失败！！

 2.11 销毁

SeqList.h

void SLDestroy(SL* ps);

 SeqLis.c

  1. void SLDestroy(SL* ps)
  2. {
  3.   assert(ps);
  4.   if(ps->arr)  //如果arr本身就是空的，我们就没必要销毁了
  5.   {
  6.     free(ps->arr);
  7.   }
  8.   ps->arr = NULL;
  9.   ps->size = ps->capacity = 0;
  10. }

3 整理顺序表代码

SeqList.h

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>
  4.  
  5. typedef int SLDataType//等效替换int，可以实现一键替换想要的数据类型
  6. typedef struct SeqList
  7. {
  8.   SLDataType* arr;//存储数据的底层结构
  9.   int capacity;//记录顺序表的空间大小
  10.   int size;//记录顺序表当前有效的数据个数
  11. }SL;
  12.  
  13. //typedef struct SeqList SL; //与以上代码相同的去定义SeqList结构体变量SL
  14.  
  15. //初始化
  16. void SLInit(SL s1);
  17. //扩容
  18. void SLCheckCapacity(SL* ps);
  19. //打印
  20. void SLPrint(SL* ps); 
  21. //尾插
  22. void SLPushBack(SL* ps, SLDataType x);
  23. //头插
  24. void SLPushFront(SL* ps, SLDataType x);
  25. //尾删
  26. void SLPopBack(SL* ps);
  27. //头删
  28. void SLPopFront(SL* ps);
  29. //指定位置插入数据
  30. void SLInsert(SL* ps, int pos, SLDataType x);
  31. //删除指定位置数据
  32. void SLErase(SL* ps, int pos);
  33. //查找数据
  34. int SLFind(SL* ps, SLDataType x);
  35. //销毁
  36. void SLDestroy(SL* ps);

SeqList.c

  1. #include "SeqList.h"
  2.  
  3. //初始化
  4. void SLInit(SL* ps)
  5. {
  6.   ps->arr = NULL;
  7.   ps->size = ps->capacity = 0;
  8. }
  9.  
  10. //扩容
  11. void SLCheckCapacity(SL* ps)
  12. {
  13.   if(ps->size == ps->capacity)
  14.   {
  15.     int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  16.     //判断capacity是否为零，因为初始化时capacity为零，如果不为零则扩容两倍
  17.     SLDataType* tmp = (SLDataType*)realloc(ps=>arr, newCapacity * sizeof(SLDataType));
  18.     //注意newCapacity的单位，要乘上数据类型的大小
  19.     //设一个零时变量tmp是为了防止realloc开辟空间失败导致地址丢失
  20.     if(tmp == NULL)
  21.     {
  22.       perror("realloc fail!");
  23.       exit(1);
  24.     }
  25.     //扩容成功
  26.     ps->arr = tmp;
  27.     ps->capacity = newCapacity;
  28.   }
  29. }
  30.  
  31. //打印
  32. void SLPrint(SL* ps)
  33. {
  34.   for(int i = 0; i < ps->size; i++)
  35.   {
  36.     printf("%d", ps->arr[i]);
  37.   }
  38.   printf("\n");
  39. }
  40.  
  41. //尾插
  42. void SLPushBack(SL* ps, SLDataType x)
  43. {
  44.   //为了防止传的地址为NULL
  45.   //assert--粗暴的解决方式,如果等于NULL或者判断为假就会报错,程序无法继续运行下去
  46.   assert(ps);
  47.   //assert(ps != NULL);//等同于上一行
  48.   
  49.   //if判断--温柔的解决方式,如果等于NULL就就直接跳过而不插入
  50.   //if(ps == NULL)
  51.   //{
  52.   //  return;
  53.   //}
  54.   
  55.   //空间不够,扩容
  56.   SLCheckCapacity(ps);
  57.   
  58.   //空间足够,直接插入
  59.   ps->arr[ps->size++] = x;
  60. }
  61.  
  62. //头插
  63. void SLPushFront(SL* ps, SLDataType x)
  64. {
  65.   assert(ps);
  66.  
  67.   //判断是否扩容
  68.   SLCheckCapacity(ps);
  69.  
  70.   //旧的数据往后挪一位
  71.   for(int i = ps->size; i > 0; i--) //i最后值为1
  72.   {
  73.     ps->arr[i] = ps->arr[i-1];  //最后一个循环为 ps->arr[1] = ps->arr[0]
  74.   }
  75.   ps->arr[0] = x;
  76.   ps->size++;
  77. }
  78.  
  79. //尾删
  80. void SLPopBack(SL* ps)
  81. {
  82.   assert(ps);
  83.   assert(ps->size);  //判断顺序表是否为空,为空不能进行删除操作
  84.   
  85.   //顺序表不为空
  86.   ps->size--;  //这里属于是看不见就等于没有,这并不影响数据的查找,修改,插入
  87. }
  88.  
  89. //头删
  90. void SLPopFront(SL* ps)
  91. {
  92.   assert(ps);
  93.   assert(ps->size);
  94.  
  95.   //不为空执行挪动操作
  96.   for(int i = 0; i < size-1; i++)  //i最后的值为size-2
  97.   {
  98.     ps->arr[i] = ps->arr[i+1];  //最后一次循环为 ps->arr[size-2] = ps->arr[size-1]
  99.   }
  100.   ps->size--;
  101. }
  102.  
  103. //指定位置插入数据
  104. void SLInsert(SL* ps, int pos, SLDataType x)
  105. {
  106.   assert(ps);
  107.   assert(pos >= 0 && pos <= ps->size);  //限制pos的大小，否则会出现插入失败的情况
  108.  
  109.   SLCheckCapacity(ps);
  110.  
  111.   //pos及之后的数据往后挪动一位，把pos空出来
  112.   for(int i = ps->size; i > pos; i--)
  113.   {
  114.     ps->arr[i] = ps->arr[i-1];  //最后一步ps->arr[pos+1] = ps->arr[pos]
  115.   }
  116.   ps->arr[pos] = x;
  117.   ps->size++;
  118. }
  119.  
  120. //删除指定位置数据
  121. void SLErase(SL* ps, int pos)
  122. {
  123.   assert(ps);
  124.   assert(pos >= 0 && ps < ps->size);
  125.  
  126.   //pos以后的数据往前挪一位
  127.   for(int i = pos; i < ps->size-1; i++)
  128.   {
  129.     ps->arr[i] = ps->arr[i+1];  //最后一步ps->arr[i-2] = ps->arr[i-1]
  130.   }
  131.   ps->size--;
  132. }
  133.  
  134. //查找数据
  135. int SLFind(SL* ps, SLDataType x)
  136. {
  137.   assert(ps);  //加上断言对代码的健壮性更好
  138.   for(int i = 0; i < ps->size; i++)
  139.   {
  140.     if(ps->arr[i] == x)
  141.     {
  142.       return i;
  143.     }
  144.   }
  145.   return -1;
  146. }
  147.  
  148. //销毁
  149. void SLDestroy(SL* ps)
  150. {
  151.   assert(ps);
  152.   if(ps->arr)  //如果arr本身就是空的，我们就没必要销毁了
  153.   {
  154.     free(ps->arr);
  155.   }
  156.   ps->arr = NULL;
  157.   ps->size = ps->capacity = 0;
  158. }

 

 

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号