动态顺序表实现

❤️ 动态顺序表实现

文章目录

• ❤️ 动态顺序表实现
• • 💚 1、顺序表介绍
  • 💘 2、顺序表源码查看
  • 💛 3、相关接口
  • 💟 4、顺序表书写心得（注意事项）
  • • 1、注意事项
    • 2、难点理解
  • ❣️ 5、顺序表的缺陷
  • 💕6、总结

💚 1、顺序表介绍

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成增删查改 *** 作。

顺序表分为静态顺序表和动态顺序表两种。

• 静态顺序表：使用定长数组存储元素。

由于静态顺序表只适用于确定知道需要存多少数据的场景。如果需要存储的数据个数未知，那静态顺序表的定长数组就难以确定一个合适的长度N,如果N定大了，空间开多了就浪费，如果N定小了，那么数据将无法有效的进行存储。

• 动态顺序表：使用动态开辟的数组存储（使用动态内存开辟函数）

动态顺序表能够合理的根据数据个数进行分配空间，从而避免空间浪费。

💘 2、顺序表源码查看

1、顺序表实现源文件查看移步到Gitee ----------> 顺序表源码

2、顺序表实现头文件查看移步到Gitee -----------> 顺序表头文件

3、顺序表实现主文件查看移步到Gitee ----------->顺序表主文件

💛 3、相关接口

//1、初始化函数
void SLInit(SL* SList);
//2、销毁函数
void SLDestory(SL* SList);
//3、打印函数
void SLPrint(SL* SList);
//4、检查容量是否足够函数
void SLCheckCapacity(SL* SList);
//5、头插函数
void SLPushFront(SL* SList, SLDataType x);
//6、尾插函数
void SLPushBack(SL* SList, SLDataType x);
//7、尾删函数
void SLPopBack(SL* SList);
//8、头删函数
void SLPopFront(SL* SList);
//9、修改函数
void SLModify(SL* SList, size_t pos, SLDataType x);
//10、插入函数
void SLInsert(SL* SList, size_t pos, SLDataType x);
//11、顺序表查找元素
int SLFind(SL* SList, SLDataType x);
//12、删除pos位置的值的函数
void SLErase(SL* SList, size_t pos);

💟 4、顺序表书写心得（注意事项） 1、注意事项

1、对于形参指针善用断言

• 顺序表传参，传的都是结构体的地址，为防止误 *** 作传了错误的指针，善用assert对形参进行判断

2、调试过程中写测试函数进行函数，避免在主函数中直接进行测试，引发混淆！写完一个函数就测试一个函数！

• //如下
  //测试1函数（插入函数测试）
  void test1()
  {
  	SL test1;
  	SLInit(&test1);
  	SLPushFront(&test1, 1);
  	SLPushFront(&test1, 2);
  	SLPushBack(&test1, 7);
  	SLPrint(&test1);
  }
  //测试2函数（删除函数测试）
  void test2()
  {
  	SL test2;
  	SLInit(&test2);
  	SLPushBack(&test2, 4);
  	SLPushBack(&test2, 5);    
  	//SLPrint(&test2);
  	SLPopBack(&test2);
  	SLPopFront(&test2);
  	SLPrint(&test2);
  }
  

3、结构体传参问题！

• 结构体传参涉及传址和传值两者情况，顺序表中，我们要在函数内对结构体的内容进行修改。所以传的参数为结构体的地址！同时用结构体指针进行接收！

4、顺序表尽量少使用头插头删，消耗的时间过多，头插看链表

• //头插函数
  typedef int SLDataType;
  void SLPushFront(SL* SList,SLDataType x)
  {
      assert(SList);
      SLCheckCapacity(SList);
      int end = SList->size;
      while(end)
      {
          SList->ptr[end] = SList->ptr[end-1];
          end--;
      }
      SList->ptr[0] = x;
      SList->size++;
  }
  

• 当使用头删和头插函数时，时间复杂度为O(N),所以顺序表尽量避免使用头插头删！

5、扩容时必须进行容量检查，删除时考虑到size为0的情况！

6、找到函数要对查找不到的情况进行处理！

2、难点理解

• 在指定的pos位置插入数据问题

//在pos位置插入数据函数
typedef int SLDataType;
void SLInsert(SL* SList, size_t pos, SLDataType x)
{
    assert(SList);
    assert(SList->size >= pos);
    SLCheckCapacity(SList);
    size_t end = SList->size;
    while(end > pos)
    {
        SList->ptr[end] = SList->ptr[end-1];
        end--;
    }
    SList->ptr[pos] = x;
    SList->size++;
}

在pos的位置插入x，size_t 问题（算术转化）

1、当end类型为size_t时，要注意 >=的情况，两边都为size_t类型，所以当pos为0时，会陷入死循环

2、把end的类型换为int，但是会存在算术转化的问题，导致当pos为0时，还是会陷入死循环

解决方案：

• end的类型为size_t,但end为psl->size,避免=的存在 (推荐这种方式)

• end的类型为int，但比较时，将pos的类型强制转化，避免整型提升问题发生（强制类型转化）

❣️ 5、顺序表的缺陷

1、中间/头部的插入，时间复杂度为O（N）

2、若为异地增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3、增容为成倍数增长。若原来的容量已经较大，再次按倍数增长，需要的内存较大，再加上倘若存储的数据较少的话，浪费的内存较多。

💕6、总结

顺序表只是线性表中的一种，存在自身的优势和缺陷！应与线性表中的其他数据结构有机结合才可以发挥更好的效果！
PS:详细的查看顺序表的代码移步到Gitee进行查看，注释清晰，一看就懂！😃