A kind of construction and storage method of data structure
A kind of construction and storage method of data structure
 CN 102,750,328 B
 Filed: 05/29/2012
 Issued: 08/10/2018
 Est. Priority Date: 05/29/2012
 Status: Active Grant
First Claim
Patent Images
1. the construction and storage method of a kind of data structure, including：
 Each node in data structure is numbered；
Relationship between superior and subordinate information of at least one relationship array for storing all nodes in data structure successively is set, wherein rightIn different data structures, the relationship between superior and subordinate of all nodes in the data structure is indicated with the array of different number respectively；
Multidate information field of at least one dynamic array for storing all nodes in data structure successively is set, wherein describedDynamic array is onedimension array, and the multidate information field changes in special time period, and often changes in special time periodMultidate information field constructs the primary dynamic array；
AndStatic information fields of at least one static array for storing all nodes in data structure successively are set, wherein describedStatic array is onedimension array, and the static information fields are constant in special time period, and is only constructed in special time periodStatic array.
Chinese PRB Reexamination
Abstract
The present invention provides a kind of construction of data structure and storage methods, including：Each node in data structure is numbered；Relationship between superior and subordinate information of at least one relationship array for storing all nodes in data structure successively is set；Multidate information field of at least one dynamic array for storing all nodes in data structure successively is set；And static information fields of at least one static array of setting for storing all nodes in data structure successively.Method provided by the invention significantly reduces the time complexity and space complexity of data manipulation.
10 Claims

1. the construction and storage method of a kind of data structure, including：

Each node in data structure is numbered； Relationship between superior and subordinate information of at least one relationship array for storing all nodes in data structure successively is set, wherein rightIn different data structures, the relationship between superior and subordinate of all nodes in the data structure is indicated with the array of different number respectively； Multidate information field of at least one dynamic array for storing all nodes in data structure successively is set, wherein describedDynamic array is onedimension array, and the multidate information field changes in special time period, and often changes in special time periodMultidate information field constructs the primary dynamic array；
AndStatic information fields of at least one static array for storing all nodes in data structure successively are set, wherein describedStatic array is onedimension array, and the static information fields are constant in special time period, and is only constructed in special time periodStatic array.


2. according to the method described in claim 1, including：

The sequence for setting traversal, according to the sequence of traversal by the node number consecutively in data structure； The superior relation of each node is indicated at least one onedimension array； The inferior relation of each node is indicated at least one onedimension array； Store the information field of each node respectively at least one onedimension array, each information field of all nodes is stored in oneIn a onedimension array, wherein the multidate information field of realtime change is stored in dynamic array, by the static state of non realtime variationInformation field is stored in static array.


3. method according to claim 1 or 2, wherein the data structure is reticular structure；

At least one relationship array is arranged includes for storing data the step of the relationship between superior and subordinate information of all nodes in structureFollowing steps： The superior relation of at least three onedimensional each nodes of higher level'"'"'s array representation is set, and three arrays include series on firstGroup, second higher level'"'"'s array and third higher level'"'"'s array； The superior node number for calculating each node deposits the superior node number of the node according to the sequence of node serial number successivelyEnter first higher level'"'"'s array； According to the sequence of node serial number, by number segmentation second higher level'"'"'s array of deposit of all superior nodes of each node； According to the sequence of node serial number, each section of starting subscript of the second higher level array is stored in third higher level'"'"'s array； The inferior relation of at least three onedimensional each nodes of subordinate'"'"'s array representation is set, and three subordinate'"'"'s arrays include under the 4thGrade array, the 5th subordinate'"'"'s array and the 6th subordinate'"'"'s array； The downstream site number for calculating each node deposits the downstream site number of the node according to the sequence of node serial number successivelyEnter the 4th subordinate'"'"'s array； According to the sequence of node serial number, by number segmentation the 5th subordinate'"'"'s array of deposit of all downstream sites of each node； According to the sequence of node serial number, the starting subscript of each section of the 5th subordinate'"'"'s array is stored in the 6th subordinate'"'"'s array.


4. method according to claim 1 or 2, wherein the data structure is reticular structure；

At least one relationship array is arranged includes for storing data the step of the relationship between superior and subordinate information of all nodes in structureFollowing steps： The superior relation of at least three onedimensional each nodes of higher level'"'"'s array representation is set, and three arrays include series on the 7thGroup, the 8th higher level'"'"'s array and the 9th higher level'"'"'s array； The immediate superior number of nodes for calculating each node, according to the sequence of node serial number, by the immediate superior node of the nodeNumber is sequentially stored into the 7th higher level'"'"'s array； According to the sequence of node serial number, by number segmentation the 8th higher level'"'"'s array of deposit of the immediate superior node of each node； According to the sequence of node serial number, the starting subscript of each section of the 8th higher level'"'"'s array is stored in the 9th higher level'"'"'s array； The inferior relation of at least three onedimensional each nodes of subordinate'"'"'s array representation is set, and three subordinate'"'"'s arrays include under the tenthGrade array, the tenth once grade array and the 12nd subordinate'"'"'s array； The direct downstream site number for calculating each node, according to the sequence of node serial number, by the direct downstream site of the nodeNumber is sequentially stored into the tenth subordinate'"'"'s array； According to the sequence of node serial number, the number of the direct downstream site of each node is segmented the grade array once of deposit the tenth； According to the sequence of node serial number, the starting subscript of the described tenth once each section of grade array is stored in the 12 times seriesGroup.


5. method according to claim 1 or 2, wherein the data structure is tree；

The node in the data structure is numbered according to preorder traversal mode； Be arranged at least one relationship array for storing data in structure the step of the relationship between superior and subordinate information of all nodes into oneStep includes the following steps： The superior relation of one onedimensional each node of higher level'"'"'s array representation is set, according to the sequence of node serial number, by each nodeThe number of superior node be stored in onedimensional higher level'"'"'s array； The inferior relation of one onedimensional each node of subordinate'"'"'s array representation is set, according to the sequence of node serial number, by each nodeThe sum of downstream site be stored in onedimensional subordinate'"'"'s array.


6. according to claim 15 any one of them methods, wherein according to the order of preorder traversal to the section in data structurePoint is traversed and is numbered.

7. according to claim 15 any one of them methods, wherein execute following steps when constructing data structure：

A fixed Staticstate Space of application is for storing the static array； According to the multiple pairs for using more parts of dynamic spaces of number of threads application of the data structure to be used to store the dynamic arrayThis.


8. according to claim 15 any one of them methods, wherein execute following steps when constructing data structure：

A fixed Staticstate Space of application is for storing the static array； Apply for multiple copies of the more parts of fixed Staticstate Spaces for storing the dynamic array.


9. according to claim 15 any one of them methods, further include：
An array is constructed, according to the number of each node of the sequential storage of the node serial number.

10. according to claim 13 any one of them methods, to each node definition one in the hierachical data structureThe value not changed over time is used in combination Hash table to record the mapping relations between the value and the node serial number, when utilization nodeWhen field searches node, the lookup of the node is realized by Hash table.
Specification(s)