Linear Table Basics Summary

Posted on Edited on In Waline:

These two weeks took out the university’s data structures and algorithms again to look at the second chapter of the linear table part, and some new gains, I think, to summarize.

Basic concepts of data structures

Data

Data is a carrier of information, a collection of numbers, characters and all symbols that can be entered into a computer and recognized and processed by a computer program to describe the properties of objective things. Data is the raw material for computer program processing.

Data elements

A data element is the basic unit of data and is usually considered and treated as a whole. A data element can be composed of several data items, and data items are the smallest indivisible units that make up a data element. For example, a student record is a data element that consists of data items such as student number, name, etc.

Data objects

A data object is a collection of data elements with the same properties and is a subset of the data. For example, an integer object is a set N={0,1,2,…}

Data type

A data type is a generic term for a collection of values and a set of operations defined on this collection.

  • Atomic types: Data types whose values are indivisible
  • Structure type: A data type whose values can be subdivided into components (components)
  • Abstract data types: abstract data organization and the operations associated with them

Data structure

A data structure is a collection of data elements that have one or more specific relationships with each other. In any problem, data elements do not exist in isolation, they have some relationship with each other, and this relationship between data elements is called structure.

Data structure consists of three aspects: logical structure, storage structure and operations on data.

The logical structure of the data and the storage structure are two inseparable aspects.** The design of an algorithm depends on the chosen logical structure, and the implementation of the algorithm, on the storage structure used**.

Logical Structure

Logical structure refers to the logical relationship between data elements, i.e., describing the data in terms of logical relationships. It is independent of the storage structure of the data and is computer independent.

The logical structure of data is divided into linear and non-linear structures. Linear table is a typical linear structure. Sets, trees, and graphs are typical nonlinear structures.

storage structure

The storage structure is the representation of the data structure in the computer, which also becomes the physical structure.

The main ones are sequential storage, chained storage, indexed storage and hash storage.

Basic concepts of linear tables

Definition of linear table

A linear table is a finite sequence of n data elements with same data type.

Characteristics of linear tables:

  • Limited number of elements in the table
  • The elements in a table are logically sequential, and the elements in a table have their own order of precedence.
  • The elements in the table are all data elements, and each element is a single element.
  • The elements in the table all have the same data type, which means that each element occupies the same size of storage space.
  • The elements of the table are abstract in nature, i.e., the logical relationships between elements are discussed without regard to what exactly the elements represent.

**Linear table is a logical structure that represents one-to-one adjacency between elements. **

**Sequential tables and chained tables represent storage structures. **

A few simple but clever algorithmic ideas seen

First

Delete all elements whose values are between the given values s and t (containing s and t, requiring s<t) from the sequence table. If s or t is not reasonable or the sequence table is empty, an error message is displayed and the run is exited.

Algorithm idea: Scan the order table L from front to back, record the number of elements whose values are between s and t with k (initially k=0), and for the currently scanned element, if its value is no longer between s and t, move forward k positions, otherwise perform k++. Due to this, each element that is not between s and t is moved only once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool Del_s_t(SqlList &L, ElemType s, ElemType t) {
    int i, k = 0;
    if (L.length= 0 || s >= t) {
        return false;
    }
    for(i = 0; i < L.length; i++) {
        if(L.data[i] >= s && L.data[i] <= t) {
            k++
        } else {
            L.data[i - k] = L.data[i];
        }
    }
    L.length -= k;
    return true;
}

In this algorithm, i denotes the nodes currently traversed and k denotes the number of nodes to be deleted between 0 - i. This means that between 0 and (i - k) are the nodes to be kept and between (i - k) and i are the points to be deleted.

This relationship, using mathematical induction, starts when i equals 0, and in the next traversal to each node the entire relationship is guaranteed, that finally when i is L.length, the final array of reserved nodes should be 0 to L.length-k

In fact, you can also use k to indicate the number of nodes to be reserved, then this code becomes

1
2
3
4
5
6
7
8
9
10
11
12
13
bool Del_s_t(SqlList &L, ElemType s, ElemType t) {
    int i, k = 0;
    if (L.length= 0 || s >= t) {
        return false;
    }
    for(i = 0; i < L.length; i++) {
        if(L.data[i] < s || L.data[i] > t) {
            L.data[k++] = L.data[i]
        }
    }
    L.length = k;
    return true;
}

Second

Let n integers be stored into a one-bit array R. Design an algorithm that is as efficient as possible in both time and space. Shift the sequence stored in R cyclically left by p positions, i.e., the data in R changes from (X0, X1, … , XR) to (Xp, Xp+1, … XR, X0, X1, … , Xp - 1)

Algorithmic idea: Consider this problem as transforming the array ab into ba, then first invert a to get a-inverse b, then invert b to get a-inverse b-inverse, and finally invert the entire a-inverse b-inverse to get ba.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Reverse(int R[], int from, int to) {
    int i, temp;
    for(i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);
    Reverse(R, p, n - 1);
    Reverse(R, 0, n - 1);h
}

The third one

Let an ascending sequence S be of length L. The number at the position [L / 2] is called the median of S. For example, the median of an ascending sequence S1 (11, 13, 15, 17, 19) is 15. For example, if the ascending sequence S1 (11,13,15,17,19), then its median is 15. The median of two sequences is the median of the ascending sequence containing all their elements. For example, if S2 (2,4,6,8,20), then the median of S1 and S2 is 11. There are two equal ascending sequences A and B. Design a time and space efficient algorithm to find the median of A and B.

Algorithm idea 1: We can easily think of the first algorithm, because A and B are in ascending order, so set two pointers i, j, initially pointing to the first element of A and B. Then each time we compare A[i] and B[j], if A[i] is small, then i++, if B[j] is small, then j++, when comparing to the first A.length times, at this time the smaller is the median of A and B. The time complexity of this algorithm is O(n)

Algorithm idea 2: You can use the dichotomy method to improve efficiency. The procedure for finding the median of two ascending sequences A and B, set as a and b, respectively, is as follows:

  • If a=b, then a or b is the median and the result is returned.
  • If a < b, the smaller half of A is discarded, while the larger half of B is discarded, requiring that the two discards be of equal length.
  • If a > b, then discard the larger half of A while discarding the smaller half of B. The length of the two discards is required to be equal.

In retaining the two ascending sequences, the above three processes are repeated until both sequences contain only one element position, and the smaller one is the median sought.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int M_Search(int A[], int B, int n) {
    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    while(s1 != d1 || s2 != d2) {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1]= B[m2]) {
            return A[m1]
        }
        if (A[m1] < B[m2]) {
            s1 = (s1 + d1) % 2= 0 ? m1 : m1 + 1;
            d2 = m2;
        } else {
            d1 = m1;
            s2 = (s2 + d2) % 2= 0 ? m2 : m2 + 1;
        }
    }
    
    return A[s1] < B[s2] ? A[s1] : B[s2];
}