新手向超详细的C语言实现动态顺序表

目录
  • 一、各个函数接口的实现
    • 1.1 不太好‘'李姐‘'的“容量检测函数”
    • 1.2 在任意位置插入的函数"坑!"
    • 1.3 在任意位置删除数据的函数
    • 1.4 其余简单的接口函数
  • 二、顺序表结构体声明与定义
  • 三、头文件的调用

一、各个函数接口的实现

1.1 不太好‘'李姐‘'的“容量检测函数”

对顺序表进行插入数据时,需要判断顺序表的容量是否充足,增加数据的同时需要反复地检测容量,所以推荐直接将以上步骤封装成一个函数。

函数实现算法:若容量大小 == 有效数据大小,则为现有顺序表增容一倍的空间。

但是需要注意的是:初始顺序表后,容量为0,则需开辟4个有效数据的空间。

void SeqListCheckCapacity(SLT* psl)
{
 assert(psl);
 if (psl->size == psl->capacity)
 {
  size_t newcapacity = psl->capacity == 0 ? 4 : (psl->capacity) * 2;
  psl->a = (SQDatatype*)realloc(psl->a, sizeof(SQDatatype) * newcapacity);
  psl->capacity = newcapacity;
 }
}

1.2 在任意位置插入的函数"坑!"

算法实现:首先检测容量,再通过想要插入的下标找到位置,将包括该下标的元素以及其后的所有元素往后挪一步,最后在该下标位置放入数据。

void SeqListInsert(SLT* psl, size_t pos, SQDatatype x)
{
 assert(psl);
 assert(pos >= 0 && pos <= psl->size);
 SeqListCheckCapacity(&psl);
 int end = psl->size - 1;
 while (end >= pos)
 {
  psl->a[end + 1] = psl->a[end];
  end--;
 }
 psl->a[pos] = x;
 psl->size++;
}

考虑到下标pos一定是个非负整数,故使用size_t类型。

如果利用该函数进行头插,即pos == 0;在while循环的最后一步,即end == pos时,end--后end变成-1,再回到while循环的判断条件时,end会出现整形提升的情况,即-1变成无符号整形,约为21亿。

end出现整形提升的原因在于pos是size_t类型。

解决方法就是保证while循环中和pos比较的式子为非负数即可。

void SeqListInsert(SLT* psl, size_t pos, SQDatatype x)
{
 assert(psl);
 assert(pos >= 0 && pos <= psl->size);
 SeqListCheckCapacity(psl);
 int end = psl->size;
 while (end >= pos + 1)
 {
  psl->a[end] = psl->a[end - 1];
  end--;
 }
 psl->a[pos] = x;
 psl->size++;
}

1.3 在任意位置删除数据的函数

算法思路:把指定元素之后的所有元素全部向前挪动一步。

void SeqListErase(SLT* psl, size_t pos)
{
 assert(psl);
 assert(pos >= 0 && pos < psl->size);
 size_t begin = pos;
 if (begin == psl->size - 1)
 {
  psl->size--;
  return;
 }
 while (begin < psl->size - 1)
 {
  psl->a[begin] = psl->a[begin + 1];
  begin++;
 }
 psl->size--;
}

上述代码中if条件语句用于判断是否为尾删。

注意:避免负数与无符号数通过操作符连接,避免有符号数变成负数后被整型提升为无符号数或者强制转换。

1.4 其余简单的接口函数

初始化函数

void SeqListInit(SLT* psl)
{
 assert(psl);
 psl->a = NULL;
 psl->capacity = psl->size = 0;
}

销毁函数

void SeqListDestory(SLT* psl)
{
 assert(psl);
 if (psl->a)
 {
  free(psl->a);
  psl->a = NULL;
 }
 psl->capacity = psl->size = 0;
}

打印函数

void SeqListPrint(SLT* psl)
{
 assert(psl);
 int i = 0;
 for (i = 0; i < psl->size; i++)
 {
  printf("%d ", psl->a[i]);
 }
 printf("\n");
}

尾插

void SeqListPushBack(SLT* psl, SQDatatype x)
{
 assert(psl);
 SeqListCheckCapacity(psl);
 psl->a[psl->size] = x;
 psl->size++;
}

头插

void SeqListPushFront(SLT* psl, SQDatatype x)
{
 assert(psl);
 SeqListCheckCapacity(psl);
 int i = 0;
 for (i = psl->size - 1; i >= 0; i--)
 {
  psl->a[i + 1] = psl->a[i];
 }
 psl->a[0] = x;
 psl->size++;
}

尾删

void SeqListPopBack(SLT* psl)
{
 assert(psl);
 psl->size--;
}

头删

{
 assert(psl);
 assert(psl->size > 0);
 int begin = 0;
 while (begin < psl->size - 1)
 {
  psl->a[begin] = psl->a[begin + 1];
  begin++;
 }
 psl->size--;
}

通过数据查找下标

int SeqListFind(SLT* psl, SQDatatype x)
{
 assert(psl);
 int begin = 0;
 while (begin < psl->size)
 {
  if (x == psl->a[begin])
   return begin;
  begin++;
 }
 return -1;
}

二、顺序表结构体声明与定义

typedef int SQDatatype;

重定义可方便以后更换元素类型时修改

typedef struct SeqList
{
 SQDatatype* a;
 int size;
 int capacity;
}SLT;

重定义可以让定义结构体对象(变量)时,免去代码的冗余。

如struct SeqList s1;可修改为SLT s1;

三、头文件的调用

  • #include<stdio.h>标准输入输出
  • #include<assert.h>断言错误,避免空指针对程序的影响
  • #include<stdlib.h>动态函数

到此这篇关于新手向超详细的C语言实现动态顺序表的文章就介绍到这了,更多相关C语言动态顺序表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现动态顺序表的实现代码

    C语言实现动态顺序表的实现代码 顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 静态实现:结构体内部只需两个成员,其中一个为固定大小(MAX)的数组,用来存放我们的数据.数组大小我们可以通过在头文件中改变MAX的值来改变. 动态实现:在内存中开辟一块空间,可以随我们数据数量的增多来扩容. 来看看动态的顺序表实现: 1.seqli

  • C语言实现动态顺序表详解

    目录 什么是顺序表? 1. 定义顺序表结构体: 2. 初始化顺序表: 3. 销毁顺序表: 4. 打印顺序表: 5. 判断容量+扩容: 6. 头插数据: 7. 尾插数据: 8. 指定下标位置插入数据: 9. 删除数据: 10. 尾删数据: 11. 指定下标位置删除数据: 12. 查找数据: 13. 修改数据: 14. 源代码: 1. SeqList.h: 2. SeqList.cpp: 3. test.cpp: 15. 测试: 总结 什么是顺序表? 顺序表是在计算机内存中以数组的形式保存的线性表,

  • 新手向超详细的C语言实现动态顺序表

    目录 一.各个函数接口的实现 1.1 不太好''李姐''的"容量检测函数" 1.2 在任意位置插入的函数"坑!" 1.3 在任意位置删除数据的函数 1.4 其余简单的接口函数 二.顺序表结构体声明与定义 三.头文件的调用 一.各个函数接口的实现 1.1 不太好''李姐''的"容量检测函数" 对顺序表进行插入数据时,需要判断顺序表的容量是否充足,增加数据的同时需要反复地检测容量,所以推荐直接将以上步骤封装成一个函数. 函数实现算法:若容量大小 ==

  • C语言实现动态顺序表的示例代码

    目录 顺序表概念及结构 基本操作 功能实现 程序运行 顺序表概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改. 分类: 一般分为静态顺序表和动态顺序表: 静态顺序表:数组大小是固定的用完了无法增容:同时我们无法控制给数组开多少空间合适,开少了,空间不够:开多了,有回会存在空间浪费: 动态顺序表:空间是可以变动的,空间满了我们就增容:解决了静态顺序表的空间不足问题,同时也在一定程度上减少了空间浪费: 因此本篇博客主要实现

  • 超详细分析C语言动态内存管理问题

    目录 一.为什么存在动态内存的分配 二.动态内存函数的介绍 2.1 malloc和free 2.2 calloc 2.3 realloc 三.常见的动态内存错误 3.1 对NULL指针的解引用操作 3.2 对动态开辟空间的越界访问 3.3 对非动态开辟内存使用free释放 3.4 对同一块动态内存多次释放 3.5 动态开辟内存忘记释放(内存泄漏) 四.几个经典的笔试题 五.C/C++程序的内存开辟 六.柔性数组 6.1 柔性数组的特点 6.2 柔性数组的使用 6.3 柔性数组的优势 上期结束了[

  • C语言实现静态顺序表的实例详解

    C语言实现静态顺序表的实例详解 线性表 定义一张顺序表也就是在内存中开辟一段连续的存储空间,并给它一个名字进行标识.只有定义了一个顺序表,才能利用该顺序表存放数据元素,也才能对该顺序表进行各种操作. 接下来看看静态的顺序表,直接上代码: SeqList.h #define _CRT_SECURE_NO_WARNINGS 1 #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include <stdio.h> #include <stdlib.h&g

  • C语言数据结构之顺序表和单链表

    一.顺序表的创建.删除和插入 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> struct sqlist { int date[10]; int length; }; void InitList(sqlist& L) { for (int i = 0;i < 10;i++) { L.date[i] = 0; } L.length = 0; } void charu(sqlist& L) { for (int j =

  • C语言动态顺序表实例代码

    目录 顺序表概念: 一.准备工作 二.顺序表的基本操作  1.顺序表的初始化函数 2.尾插函数(在尾部插入数据) 3.头插函数(在数组头部插入数据)  4.尾删函数 5.头删函数 6.在第pos的位置插入数据 7.删除第pos个位置的数据 8.修改第pos个位置的数据 9.查找函数. 10.销毁函数 11.打印函数 三.总代码: 顺序表概念:         顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构.一般情况下用数组存储.在数组上完成数据的增删查改. 代码解析: 一.准备工

  • C语言深入浅出讲解顺序表的实现

    目录 1.线性表 2.顺序表 2.1 概念及结构 2.2 提供接口 2.3 接口实现 今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表. 1.线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表.链表.栈.队列.字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 2.顺序表

  • C语言全面讲解顺序表使用操作

    目录 一.顺序表的结构定义 二.顺序表的结构操作 1.初始化 2.插入操作 3.删除操作 4.扩容操作 5.释放操作 6.输出 三.示例 编程环境为 ubuntu 18.04. 顺序表需要连续一片存储空间,存储任意类型的元素,这里以存储 int 类型数据为例. 一.顺序表的结构定义 size 为容量,length 为当前已知数据表元素的个数 typedef struct Vector{ int *data; //该顺序表这片连续空间的首地址 int size, length; } Vec; 二.

随机推荐