C++实现数据结构的顺序表详解

介绍

在进行程序开发时，常常需要对数据进行存储和操作。其中一种数据结构是顺序表，它提供了一种在内存中线性存储数据的方法，能够方便地对数据进行插入、删除、查找等操作。本文将详细介绍如何使用C++实现数据结构的顺序表，帮助读者掌握顺序表的创建、插入、删除、查找等操作。

创建顺序表

顺序表可以使用数组来实现。下面的代码展示了如何创建一个长度为10的顺序表，其中元素类型为整型:

#define MAX_SIZE 10

class SeqList {
public:
    SeqList() {
        m_size = 0;
    }

    void insert(int pos, int value) {
        //确保插入位置合法
        if (pos < 0 || pos > m_size) {
            return;
        }

        //如果列表已满，则无法插入新的元素
        if (m_size == MAX_SIZE) {
            return;
        }

        //将插入位置及之后的元素向后移动一位
        for (int i = m_size; i > pos; --i) {
            m_data[i] = m_data[i-1];
        }

        //在插入位置处插入新的元素
        m_data[pos] = value;

        //更新列表长度
        ++m_size;
    }

    void remove(int pos) {
        //确保删除位置合法
        if (pos < 0 || pos >= m_size) {
            return;
        }

        //将删除位置之后的元素向前移动一位
        for (int i = pos + 1; i < m_size; ++i) {
            m_data[i-1] = m_data[i];
        }

        //更新列表长度
        --m_size;
    }

    int find(int value) {
        for (int i = 0; i < m_size; ++i) {
            if (m_data[i] == value) {
                //返回元素在列表中的位置
                return i;
            }
        }

        //如果没有找到该元素，则返回-1
        return -1;
    }

private:
    int m_data[MAX_SIZE];
    int m_size;
};

插入和删除元素

在顺序表中插入和删除元素的操作比较简单。当需要在顺序表的pos位置插入新元素value时，应将pos及之后的元素都向后移动一位，然后在pos处插入新元素。删除元素pos时，应将pos之后的元素都向前移动一位。

例如，如果想在下面这个列表中插入元素3：

1, 2, 4, 5, 6

则应将4, 5, 6向后移动一位，变成：

1, 2, 4, 5, 5, 6

然后在空出的位置2处插入新元素3，得到：

1, 2, 3, 4, 5, 6

如果要删除元素4，则应将5和6向前移动一位，得到：

1, 2, 5, 6

查找元素

查找元素在顺序表中的位置的操作也比较简单，只需要遍历整个列表，逐个比较每个元素是否等于待查找的元素值。

例如，如果要查找下面这个列表中元素5的位置：

1, 2, 3, 4, 5, 6

则需要逐个比较每个元素是否等于5，直到找到对应位置，即4。

示例

下面展示两个完整的示例，演示如何使用C++编写顺序表的相关操作。

示例1：插入和删除元素

下面的代码演示如何创建一个长度为5的顺序表，并在其中插入和删除元素：

#include <iostream>

using namespace std;

#define MAX_SIZE 5

class SeqList {
public:
    SeqList() {
        m_size = 0;
    }

    void insert(int pos, int value) {
        //确保插入位置合法
        if (pos < 0 || pos > m_size) {
            return;
        }

        //如果列表已满，则无法插入新的元素
        if (m_size == MAX_SIZE) {
            return;
        }

        //将插入位置及之后的元素向后移动一位
        for (int i = m_size; i > pos; --i) {
            m_data[i] = m_data[i-1];
        }

        //在插入位置处插入新的元素
        m_data[pos] = value;

        //更新列表长度
        ++m_size;
    }

    void remove(int pos) {
        //确保删除位置合法
        if (pos < 0 || pos >= m_size) {
            return;
        }

        //将删除位置之后的元素向前移动一位
        for (int i = pos + 1; i < m_size; ++i) {
            m_data[i-1] = m_data[i];
        }

        //更新列表长度
        --m_size;
    }

    int find(int value) {
        for (int i = 0; i < m_size; ++i) {
            if (m_data[i] == value) {
                //返回元素在列表中的位置
                return i;
            }
        }

        //如果没有找到该元素，则返回-1
        return -1;
    }

private:
    int m_data[MAX_SIZE];
    int m_size;
};

int main() {
    SeqList list;

    //插入元素1和2
    list.insert(0, 1);
    list.insert(1, 2);

    //打印当前列表
    cout << "当前列表：";
    for (int i = 0; i < list.size(); ++i) {
        cout << list[i] << " ";
    }
    cout << endl;

    //插入元素3
    list.insert(1, 3);

    //打印当前列表
    cout << "当前列表：";
    for (int i = 0; i < list.size(); ++i) {
        cout << list[i] << " ";
    }
    cout << endl;

    //删除元素1
    list.remove(0);

    //打印当前列表
    cout << "当前列表：";
    for (int i = 0; i < list.size(); ++i) {
        cout << list[i] << " ";
    }
    cout << endl;

    return 0;
}

输出结果为：

当前列表：1 2 
当前列表：1 3 2 
当前列表：3 2

示例2：查找元素

下面的代码演示如何创建一个长度为10的顺序表，并在其中查找元素：

#include <iostream>

using namespace std;

#define MAX_SIZE 10

class SeqList {
public:
    SeqList() {
        m_size = 0;
    }

    void insert(int pos, int value) {
        //确保插入位置合法
        if (pos < 0 || pos > m_size) {
            return;
        }

        //如果列表已满，则无法插入新的元素
        if (m_size == MAX_SIZE) {
            return;
        }

        //将插入位置及之后的元素向后移动一位
        for (int i = m_size; i > pos; --i) {
            m_data[i] = m_data[i-1];
        }

        //在插入位置处插入新的元素
        m_data[pos] = value;

        //更新列表长度
        ++m_size;
    }

    void remove(int pos) {
        //确保删除位置合法
        if (pos < 0 || pos >= m_size) {
            return;
        }

        //将删除位置之后的元素向前移动一位
        for (int i = pos + 1; i < m_size; ++i) {
            m_data[i-1] = m_data[i];
        }

        //更新列表长度
        --m_size;
    }

    int find(int value) {
        for (int i = 0; i < m_size; ++i) {
            if (m_data[i] == value) {
                //返回元素在列表中的位置
                return i;
            }
        }

        //如果没有找到该元素，则返回-1
        return -1;
    }

private:
    int m_data[MAX_SIZE];
    int m_size;
};

int main() {
    SeqList list;

    //插入元素1到10
    for (int i = 1; i <= 10; ++i) {
        list.insert(i-1, i);
    }

    //查找元素7
    int pos = list.find(7);

    if (pos == -1) {
        cout << "没有找到元素7" << endl;
    } else {
        cout << "元素7的位置为：" << pos << endl;
    }

    return 0;
}

输出结果为：

元素7的位置为：6

总结

本文介绍了如何使用C++实现数据结构的顺序表。创建顺序表可以使用数组来实现，然后可以实现插入、删除、查找等操作。代码示例演示了如何实现插入、删除、查找操作，并且提供了两个完整的示例，帮助读者理解顺序表的操作。顺序表是一种比较简单但实用的数据结构，掌握其原理和使用方法有助于提升编程技能。