追梦之旅【数据结构篇】——详解C语言动态实现顺序表-阿里云开发者社区

追梦之旅【数据结构篇】——详解C语言动态实现顺序表

2023-04-27 64

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

日志服务 SLS，月写入数据量 50GB 1个月

简介： 顺序表概念及结构🙌 在实现顺序表之前，我们先要了解一下什么是顺序表，它的大概结构是怎么样的？其实顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

微信图片_20230427172747.gif

😎博客昵称：博客小梦

😊最喜欢的座右铭：全神贯注的上吧！！！

😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！

😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

微信图片_20230427160707.gif

前言🙌

哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家学习C语言动态实现顺序表~ 都是精华内容，可不要错过哟！！！😍😍😍

顺序表概念及结构🙌

在实现顺序表之前，我们先要了解一下什么是顺序表，它的大概结构是怎么样的？其实顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

微信图片_20230427173014.png

顺序表一般可以分为：

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

动态顺序表：使用动态开辟的数组存储。

其实静态实现和动态实现的方法都差不多，但是相比而言动态实现的顺序表的性能更优，实际应用的价值更大，比较灵活。

实现大概思路分析：

首先在头文件先定义结构体和各个功能函数的声明，并把有关的头文件包含上去。各个函数如何实现的，主要是对各个函数的实现，用到realloc动态开辟新节点的空间，用assert断言确保指针有效，通过画图来帮助理清代码实现的思路，指针的指向如何，要考虑哪些情况。然后再测试代码中，将上述代码都进行测试，显示结果。

功能函数的具体实现分析：🙌

尾插函数具体实现：

设计思路分析：

1.首先设计一个检查容量的函数，保证有空间才能进行插入操作。

2.将size为下标的元素改为x，别忘了将size++。

3.或者实现任意插函数之后，而尾插作为其一种特殊情况，可以通过调用任意插函数来实现尾插的功能

//尾插
void SeqListPushBack(SL* p, DataSeqList x)
{
  /*SeqListCheckCapacity(p);
  p->arr[p->size] = x;
  p->size++;*/
  SeqListInsert(p, p->size, x);
}

头插函数具体实现：

设计思路分析：

首先设计一个检查容量的函数，保证有空间才能进行插入操作。

注意挪动数据如何挪，将控制条件控制好即可。

将首元素改为x，别忘了将size++。

或者实现任意插函数之后，而头插作为其一种特殊情况，可以通过调用任意插函数来实现头插的功能

//头插
void SeqListPushFront(SL* p, DataSeqList x)
{
  //SeqListCheckCapacity(p);
  挪动数据
  //int end = p->size - 1;
  //while (end >= 0)
  //{
  //  p->arr[end + 1] = p->arr[end];
  //  end--;
  //}
  //p->arr[0] = x;
  //p->size++;
  SeqListInsert(p,0, x);
}

头删插函数具体实现：

设计思路分析：

先assert检查顺序表的元素个数，如果没有元素就不用再删了。

注意数据挪动，可以采用画图分析的方法控制挪动数据的控制条件。

不要忘了将size-减减。

或者实现任意删函数之后，而头删作为其一种特殊情况，可以通过调用任意删函数来实现头删的功能

//头删
void SeqListPopFront(SL* p)
{
  删完就不用删了
  //assert(p->size);
  //int begin = 1;
  //while (begin < p->size)
  //{
  //  p->arr[begin - 1] = p->arr[begin];
  //  begin++;
  //}
  //p->size--;
  SeqListEraes(p, 0);
}

任意插函数具体实现：

设计思路分析：

先判断容量，有空间才进行插入操作。

检查插入的合法性，在pos >= 0 && pos <= p->size 的范围才能进行插入

注意数据挪动，可以采用画图分析的方法控制挪动数据的控制条件。

别忘了将size加加

//任意插
void SeqListInsert(SL* p,int pos ,DataSeqList x)
{
  SeqListCheckCapacity(p);
  assert(pos >= 0 && pos <= p->size);
  int end = p->size - 1;
  while (end >= pos)
  {
    p->arr[end + 1] = p->arr[end];
    end--;
  }
  p->arr[pos] = x;
  p->size++;
}

任意删函数具体实现：

设计思路分析：

先判断顺序表有没有数据，没有就不用删了。

检查删的位置的合法性，在pos >= 0 && pos < p->size的范围才能进行删除。

注意数据挪动，可以采用画图分析的方法控制挪动数据的控制条件。

别忘了将size减减。

//任意删
void SeqListEraes(SL* p, int pos)
{
  //删完就不用删了
  assert(p->size);
  //删的合法性判断
  assert(pos >= 0 && pos < p->size);
  int begin = pos+1;
  while (begin < p->size)
  {
    p->arr[begin - 1] = p->arr[begin];
    begin++;
  }
  p->size--;
}

销毁顺序表函数具体实现：

设计思路分析：

因为顺序表的空间建立是动态开辟的，动态开辟的空间需要手动free释放。

/销毁
void SeqListDestory(SL* p)
{
  free(p->arr);
  p->arr = NULL;
  p->capacity = p->size = 0;
}

查找函数具体实现：

设计思路分析：

这个比较简单，直接写个循环遍历一遍，找到了x就返回它的下标，找不到返回-1.

//查找
int SeqListFind(SL* p, DataSeqList x)
{
  assert(p);
  for (int i = 0; i < p->size; i++)
  {
    if (p->arr[i] == x)
    {
      return i;
    }
  }
  return -1;
}

检查容量函数具体实现：

设计思路分析：

分为没有空间和空间满了两种情况进行。

如果没有空间，就显动态分配四个数据大小的空间。

如果空间存储满了，就动态扩容到原来的2倍空间。

//检查容量
void SeqListCheckCapacity(SL* p)
{
  if (p->size == p->capacity)
  {
    int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
    DataSeqList* tem = realloc(p->arr, newcapacity * sizeof(DataSeqList));
    assert(tem);
    p->arr = tem;
    p->capacity = newcapacity;
  }
}

初始化函数具体实现：

设计思路分析：

将p->arr = NULL;p->capacity = p->size = 0;

//初始化
void SeqListInit(SL* p)
{
  assert(p);
  p->arr = NULL;
  p->capacity = p->size = 0;
}

打印函数具体实现：

设计思路分析：

这个比较简单，直接写个循环遍历一遍打印即可。

//打印
void SeqListPrintf(SL* p)
{
  int i = 0;
  for (i = 0; i < p->size; i++)
  {
    printf("%d ", p->arr[i]);
  }
  printf("\n");
}

头文件全部源码分享🙌

这里负责函数功能的声明和库函数头文件的包含，写任何一个项目时，可以先把头文件编写好，也就是理清一下项目需要实现哪些功能函数，整理一下项目的整体思路。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define DataSeqList int
typedef struct SeqList
{
  DataSeqList* arr;
  int size;
  int capacity;
}SL;
//初始化
void SeqListInit(SL* p);
//尾插
void SeqListPushBack(SL* p, DataSeqList x);
//尾删
void SeqListPopBack(SL* p);
//头插
void SeqListPushFront(SL* p, DataSeqList x);
//头删
void SeqListPopFront(SL* p);
//任意插
void SeqListInsert(SL* p, int pos, DataSeqList x);
//任意删
void SeqListEraes(SL* p, int pos);
//打印
void SeqListPrintf(SL* p);
//销毁
void SeqListDestory(SL* p);
//查找
int SeqListFind(SL* p, DataSeqList x);
//检查容量
void SeqListCheckCapacity(SL* p);

功能文件全部源码分享🙌

#include"SeqList.h"
//初始化
void SeqListInit(SL* p)
{
  assert(p);
  p->arr = NULL;
  p->capacity = p->size = 0;
}
//尾插- 会遇到三种情况
// 1 - 没有空间    2 - 空间不足，要扩容（查容量）  3 - 空间足够，插入数据
//检查容量
void SeqListCheckCapacity(SL* p)
{
  if (p->size == p->capacity)
  {
    int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
    DataSeqList* tem = realloc(p->arr, newcapacity * sizeof(DataSeqList));
    assert(tem);
    p->arr = tem;
    p->capacity = newcapacity;
  }
}
//打印
void SeqListPrintf(SL* p)
{
  int i = 0;
  for (i = 0; i < p->size; i++)
  {
    printf("%d ", p->arr[i]);
  }
  printf("\n");
}
//尾插
void SeqListPushBack(SL* p, DataSeqList x)
{
  /*SeqListCheckCapacity(p);
  p->arr[p->size] = x;
  p->size++;*/
  SeqListInsert(p, p->size, x);
}
//尾删
void SeqListPopBack(SL* p)
{
  /*assert(p->size);
  p->size--;*/
  SeqListEraes(p, p->size - 1);
}
//头插
void SeqListPushFront(SL* p, DataSeqList x)
{
  //SeqListCheckCapacity(p);
  挪动数据
  //int end = p->size - 1;
  //while (end >= 0)
  //{
  //  p->arr[end + 1] = p->arr[end];
  //  end--;
  //}
  //p->arr[0] = x;
  //p->size++;
  SeqListInsert(p,0, x);
}
//头删
void SeqListPopFront(SL* p)
{
  删完就不用删了
  //assert(p->size);
  //int begin = 1;
  //while (begin < p->size)
  //{
  //  p->arr[begin - 1] = p->arr[begin];
  //  begin++;
  //}
  //p->size--;
  SeqListEraes(p, 0);
}
//任意插
void SeqListInsert(SL* p,int pos ,DataSeqList x)
{
  SeqListCheckCapacity(p);
  assert(pos >= 0 && pos <= p->size);
  int end = p->size - 1;
  while (end >= pos)
  {
    p->arr[end + 1] = p->arr[end];
    end--;
  }
  p->arr[pos] = x;
  p->size++;
}
//任意删
void SeqListEraes(SL* p, int pos)
{
  //删完就不用删了
  assert(p->size);
  //删的合法性判断
  assert(pos >= 0 && pos < p->size);
  int begin = pos+1;
  while (begin < p->size)
  {
    p->arr[begin - 1] = p->arr[begin];
    begin++;
  }
  p->size--;
}
//销毁
void SeqListDestory(SL* p)
{
  free(p->arr);
  p->arr = NULL;
  p->capacity = p->size = 0;
}
//查找
int SeqListFind(SL* p, DataSeqList x)
{
  assert(p);
  for (int i = 0; i < p->size; i++)
  {
    if (p->arr[i] == x)
    {
      return i;
    }
  }
  return -1;
}

测试文件代码🙌

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void test1()
{
  SL s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
  SeqListPrintf(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPrintf(&s);
  SeqListPushFront(&s, 10);
  SeqListPushFront(&s, 20);
  SeqListPushFront(&s, 30);
  SeqListPushFront(&s, 40);
  SeqListPrintf(&s);
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPrintf(&s);
  SeqListDestory(&s);
}
void test2()
{
  SL s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
  SeqListPrintf(&s);
  SeqListInsert(&s, 3, 30);
  SeqListPrintf(&s);
  SeqListEraes(&s, 3);
  SeqListEraes(&s, 2);
  SeqListPrintf(&s);
  SeqListDestory(&s);
}
void test3()
{
  SL s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
  SeqListPrintf(&s);
  SeqListInsert(&s, 3, 30);
  SeqListEraes(&s, 2);
  SeqListPrintf(&s);
  SeqListDestory(&s);
}
void test4()
{
  SL s;
  printf("尾插数据1,2,3,4,5\n");
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
  SeqListPrintf(&s);
  printf("头插数据10， 20 ， 30\n");
  SeqListPushFront(&s, 10);
  SeqListPushFront(&s, 20);
  SeqListPushFront(&s, 30);
  SeqListPrintf(&s);
  SeqListDestory(&s);
}
int main()
{
  //test1();
  //test2();
  //test3();
  test4();
  return 0;
}

部分功能测试结果图：

微信图片_20230427175930.png

总结撒花💞

本篇文章旨在分享详解C语言动态实现顺序表。希望大家通过阅读此文有所收获！😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘

追梦之旅【数据结构篇】——详解C语言动态实现顺序表

前言🙌

顺序表概念及结构🙌

功能函数的具体实现分析：🙌

尾插函数具体实现：

头插函数具体实现：

头删插函数具体实现：

任意插函数具体实现：

任意删函数具体实现：

销毁顺序表函数具体实现：

查找函数具体实现：

检查容量函数具体实现：

初始化函数具体实现：

打印函数具体实现：

头文件全部源码分享🙌

功能文件全部源码分享🙌

测试文件代码🙌

总结撒花💞

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

追梦之旅【数据结构篇】——详解C语言动态实现顺序表

前言🙌

顺序表概念及结构🙌

功能函数的具体实现分析：🙌

尾插函数具体实现：

头插函数具体实现：

头删插函数具体实现：

任意插函数具体实现：

任意删函数具体实现：

销毁顺序表函数具体实现：

查找函数具体实现：

检查容量函数具体实现：

初始化函数具体实现：

打印函数具体实现：

头文件全部源码分享🙌

功能文件全部源码分享🙌

测试文件代码🙌

总结撒花💞

热门文章

最新文章

相关课程

相关电子书