CN111898002A - Method for generating and reading one-way linked list and device - Google Patents
Method for generating and reading one-way linked list and device Download PDFInfo
- Publication number
- CN111898002A CN111898002A CN202010788705.XA CN202010788705A CN111898002A CN 111898002 A CN111898002 A CN 111898002A CN 202010788705 A CN202010788705 A CN 202010788705A CN 111898002 A CN111898002 A CN 111898002A
- Authority
- CN
- China
- Prior art keywords
- node
- linked list
- group
- current node
- information
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Mobile Radio Communication Systems (AREA)
Abstract
The invention provides a method for generating a single linked list, a method for reading the single linked list and a device thereof, which determine a target group number by utilizing the jump relation between a current node and a subsequent node in the single linked list and the group number of a preorder structure information group, and generate a current structure information group pointing to the subsequent node in the linked list information of the current node according to the mark and the position information of the subsequent node and the target group number, namely, distinguish a plurality of subsequent nodes pointed by the current node by the group number. On the basis, when the unidirectional chain table is read, the structure information group pointing to the subsequent node in the chain table information of the current node can be determined according to the preorder structure information combination group number and the group number of the structure information group in the chain table information of the current node, so that the subsequent node can be accurately read by the current node, and the problem of reading lost caused by repeated use of the node in the unidirectional chain table is solved.
Description
Technical Field
The invention relates to the technical field of data structures, in particular to a method and a device for generating and reading a single-direction linked list.
Background
The single-direction linked list is one kind of linked list, and is formed by unidirectionally linking a plurality of nodes, wherein the nodes are used for storing data, and the single-direction linked list is characterized in that the link direction of the linked list is single-direction, as shown in fig. 1, the last node is pointed to the next node, and the access to the linked list needs to be sequentially read according to the link direction of the nodes.
However, in practical applications, the one-way linked list has a problem of node reuse, as shown in fig. 2, a node (ID: 400) is reused 3 times, a node (ID: 403) is reused 3 times, and in one-way linked list, the repeatedly used node has a plurality of directions of next nodes.
Disclosure of Invention
In view of this, the invention provides a method for generating a single-direction linked list, a method for reading the single-direction linked list and a device thereof, which solve the problem of read lost caused by repeated use of nodes in the single-direction linked list.
In order to solve the technical problems, the invention provides a specific technical scheme that:
a method for generating a singly-linked list comprises the following steps:
acquiring identification and position information of a subsequent node of a current node in a single-direction linked list, and a preorder structure information group pointing to the current node in linked list information of a preorder node of the current node;
determining a jump relationship between the current node and the subsequent node;
determining a target group number according to the jump relation between the current node and the subsequent node and the group number of the preorder structure information group;
and generating a structural information group pointing to the subsequent node in the linked list information of the current node according to the identification and the position information of the subsequent node and the target group number.
Optionally, the determining a target group number according to the jump relationship between the current node and the subsequent node and the group number of the preamble structure information group includes:
and when the jumping relation between the current node and the subsequent node is that the branch line jumps to the main line, determining that the target group number is 0, wherein the main line is a line for performing node access according to the original sequence of the nodes, and the branch line is a line for performing node access not according to the original sequence of the nodes.
Optionally, the determining a target group number according to the jump relationship between the current node and the subsequent node and the group number of the preamble structure information group includes:
and when the jumping relation between the current node and the subsequent node is the jumping on the main line or the jumping on the branch line, determining the target group number as the same value as the group number of the preorder structure information group.
Optionally, the determining a target group number according to the jump relationship between the current node and the subsequent node and the group number of the preamble structure information group includes: and when the jumping relation between the current node and the subsequent node is that the main line jumps to the branch line, determining the target group number as the value of adding 1 to the group number of the preorder structure information group.
A method for reading a single-direction linked list, which is used for reading the single-direction linked list generated by the method for generating a single-direction linked list disclosed in the above embodiment, the method includes:
under the condition that the linked list information of the current node in the one-way linked list is not empty, acquiring a structural information group in the linked list information of the current node;
under the condition that the current node is determined to have a subsequent node according to the structure information group in the linked list information of the current node, acquiring a preamble structure information group which points to the current node in the linked list information of the preamble node of the current node;
determining a structure information group pointing to the subsequent node in the linked list information of the current node according to the group number of the preorder structure information group and the group number of the structure information group in the linked list information of the current node;
and reading the subsequent node according to the identification and the position information of the subsequent node in the structural information group pointing to the subsequent node in the linked list information of the current node.
Optionally, the determining that the current node has a subsequent node according to the structural information group in the linked list information of the current node includes:
judging whether an ending structure information group exists in the linked list information of the current node;
if the ending structure information group exists, determining that the subsequent node does not exist in the current node;
and if the ending structure information group does not exist, determining that the current node has the subsequent node.
Optionally, the determining, according to the group number of the preamble structure information group and the group number of the structure information group in the linked list information of the current node, the structure information group that is directed to the subsequent node in the linked list information of the current node includes:
judging whether a structural information group with the group number same as that of the preorder structural information group exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with the group number same as that of the preorder structural information group, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
if the linked list information of the current node does not have a structural information group with the group number identical to that of the preorder structural information group, judging whether a structural information group with the group number of 0 exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with a group number of 0, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
and if the structural information group with the group number of 0 does not exist in the linked list information of the current node, determining the structural information group with the first group number which is larger than the group number of the preorder structural information group in the linked list information of the current node as the structural information group which points to the subsequent node in the linked list information of the current node.
An apparatus for generating a singly linked list, comprising:
a first data obtaining unit, configured to obtain an identifier and position information of a subsequent node of a current node in a single-direction linked list, and a preamble structure information group pointing to the current node in linked list information of a preamble node of the current node;
a jump relation determining unit, configured to determine a jump relation between the current node and the subsequent node;
a group number determining unit, configured to determine a target group number according to a jump relationship between the current node and the subsequent node and a group number of the preamble structure information group;
and the information group generating unit is used for generating a structural information group pointing to the subsequent node in the linked list information of the current node according to the identification and the position information of the subsequent node and the target group number.
Optionally, the group number determining unit is specifically configured to determine that the target group number is 0 when the jump relationship between the current node and the subsequent node is a branch line jumping to a main line, where the main line is a line in which node access is performed according to an original sequence of nodes, and the branch line is a line in which node access is not performed according to the original sequence of nodes.
Optionally, the group number determining unit is specifically configured to determine the target group number as a value same as the group number of the preamble structure information group when the jump relationship between the current node and the subsequent node is a jump on the main line or a jump on the branch line.
Optionally, the group number determining unit is specifically configured to determine the target group number as a value obtained by adding 1 to the group number of the preamble structure information group when the jump relationship between the current node and the subsequent node is a jump from the main line to the branch line.
A device for reading a single-direction linked list, configured to read a single-direction linked list generated by the method for generating a single-direction linked list disclosed in the foregoing embodiment, the device including:
a second data obtaining unit, configured to obtain a structural information group in the linked list information of the current node in the one-way linked list when the linked list information of the current node in the one-way linked list is not empty;
a third data obtaining unit, configured to obtain a preamble structure information group, which is directed to the current node, in linked list information of a preamble node of the current node when it is determined that a subsequent node exists in the current node according to a structure information group in the linked list information of the current node;
a target structure information group determining unit, configured to determine a structure information group, which is directed to the subsequent node, in the linked list information of the current node according to the group number of the preamble structure information group and the group number of the structure information group in the linked list information of the current node;
and the data reading unit is used for reading the subsequent nodes according to the identifiers and the position information of the subsequent nodes in the structure information group pointing to the subsequent nodes in the linked list information of the current node.
Optionally, the apparatus further includes a subsequent node determining unit, configured to:
judging whether an ending structure information group exists in the linked list information of the current node;
if the ending structure information group exists, determining that the subsequent node does not exist in the current node;
and if the ending structure information group does not exist, determining that the current node has the subsequent node.
Optionally, the target structure information group determining unit is specifically configured to:
judging whether a structural information group with the group number same as that of the preorder structural information group exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with the group number same as that of the preorder structural information group, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
if the linked list information of the current node does not have a structural information group with the group number identical to that of the preorder structural information group, judging whether a structural information group with the group number of 0 exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with a group number of 0, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
and if the structural information group with the group number of 0 does not exist in the linked list information of the current node, determining the structural information group with the first group number which is larger than the group number of the preorder structural information group in the linked list information of the current node as the structural information group which points to the subsequent node in the linked list information of the current node.
Compared with the prior art, the invention has the following beneficial effects:
the invention discloses a method for generating a single-direction linked list, which determines a target group number by utilizing the jump relation between a current node and a subsequent node in the single-direction linked list and the group number of a preorder structure information group, and generates a current structure information group pointing to the subsequent node in the linked list information of the current node according to the mark and the position information of the subsequent node and the target group number, namely, a plurality of subsequent nodes pointed by the current node are distinguished by the group number. On the basis, when the unidirectional chain table is read, the structure information group pointing to the subsequent node in the chain table information of the current node can be determined according to the preorder structure information combination group number and the group number of the structure information group in the chain table information of the current node, so that the subsequent node can be accurately read by the current node, and the problem of reading lost caused by repeated use of the node in the unidirectional chain table is solved.
Drawings
In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, it is obvious that the drawings in the following description are only embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to the provided drawings without creative efforts.
FIG. 1 is a schematic diagram of a single linked list;
FIG. 2 is a schematic diagram of a singly linked list with node reuse;
FIG. 3 is a schematic diagram of a node data storage structure according to an embodiment of the present invention;
FIG. 4 is a flowchart illustrating a method for generating a single-direction linked list according to an embodiment of the present invention;
FIG. 5 is a schematic diagram of a single-direction chain table according to an embodiment of the present invention;
FIG. 6 is a flowchart illustrating a method for reading a single-direction linked list according to an embodiment of the present invention;
FIG. 7 is a schematic structural diagram of a device for generating a single-direction linked list according to an embodiment of the present invention;
fig. 8 is a schematic structural diagram of a device for reading a single-direction linked list according to an embodiment of the present invention.
Detailed Description
The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.
The invention discloses a method for generating and reading a single-node reusable single-direction linked list, which improves a node data storage structure, please refer to fig. 3, wherein the node data storage structure comprises a current node ID and linked list information, the linked list information comprises at least one structure information group, each structure information group comprises a group number, position information of a subsequent node and a subsequent node identifier, a plurality of subsequent nodes pointed by the current node are distinguished through the group number, and the problem of subsequent reading lost can be avoided by improving the generation of the single-direction linked list.
Referring to fig. 4, the method for generating a single-direction linked list disclosed in this embodiment includes the following steps:
s101: acquiring identification and position information of a subsequent node of a current node in a single-direction linked list, and a preorder structure information group pointing to the current node in linked list information of a preorder node of the current node;
the preorder node of the current node is a node accessed before the user accesses the current node.
S102: determining a jump relationship between the current node and the subsequent node;
in general, a user may perform node access according to an original sequence of nodes, that is, perform node access according to a main line, and taking the original node sequence shown in fig. 1 as an example, if the user performs node access according to the main line, the node access sequence is: 399-403-404-400-401-402.
However, in the practical application process, a user may access a node for multiple times, jump from the main line to the branch line, perform branch line access, and jump from the branch line to the main line, and so on. Taking the unidirectional chain with node reuse as shown in fig. 2 as an example, a user first performs main line access, 399-403-404-400, then jumps from the main line to the branch line, namely jumps from 400 to 403, jumps from 403 to 401, jumps from the branch line back to the main line, namely jumps from 401 to 402, and then jumps from the main line to the branch line, namely jumps from 402 to 400 to 399-403-400-404.
S103: determining a target group number according to the jump relation between the current node and the subsequent node and the group number of the preorder structure information group;
specifically, when the jump relationship between the current node and the subsequent node is from a branch line to a main line, the target group number is determined to be 0.
And when the jumping relation between the current node and the subsequent node is the jumping on the main line or the jumping on the branch line, determining the target group number as the same value as the group number of the preorder structure information group.
And when the jumping relation between the current node and the subsequent node is that the main line jumps to the branch line, determining the target group number as the value of adding 1 to the group number of the preorder structure information group.
S104: and generating a structural information group pointing to the subsequent node in the linked list information of the current node according to the identification and the position information of the subsequent node and the target group number.
For further describing the method for generating a single-direction linked list disclosed in this embodiment, please refer to fig. 5, where fig. 5 is a schematic diagram of a single-direction linked list supporting single-node reuse generated according to the access sequence of the nodes in fig. 2.
According to the access sequence of the nodes in fig. 2: 399-403-404-400-403-401-402-400-399-403-400-404, firstly, generating a structure information group pointing to 404 in the linked list information of 403, because 403-404 are jumps on a main line, a target group number in the structure information group to be generated is consistent with a group number 1 in a preamble structure information group (1,7,403) pointing to 403 in a preamble node 399 of 403, and then generating a structure information group (1,7,404) pointing to 404 in the linked list information of 403 according to the position information and the identification of 404.
When generating the structure information group pointing to 403 in the linked list information of 400, because 400-403 jump from main line to branch line, the value of group number 1+1 in the preamble structure information group (1,6,400) pointing to 400 in the preamble node 404 with the target group number of 400 in the structure information group to be generated is 2, and then according to the position information and the identification of 403, the structure information group (2,7,403) pointing to 403 is generated in the linked list information of 400.
When the structure information group pointing to 402 is generated in the linked list information of 401, because 401-402 jumps from the branch line to the main line, the target group number in the structure information group to be generated is 0, and then according to the position information and the identification of 402, the structure information group (0,7,402) pointing to 402 is generated in the linked list information of 401.
The generation manner of the structural information groups in other nodes is the same as that of the above examples, and is not described herein again.
It can be seen that, in the method for generating a single-direction linked list disclosed in this embodiment, linked list information including at least one structural information group is stored in each node, where the structural information group includes a group number, an identifier of a subsequent node, and location information, a target group number is determined by using a skip relationship between a current node and the subsequent node in the single-direction linked list and the group number of a preamble structural information group, and a current structural information group pointing to the subsequent node is generated in the linked list information of the current node according to the identifier, the location information, and the target group number of the subsequent node, that is, a plurality of subsequent nodes pointed to by the current node are distinguished by the group number, and the problem of subsequent read lost can be avoided by improving the generation of the single-direction linked list.
Based on the method for generating a single-direction linked list disclosed in the above embodiments, the present embodiment discloses a method for reading a single-direction linked list, please refer to fig. 6, the method for reading a single-direction linked list includes the following steps:
s201: under the condition that the linked list information of the current node in the one-way linked list is not empty, acquiring a structural information group in the linked list information of the current node;
it can be understood that when the linked list information of the current node in the single linked list is empty, the reading of the single linked list is finished, and the current node has no subsequent node.
S202: under the condition that the current node is determined to have a subsequent node according to a structure information group in the linked list information of the current node, acquiring a preorder structure information group pointing to the current node in the linked list information of the preorder node of the current node;
specifically, the method for judging whether the current node has the subsequent node is as follows:
judging whether an ending structure information group exists in the linked list information of the current node, wherein if (0,0,0) represents the reading end of the one-way linked list;
if the ending structure information group exists, determining that the current node does not have a subsequent node;
and if the ending structure information group does not exist, determining that the current node has a subsequent node.
S203: determining a structure information group pointing to a subsequent node in the linked list information of the current node according to the group number of the preorder structure information group and the group number of the structure information group in the linked list information of the current node;
corresponding to the generation method of the one-way linked list, the method for determining the structural information group pointing to the subsequent node in the linked list information of the current node is as follows:
judging whether a structural information group with the group number same as that of the preorder structural information group exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with the group number same as that of the preorder structural information group, determining the structural information group as a structural information group pointing to a subsequent node in the linked list information of the current node;
if the linked list information of the current node does not have a structural information group with the group number identical to that of the preorder structural information group, judging whether a structural information group with the group number of 0 exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with a group number of 0, determining the structural information group as a structural information group pointing to a subsequent node in the linked list information of the current node;
and if the linked list information of the current node does not have the structural information group with the group number of 0, determining the first structural information group with the group number larger than the preorder structural information group in the linked list information of the current node as the structural information group pointing to the subsequent node in the linked list information of the current node.
That is, first, it is determined whether the jump relationship between the current node and the subsequent node is a jump on the main line or a jump on the branch line, that is, it is determined whether a structural information group having a group number identical to that of the pre-order structural information group exists in the linked list information of the current node; if not, further judging whether the jumping relation between the current node and the subsequent node is from the branch line to the main line, namely judging whether a structural information group with a group number of 0 exists in the linked list information of the current node; if not, the jumping relation between the current node and the subsequent node is judged to be jumping to the branch line from the main line, namely, the first structural information group which is larger than the group number of the preorder structural information group in the linked list information of the current node is determined as the structural information group which points to the subsequent node in the linked list information of the current node.
Taking the schematic diagram of the singly linked list supporting the reuse of a single node generated according to the access sequence of the nodes in fig. 2 in fig. 5 as an example, when 403 is taken as the current node, it is found that a structural information group (1,7,404) identical to the group number 1 of the preamble structural information group pointing to 403 in the preamble node 399 of 403 exists in the linked list information of 403, and then the subsequent node of 403 is determined 404.
When 404 is taken as the current node, if the linked list information of 404 is found to have a structure information group (1,6,400) which is the same as the group number 1 of the preamble structure information group of the pointer 404 in the preamble node 403 of 404, 400 is determined to be a subsequent node of 404.
When 400 is taken as the current node, if the linked list information of 400 does not have the structure information group with the same group number 1 as the preamble structure information group of 400 in the preamble node 404 of 400 and does not have the structure information group with the group number of 0, the structure information group (2,7,403) corresponding to the first group number larger than 1 in the linked list information of 400 is determined 403 as the subsequent node of 400.
When 403 is taken as the current node, it is found that the linked list information of 403 has the same structure information group (2,6,401) as the group number 2 of the preamble structure information group pointing to 403 in the preamble node 400 of 403, and 401 is determined to be the subsequent node of 403.
When 401 is taken as the current node, only the structure information group (0,7,402) with the group number of 0 exists in the linked list information of 401, and then 402 is determined as the subsequent node of 401.
The manner of determining the subsequent node in the other nodes is the same as that in the above examples, and is not described herein again.
S204: and reading the subsequent nodes according to the identifiers and the position information of the subsequent nodes in the structure information group pointing to the subsequent nodes in the linked list information of the current node.
It can be seen that, with the method for reading a single-direction linked list disclosed in this embodiment, when reading a single-direction linked list, a structure information group pointing to a subsequent node in the linked list information of the current node can be determined according to a group number of a pre-order structure information combination group and a group number of a structure information group in the linked list information of the current node, so that the subsequent node is accurately read by the current node, and the problem of read lost due to repeated use of nodes in the single-direction linked list is solved.
Based on the method for generating a single-direction linked list disclosed in the foregoing embodiments, this embodiment correspondingly discloses a device for generating a single-direction linked list, please refer to fig. 7, where the device includes:
a first data obtaining unit 301, configured to obtain an identifier and position information of a subsequent node of a current node in a single-direction linked list, and a preamble structure information group pointing to the current node in linked list information of a preamble node of the current node;
a jump relation determining unit 302, configured to determine a jump relation between the current node and the subsequent node;
a group number determining unit 303, configured to determine a target group number according to a jump relationship between the current node and the subsequent node and a group number of the preamble structure information group;
an information group generating unit 304, configured to generate a structure information group pointing to the subsequent node in the linked list information of the current node according to the identifier and the location information of the subsequent node and the target group number.
Optionally, the group number determining unit 303 is specifically configured to determine that the target group number is 0 when the jump relationship between the current node and the subsequent node is a jump from a branch line to a main line, where the main line is a line in which node access is performed according to the original ordering of nodes, and the branch line is a line in which node access is not performed according to the original ordering of nodes.
Optionally, the group number determining unit 303 is specifically configured to determine the target group number as a value same as the group number of the preamble structure information group when the jump relationship between the current node and the subsequent node is a jump on the main line or a jump on the branch line.
Optionally, the group number determining unit 303 is specifically configured to determine the target group number as a value obtained by adding 1 to the group number of the preamble structure information group when the jump relationship between the current node and the subsequent node is a jump from the main line to the branch line.
The device for generating the single-direction linked list disclosed by the embodiment stores linked list information comprising at least one structural information group in each node, wherein the structural information group comprises a group number, identification and position information of subsequent nodes, a target group number is determined by utilizing a jump relation between a current node and the subsequent nodes in the single-direction linked list and the group number of a preorder structural information group, and a current structural information group pointing to the subsequent nodes is generated in the linked list information of the current node according to the identification, the position information and the target group number of the subsequent nodes, namely, a plurality of subsequent nodes pointing to the current node are distinguished by the group number, and the problem of subsequent reading lost can be avoided by improving the generation of the single-direction linked list.
Based on the method for reading a single-direction linked list disclosed in the foregoing embodiment, this embodiment correspondingly discloses a device for reading a single-direction linked list, which is used for reading a single-direction linked list generated by the method for generating a single-direction linked list disclosed in the foregoing embodiment, please refer to fig. 8, where the device includes:
a second data obtaining unit 401, configured to obtain a structural information group in the linked list information of the current node in the one-way linked list when the linked list information of the current node in the one-way linked list is not empty;
a third data obtaining unit 402, configured to obtain a preamble structure information group pointing to the current node in the linked list information of the preamble node of the current node when it is determined that a subsequent node exists in the current node according to a structure information group in the linked list information of the current node;
a target structure information group determining unit 403, configured to determine, according to the group number of the preamble structure information group and the group number of the structure information group in the linked list information of the current node, a structure information group that is directed to the subsequent node in the linked list information of the current node;
a data reading unit 404, configured to read the subsequent node according to the identifier and the position information of the subsequent node in the structure information group pointing to the subsequent node in the linked list information of the current node.
Optionally, the apparatus further includes a subsequent node determining unit, configured to:
judging whether an ending structure information group exists in the linked list information of the current node;
if the ending structure information group exists, determining that the subsequent node does not exist in the current node;
and if the ending structure information group does not exist, determining that the current node has the subsequent node.
Optionally, the target structure information group determining unit 403 is specifically configured to:
judging whether a structural information group with the group number same as that of the preorder structural information group exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with the group number same as that of the preorder structural information group, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
if the linked list information of the current node does not have a structural information group with the group number identical to that of the preorder structural information group, judging whether a structural information group with the group number of 0 exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with a group number of 0, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
and if the structural information group with the group number of 0 does not exist in the linked list information of the current node, determining the structural information group with the first group number which is larger than the group number of the preorder structural information group in the linked list information of the current node as the structural information group which points to the subsequent node in the linked list information of the current node.
The reading device for the single-direction linked list disclosed by the embodiment can determine the structure information group pointing to the subsequent node in the linked list information of the current node according to the group number of the preorder structure information combination group and the group number of the structure information group in the linked list information of the current node when the single-direction linked list is read, so that the subsequent node is accurately read by the current node, and the problem of reading lost caused by repeated use of the node in the single-direction linked list is solved.
The embodiments in the present description are described in a progressive manner, each embodiment focuses on differences from other embodiments, and the same and similar parts among the embodiments are referred to each other. The device disclosed by the embodiment corresponds to the method disclosed by the embodiment, so that the description is simple, and the relevant points can be referred to the method part for description.
It is further noted that, herein, relational terms such as first and second, and the like may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Also, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising an … …" does not exclude the presence of other identical elements in a process, method, article, or apparatus that comprises the element.
The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in Random Access Memory (RAM), memory, Read Only Memory (ROM), electrically programmable ROM, electrically erasable programmable ROM, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art.
The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.
Claims (9)
1. A method for generating a singly linked list, comprising:
acquiring identification and position information of a subsequent node of a current node in a single-direction linked list, and a preorder structure information group pointing to the current node in linked list information of a preorder node of the current node;
determining a jump relationship between the current node and the subsequent node;
determining a target group number according to the jump relation between the current node and the subsequent node and the group number of the preorder structure information group;
and generating a structural information group pointing to the subsequent node in the linked list information of the current node according to the identification and the position information of the subsequent node and the target group number.
2. The method of claim 1, wherein determining a target group number according to the hop relationship between the current node and the subsequent node and the group number of the preamble structure information group comprises:
and when the jumping relation between the current node and the subsequent node is that the branch line jumps to the main line, determining that the target group number is 0, wherein the main line is a line for performing node access according to the original sequence of the nodes, and the branch line is a line for performing node access not according to the original sequence of the nodes.
3. The method of claim 2, wherein determining a target group number according to the hop relationship between the current node and the subsequent node and the group number of the preamble structure information group comprises:
and when the jumping relation between the current node and the subsequent node is the jumping on the main line or the jumping on the branch line, determining the target group number as the same value as the group number of the preorder structure information group.
4. The method of claim 2, wherein determining a target group number according to the hop relationship between the current node and the subsequent node and the group number of the preamble structure information group comprises: and when the jumping relation between the current node and the subsequent node is that the main line jumps to the branch line, determining the target group number as the value of adding 1 to the group number of the preorder structure information group.
5. A method for reading a singly linked list generated by the method for generating a singly linked list according to any one of claims 1 to 4, the method comprising:
under the condition that the linked list information of the current node in the one-way linked list is not empty, acquiring a structural information group in the linked list information of the current node;
under the condition that the current node is determined to have a subsequent node according to the structure information group in the linked list information of the current node, acquiring a preamble structure information group which points to the current node in the linked list information of the preamble node of the current node;
determining a structure information group pointing to the subsequent node in the linked list information of the current node according to the group number of the preorder structure information group and the group number of the structure information group in the linked list information of the current node;
and reading the subsequent node according to the identification and the position information of the subsequent node in the structural information group pointing to the subsequent node in the linked list information of the current node.
6. The method of claim 5, wherein the determining that the current node has a subsequent node according to the structural information group in the linked list information of the current node comprises:
judging whether an ending structure information group exists in the linked list information of the current node;
if the ending structure information group exists, determining that the subsequent node does not exist in the current node;
and if the ending structure information group does not exist, determining that the current node has the subsequent node.
7. The method according to claim 5, wherein determining the structural information group in the linked list information of the current node, which is directed to the subsequent node, according to the group number of the preamble structural information group and the group number of the structural information group in the linked list information of the current node comprises:
judging whether a structural information group with the group number same as that of the preorder structural information group exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with the group number same as that of the preorder structural information group, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
if the linked list information of the current node does not have a structural information group with the group number identical to that of the preorder structural information group, judging whether a structural information group with the group number of 0 exists in the linked list information of the current node;
if the linked list information of the current node has a structural information group with a group number of 0, determining the structural information group as a structural information group pointing to the subsequent node in the linked list information of the current node;
and if the structural information group with the group number of 0 does not exist in the linked list information of the current node, determining the structural information group with the first group number which is larger than the group number of the preorder structural information group in the linked list information of the current node as the structural information group which points to the subsequent node in the linked list information of the current node.
8. An apparatus for generating a singly-linked list, comprising:
a first data obtaining unit, configured to obtain an identifier and position information of a subsequent node of a current node in a single-direction linked list, and a preamble structure information group pointing to the current node in linked list information of a preamble node of the current node;
a jump relation determining unit, configured to determine a jump relation between the current node and the subsequent node;
a group number determining unit, configured to determine a target group number according to a jump relationship between the current node and the subsequent node and a group number of the preamble structure information group;
and the information group generating unit is used for generating a structural information group pointing to the subsequent node in the linked list information of the current node according to the identification and the position information of the subsequent node and the target group number.
9. An apparatus for reading a singly linked list generated by the method for generating a singly linked list according to any one of claims 1 to 4, the apparatus comprising:
a second data obtaining unit, configured to obtain a structural information group in the linked list information of the current node in the one-way linked list when the linked list information of the current node in the one-way linked list is not empty;
a third data obtaining unit, configured to obtain a preamble structure information group, which is directed to the current node, in linked list information of a preamble node of the current node when it is determined that a subsequent node exists in the current node according to a structure information group in the linked list information of the current node;
a target structure information group determining unit, configured to determine a structure information group, which is directed to the subsequent node, in the linked list information of the current node according to the group number of the preamble structure information group and the group number of the structure information group in the linked list information of the current node;
and the data reading unit is used for reading the subsequent nodes according to the identifiers and the position information of the subsequent nodes in the structure information group pointing to the subsequent nodes in the linked list information of the current node.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010788705.XA CN111898002B (en) | 2020-08-07 | 2020-08-07 | Method for generating unidirectional linked list, method for reading unidirectional linked list and device for generating unidirectional linked list |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010788705.XA CN111898002B (en) | 2020-08-07 | 2020-08-07 | Method for generating unidirectional linked list, method for reading unidirectional linked list and device for generating unidirectional linked list |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111898002A true CN111898002A (en) | 2020-11-06 |
| CN111898002B CN111898002B (en) | 2024-03-29 |
Family
ID=73247285
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010788705.XA Active CN111898002B (en) | 2020-08-07 | 2020-08-07 | Method for generating unidirectional linked list, method for reading unidirectional linked list and device for generating unidirectional linked list |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111898002B (en) |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5765165A (en) * | 1996-02-29 | 1998-06-09 | Sun Microsystems, Inc. | Fast method of determining duplicates on a linked list |
| CN101276334A (en) * | 2007-03-29 | 2008-10-01 | 上海新跃仪表厂 | Linked list implementing method for quickly searching data |
| CN104679949A (en) * | 2015-02-06 | 2015-06-03 | 中山大学 | Method for creating Paramics road network based on XML (Extensive Markup Language) road network data |
| CN110727675A (en) * | 2018-07-17 | 2020-01-24 | 阿里巴巴集团控股有限公司 | Method and device for processing linked list |
-
2020
- 2020-08-07 CN CN202010788705.XA patent/CN111898002B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5765165A (en) * | 1996-02-29 | 1998-06-09 | Sun Microsystems, Inc. | Fast method of determining duplicates on a linked list |
| CN101276334A (en) * | 2007-03-29 | 2008-10-01 | 上海新跃仪表厂 | Linked list implementing method for quickly searching data |
| CN104679949A (en) * | 2015-02-06 | 2015-06-03 | 中山大学 | Method for creating Paramics road network based on XML (Extensive Markup Language) road network data |
| CN110727675A (en) * | 2018-07-17 | 2020-01-24 | 阿里巴巴集团控股有限公司 | Method and device for processing linked list |
Also Published As
| Publication number | Publication date |
|---|---|
| CN111898002B (en) | 2024-03-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Kapoor et al. | Algorithms for enumerating all spanning trees of undirected and weighted graphs | |
| CN112907198B (en) | Service state circulation maintenance method and device and electronic equipment | |
| CN106326309A (en) | Data query method and device | |
| CN110147410B (en) | Data verification method, system, device and equipment in block chain type account book | |
| KR950016018A (en) | Efficient memory usage method, efficient resource usage method, determination of next state cost for retention, integrated circuit and digital signal conversion method for signal processing | |
| CN112508524A (en) | Electronic approval method, system, device and storage medium | |
| CN113626206A (en) | Method, device and equipment for adjusting number of application examples of container | |
| CN113706146B (en) | Processing method, device and system for executing batch transactions based on blockchain | |
| CN112579682B (en) | Method and device for notifying change of data model, electronic equipment and storage medium | |
| CN111930734B (en) | Task and field-based data offline method and system | |
| CN111898002A (en) | Method for generating and reading one-way linked list and device | |
| CN112905467A (en) | Test case execution management method, device, equipment and storage medium | |
| CN111967938B (en) | Cloud resource recommendation method and device, computer equipment and readable storage medium | |
| CN113238800B (en) | Stack frame structure and function calling method and system | |
| CN114637761A (en) | Business object generation method and device | |
| CN108241705B (en) | Data insertion method and device | |
| CN111159196A (en) | Block chain data storage and acquisition method and device based on fragmentation | |
| CN109739756A (en) | The method and apparatus of mobile terminal application test | |
| CN111045608B (en) | Method, device and equipment for searching validity codes and readable storage medium | |
| CN116185555A (en) | A data processing method and device, storage medium | |
| CN110928500A (en) | Storage cluster function configuration method, device, equipment and medium | |
| CN116340658A (en) | Website vulnerability scanning result display method, device, equipment and storage medium | |
| CN114936248A (en) | Data export method, device, equipment and storage medium | |
| CN119165807B (en) | Power supply equipment output control method, electronic equipment, power supply equipment and device | |
| CN110888941B (en) | Processing method and processing system for link relation event in business scene |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |