2010計(jì)算機(jī)聯(lián)考真題之大題順序表.png

typedef int ElemType;
//使用靜態(tài)分配的方式創(chuàng)建一維數(shù)組：數(shù)組的大小和空間固定没佑，一旦占滿再加入新的數(shù)據(jù)會(huì)導(dǎo)致程序崩潰脸甘。 
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}Vector;

/*算法思想：借助輔助數(shù)組v_temp存儲(chǔ)原表的前p個(gè)元素，并把原順序表中p之后的元素順序前移咒唆，然后將v_temp中暫存的p個(gè)數(shù)的元素依次放回到原順序表的后續(xù)單元弯屈。*/
Vector* CircleLeftMove(Vector *v , int p){
    Vector *v_temp = (Vector*)malloc(sizeof(Vector));
    v_temp->length =  p;
    int i;
    for(i = 0;i < v->length ;i++){
        v_temp->data[i] = v->data[i];
        v->data[i] = v->data[i+p];
    }
    for(i = 0 ; i < p ;i++){
        v->data[v->length - p + i] = v_temp->data[i];
    }
    return v;
}
/*時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(p)*/

2010計(jì)算機(jī)聯(lián)考真題之大題順序表測(cè)試結(jié)果.png

解2

/*算法思想：1. 把順序表中的前p個(gè)元素逆序存儲(chǔ)睡毒，
            2. 再把順序表中的后length-p個(gè)元素逆序存儲(chǔ)谱秽，
            3. 然后把整個(gè)順序表逆序存儲(chǔ)生巡。
比如：v = 1 2 3 4 5 6 7 p = 3
    1. v = 3 2 1 4 5 6 7
    2. v = 3 2 1 7 6 5 4
    3. v = 4 5 6 7 1 2 3*/
Vector* Reverse(Vector *v , int from, int to){
    int i ; 
    ElemType temp ;
    for( i = 0 ; i < (to-from+1)/2 ; i++){
        temp = v->data[from+i];
        v->data[from+i] = v->data[to-i];
        v->data[to-i] = temp;
    }
    return v;
}

Vector* CircleLeftMove2(Vector *v , int p){
    Reverse(v,0,p-1);
    Reverse(v,p,v->length-1);
    Reverse(v,0,v->length-1);
}
/*時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(1)*/

2010計(jì)算機(jī)聯(lián)考真題之大題順序表測(cè)試結(jié)果ByReverse.png

2011計(jì)算機(jī)聯(lián)考真題之大題順序表.png

/*算法思想： 
        1.若v1.data[mid1] == v2.data[mid2]耙蔑，則mid1和mid2即為所求中位數(shù)，立即返回孤荣。
        2.若v1.data[mid1] < v2.data[mid2]2甸陌，則序列1中比mid1還要小數(shù)必不可能為所求中位數(shù)，故舍棄序列1中較小的一半
                        (若序列元素個(gè)數(shù)為奇數(shù)則舍棄中位數(shù)前的元素盐股，若為偶數(shù)則舍去包括中位數(shù)在內(nèi)的元素)钱豁，
                        同理，這時(shí)也要舍棄序列2中較大的一半
                        （兩次舍棄的長(zhǎng)度需相等疯汁，這樣才能保證同升序且等長(zhǎng)）牲尺。
        3.若v1.data[mid1] > v2.data[mid2], 則舍棄序列1中大于mid1的數(shù)，同時(shí)也要舍棄序列2中較小的一半
                        (若序列元素個(gè)數(shù)為奇數(shù)則舍棄序列2中位數(shù)的元素幌蚊，若為偶數(shù)則舍去包括中位數(shù)在內(nèi)的元素)谤碳。
            直到邏輯上的序列只含一個(gè)元素時(shí)，較小者即為所求中位數(shù)霹肝。*/
int getMidByCompare(Vector v1,Vector v2){
    int num1 = 0,num2 = 0; //num結(jié)點(diǎn)始終指向序列中的第一個(gè)元素的下標(biāo) 
    int end1 = v1.length - 1;
    int end2 = v2.length - 1;//end結(jié)點(diǎn)始終指向序列中的最后一個(gè)元素的下標(biāo) 
    int mid1 , mid2;
    while(num1 != end1 || num2 != end2){
        mid1 = (num1 + end1)/2;//邏輯上的中位數(shù)下標(biāo) 
        mid2 = (num2 + end2)/2;
        if(v1.data[mid1] == v2.data[mid2]){
            return v1.data[mid1];
        }
        if(v1.data[mid1] < v2.data[mid2]){
            if((num1+end1) %2 == 0){
                //v1的元素個(gè)數(shù)為奇數(shù) 
                num1 = mid1; //舍棄序列1中位數(shù)前的元素
                end2 = mid2;
            }else{
                num1 = mid1 + 1; //舍棄序列1中位數(shù)及中位數(shù)前的元素
                end2 = mid2;
            }
        }else{//序列1的中位數(shù)大于序列2的中位數(shù) 
            if((num2+end2)%2 == 0){
                end1 = mid1;//舍棄序列1中比中位數(shù)大的元素
                num2 = mid2; 
            }else{
                end1 = mid1;
                num2 = mid2+1; //舍棄序列2的中位數(shù)及比中位數(shù)小的元素 
            }
        }
    }
    return v1.data[num1] < v2.data[num2] ? v1.data[num1] : v2.data[num2];
}
/*時(shí)間復(fù)雜度：O(log2n) 空間復(fù)雜度：O(1)*/ 

2011計(jì)算機(jī)聯(lián)考真題之大題順序表測(cè)試結(jié)果.png

2013計(jì)算機(jī)聯(lián)考真題之大題順序表.png

/*算法思想： 
        從數(shù)組的第一個(gè)元素開(kāi)始遍歷估蹄，為每個(gè)元素設(shè)置一個(gè)count值表示數(shù)組中該元素值的元素個(gè)數(shù)，
        和后面的元素比較沫换，當(dāng)值相等時(shí)臭蚁，count+1最铁，當(dāng)某個(gè)元素的count值大于數(shù)組長(zhǎng)度一半時(shí)立刻返回該元素的值。
        當(dāng)某個(gè)元素的count值等于數(shù)組長(zhǎng)度一半時(shí)立刻返回-1垮兑，因?yàn)楸夭豢赡艽嬖谄渌闹髟亍?/
int getMain(int a[],int length){
    int i,j;
    for(i = 0; a[i] <length;.i++){
        int count = 1;
        for( j = i+1; a[j] <length;j++){
            if(a[i] == a[j]){
                count++;            
            }
        }
        if(count > length/2){
                return a[i];
        }else if(count == length/2){
            return -1;
        }
    }
    return -1;
}
/*時(shí)間復(fù)雜度：O(n^2) 空間復(fù)雜度：O(1)*/ 

/*其他解法：先排序再統(tǒng)計(jì)O(nlong2n)*/
/*最優(yōu)解：標(biāo)記一個(gè)可能成為主元素的元素冷尉。然后重新計(jì)算是否為主元素。
        1. 選取候選的主元素（數(shù)列中出現(xiàn)次數(shù)最多的元素）：
        依次掃描所給數(shù)組中的每個(gè)整數(shù)系枪，將遇到的第一個(gè)元素保存到main中雀哨，
        記錄該元素出現(xiàn)的次數(shù)為1；若遇到下一個(gè)整數(shù)仍等于main,則count+1私爷，否則count-1雾棺。
        當(dāng)count == 0時(shí)，將遇到的下一個(gè)整數(shù)保存到main中衬浑，count重新設(shè)置為1，開(kāi)始新一輪計(jì)數(shù)工秩。
        重復(fù)上述過(guò)程直到掃描完所有數(shù)組元素尸饺。
        2.判斷main是否為真正的主元素：再次遍歷數(shù)組助币，統(tǒng)計(jì)main元素出現(xiàn)的次數(shù)浪听，
        如果大于數(shù)組長(zhǎng)度一半則返回main否則返回-1.*/ 

int getMain(int a[],int length){
    int i, main , count = 1;
    main = a[0];
    for(i = 1;i < length;i++){
        if(a[i] == main){
            count++ ;
        }else{
            if(count>0){
                count--;
            }else{
                main = a[i];
                count = 1;
            }
        }
    }
    if(count > 0){
        for(i = count = 0;i<length;i++){
            if(a[i] == main){
                count++;
            }
        }
    }
    if(count > (length/2)){
        return main;
    }else return -1;
} 
/*時(shí)間復(fù)雜度：O(N),空間復(fù)雜度O(1)*/

參考資料：《王道數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)》