C++实现顺序表

顺序表,一种线性表,因此顺序表是线性的.
因为顺序表在物理结构与逻辑结构都是连续的.意味着在内存中是连续存储的,形如数组的内存存储方式,我将用数组实现顺序表.
实现顺序表的主要功能为:增删查改.
顺序表是一种简单的数据结构,原理与实现并不难
主要维护下标size,内存空间capacity的大小即可

Seqlist.h头文件声明

#pragma once
#include<iostream>
#include<cstdlib>
#include<cassert>
using namespace std;
// 顺序表结构定义
typedef int SLDataType;
class SeqList {
public:
    SLDataType* arr;
    int size;
    int capacity;
};
typedef SeqList SL;
//检查顺序表容量是否合理
void checkSLCaoacity(SL* ps);
//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);

//顺序表的插入操作
//头插尾插
void SLPushFront(SL* ps,SLDataType x);
void SLPushBack(SL* ps, SLDataType x);
//头删尾删
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);
//选择插入
void SLInsert(SL* ps,int i, SLDataType x);
//选择删除
void SLDelete(SL* ps, SLDataType x);

//顺序表的查找操作
void SLFind(SL* ps, SLDataType x);
//顺序表的修改操作
void SLUpdate(SL* ps, int i, SLDataType x);

//输出所以元素
void SLPrint(SL* ps);

Seqlist.cpp原文件中存方法

#include"SeqList.h"

void SLInit(SL* ps) {
    ps->arr = NULL;
    ps->size=ps->capacity=0;
}

void SLDestroy(SL* ps) {
    if (ps->arr) {
        delete[] ps->arr;
    }
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

void checkSLCaoacity(SL* ps) {
    //先判断空间够不够
    if (ps->size == ps->capacity) {
        int newCapacity = (ps->capacity == 0) ? sizeof(SLDataType) : 2 * ps->capacity;
        SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        if (!temp) {
            perror("realloc failed");
            exit(1);
        }
        ps->arr = temp;
        //delete(temp);
        ps->capacity = newCapacity;
    }
}
    
//头插尾插
void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);//传其他类型指针会导致崩溃，给爷爬
    checkSLCaoacity(ps);
    //插入
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}
void SLPushBack(SL* ps, SLDataType x) {
    assert(ps);
    checkSLCaoacity(ps);
    ps->arr[ps->size++] = x;
}
//头删尾删
void SLPopFront(SL* ps) {
    assert(ps);
    if (ps->size == 0) {
        return;
    }
    for (int i = 0; i < (ps->size--) - 1; i++) {
        ps->arr[i + 1] = ps->arr[i];
    }
}
void SLPopBack(SL* ps) {
    assert(ps);
    if (ps->size == 0) {
        return;
    }
    ps->size--;
}
//选择插入
void SLInsert(SL* ps, int i, SLDataType x) {
    assert(ps);
    checkSLCaoacity(ps);
    //1 2 3 4 5 size
    //0 1 2 3 4 
    for (int j = ps->size; j >i; j--) {
        ps->arr[j] = ps->arr[j - 1];
    }
    ps->arr[i] = x;
    ps->size++;
}
//选择删除
void SLDelete(SL* ps, SLDataType x) {
    assert(ps);
    if (ps->size == 0) { return; }
    for (int j = 0; j < ps->size; j++) {
        if (ps->arr[j] == x) {
            for (int k = j; k < ps->size - 1; k++) {
                ps->arr[k] = ps->arr[k + 1];
            }
            ps->size--;
            return;
        }
    }
    cout << "没有找到要删除的元素" << '\n';
}

//顺序表的查找操作
void SLFind(SL* ps, SLDataType x) {
    assert(ps);
    for (int i = 0; i <= ps->size - 1; i++) {
        if (ps->arr[i] == x) {
            cout << "找到了第" << i + 1 << "个元素\n";
            cout << "值为:" << ps->arr[i] << '\n';
            return;
        }
    }
    cout << "没有找到要查找的元素" << '\n';
}
//顺序表的修改操作
void SLUpdate(SL* ps, int i, SLDataType x) {
    assert(ps);
    checkSLCaoacity(ps);
    if (i <= 0 || i > ps->size - 1) {
        cout << "索引越界" << '\n';
        return;
    }
    ps->arr[i - 1] = x;
}

//输出所有元素
void SLPrint(SL* ps) {
    assert(ps);
    checkSLCaoacity(ps);
    for (int i = 0; i < ps->size; i++) {
        cout << ps->arr[i] << " ";
    }
    cout << '\n';
}

test.cpp源文件中用于测试实现的功能

#include"SeqList.h"

void test01() {
    SL s;
    SLInit(&s);//初始化
    //增删查改
    //使用for循环插入100个元素
    for (int i = 1; i <= 100; i++)
    {
        if(i&1)
            SLPushFront(&s, i);
        else
            SLPushBack(&s, i);
    }
    //输出所有元素
    SLPrint(&s);
    //查找元素
    SLFind(&s, 55);
    SLFind(&s, 999);
    //删除元素
    SLDelete(&s, 100);
    SLDelete(&s, 404);
    SLPrint(&s);
    //修改元素
    SLUpdate(&s, 55, 969696);
    SLPrint(&s);
    SLDestroy(&s);//销毁
}

int main()
{
    test01();
    return 0;
}