[数据结构与算法] 王道第二章算法部分代码总结-个人使用

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 王道第二章算法部分代码总结-个人使用 -> 正文阅读

[数据结构与算法]王道第二章算法部分代码总结-个人使用

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

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;
}

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;
    }
}

删除线性表值为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;
}

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;
}

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;
}

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;
}

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;
}

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);
  
}

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]<x;
        // if 是 2 , 那么A[mid-1=high]<x;
        for (i = n-1; i > high;i --) {
            A[i+1] = A[i];
        }
        A[i+1] = x;
    }
}

10.【2010年真题】

算法的基本设计思想：

可将这个问题视为把数组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中，两个参数分别表示数组中待转换元素的始末位置。

使用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);
}

11.【2011年真题】

算法的基本设计思想

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

代码

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];
}

12.【2014年统考真题】

算法的基本设计思想

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

13.【2018年真题】

算法的基本设计思想

分配一个用于标记的数组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<A[i]<=n，则令B[A[i]-1]=1；否则不做任何操作。对A遍历结束后开始遍历数组B，若能找到第一个满足B[i]==0的下标i，返回i+1，即为结果，此时说明A中未出现的最小正整数在1~n之间。若B[i]全部不为0，返回i+1。

算法实现

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;
}

14.【2020年真题】

算法的基本设计思想

①、使用D_min记录所有已处理的三元组的最小距离，初值为一个足够大的整数。
②、集合S1、S2和S3分别保存在数组A、B、C中。数组的下标变量i=j=k=0，
当i<|S1|<j<|S2|且k<|S3|时，循环执行下面的步骤：
a) 计算(A[i],B[j],C[k])的距离D；
b) 若 D<Dmin,更新Dmin=D
c) 将A[i],B[j],C[k]中的最小值的下标+1；
③、输出Dmin，结束。
算法实现

#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;
}