当前位置：首页 > article >正文

数据结构第二周做题总结_顺序表

article 2024/11/15 5:22:52

id:17 A. DS顺序表–类实现

题目描述

用C++语言和类实现顺序表

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

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

类定义参考
在这里插入图片描述

输入

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

输出

数据之间用空格隔开

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

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

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

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

输入样例

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

输出样例

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

提示

第i个位置是逻辑意义的位置，从1开始，在实际编程用数组，从0开始，对应数组i-1位置

题解

在主函数中构造一个类的变量，用类的成员来存储数据表，使用有参构造，传入数据表的实际长度
重载输入运算符，将输入的值传入到类的成员数据表中
在类的成员函数中，插入函数的实现是如果要插入的位置大于实际长度加一，则返回错误，否则，将插入的位置的后面元素先全部后移一位，再将该位置的元素补充，最后长度加一
删除的函数操作是，如果要删除的位置大于长度小于零，则返回错误，否则，将这个位置以后的元素全部往前移一位，然后长度减一
查询元素的操作是，首先判断位置是否合法，合法的话直接输出该位置上的元素

代码实现

#include <iostream>
using namespace std;

#define ok 0
#define error -1

// 顺序表类定义
class SeqList
{
private:
    int* list; // 元素数组
    int maxsize; // 顺序表最大长度
    int size; // 顺序表实际长度
public:
    SeqList(int n);
    ~SeqList();
    int list_size(); // 获取顺序表实际长度
    int list_insert(int i, int item); // 插入一个元素
    int list_del(int i); // 删除
    int list_get(int i); // 获取一个元素
    void list_display();
    friend istream& operator>>(istream&, SeqList&); // 重载>>
};

SeqList::SeqList(int n)
{
    maxsize = 1000;
    size = n;
    list = new int[maxsize];
}

SeqList::~SeqList()
{
    delete[] list;
}

int SeqList::list_size() // 获取顺序表实际长度
{
    return size;
}

int SeqList::list_insert(int i, int item)
{
    if (i > size + 1)
    {
        return error;
    }
    int j;
    for (j = size; j > i - 1; j--)
    {
        list[j] = list[j - 1];
    }
    list[i - 1] = item;
    size++;
    return ok;
}

int SeqList::list_del(int i)
{
    if (i > size || i < 0)
    {
        return error;
    }
    int j;
    for (j = i - 1; j < size; j++)
    {
        list[j] = list[j + 1];
    }
    size--;
    return ok;
}

int SeqList::list_get(int i)
{
    if (i > size || i < 1)
    {
        return error;
    }
    else
    {
        cout << list[i - 1];
        return ok;
    }
}

void SeqList::SeqList::list_display()
{
    int i;
    cout << size << " ";
    for (i = 0; i < size; i++)
    {
        cout << list[i] << " ";
    }
    cout << endl;
}

istream& operator>>(istream& i, SeqList& s1)
{
    int j;
    for (j = 0; j < s1.size; j++)
    {
        i >> s1.list[j];
    }
    s1.list_display();
    return i;
}

int main()
{
    int n, x1, m1, x2, m2, x3, x4, x5, x6, ans;
    ans = 11;
    cin >> n; // 长度
    SeqList a(n);
    cin >> a;

    // 插入
    cin >> x1 >> m1; // 位置和数据
    ans = a.list_insert(x1, m1);
    if (ans == ok)
    {
        a.list_display();
    }
    else
    {
        cout << "error" << endl;
    }
    cin >> x2 >> m2;
    ans = a.list_insert(x2, m2);
    if (ans == ok)
    {
        a.list_display();
    }
    else
    {
        cout << "error" << endl;
    }

    // 删除
    cin >> x3; // 位置
    ans = a.list_del(x3);
    if (ans == ok)
    {
        a.list_display();
    }
    else
    {
        cout << "error" << endl;
    }
    cin >> x4;
    ans = a.list_del(x4);
    if (ans == ok)
    {
        a.list_display();
    }
    else
    {
        cout << "error" << endl;
    }

    // 查找
    cin >> x5;
    ans = a.list_get(x5);
    if (ans == error)
    {
        cout << "error" << endl;
    }
    cin >> x6;
    ans = a.list_get(x6);
    if (ans == error)
    {
        cout << "error" << endl;
    }

    return 0;
}

id:18 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行输出执行连续删除后的顺序表内容

输入样例

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

输出样例

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

题解

类的成员和第一题一样，也是在主函数中有参构造一个类的对象，然后重载输入运算符，将输入的顺序表输入进类成员中，插入大致相同，主要是找到规律

代码实现

#include <iostream>
using namespace std;

class SeqList
{
private:
    int* list; // 元素数组
    int maxsize; // 顺序表最大长度
    int size; // 顺序表实际长度
public:
    SeqList(int n);
    ~SeqList();
    void multiinsert(int i, int n, int item[]); // 插入多个数据
    void multidel(int i, int n); // 删除多个数据
    void list_display();
    friend istream& operator>>(istream&, SeqList&); // 重载>>
};

SeqList::SeqList(int n)
{
    maxsize = 1000;
    size = n;
    list = new int[maxsize];
}

SeqList::~SeqList()
{
    delete[] list;
}

void SeqList::multiinsert(int i, int n, int item[]) // 插入多个数据
{
    int j, k;
    for (j = size + n - 1; j > i + n - 2; j--)
    {
        list[j] = list[j - 3];
    }
    for (j = i - 1, k = 0; j < (i + n - 1) && k < n; j++, k++)
    {
        list[j] = item[k];
    }
    size += n;
}

void SeqList::multidel(int i, int n) // 删除多个数据
{
    for (int j = i - 1; j < i + n - 1; j++)
    {
        list[j] = list[j + n];
    }
    size -= n;
}

void SeqList::SeqList::list_display()
{
    cout << size << " ";
    for (int i = 0; i < size; i++)
    {
        cout << list[i] << " ";
    }
    cout << endl;
}

istream& operator>>(istream& i, SeqList& s1)
{
    int j;
    for (j = 0; j < s1.size; j++)
    {
        i >> s1.list[j];
    }
    s1.list_display();
    return i;
}

int main()
{
    int n, i, k, j;
    cin >> n;
    SeqList a(n);
    cin >> a;

    // 连续插入，i表示插入开始的位置，k表示有k个插入数据
    cin >> i >> k;
    int *b = new int[k];
    for (j = 0; j < k; j++)
    {
        cin >> b[j];
    }
    a.multiinsert(i, k, b);
    a.list_display();
    delete[] b;

    // 连续删除，i表示删除开始的位置，k表示要删除k个数据
    cin >> i >> k;
    a.multidel(i, k);
    a.list_display();

    return 0;
}

id:19 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

输入样例2

3 11 33 55
5 33 44 55 88 99

输出样例2

6 11 33 44 55 88 99

代码实现

#include <iostream>
using namespace std;

class SeqList
{
private:
    int* list; // 元素数组
    int maxsize; // 顺序表最大长度
    int size; // 顺序表实际长度
public:
    SeqList(int n);
    ~SeqList();
    void add(int m1);
    void list_display();
    friend istream& operator>>(istream&, SeqList&); // 重载>>
};

SeqList::SeqList(int n)
{
    maxsize = 1000;
    size = n;
    list = new int[maxsize];
}

SeqList::~SeqList()
{
    delete[] list;
}

void SeqList::add(int m1)
{
    int i, j, temp;

    // 都输入到一个数组中
    for (i = 0; i < m1; i++)
    {
        cin >> list[size + i];
    }
    size += m1;

    // 再排序
    for (i = 0; i < size; i++)
    {
        for (j = i + 1; j < size; j++)
        {
            if (list[i] > list[j])
            {
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
    }

    // 删去重复元素
    for (i = 0; i < size - 1; i++)
    {
        if (list[i] == list[i + 1])
        {
            size--;
            for (j = i + 1; j < size; j++)
            {
                list[j] = list[j + 1];
            }
        }
    }
}

void SeqList::SeqList::list_display()
{
    cout << size << " ";
    for (int i = 0; i < size; i++)
    {
        cout << list[i] << " ";
    }
    cout << endl;
}

istream& operator>>(istream& i, SeqList& s1)
{
    int j;
    for (j = 0; j < s1.size; j++)
    {
        i >> s1.list[j];
    }
    return i;
}

int main()
{
    int n, m;
    cin >> n;
    SeqList a(n);
    cin >> a;

    cin >> m;
    a.add(m); // 合并
    a.list_display();

    return 0;
}

id:20 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

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

输出

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

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

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

输入样例

5
11 22 33 44 55
0 2
1 4

输出样例

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

代码实现

#include <iostream>
using namespace std;

int main()
{
    int n, i, dir, dis;
    cin >> n;
    int *a = new int[n + 1];
    int* b = new int[n + 1];
    int* ans = new int[n + 1];

    // 数据输入
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;

    // 移动第一次
    cin >> dir >> dis;
    if (dir == 0) // 左移
    {
        for (i = 0; i < dis + 1; i++)
        {
            b[i] = a[i + (dis % n)];
        }
        for (i = dis + 1; i < n; i++)
        {
            b[i] = a[i - (dis % n) - 1];
        }
    }
    else // 右移
    {
        for (i = 0; i < dis - 1; i++)
        {
            b[i] = a[i + n - dis];
        }
        for (i = dis; i < n; i++)
        {
            b[i] = a[n - dis - 1];
        }
    }
    for (i = 0; i < n; i++)
    {
        cout << b[i] << " ";
    }
    cout << endl;
    delete[] a;

    // 移动第二次
    cin >> dir >> dis;
    if (dir == 0) // 左移
    {
        for (i = 0; i < dis + 1; i++)
        {
            ans[i] = b[i + (dis % n)];
        }
        for (i = dis + 1; i < n; i++)
        {
            ans[i] = b[i - (dis % n) - 1];
        }
    }
    else // 右移
    {
        for (i = 0; i < dis; i++)
        {
            ans[i] = b[i + n - dis];
        }
        for (i = dis; i < n; i++)
        {
            ans[i] = b[n - dis - 1];
        }
    }
    for (i = 0; i < n; i++)
    {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

id:248 E. DS顺序表—多项式相加

题目描述

对于一元多项式 p(x)=p0+p1x+p2x2+ … +pnxn ，每个项都有系数和指数两部分，例如p2x2的系数为p2,指数为2。

编程实现两个多项式的相加。

例如5+x+2x2+3x3，-5-x+6x2+4x4，两者相加结果：8x2+3x3+4x4

其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。

需用顺序表实现。

输入

第1行：输入t表示有t组测试数据

第2行：输入n表示有第1组的第1个多项式包含n个项

第3行：输入第一项的系数和指数，以此类推输入n行

接着输入m表示第1组的第2个多项式包含m项

同理输入第2个多项式的m个项的系数和指数

参考上面输入第2组数据，以此类推输入t组

假设所有数据都是整数

输出

对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况

输出格式参考样本数据，格式要求包括：

如果指数或系数是负数，用小括号括起来。
如果系数为0，则该项不用输出。
如果指数不为0，则用符号 ^ 表示，例如x的3次方，表示为x^3。
多项式的每个项之间用符号+连接，每个+两边加1个空格隔开。

输入样例

2
4
5 0
1 1
2 2
3 3
4
-5 0
-1 1
6 2
4 4
3
-3 0
-5 1
2 2
4
9 -1
2 0
3 1
-2 2

输出样例

5 + 1x^1 + 2x^2 + 3x^3
(-5) + (-1)x^1 + 6x^2 + 4x^4
8x^2 + 3x^3 + 4x^4
(-3) + (-5)x^1 + 2x^2
9x^(-1) + 2 + 3x^1 + (-2)x^2
9x^(-1) + (-1) + (-2)x^1

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

class CDS
{
private:
    int x, z;
public:
    CDS();
    void set(int x1, int z1);
    CDS(const CDS&);
    int getZ();
    CDS add(CDS c);
    friend void print(CDS *cc, int n1);
};

CDS::CDS()
{
    x = 0;
    z = 0;
}

void CDS::set(int x1, int z1)
{
    x = x1;
    z = z1;
}

int CDS::getZ()
{
    return z;
}

CDS::CDS(const CDS& c1)
{
    x = c1.x;
    z = c1.z;
}

CDS CDS::add(CDS c)
{
    x += c.x;
    return *this;
}

void print(CDS *cc, int n1)
{
    int i;

    if (cc[0].x != 0)
    {
        // 常量
        if (cc[0].z == 0)
        {
            // 系数小于0
            if (cc[0].x < 0)
            {
                cout << "(" << cc[0].x << ")";
            }
            else
            {
                cout << cc[0].x;
            }

        }
        else
        {
            // 指数小于0
            if (cc[0].z < 0)
            {
                // 系数小于0
                if (cc[0].x < 0)
                {
                    cout << "(" << cc[0].x << ")x^(" << cc[0].z << ")";
                }
                else
                {
                    cout << cc[0].x << "x^(" << cc[0].z << ")";
                }
            }
            else
            {
                if (cc[0].x < 0)
                {
                    cout << "(" << cc[0].x << ")x^" << cc[0].z;
                }
                else
                {
                    cout << cc[0].x << "x^" << cc[0].z;
                }
            }
        }
    }

    for (i = 1; i < n1 - 1; i++)
    {
        if (cc[i].x == 0)
        {
            continue;
        }
        if (cc[i - 1].x == 0)
        {
            ;
        }
        else
        {
            cout << " + ";
        }

        // 常量
        if (cc[i].z == 0)
        {
            // 系数小于0
            if (cc[i].x < 0)
            {
                cout << "(" << cc[i].x << ")";
            }
            else
            {
                cout << cc[i].x;
            }
            
        }
        else
        {
            // 指数小于0
            if (cc[i].z < 0)
            {
                // 系数小于0
                if (cc[i].x < 0)
                {
                    cout << "(" << cc[i].x << ")x^(" << cc[i].z << ")";
                }
                else
                {
                    cout << cc[i].x << "x^(" << cc[i].z << ")";
                }
            }
            else
            {
                if (cc[i].x < 0)
                {
                    cout << "(" << cc[i].x << ")x^" << cc[i].z;
                }
                else
                {
                    cout << cc[i].x << "x^" << cc[i].z;
                }
            }
        }
    }
    if (cc[i].x != 0)
    {
        if (cc[i].x < 0)
        {
            cout << " + (" << cc[i].x << ")x^" << cc[i].z << endl;
        }
        else
        {
            cout << " + " << cc[i].x << "x^" << cc[i].z << endl;
        }
    }
}

int main()
{
    int t, i, n, m, j, x1, z1, k, ss;
    cin >> t; // 测试数据

    for (i = 0; i < t; i++)
    {
        cin >> n; // n个项
        CDS* c1 = new CDS[n + 1];
        for (j = 0; j < n; j++)
        {
            cin >> x1 >> z1;
            c1[j].set(x1, z1);
        }
        print(c1, n);

        cin >> m; // m个项
        CDS* c2 = new CDS[m + 1];
        for (j = 0; j < m; j++)
        {
            cin >> x1 >> z1;
            c2[j].set(x1, z1);
        }
        print(c2, m);

        // 相加
        // 以c1为主
        if (n >= m)
        {
            for (j = 0; j < n; j++)
            {
                for (k = 0; k < m; k++)
                {
                    if (c1[j].getZ() == c2[k].getZ())
                    {
                        c1[j].add(c2[k]);
                        break;
                    }
                    if (c1[j].getZ() < c2[k].getZ())
                    {
                        c1[j + 1] = c2[k];
                    }
                }
            }
            print(c1, n + 1);
        }
        else
        {
            for (j = 0; j < n; j++)
            {
                for (k = 0; k < m; k++)
                {
                    if (c1[j].getZ() == c2[k].getZ())
                    {
                        c2[k].add(c1[j]);
                        break;
                    }
                }
            }
            print(c2, m);
        }

        delete[] c1;
        delete[] c2;
    }
    cout << endl;

    return 0;
}