Learn from the beginning -> Java Data Structure series:

Learning from the Ground up – Java Data Structures part 1: Physical Storage Structures

Learning from the Ground up – Java Data Structures part 2: Logical Structures of Data

Learning from the Ground up – Java Data Structures part 3: General Linear Tables

Learning from the Ground up – Java Data Structures part 4: Constrained Linear Tables

Learning from the ground up – Java Data Structures part 5: Generalization to Linear Tables

preface

For the previous two articles, linear table, basically have been finished, but it was only to special linear table, this kind of special linear table, mainly reflected in the corresponding linear table data structure elements in the one-to-one relationship exists, but we speak a few articles are in front of the has very obvious direct one-to-one relationships, but in the actual division, We have a broader division of linear tables.

This article is mainly about what data structures can be used to calculate linear tables if linear tables are understood in a broad sense.

The body of the

Data structures, by themselves, have no precise meaning to describe categorization, but why do we always classify these data structures? The purpose is very simple, the more similar properties of the data structure as a class, and the nature of the type of abstraction, so that we can more easily understand the nature of the data structure.

However, you should never assume that this data structure must be of this type. In other words, is there truth in this world?

So the same is true for linear tables, if only to narrow the definition of linear tables, I believe that most of the data structure of linear tables, I have combed almost, but we still want to talk about a generalization of linear tables.

What is a generalization of linear tables? On the name of it, the promotion of the linear table, also is an extension of the concept of linear table, an expanded, that is to say, may look from the storage structure, the data structure is not linear structure, but we are from different angles to analyze the data structure, can discover, actually this data structure, the cognitive perspective, You can actually view it as a linear structure.

Then, this paper mainly describes two linear structures, as follows:

1. Multidimensional array
2. Generalized table

Next, let’s begin formally to understand these two data structures and why they can be called linear tables.

1. Multidimensional arrays

Before we get to multidimensional arrays, we need to know about one-dimensional arrays.

In the article I wrote the study from the very beginning – > Java data structures (3) : general linear table “, actually, I’m already tells the story of array structure, this structure is a typical sequential storage structure, but also has the typical one-to-one relationship, so we can conclude that it is necessarily a linear list, array, but here I said is a one dimensional array.

So what is a multidimensional array? Look at the picture first:

We can see that the first element of the one-dimensional array A, A0, stores A one-dimensional array B, and this form of storage is called A two-dimensional array. So if the data elements in a one-dimensional array are stored in a two-dimensional array, then that array is called a three-dimensional array, and that array form is called a multidimensional array.

In other words, an n-dimensional array can be viewed as a one-dimensional array of data elements stored in an (n-1) -dimensional array.

But we all know that one-dimensional arrays are linear tables, so multidimensional arrays can be linear tables in that sense. So we’re going to think of multidimensional arrays as an extension, a generalization of linear tables.

2. The general table

What is a generalized table?

Generalized table is a kind of discontinuous data structure, which is an extension of linear table.

In the generalized table, the atomic constraint on table elements is relaxed and each data element is allowed to have its own structure.

If only this, maybe we will have some confusion, the definition of the generalized table seems to be no different from the multidimensional array, the same is true of the multidimensional array, each data element of the multidimensional array can also be an array, which is the same as the meaning of the generalized table, right?

Note, however, that the data elements of a multidimensional array are either non-divisible data elements or arrays, not both. And generalized tables do exactly that.

Examples can be given as follows:

A = (), / / empty generalized table B = (f), / / generalized only data elements in table B C = f (g (h, I, j, k)), / / there are two elements in the generalized table C, Atomic g and child table (g, I, j, k) = (A, B, C) = D ((), (f), (g (h, I, j, k))), / / general has three child table in table D A, B, C, E = (m, E) = (m, (m, (m, (m,...). There are two elements in the generalized table E, atom A and itself. This is a recursive generalized tableCopy the code

As can be seen from these examples, generalized tables can store both non-separable data elements and generalized tables, and both can exist at the same time.

conclusion

As we all know, a general linear list is a finite sequence of zero or more data elements. But this data element, it’s all indivisible singleton. But if you let that go, then multi-dimensional arrays and generalized tables are linear tables, but strictly speaking, these two data structures are not linear structures, so we call these two data structures generalization of linear tables.