王道第二章算法部分代码总结-个人使用

1. 从顺序表中删除具有最小值的元素（唯一）

bool Del_Min(sqList &L,ElemType &value) {
    if (L.Length==0) {
        return false;
    }
    value = L.data[0];
    int pos=0;
    for (int i = 1;i < L.length; i ++) {
        i f(L.data[i] < value ) {
            value = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length-1];
    L.length --;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.逆置顺序表

void Reverse (Sqlist &L) {
    Elemtype temp;
    int n = L.length;
    for (int i = 0;i < n/2;i ++) {
        temp = L.data[i];
        L.data[i] = L.data[n-i-1];
        L.data[n-i-1] = temp;
    }
}
1
2
3
4
5
6
7
8
9

3. 删除线性表值为x的元素

void del_x_l(Sqlist &L,Elemtype x) {
    int k = 0,i;
    for (i = 0;i < L.length;i ++) {
        if (L.data[i] !=x) {
            L.data[k] = L.data[i];k++;
        }
    }
    L.lenth = k;
}
1
2
3
4
5
6
7
8
9

bool Del_s_t2(Sqlist &L,ElemType s,Elemtype t) {
    int i ,j;
    if (i = 0;i < L.length && L.data[i] <s ;i ++) ;
    if (i >= L.length)  return false;
    for (j = i;j < L.length &&L.data[j] <= t; j ++) ;
    for (;j < L.length;j ++,i ++) 
        L.data[i] = L.data[j];
    L.length = i;
    return true;
}
1
2
3
4
5
6
7
8
9
10

5

bool Del_s_t(SqList &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;
}
1
2
3
4
5
6
7
8
9
10

6

bool Delete_Same(SeqList &L) {
    if (L.length == 0) {
        return false;
    }
    int i ,j ;
    for (i = 0,j = 1;j < L.length;j ++) {
        if(L.data[i] !=L.data[j]) L.data[++i] = L.data[j];
    }
    L.length = i + 1;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11

7

bool Merge (SeqList A,SeqList B,SeqList C) {
    if (A.length+B.length>C.maxSize) return false;
    int i = 0,j = 0,k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] <= B.data[j]) 
            C.data[k ++] = A.data[i ++];
        else 
            C.data[k ++] = B.data[j ++];
    }
    while (i < A.length)
        C.data[k ++] = A.data[i ++];
    while (j < B.length) 
        C.data[k ++] = B.data[j ++];
    C.length = k;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8

typedef int DataType;
void Reverse(DataType A[],int left,int right,int arraySize) {
    if (left>=right || right >= arraySize) return;
    int mid = (left + right)/2;
    for (int i = 0;i <= mid-left;i ++) {
        DataType temp = A[left+i];
        A[left+i] = A[right - i];
        A[right-i]=temp;
    }
}
void Exchange(DataType A[],int m,int n,int arraySize) {
    Reverse(A,0,m+n-1,arraySize);
    Reverse(A,0,n-1,arraySize);
    Reverse(A,n,m+n-1,arraySize);
  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9

void SearchExchangeInsert(ElemType A[],ElemType x) {
    int low = 0,high = n-1,mid;
    while (low <= high) {
        mid = (low+high)/2;
        if (A[mid] == x) break;
        else if (A[mid] < x) low = mid + 1; // 1
        else high = mid - 1;                // 2
    }
    // 若最后一个元素与x相等，则不存在与其后继交换的操作
    if (A[mid] == x&&mid != n-1) {
        t = A[mid];A[mid] = A[mid + 1];A[mid + 1] = t;
    }
    if (low > high) {
        // 关于这里为啥最后是 A[high] 是小于x的：
        // 跳出循环的那一步应该是 mid == high == low;
        // if 是上部 1 处是最后一步，那么A[mid=high=low]
        // if 是 2 , 那么A[mid-1=high]
        for (i = n-1; i > high;i --) {
            A[i+1] = A[i];
        }
        A[i+1] = x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

10.【2010年真题】

1. 算法的基本设计思想：

可将这个问题视为把数组ab转换成数组ba（a代表数组的前 p 个元素，b 代表数组中余下的 n-p 个元素），先将
a 逆置 得到 $a^{-1}b$，再将 b 逆置得到 $a^{{}_1}{b}^{-1}$，最后将 $a^{{}_1}{b}^{-1}$ 逆置得到 ba。
设 Reverse 函数执行将数组元素逆置的操作，对 abcdefg 向左循环移动 3 个位置的过程如下：
Reverse(0,p-1)
Reverse(p,n-1)
Reverse(0,n-1)
注： Reverse中，两个参数分别表示数组中待转换元素的始末位置。

2. 使用C语言描述如下

   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);
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13

11.【2011年真题】

1. 算法的基本设计思想

分别求两个升序序列 A，B 的中位数，设为 a 和 b，求序列A、B的中位数过程如下：
①：若a==b，则a或b即为，所求中位数，算法结束。
②：若a ③：若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等
在保留的两个升序序列中，重复过程①，②，③，知道两个序列中均只含一个元素时为止。

2. 代码

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]) {
            if ((s1+d1)%2==0) {
                s1 = m1;d2 = m2;
            } else {
                s1 = m1 + 1;
                d2 = m2;
            }
        }
        else {
            if ((s2+d2)%2 == 0) {
                d1 = m1;
                s2 = m2;
            } else {
                d1 = m1;
                s2 = m2 + 1;
            }
        }
    }
    return A[s1] < B[s2]?A[s1]:B[s2];
}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]) {
            if ((s1+d1)%2==0) {
                s1 = m1;d2 = m2;
            } else {
                s1 = m1 + 1;
                d2 = m2;
            }
        }
        else {
            if ((s2+d2)%2 == 0) {
                d1 = m1;
                s2 = m2;
            } else {
                d1 = m1;
                s2 = m2 + 1;
            }
        }
    }
    return A[s1] < B[s2]?A[s1]:B[s2];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

12.【2014年统考真题】

1. 算法的基本设计思想

算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数确认Num
是否是主元素。
算法可分为以下两步：
①、选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num
的出现次数为1；若遇到的下一个整数仍等于Num，则计数加一，否则计数减一；当计数减到0时，将遇到的下一个
整数保存到c中，计数重新计为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部
数组元素。
②、判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；
否则序列中不存在主元素。

2. 算法实现

int Majority(int A[],int n)
{
    int i,c,count = 1;
    c = A[0];
    for (i = 1;i < n;i ++) {
        if (A[i] == c) count ++;
        else
            if (count > 0) count --;
            else {
                c = A[i];count = 1;
            }
    }
    if (count > 0) {
        for (i = count = 0;i < n;i ++) 
            if (A[i] == c) count ++;
    }
    if (count > n/2) return c;
    else return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

13.【2018年真题】

1. 算法的基本设计思想

分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应 正整数n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1~n+1,当A中n个数恰好为1~n时返回 n+1。当数组A中出现了小于等于0或大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此 对于A中出现了小于等于0或大于n的值，可以不采取任何操作。 算法流程：从A[0]开始遍历A，若0

int findMissMin(int A[],int n) 
{
    int i,*B;
    B = (int *)malloc(sizeof(int)*n);

    memset(B,0,sizeof(int)*n);
    for (i = 0;i < n;i ++) {
        if (A[i] > 0&&A[i]<=n) 
            B[A[i]-1] = 1;
    }
    for (i = 0;i < n;i ++) 
        if (B[i] == 0) break;
    return i + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#define INT_MAX 0x7fffffff
int abs_(int a) 
{
    if (a < 0) return -a;
    else return a;
}

bool xls_min(int a,int b,int c)
{
    if (a <= b&&a <= c) return true;
    return false;
}

int findMinofTrip(int A[],int n,int B[],int m,int C[],int p)
{
    int i = 0,j = 0,k = 0,D_min = INT_MAX,D;
    while (i < n&& j < m&&k < p&&D_min > 0) {
        D = abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]);
        if (D<D_min) D_min = D;
        if(xls_min (A[i],B[j],C[k])) i ++;
        else if (xls_min(B[j],C[k],A[i])) j ++;
        else k ++;
    }
    return D_min;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25