顺序表(更新版)——“数据结构与算法”

本文涉及的产品
日志服务 SLS,月写入数据量 50GB 1个月
简介: 顺序表(更新版)——“数据结构与算法”

各位CSDN的uu们你们好呀,今天小雅兰又来更新新专栏啦,其实之前我就已经写过了顺序表的内容,只是之前的内容不是最新版的顺序表,现在,我来更新一下最新版的顺序表,下面,就让我们进入更新版的顺序表的世界吧


顺序表和小雅兰之前写的三子棋、扫雷、通讯录一样,分为三个文件:


https://xiaoyalan.blog.csdn.net/article/details/128705747?spm=1001.2014.3001.5502


https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502


https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502


https://xiaoyalan.blog.csdn.net/article/details/129788167?spm=1001.2014.3001.5502


https://xiaoyalan.blog.csdn.net/article/details/129896970?spm=1001.2014.3001.5502


test.c——测试代码功能


SeqList.c——顺序表的实现


SeqList.h——顺序表的声明


https://xiaoyalan.blog.csdn.net/article/details/129380414?spm=1001.2014.3001.5502


这是小雅兰之前写的顺序表的知识,有兴趣的可以去看看


我们写的是一个动态版的顺序表:  

typedef struct SeqList
{
  SLDataType* a;
  int size;//存储的有效数据的个数
  int capacity;//容量
}SL;

把struct SeqList这个结构体重命名为SL

typedef int SLDataType;

把int重命名为SLDataType

写成这样的形式是因为:如果以后想要修改类型,那就直接改int就可以了,如果不这样写,要改很多个地方,就很麻烦

顺序表的初始化:

//初始化
void SLInit(SL* ps1)
{
  ps1->a = malloc(sizeof(SLDataType) * 4);
  if (ps1 == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps1->size = 0;
  ps1->capacity = 4;
}

动态开辟出4个SLDataType类型的大小的空间

顺序表的销毁:也就是把空间还给操作系统

//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1)
{
  free(ps1->a);
  ps1->a = NULL;
  ps1->size = 0;
  ps1->capacity = 0;
}

打印顺序表的内容:

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

尾插:

ps1->a[ps1->size] = x;
ps1->size++;

在这里,我们需要想一个问题:在尾插的过程中,如果空间不够了该怎么办呢???所以在这里,我们还需要一个检查容量的函数,如果容量不够就扩容

//检查容量,容量不够就扩容
void SLCheckCapacity(SL* ps1)
{
  if (ps1->size == ps1->capacity)
  {
    SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);
    //扩上一个二倍大小的容量
    //这个数值可以自己设定,扩多了不好,扩少了也不好
    //所以扩上二倍是最合理的选择
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps1->a = tmp;
    ps1->capacity = ps1->capacity * 2;
  }
}
//尾插
void SLPushBack(SL* ps1, SLDataType x)
{
  SLCheckCapacity(ps1);
  ps1->a[ps1->size] = x;
  ps1->size++;
}

下面,我们来测试一下尾插的功能,看是否成功

int main()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushBack(&s, 5);
  SLPushBack(&s, 6);
  SLPushBack(&s, 7);
  SLPushBack(&s, 8);
  SLPushBack(&s, 9);
  SLPushBack(&s, 10);
  SLPrint(&s);
  SLDestroy(&s);
  return 0;
}

b49daa65629f42da9be7902d2778cc78.png

结果发现,尾插的功能非常成功!!!

c954538da116418fa22c5b4bc329e864.png

若是从前往后挪动数据,就会覆盖,这是绝对不行的

//头插
void SLPushFront(SL* ps1, SLDataType x)
{
  SLCheckCapacity(ps1);
  //挪动数据
  int end = ps1->size - 1;
  while (end >= 0)
  {
    ps1->a[end + 1] = ps1->a[end];//把数据往后挪
    end--;
  }
  ps1->a[0] = x;
  ps1->size++;
}

来测试一下头插的功能:

//头插测试
void TestSeqList2()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
  SLPushFront(&s, 7);
  SLPushFront(&s, 8);
  SLPushFront(&s, 9);
  SLPrint(&s);
  SLDestroy(&s);
}

19ef7ad422ac47669d6d0d8b8e223c87.png

尾删:

da232d37e09348f79a61c05f4eaeedaf.png

直接把size--就可以了

//尾删
void SLPopBack(SL* ps1)
{
  ps1->size--;
}

来测试一下尾删的功能:

//尾删测试
void TestSeqList3()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
  SLPushFront(&s, 7);
  SLPushFront(&s, 8);
  SLPushFront(&s, 9);
  SLPrint(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPrint(&s);
  SLDestroy(&s);
}

783306b2cdcf49a19b22da029b6451f6.png

但是这个尾删仍然有点问题,需要检查一下:

//尾删
void SLPopBack(SL* ps1)
{
  //温柔的检查
  if (ps1->size == 0)
  {
    return;
  }
  ps1->size--;
}
//尾删
void SLPopBack(SL* ps1)
{
    //暴力的检查
  assert(ps1->size > 0);
  ps1->size--;
}

头删:9b89c657a3cd428ca2a40cacc8014e47.png

//头删
void SLPopFront(SL* ps1)
{
  //暴力检查
  assert(ps1->size > 0);
  int start = 0;
  while (start < ps1->size - 1)
  {
    ps1->a[start] = ps1->a[start + 1];
    start++;
  }
  ps1->size--;
}

来测试一下头删的功能:

//头删测试
void TestSeqList4()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
  SLPushFront(&s, 7);
  SLPushFront(&s, 8);
  SLPushFront(&s, 9);
  SLPrint(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPopFront(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLDestroy(&s);
}

e59ac94298ca4a24a97f968d7a3465a7.png

在中间位置插入数据:

//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{
  SLCheckCapacity(ps1);
  int end = ps1->size - 1;
  while (end >= pos)
  {
    ps1->a[end + 1] = ps1->a[end];
    end--;
  }
  ps1->a[pos] = x;
  ps1->size++;
}

0beb60ce33e84873a247d35cd4d721e9.png写了这个函数的功能之后,我们就可以把之前写的头插和尾插修改一下:

//尾插
void SLPushBack(SL* ps1, SLDataType x)
{
   SLInsert(ps1, ps1->size, x);
}
//头插
void SLPushFront(SL* ps1, SLDataType x)
{
   SLInsert(ps1, 0, x);
}

但是,这个在中间插入数据的代码还是有点问题;

//中间插数据测试
void TestSeqList5()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
  SLPushFront(&s, 7);
  SLPushFront(&s, 8);
  SLPushFront(&s, 9);
  SLPrint(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPopFront(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLInsert(&s, 2, 30);
  SLPrint(&s);
  SLInsert(&s, 20, 300);
  SLPrint(&s);
  SLDestroy(&s);
}


从此运行结果可知:越界是不会报错的!!!但是它的的确确越界了!!!

所以把代码改进为:

//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{
  assert(pos >= 0 && pos <= ps1->size);
  SLCheckCapacity(ps1);
  int end = ps1->size - 1;
  while (end >= pos)
  {
    ps1->a[end + 1] = ps1->a[end];
    end--;
  }
  ps1->a[pos] = x;
  ps1->size++;
}

在中间位置删除数据:

//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos)
{
  assert(pos >= 0 && pos < ps1->size);
  assert(ps1->size > 0);//可有可无
  int start = pos + 1;
  while (start <= pos + 1)
  {
    ps1->a[start - 1] = ps1->a[start];
    start++;
  }
  ps1->size--;
}

同样,有了这个功能之后,可以把头删和尾删修改一下:

//头删
void SLPopFront(SL* ps1)
{
   SLErase(ps1, 0);
}


//尾删
void SLPopBack(SL* ps1)
{
   SLErase(ps1, ps1->size - 1);
}

测试一下从中间删除数据的功能:

//中间删数据测试
void TestSeqList6()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPushFront(&s, 5);
  SLPushFront(&s, 6);
  SLPushFront(&s, 7);
  SLPushFront(&s, 8);
  SLPushFront(&s, 9);
  SLPrint(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPopBack(&s);
  SLPrint(&s);
  SLPopFront(&s);
  SLPopFront(&s);
  SLPopFront(&s);
  SLPrint(&s);
  SLInsert(&s, 2, 30);
  SLPrint(&s);
  SLErase(&s, 3);
  SLPrint(&s);
  SLDestroy(&s);
}

7227de61db8544b3ba9baa989e3b4048.png

查找:

//查找
//找到了返回下标,找不到返回-1
int SLFind(SL* ps1, SLDataType x)
{
  int i = 0;
  for (i = 0; i < ps1->size; i++)
  {
    if (ps1->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}

修改:

//修改
void SLModify(SL* ps1, int pos, SLDataType x)
{
  assert(pos >= 0 && pos < ps1->size);
  ps1->a[pos] = x;
}

下面,浅浅附上一波源代码:

SeqList.c的内容

#include"SeqList.h"
//初始化
void SLInit(SL* ps1)
{
  assert(ps1);
  ps1->a = malloc(sizeof(SLDataType) * 4);
  if (ps1 == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps1->size = 0;
  ps1->capacity = 4;
}
//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1)
{
  assert(ps1);
  free(ps1->a);
  ps1->a = NULL;
  ps1->size = 0;
  ps1->capacity = 0;
}
//打印
void SLPrint(SL* ps1)
{
  assert(ps1);
  int i = 0;
  for (i = 0; i < ps1->size; i++)
  {
    printf("%d ", ps1->a[i]);
  }
  printf("\n");
}
//检查容量,容量不够就扩容
void SLCheckCapacity(SL* ps1)
{
  assert(ps1);
  if (ps1->size == ps1->capacity)
  {
    SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);
    //扩上一个二倍大小的容量
    //这个数值可以自己设定,扩多了不好,扩少了也不好
    //所以扩上二倍是最合理的选择
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps1->a = tmp;
    ps1->capacity = ps1->capacity * 2;
  }
}
//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{
  assert(ps1);
  assert(pos >= 0 && pos <= ps1->size);
  SLCheckCapacity(ps1);
  int end = ps1->size - 1;
  while (end >= pos)
  {
    ps1->a[end + 1] = ps1->a[end];
    end--;
  }
  ps1->a[pos] = x;
  ps1->size++;
}
//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos)
{
  assert(ps1);
  assert(pos >= 0 && pos < ps1->size);
  assert(ps1->size > 0);//可有可无
  int start = pos + 1;
  while (start <= pos + 1)
  {
    ps1->a[start - 1] = ps1->a[start];
    start++;
  }
  ps1->size--;
}
//尾插
void SLPushBack(SL* ps1, SLDataType x)
{
  assert(ps1);
  /*SLCheckCapacity(ps1);
  ps1->a[ps1->size] = x;
  ps1->size++;*/
  SLInsert(ps1, ps1->size, x);
}
//头插
void SLPushFront(SL* ps1, SLDataType x)
{
  assert(ps1);
  //SLCheckCapacity(ps1);
  挪动数据
  //int end = ps1->size - 1;
  //while (end >= 0)
  //{
  //  ps1->a[end + 1] = ps1->a[end];//把数据往后挪
  //  end--;
  //}
  //ps1->a[0] = x;
  //ps1->size++;
  SLInsert(ps1, 0, x);
}
//尾删
void SLPopBack(SL* ps1)
{
  assert(ps1);
  温柔的检查
  //if (ps1->size == 0)
  //{
  //  return;
  //}
  //ps1->size--;
  //暴力的检查
  /*assert(ps1->size > 0);
  ps1->size--;*/
  SLErase(ps1, ps1->size - 1);
}
//头删
void SLPopFront(SL* ps1)
{
  assert(ps1);
  //暴力检查
  assert(ps1->size > 0);
  int start = 0;
  while (start < ps1->size - 1)
  {
    ps1->a[start] = ps1->a[start + 1];
    start++;
  }
  ps1->size--;
  //SLErase(ps1, 0);
}
//查找
//找到了返回下标,找不到返回-1
int SLFind(SL* ps1, SLDataType x)
{
  assert(ps1);
  int i = 0;
  for (i = 0; i < ps1->size; i++)
  {
    if (ps1->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}
//修改
void SLModify(SL* ps1, int pos, SLDataType x)
{
  assert(ps1);
  assert(pos >= 0 && pos < ps1->size);
  ps1->a[pos] = x;
}

SeqList.h的内容

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a;
  int size;//存储的有效数据的个数
  int capacity;//容量
}SL;
//初始化
void SLInit(SL* ps1);
//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1);
//打印
void SLPrint(SL* ps1);
//尾插
void SLPushBack(SL* ps1,SLDataType x);
//尾删
void SLPopBack(SL* ps1);
//头插
void SLPushFront(SL* ps1, SLDataType x);
//头删
void SLPopFront(SL* ps1);
//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x);
//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos);
//查找
//找到了返回下标,找不到返回-1
int SLFind(SL* ps1, SLDataType x);
//修改
void SLModify(SL* ps1, int pos, SLDataType x);

test.c的内容

void menu()
{
  printf("***********************************************************\n");
  printf("1、尾插数据             2、尾删数据\n");
  printf("\n");
  printf("3、头插数据             4、头删数据\n");
  printf("\n");
  printf("5、在任意位置插入数据(位置3插入20)\n");
  printf("\n");
  printf("6、在任意位置删除数据              \n");
  printf("\n");
  printf("7、查找某个数据的位置,并删除它     \n");
  printf("\n");
  printf("8、删除顺序表中有的 某个数据        \n");
  printf("\n");
  printf("9、打印数据                       \n");
  printf("\n");
  printf("-1、退出                          \n");
  printf("\n");
  printf("***********************************************************\n");
}
int main()
{
  printf("*************  欢迎大家来到动态顺序表的测试  **************\n");
  int option = 0;
  SL s;
  SLInit(&s);
  do
  {
    menu();
    printf("请输入你的操作:>");
    scanf_s("%d", &option);
    int sum = 0;
    int x = 0;
    int y = 0;
    int z = 0;
    int pos = 0;
    int w = 0;
    switch (option)
    {
    case 1:
      printf("请依次输入你要尾插的数据:,以-1结束\n");
      scanf_s("%d", &sum);
      while (sum != -1)
      {
        SLPushBack(&s, sum);    // 1.尾插
        scanf_s("%d", &sum);
      }
      break;
    case 2:
      SLPopBack(&s);             // 2.尾删
      break;
    case 3:
      scanf_s("%d", &x);
      SLPushFront(&s, x);       // 3.头插
      break;
    case 4:
      SLPopFront(&s);           // 4.头删
      break;
    case 5:
      SLInsert(&s, 3, 20);     // 5.在任意位置插入数据
      break;
    case 6:
      SLErase(&s, 3);          // 6.在任意位置删除数据
      break;
    case 7:
      printf("请输入要删除序列的中的某个数字\n");
      scanf_s("%d", &z);
      y = SLFind(&s, z);        // 7.查找某个数字的位置,并且删除它
      printf("%d的位置在%d处: \n", z, y);
      if (y != -1)
      {
        SLErase(&s, y);
      }
      break;
    case 8:
      printf("请输入要删除序列的中的数字\n");  //8.删除顺序表中 所有的 某个数据 
      scanf_s("%d", &w);
      pos = SLFind(&s, w, 0);
      while (pos != -1)
      {
        SLErase(&s, pos);
        pos = SLFind(&s, w, pos);
      }
      break;
    case 9:
      SLPrint(&s);
      break;
    default:
      if (option == -1)
      {
        exit(0);  // 退出程序 
      }
      else
      {
        printf("输入错误,请重新输入\n");
      }
      break;
    }
  } while (option != -1);   // 退出程序
  SLDestroy(&s);
  return 0;
}

好啦,小雅兰今天的顺序表的更新版的内容就到这里啦,继续加油刷题和学习算法噢!!!

69faca538c2e474f897e4351f48a3826.jpg

相关实践学习
日志服务之使用Nginx模式采集日志
本文介绍如何通过日志服务控制台创建Nginx模式的Logtail配置快速采集Nginx日志并进行多维度分析。
相关文章
|
3月前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
74 2
|
15天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
1天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
19 5
|
2月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
2月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
90 3
|
2月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
3月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
51 6
|
3月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
31 3
|
3月前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
45 2
|
3月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
32 1
下一篇
开通oss服务