【C语言数据结构（基础篇）】第二站：顺序表（下）-阿里云开发者社区

【C语言数据结构（基础篇）】第二站：顺序表（下）

2023-11-14 41

版权

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

简介： 【C语言数据结构（基础篇）】第二站：顺序表

7.顺序表任意位置的增加

其实我们已经了解了顺序表的头插和尾插，那么就想能不能在任意位置都插入一个数据呢，或者任意位置的删除呢？我们应该也是可以实现的，所以我们现在来实现一下任意位置的插入和删除。我们先定义好这两个的函数声明

我们先来实现任意位置的插入

任意位置的插入其实和头插是极其相似的，只不过结束点从0变成了pos

代码实现如下

//任意位置的插入
void SeqListInsert(SL* ps, int pos, SQDateType x)
{
  assert(pos < ps->size);
  SeqListCheckCapacity(ps);
  int end = ps->size - 1;
  while (pos <= end)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

这样的话，我们给一组测试用例

运行结果为

8.顺序表任意位置的删除

我们接下来来实现一下任意位置的删除，其实这个跟头删也是极其相似的，只不过我们将结束条件变成了pos控制的而已

代码如下

//任意位置的删除
void SeqListEarse(SL* ps, int pos)
{
  assert(pos < ps->size);
  int start = pos + 1;
  while (start < ps->size)
  {
    ps->a[start - 1] = ps->a[start];
    start++;
  }
  ps->size--;
}

我们的测试用例如下

运行结果为

9.顺序表的销毁

我们最后还需要加上一个销毁顺序表的函数，因为我们的空间都是malloc出来的，必须要还回去，否则会发生内存泄漏

//顺序表的销毁
void SeqListDestory(SL* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}

10.顺序表的查找

增删查改，我们现在就来实现查找

我们先声明好这个函数

然后我们来实现他，实现它也很简单，就是遍历一边他知道找到这个元素，找不到返回-1，找到返回它的下标

代码实现如下

//顺序表的查找
int SeqListFind(SL* ps, SQDateType x)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}

测试用例如下

运行结果为

11.顺序表的修改

接下来就来实现顺序表的修改吧

这是顺序表修改的声明

代码如下

//顺序表的修改
void SeqListModity(SL* ps, int pos, SQDateType x)
{
  assert(pos < ps->size);
  ps->a[pos] = x;
}

测试用例

运行结果为

12.顺序表的菜单

现在，我们已经将一个顺序表的大致功能给解决了，我们接下来就来写一个菜单，将这些功能给整合起来。

菜单很好写，这里就直接给出代码了

void meau()
{
  printf("***************************************\n");
  printf("****     请输入你想要执行的操作    ****\n");
  printf("****     1.头插                    ****\n");
  printf("****     2.尾插                    ****\n");
  printf("****     3.头删                    ****\n");
  printf("****     4.尾删                    ****\n");
  printf("****     5.任意位置添加            ****\n");
  printf("****     6.任意位置删除            ****\n");
  printf("****     7.查找数据                ****\n");
  printf("****     8.修改数据                ****\n");
  printf("****     9.顺序表置零              ****\n");
  printf("****     10.打印顺序表             ****\n");
  printf("****     0.退出顺序表              ****\n");
  printf("***************************************\n");
  printf("请输入>:\n");
}
void test()
{
  int x = 0;
  int pos = 0;
  SL s;
  SeqListInit(&s);
  int input = 0;
  do
  {
    meau();
    scanf("%d", &input);
    switch (input)
    {
      case 1:
        printf("请输入你头插入的数据：\n");
        scanf("%d", &x);
        SeqListPushFront(&s, x);
        break;
      case 2 :
        printf("请输入你尾插入的数据：\n");
        scanf("%d", &x);
        SeqListPushBack(&s, x);
        break;
      case 3:
        printf("执行头删\n");
        SeqListPopFront(&s);
        break;
      case 4:
        printf("执行尾删\n");
        SeqListPopBack(&s);
        break;
      case 5:
        printf("请输入你需要插入的数据：\n");
        scanf("%d", &x);
        printf("请输入你需要插入的位置（下标从零开始）：\n");
        scanf("%d", &pos);
        SeqListInsert(&s, pos, x);
        break;
      case 6:
        printf("请输入你需要删除的数据下标（下标从零开始）：\n");
        scanf("%d", &pos);
        SeqListErase(&s, pos);
        break;
      case 7:
        printf("请输入你需要查找的数据:\n");
        scanf("%d", &x);
        int ret = SeqListFind(&s, x);
        printf("该数据的下标是：%d\n", ret);
        printf("如果返回值是-1，说明没找到\n");
        break;
      case 8:
        printf("请输入需要修改的下标（下标从零开始）：\n");
        scanf("%d", &pos);
        printf("请输入修改后的数据：\n");
        scanf("%d", &x);
        SeqListModity(&s, pos, x);
        break;
      case 9:
        SeqListInit(&s);
        printf("顺序表已经成功置零了\n");
        break;
      case 10:
        printf("顺序表目前的数据为：\n");
        SeqListPrint(&s);
        break;
      case 0:
        printf("即将退出程序,感谢您的使用\n");
        break;
      default:
        printf("输入数据有误，请重新输入！\n");
    }
  } while (input);
}
int main()
{
  test();
  return 0;
}

三、顺序表完整代码

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void meau()
{
  printf("***************************************\n");
  printf("****     请输入你想要执行的操作    ****\n");
  printf("****     1.头插                    ****\n");
  printf("****     2.尾插                    ****\n");
  printf("****     3.头删                    ****\n");
  printf("****     4.尾删                    ****\n");
  printf("****     5.任意位置添加            ****\n");
  printf("****     6.任意位置删除            ****\n");
  printf("****     7.查找数据                ****\n");
  printf("****     8.修改数据                ****\n");
  printf("****     9.顺序表置零              ****\n");
  printf("****     10.打印顺序表             ****\n");
  printf("****     0.退出顺序表              ****\n");
  printf("***************************************\n");
  printf("请输入>:\n");
}
void test()
{
  int x = 0;
  int pos = 0;
  SL s;
  SeqListInit(&s);
  int input = 0;
  do
  {
    meau();
    scanf("%d", &input);
    switch (input)
    {
      case 1:
        printf("请输入你头插入的数据：\n");
        scanf("%d", &x);
        SeqListPushFront(&s, x);
        break;
      case 2 :
        printf("请输入你尾插入的数据：\n");
        scanf("%d", &x);
        SeqListPushBack(&s, x);
        break;
      case 3:
        printf("执行头删\n");
        SeqListPopFront(&s);
        break;
      case 4:
        printf("执行尾删\n");
        SeqListPopBack(&s);
        break;
      case 5:
        printf("请输入你需要插入的数据：\n");
        scanf("%d", &x);
        printf("请输入你需要插入的位置（下标从零开始）：\n");
        scanf("%d", &pos);
        SeqListInsert(&s, pos, x);
        break;
      case 6:
        printf("请输入你需要删除的数据下标（下标从零开始）：\n");
        scanf("%d", &pos);
        SeqListErase(&s, pos);
        break;
      case 7:
        printf("请输入你需要查找的数据:\n");
        scanf("%d", &x);
        int ret = SeqListFind(&s, x);
        printf("该数据的下标是：%d\n", ret);
        printf("如果返回值是-1，说明没找到\n");
        break;
      case 8:
        printf("请输入需要修改的下标（下标从零开始）：\n");
        scanf("%d", &pos);
        printf("请输入修改后的数据：\n");
        scanf("%d", &x);
        SeqListModity(&s, pos, x);
        break;
      case 9:
        SeqListInit(&s);
        printf("顺序表已经成功置零了\n");
        break;
      case 10:
        printf("顺序表目前的数据为：\n");
        SeqListPrint(&s);
        break;
      case 0:
        printf("即将退出程序,感谢您的使用\n");
        break;
      default:
        printf("输入数据有误，请重新输入！\n");
    }
  } while (input);
}
int main()
{
  test();
  return 0;
}

SeqList.h文件

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
//以下是动态的顺序表
typedef int SQDateType;
typedef struct SeqList
{
  SQDateType* a; //指向动态开辟的数组
  int size;    //当前的有效数据个数
  int capacity;  //容量空间的大小
}SL;
//等价于typedef struct SeqList SL;
//增删查改四大功能的函数接口声明
//初始化
void SeqListInit(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SQDateType x);
//头插
void SeqListPushFront(SL* ps, SQDateType x);
//尾删
void SeqListPopBack(SL* ps);
//头删
void SeqListPopFront(SL* ps);
//打印
void SeqListPrint(SL* ps);
//任意位置的插入
void SeqListInsert(SL* ps, int pos, SQDateType x);
//任意位置的删除
void SeqListErase(SL* ps, int pos);
//销毁顺序表
void SeqListDestory(SL* ps);
//顺序表的查找
int SeqListFind(SL* ps, SQDateType x);
//顺序表的修改
void SeqListModity(SL* ps, int pos, SQDateType x);

SeqList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//以下是动态的顺序表
//顺序表初始化
void SeqListInit(SL* ps)
{
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
//打印数据
void SeqListPrint(SL* ps)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
//顺序表的销毁
void SeqListDestory(SL* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->size = 0;
}
//扩容函数
void SeqListCheckCapacity(SL* ps)
{
  //判断是否满了，如果满了，就得扩容了
  if (ps->size == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SQDateType* tmp = (SQDateType*)realloc(ps->a, newcapacity * sizeof(SQDateType));
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    else
    {
      ps->a = tmp;
      ps->capacity = newcapacity;
    }
  }
}
//顺序表尾插
void SeqListPushBack(SL* ps, SQDateType x)
{
  SeqListCheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}
//顺序表的头插
void SeqListPushFront(SL* ps, SQDateType x)
{
  SeqListCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
}
//顺序表的尾删
void SeqListPopBack(SL* ps)
{
  assert(ps->size > 0);
  ps->size--;
}
//顺序表的头删
void SeqListPopFront(SL* ps)
{
  assert(ps->size > 0);
  int start = 1;
  while (start < ps->size)
  {
    ps->a[start - 1] = ps->a[start];
    start++;
  }
  ps->size--;
}
//任意位置的插入
void SeqListInsert(SL* ps, int pos, SQDateType x)
{
  assert(pos < ps->size);
  SeqListCheckCapacity(ps);
  int end = ps->size - 1;
  while (pos <= end)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}
//任意位置的删除
void SeqListErase(SL* ps, int pos)
{
  assert(pos < ps->size);
  int start = pos + 1;
  while (start < ps->size)
  {
    ps->a[start - 1] = ps->a[start];
    start++;
  }
  ps->size--;
}
//顺序表的查找
int SeqListFind(SL* ps, SQDateType x)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}
//顺序表的修改
void SeqListModity(SL* ps, int pos, SQDateType x)
{
  assert(pos < ps->size);
  ps->a[pos] = x;
}

总结

好了，本小节就讲解了顺序表的实现，难度可能要比之前c语言要大很多，不过不用担心，只要认真学，一定是可以学会的。加油！，如果对你有帮助的话，那么不要忘记点赞加收藏哦！！！

想看更多精彩内容，那么就赶快来关注我吧！！！

【C语言数据结构（基础篇）】第二站：顺序表（下）

7.顺序表任意位置的增加

8.顺序表任意位置的删除

9.顺序表的销毁

10.顺序表的查找

11.顺序表的修改

12.顺序表的菜单

三、顺序表完整代码

总结

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C语言数据结构（基础篇）】第二站：顺序表（下）

7.顺序表任意位置的增加

8.顺序表任意位置的删除

9.顺序表的销毁

10.顺序表的查找

11.顺序表的修改

12.顺序表的菜单

三、顺序表完整代码

总结

热门文章

最新文章

相关课程

相关电子书