YakutsukuriYuu
文章 分类 标签 github
YakutsukuriYuu

线性表P19综合题(1)

 收录于  类别 考研
     约 1382 字  预计阅读 3 分钟 

L如果你害怕失敗，那你很有可能會失敗。 If you’re afraid to fail, then you’re probably going to fail.

线性表P19综合题(1)

从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位 置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

cpp

#include "Linear.h"
using namespace std;

ElemType Del_min(List &list){
    if(list.length==0) return 0;
    ElemType mmin=list.data[0];
    int pos=0;
    for(int i=0;i<list.length;++i){
        if(mmin>list.data[i]){
            mmin=list.data[i];
            pos=i;
        }

    }
    ElemType min_val=list.data[pos];
    list.data[pos]=list.data[list.length-1];
    list.length--;
    return min_val;
}

int main(){
    List list;
    list.length=0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>list.data[i];
        list.length++;
    }
    cout<<Del_min(list)<<endl;

    return 0;
}

设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

cpp

#include "Linear.h"
using namespace std;

void swap(ElemType& a,ElemType& b){
    ElemType temp=a;
    a=b;
    b=temp;
}

void Inversion(List &list){
    for(int i=0;i<list.length/2;++i){
        swap(list.data[i],list.data[list.length-1-i]);
    }
}

int main(){
    List list;
    list.length=0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>list.data[i];
        list.length++;
    }
    Inversion(list);
    for(int i=0;i<n;i++){
        cout<<list.data[i];
    }
    return 0;
}

03

对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算 法删除顺序表中所有值为×的数据元素。

cpp

#include "Linear.h"
using namespace std;

void swap(ElemType& a,ElemType& b){
    ElemType temp=a;
    a=b;
    b=temp;
}

void Del_x(List& list,ElemType x){
    int j=list.length-1;
    for(int i=0;i<=j;++i){
        if(list.data[i]==x) {
            swap(list.data[i--],list.data[j--]);
            list.length--;
        }

    }
}

int main(){
    List list;
    list.length=0;
    int n;
    int x;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>list.data[i];
        list.length++;
    }
    Del_x(list,x);
    for(int i=0;i<list.length;i++){
        cout<<list.data[i];
    }

}

//x 可能连续出现 错误代码
//     for(int i=0;i<list.length-1;++i){
//         if(list.data[i]==x) swap(list.data[i],list.data[i+1]);
//         --list.length;
//     }
//     if(list.data[list.length-1]==x) --list.length;
// }

cpp

void Del_x_01(List& list,ElemType x){ //答案的写法1
    int k=0;
    for(int i=0;i<list.length;++i){
        if(list.data[i]!=x){ //注意不等于
            list.data[k]=list.data[i];
            ++k;
        }
    }
    list.length=k;
}

cpp

//答案2的写法 用for也可以
void Del_x_02(List& list,ElemType x){ 
    int k=0;
    int i=0;
    while(i<list.length){
        if(list.data[i]==x){ 
            ++k;
        }
        else{
            list.data[i-k]=list.data[i]; 
        }
        i++;
    }
    list.length-=k;
}

04

从顺序表中删除其值在给定值s 和1 之间(包含s 和t，要求S<t )的所有元素，若了或 t 不合理或顺序表 空，则显示出错信息并退出运行。

cpp

#include "Linear.h"
using namespace std;

void swap(ElemType& a,ElemType& b){
    ElemType temp=a;
    a=b;
    b=temp;
}


bool Del_s_t(List& list,ElemType s,ElemType t){ 
    if(s>=t || list.length==0) return false;
    int j=list.length-1;
    for(int i=0;i<=j;++i){
        if(list.data[i]>=s && list.data[i]<=t){
            swap(list.data[i--],list.data[j--]);
            list.length--;
        }
    }
    return true;
}

int main(){
    List list;
    list.length=0;
    int n;
    int s;
    int t;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++){
        cin>>list.data[i];
        list.length++;
    }
    Del_s_t_01(list,s,t);
    for(int i=0;i<list.length;i++){
        cout<<list.data[i];
    }

}

cpp

//答案的写法
bool Del_s_t_01(List& list,ElemType s,ElemType t){ 
    if(s>=t || list.length==0) return false; 
    int k=0;
    for(int i=0;i<list.length;++i){
        if(list.data[i]>=s && list.data[i]<=t){ 
            k++;
        }
        else{
            list.data[i-k]=list.data[i];

        }
    }
    list.length-=k;
    return true;
}

//同理，答案没给出的写法
bool Del_s_t_02(List& list,ElemType s,ElemType t){ 
    if(s>=t || list.length==0) return false; 
    int k=0;
    for(int i=0;i<list.length;++i){
        if(list.data[i]<s || list.data[i]>t){ //注意 用或
            list.data[k]=list.data[i];
            k++;
        }
    }
    list.length=k;
    return true;
}

05

从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

cpp

#include "Linear.h"
#include <cstdlib>
#include <list>
using namespace std;
void swap(ElemType&a ,ElemType& b){
    ElemType t;
    t=a;
    a=b;
    b=t;
}

//k维护合法的数
void Del_x(List& list,ElemType x,int l,int r){
    int k=0;
    for(int i=l;i<=r;++i){
        if(list.data[i]!=x){
            list.data[k]=list.data[i];
            k++;
        }

    }


}
void Del_same(List& list){
    int p=-1;
    for(int i=0;i<list.length;++i){
        if(list.data[i]==0){
            p=i;
            break;
        }
    }
    int len=0;
    for(int i=0;i<=list.length-2;i++){
        for(int j=i+1;j<=list.length-1;++j){
            if(list.data[i]==list.data[j] && list.data[j]>=list.data[i]){
                list.data[j]=0;
            }
        }
    }
    for(int i=0;i<list.length;++i){
        if(list.data[i]!=0) len++;
    }
    //for(int i=0;i<list.length;++i)
    //    cout<<list.data[i];
    //cout<<endl;
    
    Del_x(list,0,0,p-1);
    Del_x(list,0,p+1,list.length-1);
    //cout<<"len:"<<len<<endl;
    list.length=len+(p>=0?1:0);
    //cout<<"length"<<list.length<<endl;

}
//有序表，i维护有序表，j一轮扫描
bool Del_same1(List& list){
    if(list.length==0) return false;
    int i,j;
    for(i=0,j=1;j<=list.length-1;j++){
        if(list.data[j]!=list.data[i]){
            list.data[++i]=list.data[j];
        }
    }
    list.length=i+1;
    return true;
}

int main(){
    List list;
    list.length=0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>list.data[i];
        list.length++;
    }

    Del_same(list);


    for(int i=0;i<list.length;i++){
        cout<<list.data[i];
    }

    return 0;
}

06

将两个有序 顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

cpp


#include "Linear.h"
#include <algorithm>
using namespace std;

ElemType max(ElemType a,ElemType b){
    return a>b?a:b;
}
ElemType min(ElemType a,ElemType b){
    return a<b?a:b;
}
List merge(List& list1,List& list2){
    List mlist;
    mlist.length=list1.length+list2.length;
    int j1=0,j2=0;
    for(int i=0;i<mlist.length;++i){
        if(list1.data[j1]<list2.data[j2]){
            mlist.data[i]=list1.data[j1++];
        }
        else{
            mlist.data[i]=list2.data[j2++];
            if(j2>list2.length-1) j2=list2.length-1;
        }
        if(j1==list1.length){
            for(;j2<list2.length;++j2)
                mlist.data[++i]=list2.data[j2];
                cout<<"123"<<endl;
            break;
        }
        if(j2==list2.length){
            for(;j1<list1.length;++j1)
                mlist.data[++i]=list1.data[j1++];
            break;
        }

    }
    return mlist;
}
//双指针问题，类似的问题用while会方便
List merge2(List& list1,List& list2){
    List mlist;
    mlist.length=list1.length+list2.length;
    int i=0,j=0,k=0;
    while(i<list1.length && j<list2.length){
        if(list1.data[i]<list2.data[j]) mlist.data[k++]=list1.data[i++];
        else mlist.data[k++]=list2.data[j++];
    }
    if(i<j) while(i<list1.length) mlist.data[k++]=list1.data[i++];
    else while(j<list2.length) mlist.data[k++]=list2.data[j++];
    return mlist;
}

int main(){
    List list1,list2,mlist;
    list1.length=0;
    list2.length=0;

    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>list1.data[i];
        list1.length++;
    }
    for(int i=0;i<m;i++){
        cin>>list2.data[i];
        list2.length++;
    }
    //function
    mlist=merge2(list1,list2);
    for(int i=0;i<mlist.length;i++){
        cout<<mlist.data[i];
    }

    return 0;
}

07

已知在一维数组A[m+m]中依次存放两个线性表(a1,Q2.Q3“ ，Qm)和(b162、b3， ，b.)。编写一 个函数，将数组中两个顺序表的位置互换，即将(b」，b2,b3。" ，b，)放在(al,C2、03“ ，Qw)的前面。

cpp


#include "Linear.h"
#include <algorithm>
using namespace std;

void swap(ElemType& a,ElemType& b){
    ElemType t;
    t=a;
    a=b;
    b=t;

}
void swapmn(List& list,int m,int n){

    List temp;
    temp.length=list.length;
    for(int i=0;i<=m-1;i++){
        temp.data[n+i]=list.data[i];
    }
    for(int i=m;i<=m+n-1;i++){
        temp.data[i-m]=list.data[i];
    }
    for(int i=0;i<m+n;i++)
        cout<<temp.data[i]<<" ";
    cout<<endl;
    list=temp;
    
}

int main(){
    List list;
    list.length=0;
    int n,m;
    cin>>m>>n;
    for(int i=0;i<n+m;i++){
        cin>>list.data[i];
        list.length++;
    }

    //function
    swapmn(list,m,n);
    for(int i=0;i<list.length;i++){
        cout<<list.data[i];
    }

    return 0;
}

08

线 性 表 ( a 1 , Q 2 、Q 3 “ ， Q ， ) 中 的 元 素 递 增 有 序 且 按 顺 序 存 储 于 计 算 机 内 。 要 求 设 计 一 个 算 法 ， 完 成 用 最 少 时 间 在 表 中 查 找数 值 为 x 的 元 素 ， 若 找 到 ， 则 将 其 与 后 继 元 素 位 置 相 交 换 ， 若找不到，则将其插入表中并使表中元素仍递增有序。

cpp


#include "Linear.h"
using namespace std;

bool log(List& list,ElemType x){
    ElemType l=0;
    ElemType r=list.length-1;
    ElemType p=(l+r)/2;
    bool flag=true;
    while(list.data[p]!=x){
        if(l>=r) {flag=false;break;}
        if(list.data[p]>x){
            r=p-1;
        }
        else{
            l=p+1;
        }
        p=(l+r)/2;
    }
    if(flag){
        ElemType t=list.data[p];
        list.data[p]=list.data[p+1];
        list.data[p+1]=t;
    }
    else{
        for(int i=0;i<list.length;i++)
            if(list.data[i]>x){
                for(int j=list.length-1;j>=i;j--){
                    list.data[j+1]=list.data[j];
                    
                    
                }
                list.data[i]=x;
                list.length++;
                break;
            }

    }
    return flag;
}


int main(){
    List list;
    list.length=0;
    int n,x;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>list.data[i];
        list.length++;
    }

    //function
    log(list,x);
    for(int i=0;i<list.length;i++){
        cout<<list.data[i];
    }

    return 0;
}
更新于 2024-06-02
 数据结构
 | 主页