数据结构OJ实验1-顺序表

A. DS顺序表--存储结构与操作

题目描述

实现顺序表的存储结构和操作

属性包括：数组、实际长度、最大长度（设定为1000）

操作包括：创建、插入、删除、查找

输入

第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据
第2行输入要插入的位置和新数据
第3行输入要插入的位置和新数据
第4行输入要删除的位置
第5行输入要删除的位置
第6行输入要查找的位置
第7行输入要查找的位置

输出

数据之间用空格隔开

第1行输出创建后的顺序表内容，包括顺序表实际长度和数据

每成功执行一次操作（插入或删除），输出执行后的顺序表内容

每成功执行一次查找，输出查找到的数据

如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出顺序表内容

输入样例1

6?11?22?33?44?55?66
3?777
1?888
1
9
0
5

输出样例1

6?11?22?33?44?55?66?
7?11?22?777?33?44?55?66?
8?888?11?22?777?33?44?55?66?
7?11?22?777?33?44?55?66?
error
error
44

AC代码

#include<bits/stdc++.h>
using namespace std;
class seqlist
{
    vector<int>v;
    int size;
    int maxlen;
public:
    seqlist()
    {
        maxlen=1000;
        cin>>size;
        v.resize(size);
        for(int i=0;i<size;i++)
        {
            cin>>v[i];
        }
    }
    void display()
    {
        cout<<size<<" ";
        for(int i=0;i<size;i++)
        {
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }
    void Insert(int idx,int data)
    {
        //idx从1开始要还原
        idx--;
        if(idx<0||idx>size)//可以最后插入
        {
            cout<<"error"<<endl;
            return;
        }
        int temp=v[idx];
        v.push_back(0);//增加空位
        for(int i=size-1;i>=idx;i--)
        {
            v[i+1]=v[i];
        }
        size++;
        v[idx]=data;
        display();
    }
    void Delete(int idx)
    {
        idx--;
        if(idx<0||idx>=size)
        {
            cout<<"error"<<endl;
            return;
        }
        for(int i=idx;i+1<size;i++)
        {
            v[i]=v[i+1];
        }
        size--;
        display();
    }
    void Find(int idx)
    {
        idx--;
        if(idx<0||idx>=size)
        {
            cout<<"error"<<endl;
            return;
        }
        cout<<v[idx]<<endl;
    }
};
int main()
{
    seqlist s;
    s.display();
    for(int i=0;i<2;i++)
    {
        int x,y;
        cin>>x>>y;
        s.Insert(x,y);
    }
    for(int i=0;i<2;i++)
    {
        int x;
        cin>>x;
        s.Delete(x);
    }
    for(int i=0;i<2;i++)
    {
        int x;
        cin>>x;
        s.Find(x);
    }
    return 0;
}

B. DS顺序表--连续操作

题目描述

建立顺序表的存储结构，属性包括：数组、实际长度、最大长度（设定为1000）

编写如下函数

实现顺序表的初始化函数。

插入多个数据的multiinsert(int i, int n, int item[])函数，实现在第i个位置，连续插入来自数组item的n个数据，即从位置i开始插入多个数据。

删除多个数据的multidel(int i, int n)函数，实现从第i个位置开始，连续删除n个数据，即从位置i开始删除多个数据。

编写main函数测试该顺序表。

输入

第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据

第2行先输入i表示插入开始的位置，再输入k表示有k个插入数据，接着输入k个数据

第3行先输入i表示删除开始的位置，再输入k表示要删除k个数据

输出

顺序表内容包括顺序表的实际长度和数据，数据之间用空格隔开

第1行输出创建后的顺序表内容

第2行输出执行连续插入后的顺序表内容

第3行输出执行连续删除后的顺序表内容

样例查看模式?

正常显示查看格式

输入样例1?

6?11?22?33?44?55?66
2?3?99?88?77
4?5

输出样例1

6?11?22?33?44?55?66
9?11?99?88?77?22?33?44?55?66
4?11?99?88?66?

AC代码

#include<bits/stdc++.h>
using namespace std;
class seqlist
{
    vector<int>v;
    int size;
    int maxlen;
public:
    seqlist()
    {
        maxlen=1000;
        cin>>size;
        v.resize(size);
        for(int i=0;i<size;i++)
        {
            cin>>v[i];
        }
    }
    void display()
    {
        cout<<size<<" ";
        for(int i=0;i<size;i++)
        {
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }
    void Insert(int idx,int data)
    {
        //idx从1开始要还原
        idx--;
        if(idx<0||idx>size)//可以最后插入
        {
            cout<<"error"<<endl;
            return;
        }
        int temp=v[idx];
        v.push_back(0);//增加空位
        for(int i=size-1;i>=idx;i--)
        {
            v[i+1]=v[i];
        }
        size++;
        v[idx]=data;
        display();
    }
    void Delete(int idx)
    {
        idx--;
        if(idx<0||idx>=size)
        {
            cout<<"error"<<endl;
            return;
        }
        for(int i=idx;i+1<size;i++)
        {
            v[i]=v[i+1];
        }
        size--;
        display();
    }
    void Find(int idx)
    {
        idx--;
        if(idx<0||idx>=size)
        {
            cout<<"error"<<endl;
            return;
        }
        cout<<v[idx]<<endl;
    }
    void MultiInsert(int idx,int n,vector<int>vv)
    {
        idx--;
        for(int i=0;i<n;i++)v.push_back(0);
        for(int i=size-1+n;i>=idx+n;i--)
        {
            v[i]=v[i-n];
        }
        for(int i=idx,j=0;i<idx+n;i++,j++)
        {
            v[i]=vv[j];
        }
        size+=n;
        display();
    }
    void MultiDelete(int idx,int n)
    {
        idx--;
        for(int i=idx;i<=size-1-n;i++)
        {
            v[i]=v[i+n];
        }
        size-=n;
        display();
    }
};
int main()
{
    seqlist s;
    s.display();
    int idx,k;
    cin>>idx>>k;
    vector<int>vv;
    for(int i=0;i<k;i++)
    {
        int x;
        cin>>x;
        vv.push_back(x);
    }
    s.MultiInsert(idx,k,vv);
    cin>>idx>>k;
    s.MultiDelete(idx,k);
    return 0;
}

C. DS顺序表--合并操作

题目描述

建立顺序表数据类型，属性包括：数组、实际长度、最大长度（设定为1000）

已知两个递增序列，把两个序列的数据合并到顺序表中，并使得顺序表的数据递增有序

输入

第1行先输入n表示有n个数据，接着输入n个数据，表示第1个序列，要求数据递增互不等

第2行先输入m表示有m个数据，接着输入m个数据，表示第2个序列，要求数据递增互不等

输出

顺序表内容包括顺序表的实际长度和数据，数据之间用空格隔开

第1行输出创建后的顺序表内容

样例查看模式?

正常显示查看格式

输入样例1

3?11?33?55
5?22?44?66?88?99

输出样例1

8?11?22?33?44?55?66?88?99

AC代码

#include<bits/stdc++.h>
using namespace std;
class seqlist
{
    vector<int>v;
    int size;
    int maxlen;
public:
    seqlist()
    {
        maxlen=1000;
        cin>>size;
        v.resize(size);
        for(int i=0;i<size;i++)
        {
            cin>>v[i];
        }
    }
    void display()
    {
        cout<<size<<" ";
        for(int i=0;i<size;i++)
        {
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }
    void Insert(int idx,int data)
    {
        //idx从1开始要还原
        idx--;
        if(idx<0||idx>size)//可以最后插入
        {
            cout<<"error"<<endl;
            return;
        }
        int temp=v[idx];
        v.push_back(0);//增加空位
        for(int i=size-1;i>=idx;i--)
        {
            v[i+1]=v[i];
        }
        size++;
        v[idx]=data;
        display();
    }
    void Delete(int idx)
    {
        idx--;
        if(idx<0||idx>=size)
        {
            cout<<"error"<<endl;
            return;
        }
        for(int i=idx;i+1<size;i++)
        {
            v[i]=v[i+1];
        }
        size--;
        display();
    }
    void Find(int idx)
    {
        idx--;
        if(idx<0||idx>=size)
        {
            cout<<"error"<<endl;
            return;
        }
        cout<<v[idx]<<endl;
    }
    void MultiInsert(int idx,int n,vector<int>vv)
    {
        idx--;
        for(int i=0;i<n;i++)v.push_back(0);
        for(int i=size-1+n;i>=idx+n;i--)
        {
            v[i]=v[i-n];
        }
        for(int i=idx,j=0;i<idx+n;i++,j++)
        {
            v[i]=vv[j];
        }
        size+=n;
        display();
    }
    void MultiDelete(int idx,int n)
    {
        idx--;
        for(int i=idx;i<=size-1-n;i++)
        {
            v[i]=v[i+n];
        }
        size-=n;
        display();
    }
    void Merge(vector<int>u)
    {
        int n=u.size();
        for(int i=0;i<n;i++)
        {
            v.push_back(u[i]);
        }
        sort(v.begin(),v.end());
        size+=n;
        display();
    }
    vector<int> getv()
    {
        return v;
    }
};
int main()
{
    seqlist s;
    seqlist q;
    s.Merge(q.getv());
    return 0;
}

D. DS顺序表之循环移位

题目描述

顺序表的移位是循环移位，例如顺序表：1，2，3，4，5，6。如果左移1位，即原来的头元素移动到末尾，其它元素向左移1位，变成2，3，4，5，6，1。同理，如果右移1位，即原来的尾元素移动到头，其它元素向右移1位，变成6，1，2，3，4，5。以下是移位的多个例子：

原数据：1，2，3，4，5，6

左移3位：4，5，6，1，2，3，与原数据对比

右移4位：3，4，5，6，1，2，与原数据对比

请编写程序实现顺序表的循环移位操作

输入

第1行输入n表示顺序表包含的·n个数据

第2行输入n个数据，数据是小于100的正整数

第3行输入移动方向和移动的位数，左移方向为0，右移方向为1

第4行输入移动方向和移动的位数，左移方向为0，右移方向为1

注意：移动操作是针对上一次移动后的结果进行的

输出

第一行输出创建后，顺序表内的所有数据，数据之间用空格隔开

第二行输出第一次移位操作后，顺序表内的所有数据，数据之间用空格隔开

第三行输出第二次移位操作后，顺序表内的所有数据，数据之间用空格隔开

样例查看模式?

正常显示查看格式

输入样例1

5
11?22?33?44?55
0?2
1?4

输出样例1

11?22?33?44?55?
33?44?55?11?22?
44?55?11?22?33?

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
void display()
{
    for(int i=0;i<n;i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
void transform(int op,int k)
{
    vector<int>temp;
    temp=v;
    if(op==0)//左移
    {
        for(int i=0;i<n;i++)
        {
            v[i]=temp[(i+k)%n];
        }
    }
    else//右移
    {
        for(int i=0;i<n;i++)
        {
            v[i]=temp[(i-k+n)%n];
        }
    }
}
int main()
{
    cin>>n;
    v.resize(n);
    for(int i=0;i<n;i++)cin>>v[i];
    display();
    int op,k;
    for(int i=0;i<2;i++)
    {
        cin>>op>>k;
        transform(op,k);
        display();
    }
    return 0;
}

E. 计算2支股票的M天运动平均价格

题目描述

给定2支股票的开盘价和收盘价的N天历史数据，

要求按开盘和收盘，分别计算每支股票的每个日期对应的M天移动平均价格。

假定两个股票数据如下：

日期 ? ? ? ? ? ?开盘/收盘 ? ? ?第1支股票价格S1 ? ? ? 第2支股票价格S2

2004/7/29 close 6 4

2004/7/25 close 2 6

2004/7/26 open 8 12

2004/7/30 open 2 4

2004/7/27 close 8 10

2004/7/28 open 4 2

按M=2天（日期不用连续）计算移动平均价格，按先开盘，后收盘价，输出如下：（若某日期之前，没有M-1条的记录（日期不用连续），则不用输出）

2004/7/28 open 6 7

2004/7/30 open 3 3

2004/7/27 close 5 8

2004/7/29 close 7 7

其中, 2004/7/28日的S1的值为(8+4)/2 = 6， 即将2004/7/28和（最近1条记录2004/7/26，最近2条记录，最近M-1条记录）的价格，求和并计算平均。

输入

第1行：N天记录 ? M天平均

第2行到N+1行：N天2支股票的开盘与收盘价格（注意日期是无序的）

6 ?2

2004/7/29 close 6 4

2004/7/25 close 2 6

2004/7/26 open 8 12

2004/7/30 open 2 4

2004/7/27 close 8 10

2004/7/28 open 4 2

输出

每个日期的最近M条记录（包括该日期的价格在内）的平均价格（若某日期之前没有M-1条的记录（日期不用连续），则不用输出）

2004/7/28 open 6 7

2004/7/30 open 3 3

2004/7/27 close 5 8

2004/7/29 close 7 7

样例查看模式?

正常显示查看格式

输入样例1?

6??2
2004/7/29???close??????6??4
2004/7/25???close??????2??????6
2004/7/26???open??????8??????12
2004/7/30???open??????2??????4
2004/7/27???close??????8??????10
2004/7/28???open??????4???????2

输出样例1

2004/7/28?open?6?7
2004/7/30?open?3?3
2004/7/27?close?5?8
2004/7/29?close?7?7

AC代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
vector<pair<string,pii>>Open;
vector<pair<string,pii>>Close;
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string s1,s2;
        int x,y;
        cin>>s1>>s2>>x>>y;
        if(s2=="close")
        {
            Close.push_back({s1,{x,y}});
        }
        else
        {
            Open.push_back({s1,{x,y}});
        }
    }
    sort(Close.begin(),Close.end());
    sort(Open.begin(),Open.end());
    for(int i=0;i<Open.size();i++)
    {
        if(i+m-1>=Open.size())break;
        int sum1=0;
        int sum2=0;
        for(int j=i;j<i+m;j++)
        {
            sum1+=Open[j].second.first;
            sum2+=Open[j].second.second;
        }
        cout<<Open[i+m-1].first<<" open "<<sum1/m<<" "<<sum2/m<<endl;
    }
     for(int i=0;i<Close.size();i++)
    {
        if(i+m-1>=Close.size())break;
        int sum1=0;
        int sum2=0;
        for(int j=i;j<i+m;j++)
        {
            sum1+=Close[j].second.first;
            sum2+=Close[j].second.second;
        }
        cout<<Close[i+m-1].first<<" close "<<sum1/m<<" "<<sum2/m<<endl;
    }
    return 0;
}