Data Structure (2nd edition), tsinghua University press, yan Weimin, Wu Weimin, Ed.

Logical structure of linear tables

A linear table is a data structure. A linear table is a finite sequence of n data elements. The relation N is a set of order pairs that represent the adjacent relations between data elements in a linear table, i.e. a I -1 leads a I, and a I leads a I +1.

In a slightly more complex linear table, a data element can be composed of several data items. The data elements are called records, and a large linear table is called a file. Data elements can be diverse, but elements in the same linear table must have the same properties and therefore be unified data objects.

A school’s student health status file, each student’s situation for a record, by name, student number, gender, age, class and health status and other six data items.

Basic operations on linear tables:

  1. INITIATE(L) INITIATE the initialization operation. Set an empty linear table L.
  2. LENGTH(L) to find the LENGTH function. The function value is the number of data elements in a given linear table L.
  3. GET(L, I) takes the element function. If 1≤ I ≤LENGTH(L)1\leq I \ LEq LENGTH(L)1≤ I ≤LENGTH(L), the function value is the ith data element in the given linear table L, otherwise it is NULL. Call I the bit order of the data element in a linear table.
  4. PRIOR(L,elm) It is known that ELM is the first data element in a given linear table L. If its bit order is greater than 1, the function value is the precursor of ELM; otherwise, it is an empty element.
  5. NEXT(L, ELM) to find the successor function. It is known that ELM is a data element in a given linear table L. If its bit order is less than LENGTH(L), the function value is the successor of ELM; otherwise, it is an empty element.
  6. LOCATE(L,x) LOCATE functions. Given the value x, if there is a data element in the linear table L whose value is equal to x, the function value is the bit order of the data element in the linear table, otherwise zero.
  7. INSERT(L, I,b) Insert a new data element B before the ith data element in the given linear table L.
  8. DELETE(L, I) DELETE operation. Delete the ith data element from the given linear table L.
  9. EMPTY(L) nulls the table function.
  10. CLEAR(L) Indicates that the table is empty. Result Set L to an empty table.

The sequential storage structure of linear tables

The elements of a linear table are stored in sequence by a set of storage cells with contiguous addresses, and the two elements that are logically adjacent are physically adjacent.

Assume that each element of a linear table needs to occupy L storage cells, and the storage address of the first cell is used as the storage location of data. In general, the ith element a I of a linear table is stored as:


L O C ( a i ) = L O C ( a i ) + ( i – 1 ) ∗ l LOC(a_i)=LOC(a_i)+(i-1)*l

LOC(A1)LOC(a_1)LOC(A1) is the storage location of the first data element a1A_1A1 in a linear table. It is usually called the starting location or base address of a linear table. It assigns adjacent storage locations LOC(ai)LOC(a_i)LOC(ai +1)LOC(a_{I +1})LOC(ai+1). In other words, the logical relationship between data elements in a linear table is represented by the physical proximity of the elements within the computer. As long as the starting position of the linear table is determined, any data element in the linear table can be randomly accessed, so the sequential storage structure of the linear table is a random access storage structure.

When inserting or deleting a data element at a certain position in a sequential linear table, the time is mainly spent on moving the element, and the number of moving elements depends on the position of inserting or deleting the element.

Chain storage structure for linear lists

The sequential storage structure of linear tables has three weaknesses: 1. A large number of elements need to be moved when inserting; 2. 2. When allocating space in advance, it must be allocated according to the maximum space; 3. The table capacity cannot be expanded.

The data elements of a linear table are stored in an arbitrary set of storage units, which may or may not be contiguous. The storage image of a data element is called a node (data domain + pointer domain), and n nodes are linked into a linked list.

The entire list must be accessed from the head pointer, which indicates the storage location of the first node in the list. Since the last data element has no direct successor, the pointer of the last node in the linear list is null.

When a linear linked list is used to represent a linear list, the logical relationship between data elements is indicated by the pointer in the node, and the physical location of storage of two data elements that are logically adjacent is not required to be adjacent.

Circular linked list

Another form of chained storage structure. The pointer field of the last node in the table points to the head node, and the whole list forms a ring. Starting from any node in the table can find other nodes in the table.

A circular list is basically the same as a linear linked list, except that the circular condition is determined to be equal to the head pointer.

Two-way linked list

In order to overcome the unidirectional disadvantage of single linked list, bidirectional linked list is produced. In a bidirectional linked list, a node has two pointer fields, one pointing to a direct successor and the other to a direct precursor.

A doubly linked list can also have a doubly circular list.