Linear Table
Linear tables are the simplest and most commonly used data structures. They are finite sequences composed of n individual data elements (nodes). Among them, the number n of data elements is the length of the table. When n is zero, it becomes an empty table. A non-empty linear table is usually recorded as:
(a1, a2,…, ai-1, ai, ai+1,…, an)
1. Sequential storage and algorithm of linear tables
The sequential storage of a linear table refers to the storage of the data elements of a linear table into a set of continuous storage units with addresses in their logical order. The linear table stored in this way is called a sequential table.
1. Structural definition of order table
public class SeqList { /* The initial space is 10 */ private static final int LIST_SIZE = 10; /* Array data is used to store elements*/ private int[] data; /* The current table is long, the actual number of elements stored*/ private int length; } 2. Insert operation
The insertion operation of the sequential table refers to inserting a new element between the i-1th element and the i-th element of the linear table. Since the adjacent elements of the sequence table are also adjacent in physical structure, their physical storage relationships must also undergo corresponding changes. Unless i=n+1, all elements starting from the i-th element of the original order table must be moved backwards by 1 position respectively.
/** * Insert a new element before the i-th position in the order table list node * @param list order table * @param i Insert position * @param node New element */public void insertList(SeqList list, int i, int node) { if (i < 1 || i > list.length + 1) { System.out.println("position error"); return; } if (list.length >= LIST_SIZE) { System.out.println("overflow"); return; } for (int j = list.length - 1; j >= i - 1; j --) { /* Start from the last element and move back one by one */ list.data[j+1] = list.data[j]; } /* Insert new element*/ list.data[i-1] = node; /* Add 1 to the table length */ list.length ++; } 3. Delete operation
The deletion operation of the sequential table refers to deleting the i-th element in the table. In contrast to the insertion operation, insertion is moving the element backward, and deletion operation is moving the element forward.
/** * Delete the i-th element in the order table list and return the deleted element* @param list Sequence table* @param i Element position* @return node */public int deleteList(SeqList list, int i) { int node = 0; if (i < 0 || i > list.length) { System.out.println("position error"); return node; } node = list.data[i-1]; for (int j = i; j < list.length; j ++) { /* Element forward*/ list.data[j-1] = list.data[j]; } list.length --; return node;} 4. Inverse order table
First, use half of the length of the table as the number of times loop control, exchange the last element in the table in the order of the first element, exchange the second last element in the order of the second element, and so on until the exchange is completed.
/** * Sequence table inverse* @param list Original order table* @return Sequence table after inverse*/public SeqList converts(SeqList list) { int node; int length = list.length/2; for (int i = 0; i < length; i ++) { /* Symmetrical exchange elements*/ int j = list.length - 1 - i; node = list.data[i]; list.data[i] = list.data[j]; list.data[j] = node; } return list; } 2. Chain storage and algorithm of linear tables
The storage space of the data elements of the chain storage structure that stores linear tables may be continuous or discontinuous, so the nodes of the linked list cannot be accessed randomly. Chain storage is one of the most common storage methods.
When using a chain storage structure to represent each data element, in addition to storing the information of the element itself, an address that indicates the storage location of the subsequent elements is also needed. The linear table represented by this storage method is called a linked list.
5. Structural definition of single linked list
public class LinkList { /* Data field*/ private char data; /* Successive element*/ private LinkList next;} 6. Table building algorithm
The header insertion method starts with an empty table, repeatedly reads the data, generates a new node, stores the read data in the data field of the new node, and then inserts the new node on the header of the current linked list until it ends.
/** * Create table by header insertion* @param chars character array* @return Single linked list*/public LinkList createListF(char[] chars) { LinkList node; LinkList head = null; for (char ch : chars) { /* Apply for a new node*/ node = new LinkList(); node.data = ch; /* Point to successor node*/ node.next = head; head = node; } /* Return to the head node*/ return head;} 7. Tail insertion method table building algorithm
The order of nodes in the header insertion table is the opposite of the order when inputting. If the order of input is consistent, the tail insertion method can be used.
/** * Tail insertion method to create table* @param chars character array* @return Single linked list*/public LinkList createListR(char[] chars) { LinkList node; LinkList head = null; LinkList rear = null; for (char ch : chars) { node = new LinkList(); node.data = ch; if (head == null) { /* The new node is the head node*/ head = node; } else { /* The previous node points to the new node*/ rear.next = node; } /* The tail of the table points to the new node*/ rear = node; } /* Return to the head node*/ return head;}The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.