AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

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

2023-11-14 90
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【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语言
测试技术
关键词：
C语言数据结构
数据结构c语言
数据结构顺序表
C语言数据结构顺序表
C语言顺序表
青色忘川
目录
相关文章
土木林森
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
694 1
LucianaiB
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
LucianaiB
216 4
羑悻的小杀马特
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
羑悻的小杀马特
408 13
羑悻的小杀马特
|
搜索推荐 C语言
数据结构（C语言）之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法，通过递归将数组不断分割为子数组，直到每个子数组仅剩一个元素，再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中，每次分割区间为[left, mid]和[mid+1, right]，确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值（初始为1），先对单个元素排序，再逐步扩大到更大的区间进行合并，直至整个数组有序。归并排序的时间复杂度为O(n*logn)，空间复杂度为O(n)，且具有稳定性，适用于普通排序及大文件排序场景。
羑悻的小杀马特
225 13
RossyYan
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算（头歌实践教学平台习题）【合集】
本文档介绍了线性表的基本运算任务，涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法，并提供了测试说明和通关代码。 主要内容包括： - **任务描述**：实现顺序表的基本运算。 - **相关知识**：介绍线性表的基本概念及操作，如初始化、销毁、判定是否为空表等。 - **具体操作**：详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法，并附有代码示例。 - **测试说明**：提供测试输入和预期输出，确保代码正确性。 - **通关代码**：给出完整的C++代码实现，帮助完成任务。 文档
RossyYan
434 5
三三是该溜子
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
367 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
477 5
土木林森
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
557 1
那年春天
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
371 59
hahaha无
|
9月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
198 0
栈区的非法访问导致的死循环(x64)