Definition of linear table

• definition

  • Linear list: a finite sequence of zero or more data elements.

  • A linear table, as its name suggests, is a table with properties like lines.

• Linear table description

  • First of all, it is a sequence, that is, there is order between the elements

  • If there are multiple elements, the first element has no predecessor, the last element has no successor, and each other element has only one predecessor and successor.

  • If a child goes to pull the clothes behind two children, they can't line up;

  • Similarly, a child's clothes cannot be pulled by two or more children;

  • Then, the emphasis of the linear table is limited, the number of children in the class is limited, and the number of elements is of course limited.

  • In fact, the objects processed in the computer are finite, and the infinite sequence of numbers only exists in the concept of mathematics.

• For features of non empty linear table or linear structure:

  • There is a unique data element called "first";
  • There is a unique data element called "last";
  • Except for the first one, each data element in the structure has only one precursor;
  • Except for the last one, each data element in the structure has only one successor;

• It can be defined in mathematical language:

  • If the linear table is marked as (a1,..., ai-1, ai, ai+1,..., an)

    • In the table, ai-1 is ahead of AI, ai+1 is ahead of AI, and ai-1 is the direct precursor element of AI
    • ai+1 is the direct successor element of ai.
    • When i = 1,2,..., n-1, ai has only one direct successor,
    • When i = 2,3,..., n, ai has only one direct precursor.

  • As shown in the figure:

    

• Difference between merging and merging of linear tables:

  • Merge: only two linear tables are merged into one linear table. It is not guaranteed to be orderly.
  • Merge: it is required that the two linear tables are still in order after merging.

Abstract data type of linear table

We know the definition of a linear table. Let's analyze what operations a linear table should have.

In the case of children in kindergartens, in order to let children in and out in an orderly way, the teacher considered to line them up in a long-term order. This process of consideration and arrangement is actually a process of creating and initializing a linear table.

At first, I was inexperienced. After I lined up the children, I found that some were tall and some were short. The team was ugly, so I asked the children to break up and arrange again - this is an operation to reset the linear table to the empty table.

After we have lined up, we can call out the names and details of the children at a certain position in the team at any time. For example, a parent asked why the fifth child in the team was so naughty and what his name was. The teacher could quickly tell the parent that this was song Yuanqiao's son, songqingshu. This kind of data element that can be obtained according to bit order is also a very important linear table operation.

What else? Sometimes we want to know whether a child, such as Guo Jing, is a child in the class. The teacher will say, no, Guo Jing is in the Peach Blossom Island Kindergarten, not in our kindergarten. This kind of operation to find whether an element exists is very common.

Then some parents asked the teacher how many children there are in the class. It is also common to get the length of the linear table.
Obviously, it is normal for a kindergarten to add a new child to the queue or remove a position because a child is ill. For a linear table, both inserting and deleting data are necessary operations.

• dataType [Han: data type]

  • The data object set of the linear table is {a1, a2,..., an}, where the type of each element is DataType.
  • Except for the first element a1, each element has only one direct precursor element.
  • Except for the last element an, each element has only one direct successor element.
  • The relationship between data elements is one-to-one.

• Operation

  • InitList(*L): initialize to create an empty linear table L.

  • ListEmpty(L): returns true if the linear table is empty; otherwise, returns false.

  • ClearList(*L): clear the linear table.

  • GetElem(L, i, *e): returns the value of the ith position element in the linear table l to E.

  • LocateElme(L, e): finds an element equal to the given value E in the linear table L,

  • If the search is successful, the sequence number of the element in the table indicates success;

Manually implement union operation [pseudo code]

/* Insert all data elements in the linear table Lb but not in La into La */
void unionL(List *La, List Lb)
{
	int La_len, Lb_len, i;
	/* Declare the same element e as La and Lb */
	ElemType e ;
	/* Find the length of linear table */
	La_len = ListLength(*La);
	Lb_len = ListLength(Lb);
	for (i = 1; i <= Lb_len; i++)
	{
		/* Assign the ith data element in Lb to e */
		GetElem(Lb, i, &e);
		/* La The same data element as e does not exist in */
		if (!LocateElem(*La, e))
			/* insert */
			ListInsert(La, ++La_len, e);
		}
}

Linear table and its sequential storage structure

Definition of sequence table

The so-called sequential table is a linear table stored in sequence. Sequential storage is a storage structure in which each data element in a linear table is successively stored in a group of storage units with consecutive addresses

Characteristics of sequence table

• Sequential storage

  • The sequential storage structure of a linear table refers to the sequential storage of data elements of a linear table with a segment of storage units with consecutive addresses. It is one of the two physical structures of a linear table.

  • The sequential storage diagram of linear tables (a1,a2,..., an) is as follows:

    

• give an example

  In reality, there are also such examples. In the University, there are eight people in a dormitory. Xiao Yu is very honest and warm-hearted. We often ask him to help us occupy seats in the library. He always agrees. Think about it, it's obviously a bully. Every time he finished breakfast, he rushed to the library, picked a good place, and put the books in his schoolbag one by one. If there were not enough books in his schoolbag, he would use his lunch box, water cup and pen. In a long row, nine seats were occupied by him. When Xiaoyu is occupying a seat, if there are many empty seats in the library, he certainly does not have to choose the first seat in the first row, but can choose a place with good feng shui and more beautiful women. After finding it, put a schoolbag in the first position, which means that from here on, this place belongs to me for the time being.

  Then, because there were eight people, he needed to occupy eight seats. In a linear table, we estimate the maximum storage capacity of the linear table and create an array. The length of the array is the maximum storage capacity.

  But in fact, there are always a few people who are not very eager to learn in a dormitory. For games and love, they don't go to the library for self-study. Suppose eight of us go to six seats, only six seats are actually used, and the other two are empty. Similarly, we have the starting position and the maximum capacity, so we can add data in it. As the data is inserted, the length of our linear table begins to grow. However, the current length of the linear table cannot exceed the storage capacity, that is, the length of the array. If we had nine people and only eight seats, we would not be able to sit down.

• Professional description

  • The sequential storage structure of a linear table, to put it bluntly, is to find a block of space in the memory, occupy a certain memory space in the form of space occupation, and then store the data elements of the same data type in this space in turn.
  • Since the types of each data element of the linear table are the same, the sequential storage structure can be realized by using the one-dimensional array of C|java language (the same for other languages), that is, the first data element is stored in the position where the array subscript is 0, and then the adjacent elements of the linear table are stored in the adjacent positions in the array.
  • In order to build a linear table, you need to find a piece of land in the memory. Therefore, the first location of the land is very critical. It is the starting location of the storage space.

• The sequential storage structure requires three attributes:

  • The starting position of the storage space: array data. Its storage position is the storage position of the storage space.

  • Maximum storage capacity of linear table: array length MaxSize.

  • Current length of linear table: length

        private int MaxSize = 10;
        private int [] seqYaHui = new int[MaxSize];
    

• Distinguishing the length of array from that of linear table

  • The length of the array is the length of the storage space where the linear table is stored. After storage allocation, this amount is generally unchanged.
  • A one-dimensional array that can be dynamically allocated. Yes, general high-level languages, such as C, VB and c++ can use programming methods to dynamically allocate arrays, but this will bring performance losses.
  • The length of a linear table is the number of data elements in the linear table. This quantity changes with the insertion and deletion of the linear table.
  • At any time, the length of the linear table should be less than or equal to the length of the array.

Java code implementation of sequence table

Java interface description of linear table abstract data type

package linearTable;

/**
 * Java interface description of linear table abstract data type
 */
public interface IList {
    //     Set an existing linear table as an empty table
    public void clear();

    //     Judge whether the linear table is empty
    public boolean isEmpty();

    //     Find the number of data elements in the linear table and return
    public int length();

    //     Read and return the ith data element in the linear table
    public Object get(int i);

    //     Insert a data element with a value of o before the ith data element of the linear table
    public void insert(int i, Object o);

    //    Delete the ith data element in the subscript (bit sequence number) in the linear table
    public void remove(int i);

    //    Returns the subscript (bit sequence number) of the first occurrence of o in a linear table
    public int indexOf(Object o);

    //    Output all data in linear table
    public void display();
}

Implementation of linear table class

package linearTable;

/**
 * Sequential linear table and its basic operation
 */
public class SqList implements IList {
    private final Object[] listElem; // Linear table storage space

    private int curLen; // Current length

    // Constructor of sequential table to construct a linear table with storage capacity of maxSize
    public SqList(int maxSize) {
        curLen = 0; // Set the current length of the sequence table to 0
        listElem = new Object[maxSize];// Allocate maxSize storage units for the sequence table
    }

    // Make an existing linear table empty
    public void clear() {
        curLen = 0; // Set the current length of the sequence table to 0

    }

    // Judge whether the number of data elements in the current linear table is 0. If it is 0, the function returns true; otherwise, it returns false
    public boolean isEmpty() {
        return curLen == 0;
    }


    // Find the number of data elements in the linear table and return their values by the function
    public int length() {
        return curLen; // Returns the current length of the sequence table
    }

    // Read the ith data element in the linear table and return its value by the function. Where the value range of i is: 0 ≤ i ≤ length()-1. If the value of i is not in this range, an exception will be thrown
    public Object get(int i) throws Exception {
        if (i < 0 || i > curLen - 1) // i is less than 0 or greater than table length minus 1
            throw new Exception("Section" + i + "Elements do not exist"); // Output exception

        return listElem[i]; // Return the ith data element in the sequence table
    }

    // Insert a data element with a value of x before the ith data element of the linear table. Where the value range of I is: 0 ≤ I ≤ length (). If the I value is not in this range, an exception will be thrown. When i=0, it means inserting a data element x in the header. When i=length(), it means inserting a data element x in the footer
    public void insert(int i, Object x) throws Exception {
        if (curLen == listElem.length) // Judge whether the sequence table is full
            throw new Exception("Sequence table is full");// Output exception

        if (i < 0 || i > curLen) // i is less than 0 or greater than the table length
            throw new Exception("Unreasonable insertion position");// Output exception

        for (int j = curLen; j > i; j--)
            listElem[j] = listElem[j - 1];// Insert position and subsequent element move back

        listElem[i] = x; // Insert x
        curLen++;// Table length increased by 1
    }

    // Delete the ith data element in the linear table. Where the value range of i is: 0 ≤ i ≤ length()- 1. If the value of i is not in this range, an exception will be thrown
    public void remove(int i) throws Exception {
        if (i < 0 || i > curLen - 1) // i is less than 1 or greater than table length minus 1
            throw new Exception("Unreasonable deletion position");// Output exception

        for (int j = i; j < curLen - 1; j++)
            listElem[j] = listElem[j + 1];// Move element left after deleted element

        curLen--; // Table length minus 1
    }

    // Returns the index of the specified element in the linear table for the first time. If the list does not contain this element, -1
    public int indexOf(Object x) {
        int j = 0;// j is the counter
        while (j < curLen && !listElem[j].equals(x))
            // Search from the first node in the sequence table until listelement[j] points to element x or reaches the end of the sequence table
            j++;
        if (j < curLen)// Judge whether the position of j is in the table
            return j; // Returns the position of the x element in the sequence table
        else
            return -1;// The x element is not in the sequence table
    }

    // Output data elements in a linear table
    public void display() {
        for (int j = 0; j < curLen; j++)
            System.out.print(listElem[j] + " ");
        System.out.println();// Line feed

    }

    // Realize local inversion of sequence table
    public void reverse() {
        for (int i = 0, j = curLen - 1; i < j; i++, j--) {
            Object temp = listElem[i];
            listElem[i] = listElem[j];
            listElem[j] = temp;
        }
    }
}

Advantages and disadvantages of linear table sequential structure