请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

稀疏数组、队列的概念与实践

[复制链接]
查看: 15|回复: 0

2万

主题

2万

帖子

7万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
75461
发表于 2020-9-17 02:50 | 显示全部楼层 |阅读模式
目录

一、前言

数据结构包括:线性结构和非线性结构。
1.1 线性结构


  • 线性结构是最常见的数据结构,其特点是数据元素与下标之间存在一一对应的关系;
  • 线性结构有两种不同的存储结构,即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的的线性表称为顺序表,顺序表中存储的数据在存储空间上是连续的;链式存储的线性表称为链表,链表中的数据在存储空间上不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。
  • 线性结构常见的有:数组、队列、链表和栈。
1.2 非线性结构


  • 非线性结构包括:二维数组、多维数组、广义表、图结构和树结构。
二、稀疏数组的概念与实践

当一个二维数组存在大量无意义的数据时,可以选择稀疏数组来保存该数组。
2.1 实际需求

在五子棋程序的实现中,存在存盘退出和续上盘的功能。
我的关键词 稀疏数组、队列的概念与实践  新闻咨询 1527720-20200418132723657-1342307576

因为该二维数组的默认值是0,因此记录了很多没有意义的数据,故可以使用稀疏数组来保存该数组。
2.2 基本介绍

2.2.1 稀疏数组的处理方式是


  • 记录数组有几行、几列,有多少个不同的值;
  • 把具有不同值得元素的行列及值记录在一个小规模的数组中,从而实现缩小二维数组的规模。
2.2.2 应用举例

我的关键词 稀疏数组、队列的概念与实践  新闻咨询 1527720-20200418132745041-1093625888

转换过后的数组说明:

  • [0]列:表示原二维数组有6行7列,其中有8个数据值不是默认值。
  • [1]列:表示原二维数组0行3列位置的数据值是22。其后的数据表示方式与此相似。
2.2.3 代码实现

2.2.3.1 思路分析

我的关键词 稀疏数组、队列的概念与实践  新闻咨询 1527720-20200418132804904-154102192


  • 二维数组 转 稀疏数组的思路

  • 遍历  原始的二维数组,得到有效数据的个数 sum
  • 根据sum 就可以创建 稀疏数组 sparseArr   int[sum + 1] [3]
  • 将二维数组的有效数据数据存入到 稀疏数组


  • 稀疏数组转原始的二维数组的思路

  • 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的  chessArr2 = int [11][11]
  • 在读取稀疏数组后几行的数据,并赋给 原始的二维数组 即可.
2.2.3.2 code

代码实现:https://github.com/goSilver/daydayup/blob/master/datastructure/src/hanshunping/chapter03/SparseArray.java
三、队列的概念及实践

3.1 队列简介


  • 队列是一个有序列表,可以用数组或是链表来实现;
  • 遵循先入先出的原则;
3.2 数组模拟队列思路

队列是有序的,使用数组机构来模拟队列时,需要对数组作以下声明:

  • maxSize是该队列的最大容量;
  • 因为队列的输入、输出分别是从前后两头来处理,因此需要两个变量front及rear来分别记录队列前后端的下标。front代表队列头,随着数据输出而改变;rear代表队列尾,随着数据输入而变化。如下图:
    我的关键词 稀疏数组、队列的概念与实践  新闻咨询 1527720-20200418132934835-1890805976

  • 当我们将数据存入队列是需要两个步骤:首先判断队列是否已满,若指针rear小于队列的最大容量maxSize-1,则可以存入,否则不可以存入数据;第二步将尾指针往后移一位(rear++)。
  • 在取数据的时候需要判断队列是否为空,若front==rear则表示队列为空。
3.2.1 code

代码实现:https://github.com/goSilver/daydayup/blob/master/datastructure/src/hanshunping/chapter03/arrayqueue/ArrayQueueDemo.java
3.3 使用数组模拟环形队列优化

对于3.2中的实现,存在一个问题就是数组只能使用一次就不能复用了,这里可以使用一个简单的算法,改进成一个环形的数组。(取模)
思路说明:

  • front变量的含义做一个调整:front直接指向队列的第一个元素,front的初始值变为0;
  • rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置,因为需要空出一个空间作为约定,rear的初始值为0;
  • 当队列满时,条件是(rear + 1) % maxSize = front 【满】;
  • 队列为空时,rear == front 【空】;
  • 队列中有效的数据个数:(rear + maxSize - front) % maxSize
3.3.1 code

代码实现:https://github.com/goSilver/daydayup/blob/master/datastructure/src/hanshunping/chapter03/arrayqueue/CircleArrayQueueDemo.java

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表