C++实现顺序表

• 顺序表
• • 实现

概念啥的去看B站王卓数据结构预算法

1.普通实现

#define MAXSIZE 100
typedef int  ElemType;


typedef struct {
	ElemType* elem;
	int length;
}SqList;


//初始化
bool InitList(SqList& L) {//构造空的顺序表L
	L.elem = new ElemType[MAXSIZE];
	if (!L.elem)//异常处理，分配失败是L.elem是空值NULL
	{
		return false;
	}
	L.length = 0;
	return true;
}

//销毁线性表
void DestroyList(SqList& L) {
	if (L.elem) {
		delete L.elem;//释放内存空间
	}
}
//清空线性表
void ClearList(SqList& L) {
	L.length = 0;//长度设置为0
}
//返回线性表的长度
int GetLength(SqList L) {
	return L.length;
}
//判断是否为空
bool IsEmpty(SqList L) {
	if (L.length == 0) {
		return true;
	}
	else {
		return false;
	}
}
//取值
bool GetElem(SqList L, int i, ElemType& e) {
	if (i<1 || i>L.length) {
		return false;//序号不合法
	}
	e = L.elem[i - 1];
	return true;
}
//查找
int LocateElem(SqList L, ElemType e) {
	for (int i = 0; i < L.length; i++) {
		if (L.elem[i] == e) {
			return i + 1;//查到返回序号
		}
		return -1;//未找到返回-1
	}
}
//插入
bool ListInsert(SqList& L, int i, ElemType e) {
	if (i<1 || i>L.length + 1)return false;//序号不合法
	if (L.length == MAXSIZE)return false;//空间已满
	for (int j = L.length - 1; j >= i - 1; j--) {//把第i（序号为i-1）个开始的元素都往后移
		L.elem[j + 1] = L.elem[j];
	}
	L.elem[i-1] = e;
	L.length++;
	return true;
}
//删除元素
bool ListDelete(SqList& L, int i, ElemType& e) {
	if (i<1 || i>L.length)return false;//序号不合法
	e = L.elem[i - 1];//导出删除的元素
	for (int j = i - 1; j < L.length-1; j++) {//把第i(序号i-1)个之后的元素前移
		L.elem[j] = L.elem[j + 1];
	}
	L.length--;
	return false;
}

2. 用类实现

• SqList.h

#pragma once
#include
typedef int ElemType;
using namespace std;

class SqList
{
private:
    int myLength;//保存表长
    int mySize;//最大容量
    ElemType *myElem;
public:
    SqList(int size);
    SqList( SqList  &L);
    ~SqList();
    void PrintSqList();//打印输出
    void CreateSqList();//创建线性表
    ElemType GetElem(int i) ;//取值，取位序为i的元素，下标为i-1
    int FindElem(ElemType elem);//查找值为elem的位序i
    void InsertElem(int i, ElemType elem);//在指定位序插入元素
    void DeleteElem(int i);//删除指定位序的元素
    int GetLength () ;//返回表长 
    int GetSize();//返回容量
};

• SqList.cpp

#include"SqList.h"

//构造函数
SqList::SqList(int size){
    this->myLength = 0;
    this->mySize = size;
    this->myElem = new ElemType[this->mySize];
    this->CreateSqList();
}
SqList::SqList(  SqList  &L){
    this->myLength = L.GetLength();
    this->mySize = L.GetSize();
    this->myElem = new ElemType[this->mySize];
    for(int i = 1; i < this->myLength+1; i++){
        this->myElem[i-1] = L.GetElem(i);
    }
}
//析构函数
SqList::~SqList(){
    delete [] this->myElem;
}
//打印输出
void SqList::PrintSqList(){
    for(int i = 0; i < this->myLength; i++){
        cout << this->myElem[i] <<" ";
    }
    cout << endl;
}
//创建线性表
void SqList::CreateSqList(){
    cout << "请构造一个线性表，输入-1时结束输入" << endl;
    ElemType x;
    while(true){
        if(this->myLength==this->mySize){
            cout << "顺序表已满" << endl;
            break;
        }
        cin >> x;
        if(x==-1)break;
        this->myElem[this->myLength++] = x;
    }
}
//取值
ElemType SqList::GetElem(int i){
    if(i >= 1 && i <= this->myLength){
       return this->myElem[i-1];
    }
    else{
        cout << "位序不合法" << endl;
        return -1;//不合法，返回数组中不可能存在的元素
    }
}
//查找
int SqList::FindElem(ElemType elem){
    for(int i = 0; i < this->myLength; i++){
        if(this->myElem[i]==elem){
            return i+1;
        }
    }
    return -1;//元素存在返回-1
}
//插入
void SqList::InsertElem(int i, ElemType elem){
    if (i < 1 || i > this->myLength + 1){//合法位置是1到表长+1
        cout << "位序不合法" << endl;
        return;
    }
    for (int j = this->myLength - 1; j >= i - 1; j--){
        this->myElem[j + 1] = this->myElem[j];
    }
    this->myElem[i - 1] = elem;
    this->myLength++;
}
//删除
void SqList::DeleteElem(int i){
    if (i < 1 || i > this->myLength){
        cout << "位序不合法" << endl;
        return;
    }
    for (int j = i - 1;j < this->myLength - 1; j++ ){
        this->myElem[j] = this->myElem[j + 1];
    }
    this->myLength--;
}
//表长
int SqList::GetLength(){
    return this->myLength;
}
//容量
int SqList::GetSize(){
    return this->mySize;
}

-main.cpp

int main(){
    SqList L(100);
    L.PrintSqList();
    //取值
    cout << " 取值" <
        cout << "元素不存在" << endl;
    }
    else{
        cout << elem << "的序号为" << endl;
    }
    cout << "表长为：" << L.GetLength() <