Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to convert two-dimensional arrays into chain storage by Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Chain storage structure

The linear table of the chain storage structure will use a set of arbitrary storage units to store the data elements in the linear table. Because it does not need to be stored sequentially, linked lists are faster than sequential storage when inserting and deleting data elements, but slower than sequential storage when finding a node.

The use of linked storage can overcome the disadvantage that sequential linear tables need to know the data size in advance, and the linked list structure can make full use of memory space to achieve flexible memory dynamic management. However, chained storage loses the characteristics of array random access and increases the pointer domain of nodes, which leads to high space overhead.

The following figure is the simplest and most general one-way linked list:

Code thinking

The idea of compressing a two-dimensional array into chained storage is similar to that of an array into a sparse array.

Here I store the total number of rows, columns and valid values of the two-dimensional array in the header node of the linked list.

Each node after the head node stores the subscript of the valid value and the idea of value conversion is shown in the following figure

Code implementation

Classes that create mock nodes provide constructors and toString

/ * simulated node * / public class SingleNode {/ * @ row line number * @ column column number * @ num value * / public int row; public int colunm; public int num; / * Nextfield: point to the next node * / public SingleNode next; public SingleNode (int row, int colunm, int num) {this.row = row This.colunm = colunm; this.num = num;} @ Override public String toString () {return "SingleNode {" + "row=" + row + ", colunm=" + colunm + ", num=" + num +'}';}}

Creating a simulation list class provides methods for adding nodes, traversing linked lists, and restoring arrays.

Public class SingleLinkList {/ / header private SingleNode headSingleNode; / / initialize the header node public SingleLinkList (SingleNode headSingleNode) {this.headSingleNode = headSingleNode;} / * add a node (appended to the end of the linked list) * / public void add (SingleNode SingleNode) {SingleNode temp = headSingleNode by constructing the number of rows While (true) {if (temp.next= = null) {/ / if the next field of this node is empty, jump out of the while loop break;} / / assign the next node to temp temp = temp.next;} temp.next= SingleNode } / * traverse single linked list * / public void show () {if (headSingleNode.next = = null) {System.out.println ("current linked list is empty"); return;} SingleNode temp = headSingleNode; while (true) {if (temp.next = = null) {break } temp = temp.next; System.out.println (temp);}} / * * restore the linked list to a 2D array * @ return array restored 2D array * / public int [] [] backToArray () {SingleNode temp = headSingleNode / / the number of rows and columns of the original array is stored in the header node / / create a two-dimensional array int [] [] array = new int [headSingleNode.row] [headSingleNode.colunm]; while (true) {if (temp.next = = null) {break;} temp = temp.next / / restore one data array [temp.row] [temp.colunm] = temp.num;} return array;}} public class ArrayToLink {public static void main (String [] args) {int [] [] array = new int [4] [5] per traversal; / / initialize the two-dimensional array array [0] [2] = 1 Array [1] [1] = 2; array [2] [3] = 3; System.out.println ("= normal array ="); / / ergodic two-dimensional array int count = 0; for (int I = 0; I < array.length; iota +) {for (int j = 0; j < array [I] .length) Count++; +) {if (array [I] [j]! = 0) {count++;} System.out.print (Array [I] [j] + ");} System.out.println () } / / convert the array into chained storage SingleLinkList list = new SingleLinkList (new SingleNode (array.length,array [0] .length, count); for (int I = 0; I < array.length; ilength +) {for (int j = 0; j < array [I] .length) List.add +) {if (array [I] [j]! = 0) {/ / create a node when the number is not 0 and add it to the end of the linked list (new SingleNode (iQuery j, Array [I] [j])) } System.out.println ("= converted linked list ="); / / traversing the unidirectional linked list list.show (); int [] [] returnArray = list.backToArray (); / / traversing the restored two-dimensional array System.out.println ("= restored array ="); for (int I = 0) I < returnArray.length; iArray +) {for (int j = 0; j < roomnArray [I] .length; jaugh +) {System.out.print (normalnArray [I] [j] + ");} System.out.println ();} output result

This is the end of the content of "how to convert two-dimensional arrays into chain storage by Java". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.