【数据结构】顺序表的增删查改 (C语言实现)(2)

简介: 【数据结构】顺序表的增删查改 (C语言实现)(2)

四、完整代码

1、SeqLIst.h

#pragma once  //防止头文件重复包含
//头文件的包含
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//符号与结构的定义
#define DEF_SIZE 5       //初始容量
#define CRE_SIZE 2       //一次扩容的倍数
typedef int SLDataType;  //将数据类型重命名为SLDataType
typedef struct SeqList
{
  SLDataType* data;  //对应数据类型的指针,用来指向动态开辟的空间
  size_t size;          //记录当前有效数据的个数
  size_t capacity;      //记录当前容量,不够就增容
}SL;
//函数的声明
//初始化顺序表
void SeqListInit(SL* psl);
//在尾部插入数据
void SeqListPushBack(SL* psl, SLDataType x);
//在头部插入数据
void SeqListPushFront(SL* psl, SLDataType x);
//在尾部删除数据
void SeqListPopBack(SL* psl);
//在头部删除数据
void SeqListPopFront(SL* psl);
//在指定下标处插入数据
void SeqListInsert(SL* psl, size_t pos, SLDataType x);
//在指定下标处删除数据
void SeqListErase(SL* psl, size_t pos);
//查找数据
int SeqListFind(const SL* psl, SLDataType x);
//修改指定位置数据
void SeqListModify(SL* psl, size_t pos, SLDataType x);
//打印顺序表中的数据
void SeqListPrint(const SL* psl);
//检查容量(增容)
void CheckCapacity(SL* psl);
//销毁顺序表
void SeqListDestory(SL* psl);

2、SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//初始化顺序表
void SeqListInit(SL* psl)
{
  assert(psl);  //断言:防止psl为空
  psl->data = (SLDataType*)calloc(DEF_SIZE, sizeof(SLDataType));  //开辟默认大小的空间并初始化
  if (psl == NULL)  //判空
  {
    perror("calloc fail");  //打印错误信息
    return;
  }
  psl->size = 0;
  psl->capacity = DEF_SIZE;
}
//销毁顺序表
void SeqListDestory(SL* psl)
{
  assert(psl);  //断言:防止psl为空
  free(psl->data);    //释放(避免内存泄漏)
  psl->data = NULL;   //置空(避免野指针)
  psl->size = 0;
  psl->capacity = 0;
}
//检查容量(增容)
void CheckCapacity(SL* psl)
{
  assert(psl);  //断言:防止psl为空
  if (psl->size == psl->capacity)  //当数据个数和容量相等时扩容
  {
    //将realloc的返回值交由一个临时变量保存,防止扩容失败丢失原来空间的地址
    SLDataType* ptr = (SLDataType*)realloc(psl->data, psl->capacity * CRE_SIZE * sizeof(SLDataType));
    if (ptr == NULL)  //判空
    {
      perror("realloc fail");
      return;
    }
    psl->data = ptr;
    psl->capacity *= CRE_SIZE;  //增加容量
  }
}
//在尾部插入数据
void SeqListPushBack(SL* psl, SLDataType x)
{
  assert(psl);
  SeqListInsert(psl, psl->size, x);  //直接调用insert函数
  //assert(psl);  //判空
  //CheckCapacity(psl);  //检查容量
  //psl->data[psl->size] = x;  //插入数据
  //psl->size++;
}
//在头部插入数据
void SeqListPushFront(SL* psl, SLDataType x)
{
  assert(psl);
  SeqListInsert(psl, 0, x);  //直接调用insert函数
  //assert(psl);  //判空
  //CheckCapacity(psl);  //检查容量
  //int i = 0;
  //for (i = psl->size - 1; i >= 0; i--)
  //{
  //  psl->data[i + 1] = psl->data[i];  //将数据整体向后移
  //}
  //psl->data[0] = x;  //插入数据
  //psl->size++;
}
//打印顺序表中的数据
void SeqListPrint(const SL* psl)
{
  assert(psl);  //判空
  size_t i = 0;
  for (i = 0; i < psl->size; i++)
  {
    printf("%d ", psl->data[i]);
  }
  printf("\n");
}
//在尾部删除数据
void SeqListPopBack(SL* psl)
{
  assert(psl);
  SeqListErase(psl, psl->size - 1);  //直接调用Erase函数
  //assert(psl);
  //assert(psl->size);
  //psl->size--;  //如果尾部有数据,直接让size--即可
}
//在头部删除数据
void SeqListPopFront(SL* psl)
{
  assert(psl);
  SeqListErase(psl, 0);  //直接调用Erase函数
  //assert(psl);
  //assert(psl->size);
  //size_t i = 0;
  //for (i = 0; i < psl->size - 1; i++)
  //{
  //  psl->data[i] = psl->data[i + 1];  //让表中的数据依次往前移
  //}
  //psl->size--;
}
//查找数据
int SeqListFind(const SL* psl, SLDataType x)
{
  assert(psl);
  int i = 0;
  for (i = 0; i < (int)psl->size; i++)
  {
    if (psl->data[i] == x)
      return i;  //找到元素所在返回下标
  }
  return -1;  //找不到返回-1(一个无效下标)
}
//修改指定位置的数据
void SeqListModify(SL* psl, size_t pos, SLDataType x)
{
  assert(psl);
  assert(pos < psl->size);  //断言
  psl->data[pos] = x;  //修改数据
}
//在指定下标处插入数据
void SeqListInsert(SL* psl, size_t pos, SLDataType x)
{
  assert(psl);
  assert(pos <= psl->size);  //断言  因为可能会在尾部插入数据,所以pos可以等于size
  CheckCapacity(psl);  //检查容量
  size_t end = psl->size;
  while (end > pos)  //把pos及以后的数据向后挪动一位
  {
    psl->data[end] = psl->data[end - 1];
    --end;
  }
  psl->data[pos] = x;  //插入数据
  ++psl->size;
}
//在指定下标处删除数据
void SeqListErase(SL* psl, size_t pos)
{
  assert(psl);
  assert(pos < psl->size);
  size_t i = 0;
  for (i = pos; i < psl->size - 1; i++)
  {
    psl->data[i] = psl->data[i + 1];
  }
  psl->size--;
}

3、test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void test1()  //测试插入
{
  //初始化
  SL sl;
  SeqListInit(&sl);
  //尾插
  SeqListPushBack(&sl, 1);
  SeqListPushBack(&sl, 2);
  SeqListPushBack(&sl, 3);
  SeqListPushBack(&sl, 4);
  SeqListPrint(&sl);
  //头插
  SeqListPushFront(&sl, 8);
  SeqListPushFront(&sl, 9);
  SeqListPushFront(&sl, 10);
  SeqListPrint(&sl);
  //在指定位置插入
  SeqListInsert(&sl, 3, 6);
  SeqListInsert(&sl, 0, 6);
  SeqListInsert(&sl, 9, 6);
  SeqListPrint(&sl);
  //销毁
  SeqListDestory(&sl);
}
void test2()   //测试删除
{
  //初始化
  SL sl;
  SeqListInit(&sl);
  //尾插
  SeqListPushBack(&sl, 1);
  SeqListPushBack(&sl, 2);
  SeqListPushBack(&sl, 3);
  SeqListPushBack(&sl, 4);
  SeqListPrint(&sl);
  尾删
  //SeqListPopBack(&sl);
  //SeqListPopBack(&sl);
  //SeqListPopBack(&sl);
  //SeqListPrint(&sl);
  头删
  //SeqListPopFront(&sl);
  //SeqListPopFront(&sl);
  //SeqListPopFront(&sl);
  //SeqListPrint(&sl);
  //删除指定位置元素
  SeqListErase(&sl, 3);
  SeqListPrint(&sl);
  SeqListErase(&sl, 1);
  SeqListPrint(&sl);
  SeqListErase(&sl, 0);
  SeqListPrint(&sl);
  //销毁
  SeqListDestory(&sl);
}
void test3()  //测试查和改
{
  //初始化
  SL sl;
  SeqListInit(&sl);
  //尾插
  SeqListPushBack(&sl, 1);
  SeqListPushBack(&sl, 2);
  SeqListPushBack(&sl, 3);
  SeqListPushBack(&sl, 4);
  SeqListPrint(&sl);
  //查找并修改
  int find = 0;
  int modify = 0;
  do
  {
    scanf("%d", &find);  //要查找的元素
    scanf("%d", &modify);  //要修改的值
    int pos = SeqListFind(&sl, find);  //查找该元素是否存在
    if (pos != -1)
    {
      SeqListModify(&sl, pos, modify);  //存在就修改
    }
    SeqListPrint(&sl);
  } while (find != EOF);
  //销毁
  SeqListDestory(&sl);
}
//测试函数
int main()
{
  //test1();  //测试插入
  //test2();    //测试删除
  test3();  //测试查和改
  return 0;
}

大家也可以去我的 Gitee 仓库中获取完整代码:SeqList/SeqList · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)

五、顺序表的缺陷

顺序表存在如下缺陷:

在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低;

增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗;

增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,如果我们再继续插入了5个数据,后面没有数据插入了,那么会浪费95个数据空间;

针对顺序表存在的这些缺陷,我们设计出了链表。

六、顺序表力扣OJ题

1、移除元素

题目链接

27. 移除元素 - 力扣(LeetCode)

题目描述

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

2020062310470442.png

思路分析

思路1 – 循环遍历,挪动覆盖数据:遍历这个数组,每当遇见等于val的元素时,就将数组后面的元素整体向前挪动一位。


时间复杂度:O(N^2) 空间复杂度:O(1)。


思路2 – 遍历数组,挪动元素到新空间:开辟一个新的数组,然后遍历原来的数组,将不等于val的元素放入新开辟的数组中,将等于val的元素丢弃;最后让新开辟的数组覆盖掉原数组。


时间复杂度:O(N) 空间复杂度:O(N)。


思路3 -- 遍历数组,挪动覆盖数据(双指针解法):定义两个指针src 和 dst,最开始都指向数组第一个元素,然后开始遍历数组;如果arr[src] != val,那么让arr[dst] = arr[src],然后 src++,dst++;如果 arr[src]==val,则 src++,dst不动;这样一直往后遍历,知道把数组所有元素都遍历完。

思路三代码实现

int removeElement(int* nums, int numsSize, int val){
    int src = 0;
    int dst = 0;
    while(src < numsSize)
    {
        if(nums[src] != val)
        {
            nums[dst++] = nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dst;  
}

2020062310470442.png

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

题目链接

26. 删除有序数组中的重复项 - 力扣(LeetCode)

题目描述

给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。


由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。


将最终结果插入 nums 的前 k 个位置后返回 k 。不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

2020062310470442.png

思路分析


这道题的解题思路和上面的移除元素十分相似,都是使用双指针;让 src 和 dst 都指向数组第一个元素,然后判断 arr[src] 和 arr[dst] 是否相等,如果相等,说明是重复元素,则让 src++,dst 不动;如果不相等,就让dst++,然后将 arr[src] 赋给 arr[dst],再让 src++;然后一直往后遍历数组,直到将数组遍历完。


时间复杂度:O(N) 空间复杂度:O(1)

代码实现

int removeDuplicates(int* nums, int numsSize){
    int src = 0;
    int dst = 0;
    while(src < numsSize)
    {
        if(nums[src] != nums[dst])
        {
            nums[++dst] = nums[src++];  //注意:dst是前置++
        }
        else
        {
            src++;
        }
    }
    return dst+1;  //由于dst是前置++,所以返回值需要+1 (数组下标从0开始)
}

2020062310470442.png

3、合并两个有序数组

题目链接

88. 合并两个有序数组 - 力扣(LeetCode)

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。


注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

2020062310470442.png

思路分析

思路1:开辟新数组,并排序:我们可以将两个数组中的元素存放到一个新数组中,然后对数组中的元素进行排序,最后用新数组的数据覆盖掉原数组的数据。


时间复杂度:O((M+N)*log(M+N)) (使用qsort进行排序) 空间复杂度:O(1)。


思路2:开辟新数组,把数据有序的放入数组中(双指针法):因为两个原数组都是有序的,所以我们可以用两个指针 src1 和 src2 分别指向两个数组,如果src1 指向的元素小于 src2,就把src1的数据放入新数组中然后通过比较大小的方式把数据依次放入新数组中,最后新数组的数据覆盖掉原数组的数据。

思路1代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int src1 = 0;
    int src2 = 0;
    int dst = 0;
    int* ret = (int*)calloc(m+n, sizeof(int));
    while(src1<m && src2<n)  //当达到其中一个数组末尾时停下
    {
        if(nums1[src1] > nums2[src2])  //如果数组1中的元素大
        {
            ret[dst++] = nums2[src2++];  //将2中的元素赋给新数组
        }
        else
        {
            ret[dst++] = nums1[src1++];  //否则,将1中的元素赋给新数组
        }
    }
    if(src1 < m)  //如果1中的元素有剩余
    {
        while(src1 < m)
        {
            ret[dst++] = nums1[src1++];
        }
    }
    if(src2 < n)  //如果2中的元素有剩余
    {
        while(src2 < n)
        {
            ret[dst++] = nums2[src2++];
        }
    }
    memcpy(nums1, ret, (m+n)*sizeof(int));  //将1数组中的数据覆盖
    free(ret);
    ret = NULL;
}

2020062310470442.png

思路2代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int end1 = m - 1;  //指向数组1最后一个有效数据
    int end2 = n - 1;  //指向数组2末尾
    int end = m+n-1;   //指向数组1末尾
    while(end1 >=0 && end2 >= 0)  //当其中一个数组遍历完成后循环结束
    {
        if(nums1[end1] < nums2[end2])  //从后往前,需要找大的
        {
            nums1[end--] = nums2[end2--];
        }
        else
        {
            nums1[end--] = nums1[end1--];
        }
    }
    //如果数组1中还有元素则不用管,因为它本来就是有序的;
    if(end2 >= 0)  //如果数组2还有元素
    {
        while(end2 >= 0)
        {
            nums1[end--] = nums2[end2--];
        }
    }
}

2020062310470442.png


相关文章
|
1月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
1月前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
1月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
1月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
1月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
2天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
77 64
|
11天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
2天前
|
Go
数据结构之 - 深入了解栈数据结构
数据结构之 - 深入了解栈数据结构
12 5
|
11天前
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
11天前
|
前端开发
07_用队列实现栈
07_用队列实现栈