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

【C/C++】动态顺序表详解（附完整源码）

2023-04-18 144
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C/C++】动态顺序表详解（附完整源码）

0.png

目录

写在前面

1.静态与动态是指什么？

2.动态顺序表结构的定义

3.动态顺序表的函数接口实现

4.动态顺序表的问题及思考

5.关于顺序表的OJ题

6.OJ答案及解析

1.移除元素

2.删除有序数组中的重复项

3.合并两个有序数组

7.动态顺序表完整源码

1.SeqList.h

2.SeqList.c


前言

上一章我们学习了静态顺序表的增删查改，并认识了静态顺序表的存储结构与静态顺序表的在不同场景下的优劣。静态顺序表与动态顺序表都叫做顺序表，只不过我们平时口头所提的顺序表指的是动态顺序表。静态顺序表的局限性太高，无法应对各种复杂的情况所以我们几乎不用它。本章我们就来学习动态顺序表的实现。


正文

1.静态与动态是指什么？


静态顺序表：顺序表的大小固定，存储的数据个数有限。

#define N 5
typedef int SLDataType;
//静态顺序表
typedef struct SeqList
{
  SLDataType a[N];//定长数组
  int size;//记录存储多少个有效数据
}SeqList;

动态顺序表：运用动态内存管理，可按需调整顺序表的大小。

typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
  SLDataType* a;
  int size;//记录有多少个有效数据
  int capacity;//记录顺序表的容量大小
}SeqList;


2.动态顺序表结构的定义


typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
  SLDataType* a;
  int size;//记录有多少个有效数据
  int capacity;//记录顺序表的容量大小
}SeqList;


3.动态顺序表的函数接口实现


//初始化顺序表
void SLInit(SeqList* ps);
//释放空间
void SLDestroy(SeqList* ps);
//检查顺序表是否已满
void CheakCapacity(SeqList* ps);
//动态顺序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//动态顺序表的尾删
void SLPopBack(SeqList* ps);
//动态顺序表的头插
void SLPushFront(SeqList* ps, SLDataType data);
//动态顺序表的头删
void SLPopFront(SeqList* ps);
//pos位置插入数据
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置删除数据
void SLErase(SeqList* ps, int pos);
//查找数据
int SLFind(SeqList* ps, SLDataType data, int begin);
//判断数组是否已满
bool IsFull(SeqList* ps);
//打印存储的数据
void SLPrint(SeqList* ps);

以下是各个接口的实现：

void SLInit(SeqList* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
void SLDestroy(SeqList* ps)
{
  assert(ps);
  //若ps->a不为NULL，则释放空间
  if (ps->a)
  {
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
  }
}


void CheakCapacity(SeqList* ps)
{
  assert(ps);
  if (ps->capacity == ps->size)
  {
    //若是第一次扩容，则大小为4；
    //若不是第一次，则每次扩容为之前容量的2倍
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
    if (tmp == NULL)
    {
      perror("malloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  //检查是否做到扩容
  printf("扩容成功,现在的容量为:%d\n", ps->capacity);
}
void SLPushBack(SeqList* ps, SLDataType data)
{
  assert(ps);
  CheakCapacity(ps);
  //插入数据
  ps->a[ps->size] = data;
  ps->size++;
}
void SLPopBack(SeqList* ps)
{
  assert(ps);
  ps->size--;
}
void SLPushFront(SeqList* ps, SLDataType data)
{
  assert(ps);
  CheakCapacity(ps);
  //挪动数据
  for (int i = ps->size - 1; i >= 0; i--)
  {
    ps->a[i + 1] = ps->a[i];
  }
  //插入数据
  ps->a[0] = data;
  ps->size++;
}
void SLPopFront(SeqList* ps)
{
  assert(ps);
  assert(ps->size > 0);
  //挪动数据
  for (int i = 0; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}
void SLInsert(SeqList* ps, int pos, SLDataType data)
{
  assert(ps);
  CheakCapacity(ps);
  //挪动数据
  for (int i = ps->size - 1; i >= pos; i--)
  {
    ps->a[i + 1] = ps->a[i];
  }
  //插入数据
  ps->a[pos] = data;
  ps->size++;
}
void SLErase(SeqList* ps, int pos)
{
  assert(ps);
  assert(ps->size > 0);
  //挪动数据
  for (int i = pos; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}
int SLFind(SeqList* ps, SLDataType data, int begin)
{
  assert(ps);
  assert(begin < ps->size);
  for (int i = begin; i < ps->size; i++)
  {
    if (ps->a[i] == data)
    {
      return i;
    }
  }
  return -1;
}
void SLPrint(SeqList* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}


4.动态顺序表的问题及思考


动态顺序表与静态顺序表的差别仅仅在与一个容量是固定的，一个可以按需扩容。


动态顺序表看似灵活性有所提高但仍存在着空间浪费，特别是扩容次数越多，越容易造成空间浪费。那么有没有其他的数据结构可以解决这个问题呢？答案是肯定的。这个神奇的数据结构叫做链表，它是一种基于节点的数据结构。下一章我们就会见到它。


动态顺序表和静态顺序表都称为顺序表，它们的性能是相同的。关于顺序表的性能优劣我已经在上一章介绍过了


5.关于顺序表的OJ题


1.移除元素

原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。


2.删除有序数组中的重复项


3.合并两个有序数组


6.OJ答案及解析


1.移除元素


题目要求不能开辟新的数组，所以我们的做法是遇到等于val的元素时，将数组末尾的元素依次倒着覆盖掉等于val的元素。

代码实现;

int removeElement(int* nums, int numsSize, int val){
    int i=0;
    while(i<numsSize)
    {
        while(val==nums[i]&&i<numsSize)
        {
           nums[i]=nums[numsSize-1];
           numsSize--;
        }
        i++;
    }
    return numsSize;
}

以数组nums={3,2,5,6,3,5},val=3为例。


第一步，检查索引为0处的值是否等于val；


11.png


第二步，将索引为5处的值拷贝到索引为0处；

12.png

第三步，检查索引为1处的值；

13.png

第四步，检查索引为2处的值；

14.png

第五步，检查索引为3处的值；

15.png

第六步，检查索引为4处的值；

2.png

第七步，将索引为4处的值拷贝到索引为4处；

2.png此时i已经大于numsSize，循环结束。

2.删除有序数组中的重复项


本题我采用的是双指针的方式，p1来记录当前位置，p2来寻找与p1处的值不相同的元素。

代码实现：

int removeDuplicates(int* nums, int numsSize){
    int* p1=nums;
    int* p2=nums+1;
    int i=0;
    int returnSize=1;//至少有一个元素
    for(i=0;i<numsSize-1;i++)
    {
        if(*p1!=*(p2+i))
        {
            *(++p1)=*(p2+i);
            returnSize++;
        }
    }
    return returnSize;
}

以数组nums={0,0,1,1,1,2,2,3,3,4}为例。

1.png


3.合并两个有序数组


这道题目我采用的是双指针的方式。p1指向nums1，p2指向nums2。另外需要额外开辟一个数组arr，当合并完成之后再将arr里的内容拷贝到nums1中。

代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=0;
    int j=0;
    int arr[200]={0};
    int* p1=nums1;
    int* p2=nums2;
    int k=0;//记录arr数组里元素的个数
    //检查数组是否为空
    if(nums2Size==0)
        return;
    //将nums1或nums2任何一个数组拷贝完成之后就结束
    while(i<nums1Size-nums2Size&&j<nums2Size)
    {
        if(p1[i]<p2[j])
        {
            arr[k]=p1[i];
            i++;
        }
        else
        {
            arr[k]=p2[j];
            j++;
        }
        k++;
    }
    //如果nums1先结束，将nums2中剩余的元素全部拷贝到arr
    if(i==nums1Size-nums2Size)
    {
        for(;j<nums2Size;j++)
        {
            arr[k++]=p2[j];
        }
    }
    //如果nums2先结束，将nums1中剩余的元素全部拷贝到arr
    if(j==nums2Size)
    {
        for(;i<nums1Size-nums2Size;i++)
        {
            arr[k++]=p1[i];
        }
    }
    //将arr中的元素拷贝回nums1
    for(k=0;k<nums1Size;k++)
    {
        nums1[k]=arr[k];
    }
}


7.动态顺序表完整源码


1.SeqList.h


#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
  SLDataType* a;
  int size;//记录有多少个有效数据
  int capacity;//记录顺序表的容量大小
}SeqList;
//初始化顺序表
void SLInit(SeqList* ps);
//释放空间
void SLDestroy(SeqList* ps);
//检查顺序表是否已满
void CheakCapacity(SeqList* ps);
//动态顺序表的尾插
void SLPushBack(SeqList* ps, SLDataType data);
//动态顺序表的尾删
void SLPopBack(SeqList* ps);
//动态顺序表的头插
void SLPushFront(SeqList* ps, SLDataType data);
//动态顺序表的头删
void SLPopFront(SeqList* ps);
//pos位置插入数据
void SLInsert(SeqList* ps, int pos, SLDataType data);
//pos位置删除数据
void SLErase(SeqList* ps, int pos);
//查找数据
int SLFind(SeqList* ps, SLDataType data, int begin);
//判断数组是否已满
bool IsFull(SeqList* ps);
//打印存储的数据
void SLPrint(SeqList* ps);


2.SeqList.c


#define _CRT_SECURE_NO_DEPRECATE 1
#include"SeqList.h"
void SLInit(SeqList* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}
void SLDestroy(SeqList* ps)
{
  assert(ps);
  //若ps->a不为NULL，则释放空间
  if (ps->a)
  {
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
  }
}
void CheakCapacity(SeqList* ps)
{
  assert(ps);
  if (ps->capacity == ps->size)
  {
    //若是第一次扩容，则大小为4；
    //若不是第一次，则每次扩容为之前容量的2倍
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
    if (tmp == NULL)
    {
      perror("malloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  //检查是否做到扩容
  printf("扩容成功,现在的容量为:%d\n", ps->capacity);
}
void SLPushBack(SeqList* ps, SLDataType data)
{
  assert(ps);
  CheakCapacity(ps);
  //插入数据
  ps->a[ps->size] = data;
  ps->size++;
}
void SLPopBack(SeqList* ps)
{
  assert(ps);
  ps->size--;
}
void SLPushFront(SeqList* ps, SLDataType data)
{
  assert(ps);
  CheakCapacity(ps);
  //挪动数据
  for (int i = ps->size - 1; i >= 0; i--)
  {
    ps->a[i + 1] = ps->a[i];
  }
  //插入数据
  ps->a[0] = data;
  ps->size++;
}
void SLPopFront(SeqList* ps)
{
  assert(ps);
  assert(ps->size > 0);
  //挪动数据
  for (int i = 0; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}
void SLInsert(SeqList* ps, int pos, SLDataType data)
{
  assert(ps);
  CheakCapacity(ps);
  //挪动数据
  for (int i = ps->size - 1; i >= pos; i--)
  {
    ps->a[i + 1] = ps->a[i];
  }
  //插入数据
  ps->a[pos] = data;
  ps->size++;
}
void SLErase(SeqList* ps, int pos)
{
  assert(ps);
  assert(ps->size > 0);
  //挪动数据
  for (int i = pos; i < ps->size - 1; i++)
  {
    ps->a[i] = ps->a[i + 1];
  }
  ps->size--;
}
int SLFind(SeqList* ps, SLDataType data, int begin)
{
  assert(ps);
  assert(begin < ps->size);
  for (int i = begin; i < ps->size; i++)
  {
    if (ps->a[i] == data)
    {
      return i;
    }
  }
  return -1;
}
void SLPrint(SeqList* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
文章标签：
C++
存储
关键词：
C++源码
C++顺序表
C++顺序表源码
花想云
目录
相关文章
Hoshiᅟᅠ
|
1月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
Hoshiᅟᅠ
47 2
米码收割机
|
3月前
|
存储 算法 数据可视化
【C++】C++旅游管理系统（源码+论文）【独一无二】
【C++】C++旅游管理系统（源码+论文）【独一无二】
米码收割机
51 3
米码收割机
|
3月前
|
存储 数据可视化 C++
【C++】C++ 职工信息管理系统（源码）【独一无二】
【C++】C++ 职工信息管理系统（源码）【独一无二】
米码收割机
54 3
米码收割机
|
3月前
|
存储 数据可视化 C++
【C++】C++-机房收费管理系统（源码+注释）【独一无二】
【C++】C++-机房收费管理系统（源码+注释）【独一无二】
米码收割机
37 1
米码收割机
|
3月前
|
数据可视化 C++
【C++】C++商店销售管理系统（源码+论文）【独一无二】
【C++】C++商店销售管理系统（源码+论文）【独一无二】
米码收割机
56 1
米码收割机
|
3月前
|
C++
【C++】C++书店管理系统（源码+论文）【独一无二】
【C++】C++书店管理系统（源码+论文）【独一无二】
米码收割机
39 1
米码收割机
|
3月前
|
存储 C++ 索引
【C++ 】C++ 停车场收费系统（源码）【独一无二】
【C++ 】C++ 停车场收费系统（源码）【独一无二】
米码收割机
61 1
kgmh2cwvierzy
|
3月前
|
存储 数据可视化 C++
【C++】C++-学生考试题库管理系统（源码）
本系统设计了一个选题管理流程，包括读取题目信息、随机抽取题目、保存及查询选题结果等功能。使用 `readProjects` 从文件读取题目信息，`drawProject` 随机抽取未选中的题目，`saveSelection` 保存选题结果至文件，`querySelection` 查询并显示所有选题结果。主函数提供菜单界面，支持学生信息输入、抽题及结果查询。关注【测试开发自动化】公众号，回复“题库”获取源码。
kgmh2cwvierzy
24 0
米码收割机
|
3月前
|
存储 数据可视化 C++
【C++】C++-学生考试题库管理系统（源码）【独一无二】
【C++】C++-学生考试题库管理系统（源码）【独一无二】
米码收割机
107 0
米码收割机
|
3月前
|
算法 数据可视化 C++
【C++】C++ 学生信息管理系统（源码+面向对象）【独一无二】
【C++】C++ 学生信息管理系统（源码+面向对象）【独一无二】
米码收割机
52 0