C语言数据结构之连续存储数组的算法

2024-03-02 11:23:11

数据结构之数组定义及基本操作

　　数据结构中最基本的一个结构就是线性结构，而线性结构又分为连续存储结构和离散存储结构。所谓的连续存储结构其实就是数组。

　　数组本质其实也是数据的一种存储方式，既然有了数据的存储，就会涉及到如何对数据进行寻址的问题。首先，先说一下在数组中数据是如何存储的，在内存中，数组中的数据是以一组连续的数据集合的形式存在于内存中。当我们访问存在于内存中的数组时，我们应该找到其在内存中的地址，当我们找到数据的地址后我们就可以找到对应的数据。了解了以上知识后，我们就可以进行数组的设计了（我们就可以设计自己的数组供别人去使用了，哈哈）。

　　了解了以上知识后，第一个问题就来了，如何才能找到数据在内存中的地址？这个问题其实很简单，因为数组在内存中是一组连续的数据集合，所以我们只要知道数组首地址，然后通过对应字节长度的加减就可以找到对应字节数的数据，有了这些就可以定义出我们的数组，但是，作为一个合理的数组，还应该有数组长度的标志len和数组有效元素的标志cnt。由此给出对数组的定义（本例中采用结构体，对结构体不了解的朋友可以去查一下）

struct Arr
{
  int *pBase; //存储的是数组的第一个元素的地址
  int len; //数组所能容纳的最大元素的个数
  int cnt; //数组有效元素的个数  

};

上述代码定义了一个struct Arr的结构体，这个结构体就是一个数组，其中有存储数组元素中首地址的成员，有存储数组长度和数组有效元素个数的成员。

　　有了对结构体的定义之后，就应该涉及到对数组的基本操作，包括数组的初始化，判断数组是否为空，对数组进行显示，判断数组是否已满，对数组的最后追加一个元素，对数组元素的插入。其中，主要的算法就是对数组元素的插入，插入算法的核心就是首先应该先将被插入及插入位置之后的元素后移，然后将空出来的位置插入我们要插入的元素。一下给出c语言的实现：

/*
数组初始化函数
初始化仅仅是给出一个具有一定长度的数组，但是数组中没有有效值
*/
void init_arr(struct Arr * pArr,int len)
{
  pArr->pBase=(int *)malloc(sizeof(int)*len);
  if(NULL==pArr->pBase){
    printf("动态内存分配失败");
    exit(-1); //终止整个程序
  }
  else{
    pArr->len=len;
    pArr->cnt=0;
  }
}

/*
判断数组是否为空的函数
*/
int is_empty(struct Arr * pArr){
  if(pArr->cnt==0){
    return 0;  //0代表true
  }
  else{
    return 1;  //1代表false
  }
}

/*
数组输出显示函数
在进行数组输出时，首先应该判断数组是否为空
*/
void show_arr(struct Arr * pArr){
  if(is_empty(pArr)==0){
    printf("当前数组为空！");
  }
  else{
    int i;
    for(i=0; i<pArr->cnt; ++i){
      printf("%d  ",pArr->pBase[i]);
    }
    printf("\n");
  }
}

/*
判断数组是否已满的函数
*/
int is_full(struct Arr * pArr){
  if(pArr->cnt==pArr->len){
    return 0; //0代表true，表示已满
  }
  else{
    return 1; //1代表false，表示未满
  }
}

/*
在数组的最后追加一个元素
在追加数组元素前要判断当前数组是否已满，已满时不允许追加新的元素
*/
int append_arr(struct Arr *pArr,int val){
  if(is_full(pArr)==0){
    return 0;
  }
  else{
    pArr->pBase[pArr->cnt]=val;
    pArr->cnt++;
    return 1;
  }
}

/*
在数组的指定位置插入元素
插入算法：首先将被插入位置的元素全部后移，然后再将空出来的位置插入。
根据算法原理，所以，在插入的时候应该检查数组是否已满。
上述两种情况均合理时，进行数据的插入，插入时，若插入第三个位置，实际是将数据赋值给arr[pos-1]
注意：再将插入位置后的元素后移时，应该从后向前移动。否则，将会造成“被移到”的位置的值被覆盖
*/
int insert_arr(struct Arr *pArr,int pos,int val){
  if(is_full(pArr)==0){
    return 0; //0表示当前数组已满，无法再进行插入
  }
  //在数组可插入的情况下，应该检查用户输入的pos位置值是否合理
  if(pos<0||pos>(pArr->len)){
    return 1; //1表示当前用户插入位置不合法
  }
  //移动位置
  int i;
  for(i=pArr->cnt  -1;i>=pos-1;--i){
    pArr->pBase[i+1]=pArr->pBase[i];
  }
  //空缺位置插入元素
  pArr->pBase[pos-1]=val;
  return 2; //2表示当前插入成功
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

数据结构之数组Array实例详解

数据结构之数组Array实例详解数组Array 基本操作 Status InitArray(int dimm,...)//若维数dim和随后的各维长度合法,则构造相应的数组A,并返回OK Status DestroyArray() //销毁数组A Status Locate(va_list ap,int &off) //若ap指示的各下标值合法,则求出该元素在A中相对地址off Status Value(ElemType &e,...) //A是n维数组,e为元素变量,随后是n个下标值.
数据结构之数组翻转的实现方法

数据结构之数组翻转的实现方法以下为实现数组翻转的方法: 1.用c语言实现的版本 #include<stdio.h> #define M 20 void fun(int *x,int n) { int *i, *j, *p, m=n/2; i = x; j = x+n-1; p = x+m; for( ; i<p; ++i,--j) { int t = *i; *i = *j; *j = t; } } void main() { int i,a[M],n; printf("En
C++ 数据结构线性表-数组实现

C++ 数据结构线性表-数组实现线性表的数组实现,实现几个核心的功能,语言是C++,如果有更好的想法和意见,欢迎留言~~~ /* Author : Moyiii * 线性表的数组实现,仅作学习之用,当然如果 * 你想拿去用,随你好啦. */ #include<iostream> using namespace std; //顺序表 class SeqList { public: //构造函数,接受一个默认的列表大小 SeqList(int size = MAX_LIST_SIZE); //析
Java数组模拟优先级队列数据结构的实例

优先级队列如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先
C语言数据结构之顺序数组的实现

C语言数据结构之顺序数组的实现以下为展示顺序数组的示例: 1.用C语言实现的版本 #include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<math.h> /* floor(),ceil(),abs() */ #include<stdlib.h> /*申请和释放内存*/ #include<stdarg.h> /*可变参数*/ #define OK 1 //成功标志 #define ERROR 0 //错误标志 #d
JavaScript数据结构之数组的表示方法示例

本文实例讲述了JavaScript数据结构之数组的表示方法.分享给大家供大家参考,具体如下: 数组类似于线性表.基本上每种语言都会讲数组作为固有类型.这里主要讲一下二维数组.我们可以把二维数组看成这样一个定长线性表:它的每个数据元素也是一个定长的线性表.数组一旦被定义,它的维数和维界就不再改变.因此,除了结构的初始化和销毁之外,数组只有存取元素和修改元素值的操作(这里注意和JavaScript中的array类型做出区分,这里说的是数据结构,而不是某一种单独语言的语法). 由于数组一般不作插入或者
PHP中使用数组实现堆栈数据结构的代码

在堆栈中,最后压入的数据(进栈),将会被最先弹出(出栈). 即在数据存储时采用"先进后出"的数据结构. PHP中,将数组当做一个栈,主要是使用array_push()和array_pop()两个系统函数来完成. 入栈主要是利用array_push()函数向第一个参数的数组尾部添加一个或多个元素,然后返回新数组的长度,示例如下: 复制代码代码如下: <?php $zhan=array("WEB");//声明一个数组当做栈 array_push($zhan,&q
C语言数据结构之连续存储数组的算法

数据结构之数组定义及基本操作数据结构中最基本的一个结构就是线性结构,而线性结构又分为连续存储结构和离散存储结构.所谓的连续存储结构其实就是数组. 数组本质其实也是数据的一种存储方式,既然有了数据的存储,就会涉及到如何对数据进行寻址的问题.首先,先说一下在数组中数据是如何存储的,在内存中,数组中的数据是以一组连续的数据集合的形式存在于内存中.当我们访问存在于内存中的数组时,我们应该找到其在内存中的地址,当我们找到数据的地址后我们就可以找到对应的数据.了解了以上知识后,我们就可以进行数组的设计了(
C语言数据结构之数组模拟实现顺序表流程详解

目录线性表和顺序表线性表顺序表静态顺序表动态顺序表代码已经放在Gitee上,需要可以小伙伴可以去看看用C语言数组模拟实现顺序表 Gitee 线性表和顺序表线性表线性表(linear list)是n个具有相同特性的数据元素的有限序列,这是我们广泛使用的数据结构. 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 常见的线性表:顺序表.链表.栈.队列.字符串- 顺序表顺序表是用一段物理地址连
C语言数据结构之单链表存储详解

目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一
C语言数据结构之线性表的链式存储结构

1.什么是线性表的链式存储结构 -链表存储结点:包括元素本身的信息,还有元素之间的关系逻辑的信息这个结点有:数据域和指针域一个指针域:指向后继结点, 单链表二个指针域: 指向前继结点,还有一个指向后继结点双链表 2.原理是: s=(LinkNode *)malloc(sizeof(LinkNode));// s->data=e; //这里赋值了 s->next=p->next; // p->next=s; //这里把指针s给到了p 结点a-> 结点b -> 结
C语言数据结构进阶之栈和队列的实现

目录栈的实现: 一.栈的概念和性质二.栈的实现思路三.栈的相关变量内存布局图四.栈的初始化和销毁五.栈的接口实现: 1.入栈 2.出栈 3.获取栈顶的数据 4.获取栈的元素个数 5.判断栈是否为空队列的实现: 一.队列的概念和性质二.队列的实现思路三.队列相关变量的内存布局图四.队列的初始化和销毁五.队列的接口实现: 1. 入数据 2.出数据 3.取队头数据 4.取队尾数据 5.获取队列元素个数 6.判断队列是否为空总结栈的实现: 一.栈的概念和性质栈(stack)又名
C语言数据结构线性表教程示例详解

目录线性表顺序表线性表数据结构里我们时常看到什么什么表,线性表是最基本.最简单.也是最常用的一种数据结构,其他各种表的万恶之源就是这个线性表,他是个啥其实顾名思义: 一个线性表是n个具有相同特性的数据元素的有限序列.数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部.比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点). 说的这么复杂其实就是
C语言数据结构深入探索顺序表

目录 1.线性表 2.顺序表 2.1概念及结构 2.2 接口实现 2.2.1初始化 2.2.2 检查容量 2.2.3 顺序表打印 2.2.4 顺序表尾插 2.2.5 顺序表尾删 2.2.6 顺序表头插 2.2.7 顺序表头删 2.2.8 顺序表在pos位置插入x 2.2.9 顺序表删除pos位置的值 2.2.10 尾插.尾删.头插.头删的改进 2.2.11 顺序表查找 2.2.12 顺序表销毁 2.3 数组相关面试题 2.4 顺序表的问题及思考 1.线性表线性表(linear list)是n个
C语言数据结构二叉树之堆的实现和堆排序详解

目录一.本章重点二.堆 2.1堆的介绍 2.2堆的接口实现三.堆排序一.本章重点堆的介绍堆的接口实现堆排序二.堆 2.1堆的介绍一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树. 但要满足每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆. 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆. 那么以下就是一个小堆. 百度百科: 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆. 若将和此次序列对应的一维数
C语言详细讲解树状数组与线段树

目录树状数组动态求连续区间和数星星线段树动态求连续区间和数列区间最大值树状数组动态求连续区间和给定 n 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列 [a,b] 的连续和. 输入格式第一行包含两个整数 n 和 m,分别表示数的个数和操作次数. 第二行包含 n 个整数,表示完整数列. 接下来 m 行,每行包含三个整数 k,a,b (k=0,表示求子数列[a,b]的和:k=1,表示第 a 个数加 b). 数列从 1 开始计数. 输出格式输出若干行数字,表示 k

C语言 数据结构之连续存储数组的算法

相关推荐

随机推荐

C语言数据结构之连续存储数组的算法