首页 > 编程语言 >06 数组与广义表 | 数据结构与算法

06 数组与广义表 | 数据结构与算法

时间:2022-10-18 19:58:40浏览次数:60  
标签:06 广义 int 元素 矩阵 算法 数组 数据结构 col

1. 数组

1. 数组的定义

  1. 数组:数组 是一组偶对(下标值,数据元素值)的集合。在数组中,对于一组有意义的下标,都存在一个与其对应的值。一维数组对应着一个下标值,二维数组对应着两个下标值
  2. 数组的特点
    1. 是由\(n(n>1)\)个具有相同数据类型的数据元素a1a2,...,an组成的有序序列,且该序列必须存储在一块地址连续的存储单元中
    2. 数组是一种随机存取结构,给定一组下标,就可以访问与其对应的数据元素
    3. 数组中的数据元素个数是 固定
  3. 直观的 \(n\) 维数组:以二维数组为例,将二维数组看成是一个定长的线性表,其每个元素又是一个定长的线性表

2. 数组的存储形式

  1. 存储形式:由于计算机的内存结构是一维的,因此用一维内存来表示多维数组,就必须按某种次序将数组元素排成一列序列,然后将这个线性序列存放在存储器中。由于对数组一般不做插入和删除操作,也就是说,数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化。因此,一般都是采用顺序存储的方法来表示数组
  2. 存储方式
    1. 行优先顺序:将数组元素按行排列,第i+1个行向量紧接在第i个行向量后面。以二维数组为例,按行优先顺序存储的线性序列为:\(a_{11},a_{12},\dots,a_{1n},a_{21},a_{22},\dots,a_{2n},\dots,a_{m1},a_{m2},\dots,a_{mn}\)
    2. 列优先顺序:将数组元素按列向量排列,第j+1个列向量紧接在第j个列向量之后,A的m × n个元素按列优先顺序存储的线性序列为:\(a_{11},a_{21},\dots,a_{m1},a_{12},a_{22},\dots,a_{m2},\dots,a_{1n},a_{2n},\dots,a_{nm}\)

2. 矩阵的压缩存储

1. 对称矩阵

  1. 特点:\(a_{ij}=a_{ji}\),因此只需要对 \(\frac{n(n+1)}{2}\) 个元素进行存储image

  2. 对称矩阵元素\(a_{ij}\)保存在原数组中时的下标值k与(i,j)之间的对应关系

    1. \(k = \frac{i\times (i - 1)}{2}+j-1,i \ge j\)
    2. \(k = \frac{j\times (j - 1)}{2}+i - 1, i < j\)

2. 三角矩阵

  1. 特点:三角部分有数字,其余为0

    1. 下三角:image

    2. 上三角:image

  2. 对应关系

    1. 下三角:\(k = \frac{i\times (i - 1)}{2}+j-1,i \le j\)
    2. 上三角:\(k = \frac{i\times (i - 1)}{2}+j-1,i \ge j\)

3. 稀疏矩阵 的压缩

  1. 特点若一个m×n的矩阵含有t个非零元素,且 t 远远小于m×n,则我们将这个矩阵称为稀疏矩阵image

  2. 压缩形式:三元组表示法 (i, j, val) ,其中 ij分别表示行号列号,val 表示数值,且以行优先存放

  3. 稀疏矩阵 快速转置 算法

    1. 本质:记录要存放的位置
    2. 算法
      // the matrix is m * n size;
      // origin is Original tripletable
      // ans is the transposed matrix's tripletable
      /*
         stuct Triple{
            int i, j, val;
            Triple(int i, int j, int val):i(i),j(j),val(val){}
         };
      */
      void FastTransposeMatrix(vector<Triple> origin, vector<Triple> ans){
         vector<int> nums(n, 0); //统计矩阵每列非零元素的个数
         vector<int> pos(n, 0);  //统计矩阵每列第一个非零元素的位置
         for(int col = 0; col < n; ++col) 
            ++num[origin[col].j];
         pos[0] = 1;
         for(int col = 1; col < n; ++col)
            pos[col] = pos[col - 1] + num[col - 1];
         for(int idx = 0; idx < n; ++idx){
            int col = origin[idx].j;
            int nowPos = pos[col];
            ans[nowPos].i = origin[idx].j;
            ans[nowPos].j = origin[idx].i;
            ans[nowPos].val = origin[idx].val;
            ++pos[col]; //更新每列第一个元素的位置
         }
      }
      

3. 广义表

  1. 定义:广义表(\(List\),又称为列表):是由\(n(n\ge 0)\)个元素组成的有穷序列: Lst = (a1, a2, ..., an)其中ai或者是原子项,或者是一个广义表,\(n\)为它的长度。若 ai 是广义表,则称为 子表
  2. 与线性表的区别:线性表的数据元素都是 相同 的数据类型,但是广义表的数据元素可以还是广义表
  3. 性质
    1. 层次性:广义表可以是一个多层次的结构
    2. 共享性:一个广义表可以被其他广义表所共享
    3. 递归性:广义表可以是本身的子表
  4. 概念
    1. 广义表的长度:广义表中元素的数目
    2. 表头:非空广义表的 第一个元素
    3. 表尾:除表头元素之外,其余元素构成的 广义表
    4. 深度:广义表中括号的重数
      List 长度 表头 表尾 深度
      A = () 0 无定义 无定义 1
      B = (e) 1 e () 2
      C = (a, (b, c, d)) 2 a ((b, c, d)) 2
      D = ((), e, (a, (b, c, d))) 3 () (e, (a, (b, c, d))) 3
      E=(a, E) 2 a (E) \(\infty\)

标签:06,广义,int,元素,矩阵,算法,数组,数据结构,col
From: https://www.cnblogs.com/RadiumGalaxy/p/16803849.html

相关文章

  • Dubbo——时间轮(Time Wheel)算法应用
    定时任务Netty、Quartz、Kafka以及Linux都有定时任务功能。 JDK自带的java.util.Timer和DelayedQueue可实现简单的定时任务,底层用的是堆,存取复杂度都是O(nlog(......
  • Problem P34. [算法课分支限界法]硬币问题
    根据题目可以联想到无限个数物品的背包问题,dp[j]表示能组合为j的个数是多少,外层i循环是遍历表示加入第i个数之后的状态,因为是无限个数,所以内层循环是正序遍历,加了......
  • vue源码分析-diff算法核心原理
    这一节,依然是深入剖析Vue源码系列,上几节内容介绍了VirtualDOM是Vue在渲染机制上做的优化,而渲染的核心在于数据变化时,如何高效的更新节点,这就是diff算法。由于源码中关于d......
  • 数据结构——————排序算法代码实现(未完待续......)
    排序算法插入排序折半插入排序希尔排序冒泡排序快速排序简单选择排序堆排序归并排序(未完成)基数排序(未完成)#include<bits/stdc++.h>usingnamespacestd;constintMAXN......
  • 数据结构作业(2018/10/10)
    1.基本的a+b(+-*/%)#include<bits/stdc++.h>usingnamespacestd;intmain(){inta,b;charch;intans;scanf("%d%d%c",&a,&b,&ch);......
  • 链表实现队列——————数据结构作业
    作业code2:-仿照作业code1的功能,将课本上链表的实现队列能完整实现-需要通过main函数调用并能进行友好的人机交互输入​​作业code1​​链表实现队列的代码:#include<bits/......
  • HDU 3068 最长回文——————Manacher
    最长回文TimeLimit:4000/2000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):30806AcceptedSubmission(s):11310ProblemDescrip......
  • 数据结构作业的代码——————栈的顺序实现
    作业code1:将上课给的顺序表形式实现栈的程序补充(代码已发给大家):实现通过键盘进行插入实现通过键盘进行删除良好的人机交互发的代码:#include<stdio.h>#include<malloc.h>t......
  • 矩阵还原——————数据结构作业
    /*给定一个一维数组,将其转化为对称矩阵(关于主对角线对称)*/#include<stdio.h>#include<string.h>constintMAXN=1e3;intmat[MAXN][MAXN];inta[MAXN];in......
  • 数据结构作业的代码——————栈的链式实现
    作业code2:仿照作业​​code1​​的功能,将课本上链表的实现栈的功能完整实现需要通过main函数调用并能进行友好的人机交互输入#include<bits/stdc++.h>#define#define#defin......