首页 > 其他分享 >数据结构应用题

数据结构应用题

时间:2022-10-02 11:00:10浏览次数:58  
标签:存储 应用题 元素 矩阵 三角区 数组 对角线 数据结构

数据结构应用题

数组应用题

数组的存储结构

一维数组

A[0...n-1]为例,存储关系

\[LOC(ai)=LOC(a0)+(i)×L(0≤i<n) \]

L是每个数组元素所占存储单元

多维数组

对于多维数组,有两种映射方法:按行优先按列优先

以二维数组为例,按行优先存储的基本思想是:先行后列。
先存储行号较小的元素,行号相等先存储列号较小的元素。
设二维数组行下标与列下标的范围分别为

\[[l1,h1],[l2,h2] \]

,则存储结构关系式为:

\[LOC(a i,j ​ )=LOC(a l 1 ​ ,l 2 ​ ​ )+[(i−l 1 ​ )×(h 2 ​ −l 2 ​ +1)+(j−l 2 ​ )]×L \]

若l1 l2均为0,则上式变成

\[LOC(a i,j ​ )=LOC(a 0,0 ​ )+[i×(h 2 ​ +1)+j)]×L \]

矩阵压缩存储

压缩存储:指为多个值相同的元素只分配一个存储空间,对零元素不分配存储空间。其目的是为了节省存储空间。

特殊矩阵:指具有许多相同矩阵元素或零元素,并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。

对称矩阵

任意一个n阶方阵A的任意元素aij=aji,则称为一个对称矩阵。
对于n nn阶方阵,其中的元素可以划分为3个部分,即上三角区、主对角线和下三角区
对称矩阵上下三角区元素相同,因此存放在一维数组

\[B[n(n+1)/2] \]

中,及aij存放在bk中,只存放主对角线和下三角区(或上三角区)

采用行优先存储,存放主对角线和下三角区在这里插入图片描述

若数组下标从0开始,则在数组B中的下标为

\[k=1+2+3+...+(i-1)+(j-1)=i(i-1)/2+j-1 \]

因此元素下标对应关系

image-20221002001057595

若存放主对角线和上三角区

在这里插入图片描述

\[k = n + ( n − 1 ) + . . . + ( n − i + 2 ) + ( j − i ) = ( i − 1 ) ( 2 n − i + 2 ) / 2 + j − i \]

image-20221002001047582

三角矩阵

除了对角线外和上/下三角区,其余的元素都相同

压缩策略:按行优先原则,将三角区和主对角线元素存入一维数组,并在最后一个位置存放常量C

下三角:

image-20221002001039120

上三角:

image-20221002001031251

三对角矩阵

\[∣i−j∣>1时,有Aij=0,呈带状 \]

image-20221002001020997

存储策略:只存储主对角线及其上、下两侧次对角线上的元素外,其他零元素一律不存储。

需要用一个一维数组B 来存储三对角矩阵中位于三对角线上的元素。同样要区分两种存储方式:即行优先方式和列优先方式。

行优先:在这里插入图片描述

那么数组B中,位于Aij(i<=j),前边的元素个数为

\[k = 2 + 3 ( i − 2 ) + j − i + 1 = 2 i + j − 3 (数组下标从0开始) \]

于是有image-20221002001223950对于i的求法,详细如下

\[\begin{align} &前i-1行有3(i-1)+1个元素\\ &前i行共有3i-1个元素\\ &B数组下标为k的元素是第k+1个\\ &3(i-1)+1<k+1<=3i-1\\ &即3(i-1)+1<=k<3i-1\\ &i=⌊(k+1)/3+1⌋ \end{align} \]

标签:存储,应用题,元素,矩阵,三角区,数组,对角线,数据结构
From: https://www.cnblogs.com/cs-gzh/p/16748417.html

相关文章

  • 高级算法/数据结构
    AhoCorasick自动机用于多模式字符串匹配。可持久化线段树利用前缀和思想求区间第k小等不易直接求出的值。后缀数组Manacher求最长回文串。......
  • 数据结构 字符串 (第6天)
    这里的三题都和字符出现次数有关,可以用​​dict​​​或​​Counter​​​来轻松解决。和​​​ditc​​​相关的可以参照文档​​docscollections​​​,里面比较常用......
  • 数据结构与算法【Java】08---树结构的实际应用
    前言数据data结构(structure)是一门研究组织数据方式的学科,有了编程语言也就有了数据结构.学好数据结构才可以编写出更加漂亮,更加有效率的代码。要学习好数据结构就......
  • 王道-数据结构-插入排序
    插入排序分为直接插入和折半插入排序直接插入排序折半插入排序1.算法思想用我自己的话说:一开始选中第二个元素,然后把之前的元素看做已经是排好序的,然后一直对......
  • PTA 21级数据结构与算法实验5—树和二叉树
    目录7-1还原二叉树7-2朋友圈7-3修理牧场7-4玩转二叉树7-5根据后序和中序遍历输出先序遍历7-6完全二叉树的层序遍历7-7列出叶结点7-8部落7-9建立与遍历二叉树7-10......
  • linux C 开发中重要的数据结构——结构体
    在linux的驱动开发中,最常用的,也最重要的数据结构是结构体,它也最容易使人混淆。要掌握结构体,首先要弄明白运算符的优先级:在所有运算符中,下面4个运算......
  • 数据结构与算法(数组&二维数组)
    数组集合、列表和数组集合:一个或多个元素构成的整体,里面的元素类型不一定相同,且是无序的列表:又称线性列表,有顺序且长度是可变的,没有索引有顺序,可以增删改数组:列表的实......
  • 数据结构学习——BST删除特定节点
    BST删除特定节点前言一个平常的星期三晚上,一节通选课中,在老师放的视频和极寒空调的折磨之下,想着做点别的什么的我,打开了博客园。想起来做题下午数据结构课中老师最后在......
  • 数据结构重点知识汇总
    1线性表的合并(编程题)1.1有序表的合并算法步骤:创建表长为m+n的空表LC。指针pc初始化,指向LC的第一个元素。指针pa和pb初始化,分别指向LA和LB的第一个元素。当指针pa和pb均为......
  • 把两个数据结构相同的数组(数组下有n个对象)合并成一个数组
    数据拼接有一个数组letarr1=[{name:''lili",age:14},{name:''小明",age:16},{name:''张三",age:24},]letarr2=[{class:"初一二班",gender:"0"},{class:"初......