数据结构-线性表的顺序表基本操作代码实现（超级详细清晰 C++实现）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构-线性表的顺序表基本操作代码实现（超级详细清晰 C++实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表：可动态增长的数组，要求数据是连续存储的

特点：随机访问

二、创建顺序表

顺序既可以静态分配，也可以动态分配。在静态分配时，由于数组的大小和空间已经事先固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的空间，用来替换原来的空间，从而达到扩充存储数组空间的目的，而不是一次性的划分。

typedef struct{
    int *data;   //指示动态分配的指针
    int length, size;  //分别表示总空间大小以及长度
}sqlist;

三、顺序表的一些基本操作

（一）初始化操作

bool InitList(sqlist &L){
    L.data = new int[Maxsize];
    if (!L.data)
        return false;   //如果顺序表不为空，则返回false
    L.length = 0;
    L.size = Maxsize;
    return true;
}

（二）返回链表长度

int Length(sqlist L){
    return L.length;
}

（三）添加元素

在顺序表的末尾添加元素：

bool AppendElem(sqlist &L, int e){
    if (L.length >= Maxsize)
        return false;
    L.data[L.length] = e;
    L.length++;
    return true;
}

（四）查找元素

如果该元素存在与顺序表中，返回该元素的位置i,不存在则返回0

int LocatedElem(sqlist L, int e){
    int i;
    for (int i = 0; i < L.length; i++){
        if (L.data[i] == e)
            return i + 1;
    }
    return 0;   //如果没有找到，返回0
}

（五）查找指定位置的元素

需要先判断该下标i是否合法，不合法返回-1；否则返回该位置元素的值；

int GetElem(sqlist L, int i){
    if (i<1 || i>L.length)
        return -1;   //如果输入的下标不合理，返回-1
    return L.data[i - 1];
}

（六）插入元素

删除和插入元素图片解释：

数据结构顺序表代码,数据结构,线性表,顺序表,数据结构,链表,c++,Powered by 金山文档

在表L的第i个位置插入指定元素e

bool InsertElem(sqlist &L, int i, int e){
    if (i<1 || i>L.length + 1)
        return false;    //检查插入的位置是否合理，不合理返回false
    if (L.length >= Maxsize)
        return false;
    for (int j = L.length; j >= i; j--){
        L.data[j ] = L.data[j-1];
    }
    L.data[i - 1] = e;
    L.length++;
}

（七）删除元素

删除表L第i个位置的元素，并用e返回删除位置元素的值

bool DeleteElem(sqlist &L, int i, int &e){
    if (i<1 || i>L.length)
        return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++){
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

（八）打印表中所有元素

void PrintList(sqlist L){
    cout << "顺序表的总空间大小为：" << L.size << "，已占用空间为：" << L.length << endl;
    for (int i = 0; i < L.length; i++){
        cout << L.data[i] << " ";
    }
    cout << endl;
}

（十）判断表是否为空

bool Empty(sqlist L){
    if (L.data)
        return true;
    else
        return false;
}

四、销毁表

void Destroy(sqlist &L){
    if (L.data)
        delete[] L.data;
    L.length = 0;
    L.size = 0;
}

五、完整代码示例

#include<iostream>
using namespace std;
#define Maxsize 100

typedef struct{
    int *data;
    int length, size;  //分别表示总空间大小以及长度
}sqlist;

bool InitList(sqlist &L){
    L.data = new int[Maxsize];
    if (!L.data)
        return false;   //如果顺序表不为空，则返回false
    L.length = 0;
    L.size = Maxsize;
    return true;
}

int Length(sqlist L){
    return L.length;
}

bool AppendElem(sqlist &L, int e){
    if (L.length >= Maxsize)
        return false;
    L.data[L.length] = e;
    L.length++;
    return true;
}

int LocatedElem(sqlist L, int e){
    int i;
    for (int i = 0; i < L.length; i++){
        if (L.data[i] == e)
            return i + 1;
    }
    return 0;   //如果没有找到，返回0
}

int GetElem(sqlist L, int i){
    if (i<1 || i>L.length)
        return -1;   //如果输入的下标不合理，返回-1
    return L.data[i - 1];
}

bool InsertElem(sqlist &L, int i, int e){
    if (i<1 || i>L.length + 1)
        return false;    //检查插入的位置是否合理，不合理返回false
    if (L.length >= Maxsize)
        return false;
    for (int j = L.length; j >= i; j--){
        L.data[j ] = L.data[j-1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}
bool DeleteElem(sqlist &L, int i, int &e){
    if (i<1 || i>L.length)
        return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++){
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

void PrintList(sqlist L){
    cout << "顺序表的总空间大小为：" << L.size << "，已占用空间为：" << L.length << endl;
    for (int i = 0; i < L.length; i++){
        cout << L.data[i] << " ";
    }
    cout << endl;
}

bool Empty(sqlist L){
    if (L.data)
        return true;
    else
        return false;
}

void Destroy(sqlist &L){
    if (L.data)
        delete[] L.data;
    L.length = 0;
    L.size = 0;
}

int main(){
    sqlist list;
    int e, index;

    cout << "顺序表初始化..." << endl;

    //1.初始化
    if (InitList(list)) {
        cout << "顺序表初始化成功！" << endl;
    }
    else cout << "顺序表初始化失败！" << endl;

    PrintList(list);

    //2.添加元素
    int count;
    cout << "请输入要添加元素的个数：" ;
    cin >> count;
    for (int i = 0; i < count; i++){
        cout << "请输入要添加元素e的值：";
        cin >> e;
        if (AppendElem(list, e))
            cout << "添加成功！" << endl;
        else
            cout << "添加失败！" << endl;
    }
    PrintList(list);

    //3.查找元素，存在则返回该元素的位置
    cout << "请输入要查找的元素e的值：";
    cin >> e;
    index = LocatedElem(list, e);
    if (index)
        cout << "该元素" << e << "在表中的第" << index << "个位置" << endl;
    else
        cout << "表中不存在该元素" << endl;
    PrintList(list);

    //4.返回第i个元素的值
    cout << "请输入要查找元素的位置：";
    cin >> index;
    if (GetElem(list, index) != -1)
        cout << "第" << index << "个位置的值为：" << GetElem(list, index) << endl;
    else
        cout << "输入的下标不合理！" << endl;
    PrintList(list);


    //5.插入元素
    cout << "请输入要插入的元素位置";
    cin >> index;
    cout << "请输入要插入的元素的值";

    cin >> e;

    if (InsertElem(list, index, e)) {
        cout << "插入成功！" << endl;
    }
    else {
        cout << "插入失败!" << endl;
    }

    PrintList(list);

    //6.删除元素
    cout << "请输入要删除的元素的位置" << endl;
    cin >> index;

    if (DeleteElem(list, index,e)) {
        cout << "删除成功！" << endl;
    }
    else {
        cout << "删除失败!" << endl;
    }
    cout << "删除的元素的值为：" << e << endl;
    PrintList(list);

    //7.销毁
    Destroy(list);

    system("pause");
    return 0;

}