王道数据结构

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

int fun(vector<int> array)
{
    if(array.empty())
    {
        cout << "输入的顺序表为空" << endl;
        return INT32_MIN;
    }
    int min = 0;
    for(int i = 1;i < array.size();i++)
    {
        if(array[i]<array[min])
            min = i;
    }
    swap(array[min],array[array.size()-1]);
    min = array[array.size()-1];
    array.pop_back();/**/
    return min;
}
int main()
{
    vector<int> array = {};
    int min = fun(array);
    cout << min;
    return 0;
}

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

//
// Created by Administrator on 2021-05-05.
//
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void reverse(vector<int> &array)
{
    for(int i = 0;i < array.size()/2;i++)
    {
        swap(array[i],array[array.size()-i-1]);
    }
    return;
}

int main()
{
    vector<int> array = {1,2,3,4,5};
    reverse(array);
    for_each(array.begin(),array.end(),[](int element){
       cout <<  element << " ";
    });

}

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

8.已知在一维数组A[m+n]中一次存放两个线性表(a₁,a₂,a₃,...,a_m)和(b₁,b₂,b₃,...,b_n)。试编写一个函数，将数组中的两个顺序表位置互换，即将(b₁,b₂,b₃,...,b_n)放在(a₁,a₂,a₃,...,a_m)的前面。
算法思想：先将数组A[m+n]中的全部元素(a₁,a₂,a₃,...,a_m,b₁,b₂,b₃,...,b_n)原地逆置为(b_n,b_n-1,b_n-2,...,b₁,a_m,a_m-1,a_m-2,...,a₁)，再对前n个元素和后m个元素分别使用逆置算法，即可得到(b₁,b₂,b₃,...,b_n,a₁,a₂,a₃,...,a_m)，从而实现顺序表的位置互换。

//头文件<algorithm>中已经实现了reverse函数，将[a,b)区间内的元素逆置
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;


void reverse(vector<int>& list,int left,int right)
{
    if(left >= right || right > list.size())
        return;
    int mid = (left+right) / 2;
    for(int i = 0;i <= mid - left;i++)
    {
        swap(list[left+i],list[right-i]);
    }

}
void exchange(vector<int>& list,int m,int n)
{
    reverse(list,0,m+n-1);
    reverse(list,0,n-1);
    reverse(list,n,m+n-1);
}


int main()
{
    vector<int> list = {0,1,2,3,8,9,10};
//    exchange(list,4,3);

    reverse(list.begin(),list.end());
    reverse(list.begin(),list.begin()+3);
    reverse(list.begin()+3,list.end());
    for(auto ele : list)
    {
        printf("%d ",ele);
    }
//    printf("%d",list.size());
    return 0;
}

9.线性表(a₁,a₂,a₃,...,a_n)中的元素递增有序且按顺序存储于计算机内。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素相互交换，若找不到则将其插入表中并使表中元素仍然递增有序。

王道数据结构

全站热榜