Linear Table - Sequential Storage p18(1.10-1.12)

1.10. Store integers in one-dimensional array R, move the sequence of loops stored in R left to p positions, that is, transform the data in R from (x0, x1,..., xn-1) to (xp, XP + 1,..., xn-1, x0, x1,..., xp-1)

```//Algorithmic ideas: transform (x0, x1,..., xp-1, xp, XP + 1,..., xn-1) to (xp, XP + 1,..., xn-1, x0, x1,..., xp-1)
void reverse(int x[], int from, int to) {
int m = (to - from + 1) / 2;
for (int i = 0; i < m;i++) {
ElemType temp = x[from + i];
x[from + i] = x[to - i];
x[to - i] = temp;
}
}
void exchange(DataType x[], int p, int n) {
reverse(x, 0, n - 1);
reverse(x, 0, p - 1);
reverse(x, p, n - 1);
}```

11. The ascending sequence S whose length is L, the number of L/2 positions is called the median of S. There are two equal-length ascending sequence A and B. Find out the median of two sequences A and B.

```//Algorithmic idea: Let the median of A and B be a and b, and if a=b, they are equal. If a < b, the smaller half of A is discarded, and if a > b, the larger half of B is discarded.
int  M_search(int A[], int B[], int n) {
int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
//s stands for the first digit, d for the last digit, and m for the median.
while (s1 != d1 || s2 != d2) {
m1 = (s1 + d1) / 2;
m2 = (s2 + d2) / 2;
if (A[m1] == B[m2])
return A[m1];
if (A[m1] < A[m2]) {
if ((s1 + d1) % 2 != 0) {
s1 = m1;
d2 = m2;
}
else {
s1 = m1 + 1; //Abandon the middle point A and the part before the middle point
d2 = m2; //Discard the part after the middle point B and keep the middle point
}
}
else {
if ((s1 + d1) % 2 != 0) {
d1 = m1;
s2 = m2;
}
else {
d1 = m1;
s2 = m2 + 1;
}
}
}
return A[s1] < B[s2] ? A[s1] : B[s2];
}```

12. Known as a series of integers A, if there is ap1=ap2=...=apm=x and M > n/2, then x is called the main element of A. Assuming that n elements in A are stored in a one-dimensional array, find out the main element of A, and if not, return - 1.

```int Majority(int A[], int n) {
int i, c, count = 1; //Save candidate primary elements with c
c = A[0]; //Set A[0] as the candidate primary element
for (i = 1;i < n;i++) { //Find candidate primary elements
if (A[i] == c) count++; // count
else {
if (count > 0) count--; //The case of non-candidate principal elements
else { //Replacement of candidate primary elements and recount
c = A[i];
count = 1;
}
}
}
if (count > 0)
for (i = count = 0;i < n;i++) //Statistics of the number of occurrences of candidate principal elements
if (A[i] > 0) count++;
if (count > n / 2) return c; //Confirmation of candidate primary elements
else return -1;
}```

Added by prudens on Mon, 30 Sep 2019 20:50:52 +0300