Write in front: the blogger is a real combat development after training into the cause of the “hill pig”, nickname from the cartoon “Lion King” in “Peng Peng”, always optimistic, positive attitude towards things around. My technical path from Java full stack engineer all the way to big data development, data mining field, now there are small achievements, I would like to share with you what I have learned in the past, I hope to help you on the way of learning. At the same time, the blogger also wants to build a perfect technical library through this attempt. Any anomalies, errors and matters needing attention related to the technical points of the article will be listed at the end, and everyone is welcome to provide materials in various ways.

• Please criticize any mistakes in the article and revise them in time.
• If you have any questions you would like to discuss or learn, please contact me at [email protected].
• The style of the published article varies from column to column, and all are self-contained. Please correct the deficiencies.

A series of literate data structures: sequence tables

Key words: data structure, basic structure, linear table, sequence table, structure implementation \

The article directories

• A series of literate data structures: sequence tables
• • What is a data structure
  • • Data and data structures
    • 2. Logical structure
    • 3. Storage structure
    • 4. Data operation
  • Two, linear table
  • • 1. Introduction to linear tables
    • Table 2. The order
  • Third, structural realization
  • • 1. Interface definition
    • 2. Function realization
    • 3. Invoke the test

What is a data structure

This column is a sub-column of “Manual Tearing Algorithm” column: “Data Structure”, which will describe some basic and classical data structure, and the implementation of conventional operations. Before this, we need to understand the relationship between data and structure, and what characteristics they have respectively.

Data and data structures

2. Logical structure

Logical structures are used to describe eachThe data elementThe logical relationship between data elements, mainly describes the organization of data elements, includingThe number of adjacent elements.Start node,The terminal node,precursor,The subsequentAnd so on. Where: set, tree and graph can also be collectively referred to asNonlinear structure.

• Loose structure (set)

If there is no relationship between data elements other than belonging to the same set (i.e. having some same property), the relationship can be said to be loose (not the focus of research).

• Linear structure

There is a one-to-one relationship between data elements in a linear structure. In the non-null case, there is one and only one start node and one end node. And the start node has no precursor, it has a successor; An endpoint has no successor, but a precursor; The remaining nodes have one and only one precursor and successor.

• A tree structure

A one-to-many relationship exists between data elements in a tree structure. In the non-null case, there is a node called root, which has no precursor node; Other nodes have one and only one precursor, but can have multiple successors (nodes with no successors are called leaf nodes).

• Graph structure

A many-to-many relationship exists between data elements in a graph structure. In the non-null case, any node may have more than one precursor and more than one successor.

3. Storage structure

4. Data operation

Data operation is the processing of data to achieve the desired effect, also known as data operation. After the data structure is determined, the following operations are usually performed on the data elements:

• create

Initialization of a data structure creates an actionable instance of the predefined structure.

• The destruction

The storage structure that has been created is recycled to release space (usually controlled by computers, not as the focus of research).

• insert

Inserts a specified new data element at a location in the data structure.

• delete

Removes a qualified data element from a data structure while preserving the nature of the data structure.

• To find the

Find the data elements in the data structure that meet the criteria.

• Modify the

Modifies the value of the specified data element in the data structure.

• traverse

Each data element in the data structure is accessed in some way or path once, and only once.

Two, linear table

1. Introduction to linear tables

A linear table is a finite sequence of N data elements, where N is the length of the linear table, and when n=0, the linear table is empty. All data in a linear table are of the same type, and there is a linear or one-to-one logical relationship between data elements.

1. The first element, which has no precursor, is called the start node.
2. The last element, which has no successor, is called an endpoint.
3. Other elements have one and only one precursor and successor.

• The order sheet

Sequential storage of linear tables: Sequential storage of linear tables. Each data element in a linear table is stored in a single storage cell with consecutive addresses.

• The list

Chained storage of linear lists: a linear list of chained storage, in which each node contains two parts: a data field and a pointer field. The data field is used to store the value of data elements, and the pointer field is used to store the location information of adjacent elements.

Table 2. The order

Third, structural realization

1. Interface definition

/** ** linear table function interface */
public interface IList {

    /** * set the linear table to an empty table */
    public void clear(a);

    /** * check if the linear table is empty *@returnTrue: empty false: non-empty */
    public boolean isEmpty(a);

    /** * check the length of the linear table *@returnCurrent number of data elements */
    public int length(a);

    /** * returns the data element at the specified location, and raises an out-of-bounds exception * if the index is out of range@paramI Index position *@returnThe corresponding data element */
    public Object get(int i);

    /** * Inserts a data element before the specified location, and raises an out-of-bounds exception * if the index is out of range@paramI Index position *@paramE Data element */
    public void insert(int i, Object e) throws Exception;

    /** * Removes and returns the data element at the corresponding location, or raises an out-of-bounds exception if the index is out of range@paramI Index position *@returnData element */
    public Object remove(int i) throws Exception;

    /** * returns the position of the first occurrence of the data element in the linear table, or -1 * if none exists@paramE Data element *@returnIndex position */
    public int indexOf(Object e);

    /** * traverses all the data elements in the output order table */
    public void show(a);

}
Copy the code

2. Function realization

Use Java code for sequential storage of linear tables, as follows:

/** ** sequential storage of linear tables: sequential table */
public class SequenceList implements IList {

    private Object[] elements;// Linear table storage space
    private int currentLength;// The current length of the linear table

    /** * Creates a sequential table with the specified storage size *@paramSize Storage space size */
    public SequenceList(int size){
        elements = new Object[size];
        currentLength = 0;// The initial data element in the linear table is 0
    }

    @Override
    public void clear(a) {
        currentLength = 0;
    }

    @Override
    public boolean isEmpty(a) {
        return currentLength == 0;
    }

    @Override
    public int length(a) {
        return currentLength;
    }

    @Override
    public Object get(int i) {
        if (i < 0 || i > currentLength - 1) {throw new IndexOutOfBoundsException(Index subscript out of bounds);
        }
        return elements[i];
    }

    @Override
    public void insert(int i, Object e) throws Exception {
        if (currentLength == elements.length){
            throw new Exception("Current order table is full");
        }
        if (i < 0 || i > currentLength){
            throw new IndexOutOfBoundsException(Index subscript out of bounds);
        }
        for (int j = currentLength; j > i; j--) {
            elements[j] = elements[j - 1];
        }
        elements[i] = e;
        currentLength++;
    }

    @Override
    public Object remove(int i) {
        if (i < 0 || i > currentLength - 1) {throw new IndexOutOfBoundsException(Index subscript out of bounds);
        }
        Object e = elements[i];
        for (int j = i; j < currentLength - 1; j++) {
            elements[j] = elements[j + 1];
        }
        currentLength--;
        return e;
    }

    @Override
    public int indexOf(Object e) {
        int j = 0;
        while(j < currentLength && ! elements[j].equals(e)){ j++; }if (j < currentLength){
            return j;
        }else {
            return -1; }}@Override
    public void show(a) {
        for (int i = 0; i < currentLength; i++) {
            System.out.print(elements[i] + "\t"); } System.out.println(); }}Copy the code

3. Invoke the test

public class SequenceListTest {

    public static void main(String[] args) throws Exception {
        // Implement the sequential table with a linear table, initialize a space of length 5
        IList list = new SequenceList(5);
        // Add 3 elements
        list.insert(0.10);
        list.insert(1.20);
        list.insert(2.30);
        // Look at the element in position 1
        System.out.println("The element in position 1 is:" + list.get(0));
        // Find the data element with the value 20
        System.out.println("Where element 20 first appears?" + list.indexOf(20));
        // Delete the data element in the third position
        System.out.println("Elements" + list.remove(2) + "Has been successfully deleted");
        // Iterate over the order table
        list.show();
        // Check the current number of data elements
        System.out.println("Current number of data elements is:" + list.length());
        // Clear the order table
        list.clear();
        // Check whether the sequence table is empty
        System.out.println(list.isEmpty() ? "Order list is empty" : "Sequence list is not empty"); }}Copy the code