[toc]

王道后面的編程題

第一部分

1

image-20210330165049293

注意由于用最后一個元素填補了前面刪去的位置,答案里長度減一了.

見仁見智吧,我覺得不減一也可以.

for(int i = 1;i<l.length;i++) 假如只有1個數(shù),不滿足i<長度1,不進行循環(huán)

int deleteMin(Dynamiclist &l){
     if(l.length==0){
        cout<<"表空"<<endl;
        return -999;
    }
    int min=l.data[0];//最小元素初始為第一個
    int index=0;//最小位置下標
    for(int i = 1;i<l.length;i++){//假如只有1個數(shù),不滿足i<長度1,不進行循環(huán)
        if(min>l.data[i]){
            min=l.data[i];
            index=i;
        }
    }
    l.data[index]=l.data[l.length-1];
    l.length--;
    return min;
}

2

image-20210330165633458

要求空間復雜度為1,就不能在重新生成一個順序表

void backwardOrder(Dynamiclist &l){
    int temp;
    for(int i=0;i<l.length/2;i++){
        temp=l.data[i];
        l.data[i]=l.data[l.length-i-1];
        l.data[l.length-i-1]=temp;
    }
}

==3==

image-20210330165745611

注意要求的時間復雜度和空間復雜度

我感覺這個思想還是很重要的,count來計數(shù)x出現(xiàn)的次數(shù),不等于值的數(shù)往前移count的位置

void deleteAllValue(Dynamiclist &l,int x){
    int count=0;//與x相等的數(shù)的個數(shù)
    for(int i=0;i<l.length;i++){
        if(l.data[i]==x){
            count++;
        }
        else{
            l.data[i-count]=l.data[i];
        }
        
    }
    l.length-=count;
}

前四個題運行

void test_Test(){
    Dynamiclist l;
    initDynamicList(l);
    for(int i=0;i<10;i++){
        insertList(l,i+1,i);
    }
    printList(l);
    cout<<"--------------------"<<endl;
    
    cout <<"最小的是"<<deleteMin( l)<<endl;
    cout <<"刪除最小的"<<endl;
    printList(l);
    cout<<"--------------------"<<endl;

    backwardOrder(l);
    cout <<"逆序后"<<endl;
    printList(l);
    cout<<"--------------------"<<endl;

   
    deleteAllValue(l,4);
    cout <<"刪除4后"<<endl;
    printList(l);
    cout<<"--------------------"<<endl;
    Dynamiclist l2;
    initDynamicList(l2);
    for(int i=0;i<8;i++){
        insertList(l2,i+1,4);
    }
    insertList(l2,9,99);
    printList(l2);
    cout<<"--------------------"<<endl;
    deleteAllValue(l2,4);
    cout <<"刪除4后"<<endl;
    printList(l2);


    cout<<"--------------------"<<endl;

第1個元素是0
第2個元素是1
第3個元素是2
第4個元素是3
第5個元素是4
第6個元素是5
第7個元素是6
第8個元素是7
第9個元素是8
第10個元素是9
--------------------
最小的是0
刪除最小的
第1個元素是9
第2個元素是1
第3個元素是2
第4個元素是3
第5個元素是4
第6個元素是5
第7個元素是6
第8個元素是7
第9個元素是8
--------------------
逆序后
第1個元素是8
第2個元素是7
第3個元素是6
第4個元素是5
第5個元素是4
第6個元素是3
第7個元素是2
第8個元素是1
第9個元素是9
--------------------
刪除4后
第1個元素是8
第2個元素是7
第3個元素是6
第4個元素是5
第5個元素是3
第6個元素是2
第7個元素是1
第8個元素是9
--------------------
第1個元素是4
第2個元素是4
第3個元素是4
第4個元素是4
第5個元素是4
第6個元素是4
第7個元素是4
第8個元素是4
第9個元素是99
--------------------
刪除4后
第1個元素是99
--------------------

第二部分

==4==

image-20210330170014220

注意是順序表,刪除的一定是一塊元素,不過我感覺還不如第三題的方法快

這里我的方法和答案不太一樣,主要是定位的方法一個是++我用的賦值

void deleteValueScopefromOrdered(Dynamiclist &l,int s,int t){
    if(l.length==0||s>=t){
        cout <<"有誤"<<endl;
        return;
    }
    int begin;//大于等于s的初始下標
    int last; //小于等于t的第一個下標
    for(int i=0;i<l.length;i++){
        if(l.data[i]<=s){
            begin=i;
        }
        if(l.data[i]<=t){
            last=i; 
        }
    }
    //假如最后一位都小于s,那么begin=l.length也就是指向最后一個的下一個,退出循環(huán)
    if(s>=l.length){
        return;
    }

    for(int i=last+1;i<l.length;i++){
        //last-begin+1 是中間數(shù)的數(shù)量
        l.data[i-(last-begin+1)]=l.data[i];
        
    } 
    l.length-=(last-begin+1);
       
}

5

image-20210330230133728

和第三題的思想差不多

void deleteValueScope(Dynamiclist &l,int s,int t){
    if(l.length==0||s>=t){
        cout <<"有誤"<<endl;
        return;
    }
    int count=0;
    for(int i=0;i<l.length;i++){
        if(l.data[i]>=s&&l.data[i]<=t){
            count++;
        }
        l.data[i-count]=l.data[i];

    }
}

4,5運行結(jié)果

注意這里第五個展示的時候還用到了動態(tài)分配的順序表的自動增長

Dynamiclist l;
    initDynamicList(l);
    for(int i=0;i<10;i++){
        insertList(l,i+1,i);
    }
    printList(l);
    deleteValueScopefromOrdered(l,3,5);
    cout<<"順序表中刪除3到5之間的數(shù)"<<endl;
    printList(l);


    cout<<"--------------------"<<endl;
    
    for(int i=0;i<10;i++){
        insertList(l,i+1,i);
    }
    printList(l);
    deleteValueScope(l,3,5);
    cout<<"刪除3到5之間的數(shù)"<<endl;
    printList(l);

第1個元素是0
第2個元素是1
第3個元素是2
第4個元素是3
第5個元素是4
第6個元素是5
第7個元素是6
第8個元素是7
第9個元素是8
第10個元素是9
順序表中刪除3到5之間的數(shù)
第1個元素是0
第2個元素是1
第3個元素是2
第4個元素是6
第5個元素是7
第6個元素是8
第7個元素是9
--------------------
第1個元素是0
第2個元素是1
第3個元素是2
第4個元素是3
第5個元素是4
第6個元素是5
第7個元素是6
第8個元素是7
第9個元素是8
第10個元素是9
第11個元素是0
第12個元素是1
第13個元素是2
第14個元素是6
第15個元素是7
第16個元素是8
第17個元素是9
刪除3到5之間的數(shù)
第1個元素是0
第2個元素是1
第3個元素是2
第4個元素是6
第5個元素是7
第6個元素是8
第7個元素是9
第8個元素是0
第9個元素是1
第10個元素是2
第11個元素是6
第12個元素是7
第13個元素是8

第三部分

==6==

image-20210330230121973

因為有序只需要比較前一個與后一個是否相同

注意這里的思想

void orderedListDeleteRepeat(Dynamiclist &l){
    int i;
    for( int j=1,i=0;j<l.length;j++){
       if(l.data[i]!=l.data[j]){
           l.data[++i]=l.data[j];
       }

    }
    l.length=i+1;
}

演示

 Dynamiclist l;
    initDynamicList(l);
    
    for(int i=0;i<10;i++){
        insertList(l,i+1,1);
    }
    insertList(l,11,9);
    insertList(l,12,99);
    printList(l);
    cout<<"刪除重復的"<<endl;
    orderedListDeleteRepeat(l);
    printList(l);

第1個元素是1
第2個元素是1
第3個元素是1
第4個元素是1
第5個元素是1
第6個元素是1
第7個元素是1
第8個元素是1
第9個元素是1
第10個元素是1
第11個元素是9
第12個元素是99
刪除重復的
第1個元素是1

==7==

image-20210330230105931

因為有序,依次比較,最后剩下的直接放到新順序表后面

Dynamiclist l;
    initDynamicList(l);
    Dynamiclist ll;
    initDynamicList(ll);
    Dynamiclist lll;
    initDynamicList(lll);
    
    for(int i=0;i<10;i++){
        insertList(l,i+1,i);
    }
     for(int i=0;i<10;i++){
        insertList(ll,i+1,i+i/2);
    }
    
    printList(l);
    printList(ll);

    cout<<"合并"<<endl;
    increaseList(lll,20);//增大容量
    combineTwoOrderedList(l,ll,lll);
    printList(lll);

結(jié)果

第1個元素是0
第2個元素是1
第3個元素是2
第4個元素是3
第5個元素是4
第6個元素是5
第7個元素是6
第8個元素是7
第9個元素是8
第10個元素是9
第1個元素是0
第2個元素是1
第3個元素是3
第4個元素是4
第5個元素是6
第6個元素是7
第7個元素是9
第8個元素是10
第9個元素是12
第10個元素是13
合并
第1個元素是0
第2個元素是0
第3個元素是1
第4個元素是1
第5個元素是2
第6個元素是3
第7個元素是3
第8個元素是4
第9個元素是4
第10個元素是5
第11個元素是6
第12個元素是6
第13個元素是7
第14個元素是7
第15個元素是8
第16個元素是9
第17個元素是9
第18個元素是10
第19個元素是12
第20個元素是13

==8==

image-20210331102944806

typedef int DataType;
//left左邊開始的下標 right結(jié)束的下標,從left到right交換
//注意是下標,所以不用減一
void reverse(DataType a[],int left,int right){
    //注意判別條件必須是中間的減去左邊的 另外取等號
    int mid=(left+right)/2;
    for(int i=0;i<=mid-left;i++){
        DataType temp;
        //注意這一段,寫錯了
        temp=a[left+i];
        a[left+i]=a[right-i];
        a[right-i]=temp;
    }

}
void exchange(DataType a[],int m,int n){
    //左邊m個元素,右邊n個元素
    reverse(a,0,m+n-1);
    reverse(a,0,n-1);
    //注意 劃分區(qū)間
    //0 n-1 n m+n-1
    reverse(a,n,m+n-1);

}

兩個函數(shù)組成,前面的復雜翻轉(zhuǎn),后面的控制翻轉(zhuǎn)

reverse(a,0,m+n-1); //整個翻轉(zhuǎn) AB--->B^-A^-

reverse(a,0,n-1); //前面翻轉(zhuǎn) B^----->B

reverse(a,m,m+n-1); //后面翻轉(zhuǎn) A^------>A

實現(xiàn)了AB-->BA

int a[7]={1,2,3,4,7,8,9};
    exchange(a,4,3);
    for(int i=0;i<7;i++){
        cout <<a[i]<<endl;
    }

結(jié)果

==9==

image-20210331110514583

快速查找,只能用二分法

//--------9
//找到元素的位置 表 元素的值
void exchange2(int mid,Dynamiclist & l){
    if(  mid!=l.length-1){
        int temp;
        temp=l.data[mid];
        l.data[mid]=l.data[l.length-1];
        l.data[l.length-1]=temp;
    }
}

void insert(Dynamiclist &l,int index,int x){
    for(int i=l.length;i>index+1;i--){
        l.data[i]=l.data[i-1];
    }
    l.data[index+1]=x;
    //別忘了長度
    l.length++;
}
//那么這里傳入的必須是引用類型,因為后面insert也要用這個參數(shù)
void search(Dynamiclist &l,int x){
    int low=0;
    int high=l.length-1;
    int mid;
    while(low<=high){
        mid=(low+high)/2;
        if(l.data[mid]==x){
            //找到了
            break;
        }
        if(l.data[mid]<x){
            low=mid+1;
        }
        else{
            high=mid-1;
        }
    }
    //是否需要插入
    if(low>high){   
        //插入在high的后面
        insert(l,high,x);       
    }
    else exchange2(mid,l);
}

運行

  //9
    Dynamiclist p;
    initDynamicList(p);
    insertList(p,1,1);
    insertList(p,2,3);
    insertList(p,3,5);
    insertList(p,4,6);
    insertList(p,5,7);
    insertList(p,6,9);
    printList(p);
    cout<<"---------"<<endl;
    //查找不存在的8
    search(p,8);
    cout<<"查找不存在的8"<<endl;
    printList(p);
    cout<<p.length<<endl;
    cout<<"---------"<<endl;
    //查找6
    search(p,6);
    cout<<"查找6"<<endl;
    printList(p);

結(jié)果

第1個元素是1
第2個元素是3
第3個元素是5
第4個元素是6
第5個元素是7
第6個元素是9
---------
查找不存在的8
第1個元素是1
第2個元素是3
第3個元素是5
第4個元素是6
第5個元素是7
第6個元素是8
第7個元素是9
7
---------
查找6
第1個元素是1
第2個元素是3
第3個元素是5
第4個元素是9
第5個元素是7
第6個元素是8
第7個元素是6

第四部分

10

image-20210331113512486

要求空間和時間都高效,就沒有新建一個順序表的做法了

循環(huán)左移,和之前那個翻轉(zhuǎn)的很像

這里和前面那個不同,用的是位序,而不是下標

//10
//翻轉(zhuǎn)的位序從begin到last
void reverse2(int a[],int begin,int last){
    int mid=(begin+last)/2;
    for(int i=0;i<=(mid-begin);i++){
        int temp=a[begin+i-1];
        a[begin+i-1]=a[last-1-i];
        a[last-1-i]=temp;

    }

}
//前一部分m個 后一部分n個 注意這里翻轉(zhuǎn)用的是位序所以不用0到m+n-1
void exchange3(int a[],int m,int n){
    reverse2(a,1,m+n);
    reverse2(a,1,n);
    reverse2(a,n+1,m+n);


}

運行

//10
    int a[7]={1,2,3,4,7,8,9};
    exchange3(a,4,3);
    for(int i=0;i<7;i++){
        cout <<a[i]<<endl;

    }

結(jié)果

時間復雜度o(n) 空間復雜度o(1)

解法2

void ten(int a[],int m,int n){
   // int b[m];棧溢出
    int* b = new int[m];
    //把a數(shù)組的前面m個放到新數(shù)組b里
    for(int i=0;i<m;i++){
        b[i]=a[i];
    }
    //a數(shù)組前移m個位置 注意n只是后面的個數(shù),所以用m來定位
    for(int i=m,j=0;i<m+n;){
        a[j++]=a[i++];
    }
    //把b數(shù)組里面的放回來
    for(int i=0;i<m;i++ ){
        a[n+i]=b[i];
    }

演示

 cout<<"解法2"<<endl;
    int b[7]={1,2,3,4,7,8,9};
    ten(b,4,3);
    for(int i=0;i<7;i++){
        cout <<b[i]<<endl;

    }

結(jié)果

==11==

image-20210331132228050

如果排序后,再找中間的位置,比較麻煩

注意這里的中間位置指L/2向下取整

兩個找中位數(shù)的序列長度相等

image-20210331134819630

理解一下.若分別求出的中文數(shù)不相同,那么說明,小的前一半以及大的那一半中,一定找不到中位數(shù),n (n n) n

注意排除的長度要相等

int searchMid(int a[],int b[],int n){
    int a1=0; //a數(shù)組的頭 下標
    int a2=n-1;  //尾下標
    int m1; //中間位置下標
    int b1=0;
    int b2=n-1;
    int m2;
    while(a1!=a2&&b1!=b2){
        m1=(a2+a1)/2;//注意是+號
        m2=(b2+b1)/2;
        if (a[m1]==b[m2]){
            return a[m1];
        }
        else if(a[m1]>b[m2]){ //舍棄a的后半部分b的前半部分
            if((a2-a1+1)%2==0){ //長度為偶數(shù)
                //a保留中間的刪除后面的
                //b保留后面的不包括中間
                //實現(xiàn)刪除的長度相同
                a2=m1;
                b1=m2+1;
            }else{
                a2=m1;
                b1=m2;
            }
        }else {
            //if(n%2==0){ 典型錯誤,不是總表的長度,而是新表
            if((a2-a1+1)%2==0){ 
                //長度為偶數(shù)
                //a保留中間的刪除后面的
                //b保留后面的不包括中間
                //實現(xiàn)刪除的長度相同
                b2=m2;
                a1=m1+1;
            }else{
                b2=m2;
                a1=m1;
            }


        }
    }
    return a[a1]<b[b1]?a[a1]:b[b1]; //升序,注意是a[a1]而不是a[m1] 

}

運行

int a[]={1,3,5,7};
     int b[]={2,4,6,8};
     cout<<"中位數(shù)是"<<searchMid(a,b,4)<<endl;
    int a2[]={1,3,5,7,9};
    int b2[]={2,4,6,8,11};
     cout<<"中位數(shù)是"<<searchMid(a2,b2,5)<<endl;

結(jié)果

中位數(shù)是4
中位數(shù)是5

第五部分

==12==

image-20210401090330048

image-20210401090600098

int findMost(int a[],int n){
    int count=1;
    int c=a[0];
    //int n=(sizeof(a)/sizeof(a[0])) ;//數(shù)組長度
    for(int i=1;i<n;i++){
        if(a[i]==c){
            count++;
        }
        else{
            if(count>0){
                count--;
            }
            else{
                c=a[i];
                //別忘了這句
                count =1;

            }
        }
    }
    if(count>0){
        count=0;
        for(int i=0;i<n;i++){
            if(c==a[i]){
                count ++;
        }
        }
    }
    if(count>n/2){
        return c;
    }
    return -1;
}

運行

  //12
    int a[]={1,2,3,4,4,7,4};
    int b[]={1,2,3,4,4,7,4,4,4};
    int n1=sizeof(a)/sizeof(a[0]);
    //注意由于數(shù)組其實是個指針,無法在函數(shù)內(nèi)求長度,求的是指針的長度
    int n2=sizeof(b)/sizeof(b[0]);
    cout<<"a的主元素"<<findMost(a,n1)<<endl;
    cout<<"b的主元素"<<findMost(b,n2)<<endl;

結(jié)果

a的主元素-1
b的主元素4

時間復雜度o(n) 空間復雜度o(1)

==13==

image-20210401090546189

空間換時間
void *memset(void *str, int c, size_t n)
str -- 指向要填充的內(nèi)存塊。

c -- 要被設置的值。該值以 int 形式傳遞，但是函數(shù)在填充內(nèi)存塊時是使用該值的無符號字符形式。

n -- 要被設置為該值的字符數(shù)。

復制字符 c（一個無符號字符）到參數(shù) str 所指向的字符串的前 n 個字符。由于只有一個字符,所以常用來初始化

int findMissMin(int a[],int n){
    int i;
    int *b=(int *)malloc(sizeof(int)*n);
    //初始化
    memset(b,0,sizeof(int)*n);//string.h
    for( i=0;i<n;i++){
        if(a[i]>0){
            b[a[i]-1]=1;
        }
    }
    for( i=0;i<n;i++){
        if(b[i]==0){
            //return i+1;  后面就返回n+1
            //優(yōu)化 返回i+1
            break;
        }
    }
    return i+1;

}

運行

 int a[]={1,2,3,4,4,7,4};
    int b[]={-1,-2,-3,-4,4,7,4};
    int n1=sizeof(a)/sizeof(a[0]);
    int n2=sizeof(b)/sizeof(b[0]);
    cout<<"a缺少的最小正元素"<<findMissMin(a,n1)<<endl;
    cout<<"b缺少的最小正元素"<<findMissMin(b,n2)<<endl;

結(jié)果

a缺少的最小正元素5
b缺少的最小正元素1

bug

編譯運行無故出現(xiàn) Cannot open output file：Permission denied可嘗試的解決辦法

關(guān)掉vscode,重新打開

變量未初始化----->變量重復定義

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一.順序表(3)

一.順序表(3)

王道后面的編程題

第一部分

1

2

==3==

前四個題運行

第二部分

==4==

5

4,5運行結(jié)果

第三部分

==6==

==7==

==8==

==9==

第四部分

10

==11==

第五部分

==12==

==13==

bug

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

一.順序表(3)

王道后面的編程題

第一部分

1

2

==3==

前四個題運行

第二部分

==4==

5

4,5運行結(jié)果

第三部分

==6==

==7==

==8==

==9==

第四部分

10

==11==

第五部分

==12==

==13==

bug

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av