【数据结构】动态顺序表(C语言实现)2

2023-02-10 212

版权

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

简介： 【数据结构】动态顺序表(C语言实现)

3.11 指定下标位置删除

在指定pos下标处删除元素：

void SeqListErase(SL* ps, int pos);

要实现这一功能，我们需要一个begin下标，数据从前往后依次前挪，直到sz-1下标移动完毕。

同样的，该接口也可复用于头删和尾删：

// 头删
void SeqListPopFront(SL* ps)
{
  SeqListErase(ps, 0);
}
// 尾删
void SeqListPopBack(SL* ps)
{
  SeqListErase(ps, ps->sz - 1);
}

3.12 修改

顺序表指定pos下标进行修改：

void SeqListModify(SL* ps, int pos, int x);

要实现这个功能非常简单，只需要判断修改位置是否合法后，直接修改即可。

void SeqListModify(SL* ps, int pos, int x)
{
  assert(ps);
  assert(pos >= 0 || pos <= ps->sz - 1);
  ps->a[pos] = x;
}

3.13 打印

在每次操作后，可以打印出顺序表，观察操作情况：

void SeqListPrint(SL* ps);// 打印

void SeqListPrint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->sz; i++)
  {
    printf("%d ", ps->a[i]);
  }
}

3.14 销毁

当操作执行完毕后，需要销毁顺序表：

void SeqListDestory(SL* ps);

销毁顺序表，只需要把动态开辟的空间释放，指针置空，其他变量置0。

void SeqListDestory(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->sz = ps->capacity = 0;
}

4. 完整代码

SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define N 1000
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList
{
  SLDataType* a;
  int sz;// 表示数组中存储了多少个数据
  int capacity;// 数组实际能存数据的空间容量是多大
}SL;
/*
 * 为什么使用这种命名风格？ 
 * 为了对应C++ STL中的命名风格
 * 方便后续学习STL
 */
// 接口函数
// 接口，就是和别人对接的
void SeqListInit(SL* ps);// 初始化
void SeqListCheckCapacity(SL* ps);// 检查增容
void SeqListPushBack(SL* ps, SLDataType x);// 尾插
void SeqListPopBack(SL* ps);// 尾删
void SeqListPushFront(SL* ps, SLDataType x);// 头插
void SeqListPopFront(SL* ps);// 头删
void SeqListPrint(SL* ps);// 打印
void SeqListDestory(SL* ps);// 销毁
// ...
// 找到了返回x位置下标，没有没到返回-1
int SeqListFind(SL* ps, SLDataType x);// 查找
void SeqListInsert(SL* ps, int pos, SLDataType x);// 指定下标位置插入
void SeqListErase(SL* ps, int pos);// 删除pos位置的数据
void SeqListModify(SL* ps, int pos, int x);// 修改pos位置的数据

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "SeqList.h"
// 初始化
void SeqListInit(SL* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->sz = ps->capacity = 0;
}
// 检查增容
void SeqListCheckCapacity(SL* ps)
{
  assert(ps);
  // 顺序表没有空间or顺序表空间不足
  if (ps->sz == ps->capacity)
  {
    // 没扩容，扩四个整形；空间不足，扩两倍
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    // realloc在起始地址为空指针时，和malloc一样效果
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
}
// 尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
  //assert(ps);
  //SeqListCheckCapacity(ps);// 检查增容
   空间足够，直接在尾部插入
  //ps->a[ps->sz] = x;
  //ps->sz++;
  SeqListInsert(ps, ps->sz, x);
}
// 尾删
void SeqListPopBack(SL* ps)
{
  //assert(ps);
  // 温柔处理
  //if (ps->sz > 0)// 不做出反应
  //{
  //  //ps->a[ps->sz - 1] = 0 ;// 不需要，sz标识顺序表的元素个数
  //  ps->sz--;
  //} 
  // 暴力处理
  //assert(ps->sz > 0);// 直接终止程序，报错
  //ps->sz--;
  SeqListErase(ps, ps->sz - 1);
}
// 头插
void SeqListPushFront(SL* ps, SLDataType x)
{
  //assert(ps);
  //SeqListCheckCapacity(ps);// 检查增容
   挪动数据
  //int end = ps->sz - 1; 
  //while (end >= 0)// 一直挪到0下标
  //{
  //  ps->a[end + 1] = ps->a[end];
  //  end--;
  //}
  //ps->a[0] = x;
  //ps->sz++;
  SeqListInsert(ps, 0, x);
}
// 头删
void SeqListPopFront(SL* ps)
{
  //assert(ps);
  //assert(ps->sz > 0);
   挪动数据
  //int begin = 1;
  //while (begin <= ps->sz - 1)
  //{
  //  ps->a[begin - 1] = ps->a[begin];
  //  begin++;
  //}
  memmove(ps->a, ps->a + 1, (ps->sz - 1) * sizeof(SLDataType));
  //ps->sz--;
  SeqListErase(ps, 0);
}
// 查找
int SeqListFind(SL* ps, SLDataType x)
{
  assert(ps);
  // 只要找到一个就可以
  for (int i = 0; i < ps->sz; i++)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
  }
  return -1;
} 
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  // 温柔处理
  //if (pos > ps->sz || pos < 0)
  //{
  //  printf("pos invaild\n");
  //  return;
  //}
  // 暴力处理
  // 断言表达式为真，相安无事
  // 为假，直接报错
  // 这两个表达式只要有一个不满足条件，便报错
  assert(pos >= 0 && pos <= ps->sz);
  SeqListCheckCapacity(ps);// 检查增容
  int end = ps->sz - 1;
  // 从后往前依次向后挪
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->sz++;
}
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->sz - 1);  
  int begin = pos + 1;
  while (begin < ps->sz)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->sz--;
}
// 修改pos位置的数据
void SeqListModify(SL* ps, int pos, int x)
{
  assert(ps);
  assert(pos >= 0 || pos <= ps->sz - 1);
  ps->a[pos] = x;
}
// 打印
void SeqListPrint(SL* ps)
{
  assert(ps); 
  for (int i = 0; i < ps->sz; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
// 销毁 
void SeqListDestory(SL* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->sz = ps->capacity = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "SeqList.h"
// 测试尾插、尾删
void TestSeqList1()
{
  SL s1;
  SeqListInit(&s1);
  SeqListPushBack(&s1, 1);
  SeqListPushBack(&s1, 2);
  SeqListPushBack(&s1, 3);
  SeqListPushBack(&s1, 4);
  SeqListPushBack(&s1, 5);
  SeqListPrint(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPrint(&s1);
  SeqListPushBack(&s1,6);
  SeqListPushBack(&s1,7);
  // 编译器也是人写的，总会有疏忽的时候
  // 当越界时，可能会检查不出来
  // 只有当销毁时，才会发现错误
  SeqListDestory(&s1);
}
// 测试头插、头删
void TestSeqList2()
{
  SL s1;
  SeqListInit(&s1);
  SeqListPushBack(&s1, 1);
  SeqListPushBack(&s1, 2);
  SeqListPushBack(&s1, 3);
  SeqListPushBack(&s1, 4);
  SeqListPushBack(&s1, 5);
  //SeqListPrint(&s1);
  SeqListPushFront(&s1, 10);
  SeqListPushFront(&s1, 20);
  SeqListPushFront(&s1, 30);
  SeqListPushFront(&s1, 40);// 程序会崩，越界了
  SeqListPrint(&s1);
  SeqListPopFront(&s1);
  SeqListPopFront(&s1);
  SeqListPopFront(&s1);
  SeqListPopFront(&s1);
  SeqListPrint(&s1);
  SeqListDestory(&s1);
}
// 测试指定位置插入
void TestSeqList3()
{
  SL s1;
  SeqListInit(&s1);
  SeqListPushBack(&s1, 1);
  SeqListPushBack(&s1, 2);
  SeqListPushBack(&s1, 3);
  SeqListPushBack(&s1, 4);
  SeqListPushBack(&s1, 5);
  SeqListPrint(&s1);
  SeqListInsert(&s1, 2, 30);
  SeqListPrint(&s1);
  int pos = SeqListFind(&s1, 4);
  if (pos != -1)
  {
    SeqListInsert(&s1, pos, 40);
  }
  SeqListPrint(&s1);
  SeqListInsert(&s1, 0, -1);
  SeqListInsert(&s1, (&s1)->sz, 8);
  SeqListPrint(&s1);
  SeqListDestory(&s1);
}
// 测试指定位置删除
void TestSeqList4()
{
  SL s1;
  SeqListInit(&s1);
  /*
  SeqListInsert可以被头插尾插复用
  */
  SeqListPushBack(&s1, 1);
  SeqListPushBack(&s1, 2);
  SeqListPushBack(&s1, 3);
  SeqListPushBack(&s1, 4);
  SeqListPushBack(&s1, 5);
  SeqListPrint(&s1);
  SeqListPushFront(&s1, 10);
  SeqListPushFront(&s1, 20);
  SeqListPushFront(&s1, 30);
  SeqListPushFront(&s1, 40);
  SeqListPrint(&s1);
  // SeqListErase可以被头删尾删复用
  SeqListErase(&s1, 1);
  SeqListPrint(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPopBack(&s1);
  SeqListPrint(&s1);
  int pos = SeqListFind(&s1, 10);
  if (pos != -1)
  {
    SeqListErase(&s1, pos);
  }
  SeqListPrint(&s1);
}
// 测试指定位置修改
void TestSeqList5()
{
  SL s1;
  SeqListInit(&s1);
  /*
  SeqListInsert可以被头插尾插复用
  */
  SeqListPushBack(&s1, 1);
  SeqListPushBack(&s1, 2);
  SeqListPushBack(&s1, 3);
  SeqListPushBack(&s1, 4);
  SeqListPushBack(&s1, 5);
  SeqListPrint(&s1);
  SeqListModify(&s1, 1, 4);
  SeqListPrint(&s1);
  SeqListDestory(&s1);
}
int main()
{
  //TestSeqList1();
  //TestSeqList2();
  //TestSeqList3();
  //TestSeqList4();
  TestSeqList5();
  return 0;
}

看到这里，相信大家对顺序表、以及它的接口实现也大概了解了。
下篇博客我会为大家带来顺序表的三道OJ题，我们敬请期待~
如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！
我是anduin，一名C语言初学者，我们下期见！

【数据结构】动态顺序表(C语言实现)2

3.11 指定下标位置删除

3.12 修改

3.13 打印

3.14 销毁

4. 完整代码

SeqList.h

SeqList.c

test.c

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【数据结构】动态顺序表(C语言实现)2

3.11 指定下标位置删除

3.12 修改

3.13 打印

3.14 销毁

4. 完整代码

SeqList.h

SeqList.c

test.c

热门文章

最新文章

相关课程

相关电子书