AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构 顺序表（上）

2022-12-04 100
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构 顺序表

1. DS顺序表–类实现


题目描述


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

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

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

类定义参考


64dc07a9f5e84841b142deb7183fff31.png


输入


第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


参考代码


#include <bits/stdc++.h>
#define ok 0
#define error -1
using namespace std;
class SeqList {
private:
    int *list;  //元素数组
    int maxsize;    //顺序表最大长度
    int size;   //顺序表实际长度
public:
    //构造函数
    SeqList() {
        maxsize = 1000;
        size = 0;
        list = new int[maxsize];
    }
    //析构函数
    ~SeqList() {
        delete[]list;
    }
    //获取顺序表实际长度
    int list_size() {
        return size;
    }
    //插入一个元素，参数是插入的数值和位置
    int list_insert(int i, int item) {
        //插入位置为i，在list中数组下标为i-1
        //对应数组下标不能小于0，也不能大于当前数组长度
        if (i - 1 < 0 || i - 1 > size)
            return error;
        //从第i-1个元素开始，将后面所有的元素后移一位
        for (int j = size - 1; j >= i - 1; j--)
            list[j + 1] = list[j];
        //在i位置插入item元素
        list[i - 1] = item;
        //实际长度+1
        size++;
        return ok;
    }
    //删除一个元素，参数是删除的位置
    int list_del(int i) {
        //插入位置为i，在list中数组下标为i-1
        //对应数组下标不能小于0，也不能大于等于当前数组长度
        if (i - 1 < 0 || i - 1 >= size)
            return error;
        //删除第i个元素，也就是从第i+1个元素开始，后面的元素前移一位
        for (int j = i - 1; j < size; j++)
            list[j] = list[j + 1];
        //实际长度-1
        size--;
        return ok;
    }
    //获取一个元素，参数是获取的位置
    int list_get(int i) {
        return list[i - 1];
    }
    void list_display() {
        //输出表头，即实际长度
        cout << size << " ";
        //输出顺序表内部内容
        for (int i = 0; i < size; i++)
            cout << list[i] << " ";
        cout << endl;
    }
};
//DS顺序表--类实现
void Q1016() {
    SeqList ex;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        ex.list_insert(i + 1, num);
    }
    ex.list_display();
    int index, data;
    //插入部分
    cin >> index >> data;
    if (ex.list_insert(index, data) == 0)
        ex.list_display();
    else
        cout << "error" << endl;
    cin >> index >> data;
    if (ex.list_insert(index, data) == 0)
        ex.list_display();
    else
        cout << "error" << endl;
    //删除
    cin >> index;
    if (ex.list_del(index) == 0)
        ex.list_display();
    else
        cout << "error" << endl;
    cin >> index;
    if (ex.list_del(index) == 0)
        ex.list_display();
    else
        cout << "error" << endl;
    //查找
    cin >> index;
    if (index - 1 < 0 || index - 1 > ex.list_size())
        cout << "error" << endl;
    else
        cout << ex.list_get(index) << endl;
    cin >> index;
    if (index - 1 < 0 || index - 1 > ex.list_size())
        cout << "error" << endl;
    else
        cout << ex.list_get(index) << endl;
}
int main() {
    Q1016();
    return 0;
}


2. 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 <bits/stdc++.h>
#define ok 0
#define error -1
using namespace std;
class SeqList {
private:
    int *list;  //元素数组
    int maxsize;    //顺序表最大长度
    int size;   //顺序表实际长度
public:
    //构造函数
    SeqList() {
        maxsize = 1000;
        size = 0;
        list = new int[maxsize];
    }
    //析构函数
    ~SeqList() {
        delete[]list;
    }
    //获取顺序表实际长度
    int list_size() {
        return size;
    }
    //插入一个元素，参数是插入的数值和位置
    int list_insert(int i, int item) {
        //插入位置为i，在list中数组下标为i-1
        //对应数组下标不能小于0，也不能大于当前数组长度
        if (i - 1 < 0 || i - 1 > size)
            return error;
        //从第i-1个元素开始，将后面所有的元素后移一位
        for (int j = size - 1; j >= i - 1; j--)
            list[j + 1] = list[j];
        //在i位置插入item元素
        list[i - 1] = item;
        //实际长度+1
        size++;
        return ok;
    }
    //删除一个元素，参数是删除的位置
    int list_del(int i) {
        //插入位置为i，在list中数组下标为i-1
        //对应数组下标不能小于0，也不能大于等于当前数组长度
        if (i - 1 < 0 || i - 1 >= size)
            return error;
        //删除第i个元素，也就是从第i+1个元素开始，后面的元素前移一位
        for (int j = i - 1; j < size; j++)
            list[j] = list[j + 1];
        //实际长度-1
        size--;
        return ok;
    }
    //获取一个元素，参数是获取的位置
    int list_get(int i) {
        return list[i - 1];
    }
    void list_display() {
        //输出表头，即实际长度
        cout << size << " ";
        //输出顺序表内部内容
        for (int i = 0; i < size; i++)
            cout << list[i] << " ";
        cout << endl;
    }
    void list_display_Q1019() {
        //输出顺序表内部内容
        for (int i = 0; i < size; i++)
            cout << list[i] << " ";
        cout << endl;
    }
    //现在第i个位置，连续插入来自数组item的n个数据，即从位置i开始插入多个数据。
    int multiinsert(int i, int n, int item[]) {
        //插入位置为i，在list中数组下标为i-1
        //对应数组下标不能小于0，也不能大于当前数组长度
        if (i - 1 < 0 || i - 1 > size)
            return error;
        for (int m = 0; m < n; m++) {
            //从第i-1个元素开始，将后面所有的元素后移一位
            for (int j = size - 1; j >= i - 1 + m; j--)
                list[j + 1] = list[j];
            size++;
        }
        for (int m = 0; m < n; m++) {
            list[i + m - 1] = item[m];
        }
        return ok;
    }
    //现从第i个位置开始，连续删除n个数据，即从位置i开始删除多个数据
    int multidel(int i, int n) {
        //插入位置为i，在list中数组下标为i-1
        //cout << i - 1 << " " << size << n << endl;
        //对应数组下标不能小于0，也不能大于等于当前数组长度
        if (i - 1 < 0 || i - 1 > size - n)
            return error;
        for (int m = 0; m < n; m++) {
            for (int j = i - 1; j < size - 1; j++)
                list[j] = list[j + 1];
            size--;
        }
        return ok;
    }
    //把两个序列的数据合并到顺序表中，并使得顺序表的数据递增有序
    void merge_list(SeqList &ex1, SeqList &ex2) {
        int i = 1;
        int j = 1;
        while (i <= ex1.list_size() && j <= ex2.list_size()) {
            if (ex1.list_get(i) < ex2.list_get(j))
                list[size++] = ex1.list_get(i++);
            else
                list[size++] = ex2.list_get(j++);
        }
        //cout<<"111"<<endl;
        if (i <= ex1.list_size()) {
            while (i <= ex1.list_size())
                list[size++] = ex1.list_get(i++);
        }
        //cout<<"222"<<endl;
        if (j <= ex2.list_size()) {
            while (j <= ex2.list_size())
                list[size++] = ex2.list_get(j++);
        }
        //cout<<"333"<<endl;
    }
    //循环移位
    void cicle_move(int type, int steps) {
        //左移
        if (type == 0) {
            for (int j = 0; j < steps; j++) {
                //保存边缘数据
                int temp_data = list[0];
                for (int i = 0; i < size - 1; i++)
                    list[i] = list[i + 1];
                list[size - 1] = temp_data;
            }
        }
            //右移
        else {
            for (int j = 0; j < steps; j++) {
                //保存边缘数据
                int temp_data = list[size - 1];
                for (int i = size - 1; i > 0; i--)
                    list[i] = list[i - 1];
                list[0] = temp_data;
            }
        }
    }
};
//1017: DS顺序表--连续操作
void Q1017() {
    SeqList ex;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        ex.list_insert(i + 1, num);
    }
    ex.list_display();
    //数据插入
    int index, number;
    cin >> index >> number;
    int data[200];
    for (int i = 0; i < number; i++)
        cin >> data[i];
    if (ex.multiinsert(index, number, data) == ok)
        ex.list_display();
    else
        cout << "error" << endl;
    //数据删除
    cin >> index >> number;
    if (ex.multidel(index, number) == ok)
        ex.list_display();
    else
        cout << "error" << endl;
}
int main() {
    Q1017();
    return 0;
}

3. DS顺序表–合并操作


题目描述


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


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


输入


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


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


输出


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


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


输入样例


3 11 33 55

5 22 44 66 88 99


输出样例


8 11 22 33 44 55 66 88 99


参考代码

#include <iostream>
#define ok 0
#define error -1
using namespace std;
class SeqList {
private:
    int *list;  //元素数组
    int maxsize;    //顺序表最大长度
    int size;   //顺序表实际长度
public:
    //构造函数
    SeqList() {
        maxsize = 1000;
        size = 0;
        list = new int[maxsize];
    }
    //析构函数
    ~SeqList() {
        delete[]list;
    }
    //获取顺序表实际长度
    int list_size() {
        return size;
    }
    //插入一个元素，参数是插入的数值和位置
    int list_insert(int i, int item) {
        //插入位置为i，在list中数组下标为i-1
        //对应数组下标不能小于0，也不能大于当前数组长度
        if (i - 1 < 0 || i - 1 > size)
            return error;
        //从第i-1个元素开始，将后面所有的元素后移一位
        for (int j = size - 1; j >= i - 1; j--)
            list[j + 1] = list[j];
        //在i位置插入item元素
        list[i - 1] = item;
        //实际长度+1
        size++;
        return ok;
    }
    //获取一个元素，参数是获取的位置
    int list_get(int i) {
        return list[i - 1];
    }
    void list_display() {
        //输出表头，即实际长度
        cout << size << " ";
        //输出顺序表内部内容
        for (int i = 0; i < size; i++)
            cout << list[i] << " ";
        cout << endl;
    }
    //把两个序列的数据合并到顺序表中，并使得顺序表的数据递增有序
    void merge_list(SeqList &ex1, SeqList &ex2) {
        int i = 1;
        int j = 1;
        while (i <= ex1.list_size() && j <= ex2.list_size()) {
            if (ex1.list_get(i) < ex2.list_get(j))
                list[size++] = ex1.list_get(i++);
            else
                list[size++] = ex2.list_get(j++);
        }
        //cout<<"111"<<endl;
        if (i <= ex1.list_size()) {
            while (i <= ex1.list_size())
                list[size++] = ex1.list_get(i++);
        }
        //cout<<"222"<<endl;
        if (j <= ex2.list_size()) {
            while (j <= ex2.list_size())
                list[size++] = ex2.list_get(j++);
        }
        //cout<<"333"<<endl;
    }
};
//DS顺序表--合并操作
void Q1018() {
    SeqList ex1;
    SeqList ex2;
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int data;
        cin >> data;
        ex1.list_insert(i, data);
    }
    // ex1.list_display();
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int data;
        cin >> data;
        ex2.list_insert(i, data);
    }
    SeqList ans;
    ans.merge_list(ex1, ex2);
    ans.list_display();
}
int main() {
    Q1018();
    return 0;
}


文章标签：
C++
关键词：
数据结构顺序表
wstqfqdpnmll4
目录
相关文章
禁默
|
2月前
|
存储 编译器 C语言
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
禁默
56 2
肾透侧视攻城狮
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找等具体详解步骤以及举例说明
肾透侧视攻城狮
29 3
ephemerals__
|
1月前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
65 3
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找习题精讲等具体详解步骤以及举例说明
肾透侧视攻城狮
23 1
小强在此
|
2月前
|
存储 Java
数据结构第二篇【关于java线性表（顺序表）的基本操作】
数据结构第二篇【关于java线性表（顺序表）的基本操作】
小强在此
35 6
GuGuStudy
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
26 3
GuGuStudy
|
2月前
|
存储 C语言
探索C语言数据结构：利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录，包括初始化、添加、删除、查找和保存联系人信息的操作，以及自定义结构体用于存储联系人详细信息。
GuGuStudy
32 2
努力学习的小廉
|
2月前
|
存储 算法 索引
【数据结构】——顺序表
【数据结构】——顺序表
努力学习的小廉
66 1
椰椰椰耶
|
2月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
椰椰椰耶
22 1
徐霞客320
|
2月前
|
存储
数据结构1——顺序表
数据结构1——顺序表
徐霞客320
19 1