数据结构与算法—一维数组、二维数组、矩阵、顺序串、链接串的C++代码实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法—一维数组、二维数组、矩阵、顺序串、链接串的C++代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、一维数组：ArrayOneD.h

数组这种数据结构可以看作线性表的推广。数组一般采用顺序存储的方法表示。

#ifndef DATA_STRUCTURE_ARRAYIONED_H
#define DATA_STRUCTURE_ARRAYIONED_H
#include<iostream>
#include<cassert>

using namespace std;

template<class T>
class ArrayOneD{
public:
    ArrayOneD(int sz=0);   //构造函数，创建一维数组
    ArrayOneD(const ArrayOneD<T>& x);  //拷贝构造函数
    ~ArrayOneD();  //析构函数，删除数组
    T& operator[](int index) const;   //重载下标运算符
    ArrayOneD<T>& operator=(const ArrayOneD<T>& x);   //重载赋值运算符
    int Length();    //求数组长度
    void Resize(int sz);    //重新设置数组长度

    void OutPut(ostream& out) const;  //将数组放到输出流out中输出
private:
    int size;   //数组元素个数
    T* element;        //数组存放空间
};

//实现构造函数
template<class T>
ArrayOneD<T>::ArrayOneD(int sz){
    assert((sz>=0));  //下标检查
    size =sz;
    element = new T[sz];
}

/*
 * 拷贝构造函数是一种特殊的构造函数，它在创建对象时，是使用同一类中之前创建的对象来初始化新创建的对象。拷贝构造函数通常用于：
 * 1、通过使用另一个同类型的对象来初始化新创建的对象。
 * 2、复制对象把它作为参数传递给函数。
 * 3、复制对象，并从函数返回这个对象。
 */
//实现拷贝构造函数
template<class T>
ArrayOneD<T>::ArrayOneD(const ArrayOneD<T>& x){
    size = x.size;
    element = new T[size];
    for(int i=0;i<size;i++){
        element[i] = x.element[i];
    }

}

//实现析构函数
template<class T>
ArrayOneD<T>::~ArrayOneD(){
    delete []element;
}

//取索引是index的元素，实现赋值和取值
template<class T>
T& ArrayOneD<T>::operator[](int index) const{
    assert(index>=0 && index<size);   //检查下标
    return element[index];
}

//实现重载赋值运算符
template<class T>
ArrayOneD<T>& ArrayOneD<T>::operator=(const ArrayOneD<T>& x){
    if(this != &x){     //如果不是给自己赋值
        delete []element;    //释放原有的内存空间
        size = x.size;
        element = new T[size];   //重新申请内存空间
        for(int i=0;i<size;i++){
            element[i] = x.element[i];
        }
    }
    return *this;
}

//实现取数组长度
template<class T>
int ArrayOneD<T>::Length(){
    return size;
}

//实现重新设置数组长度
template<class T>
void ArrayOneD<T>::Resize(int sz){
    delete []element;
    assert(sz>=0);
    size = sz;
    element = new T[size];
}

//实现一维数组的输出
template<class T>
void ArrayOneD<T>::OutPut(ostream& out) const{
    for(int i=0;i<size;i++){
        out<< element[i]<<' ';
    }
    out<<endl;
}

template<class T>
ostream& operator<<(ostream& out,const ArrayOneD<T>& x){
    x.OutPut(out);
    return out;
}
#endif //DATA_STRUCTURE_ARRAYIONED_H

这是一个模板类 ArrayOneD 的实现，用于表示一维数组。它包括了构造函数、拷贝构造函数、析构函数、重载下标运算符、重载赋值运算符、求数组长度、重新设置数组长度、输出数组等操作。

其中，构造函数创建一个指定大小的数组，拷贝构造函数用于复制同类型的对象来初始化新创建的对象，析构函数用于释放数组占用的内存，重载下标运算符用于取得指定索引位置的元素，重载赋值运算符用于将一个对象赋值给另一个对象，求数组长度用于返回数组元素个数，重新设置数组长度用于调整数组大小，输出数组用于将数组内容输出到指定的输出流。

此外，代码中还重载了输出运算符，用于将 ArrayOneD 类型的对象输出到指定的输出流中。

2、二维数组：ArrayTwoD.h

二维数组可以看作一维数组的集合

#ifndef DATA_STRUCTURE_ARRAYTWOD_H
#define DATA_STRUCTURE_ARRAYTWOD_H

#include<iostream>
#include<cassert>
#include "ArrayIOneD.h"  //二维数组可以看成一维数组的集合

using namespace std;

template<class T>
class ArrayTwoD{
public:
    ArrayTwoD(int rsz,int csz);   //构造函数，创建二维数组
    ArrayTwoD(const ArrayTwoD<T>& M);   //拷贝构造函数
    ~ArrayTwoD();    //析构函数，删除数组
    ArrayOneD<T>&  operator[](int index) const;  //重载下标运算符
    ArrayTwoD<T>& operator=(const ArrayTwoD<T>& M);   //重载赋值运算符
    int Rows();    //取数组行数
    int Columns();    //取数组列数
    void OutPut(ostream& out) const;   //将数组放到输出流out中输出

private:
    int rsize,csize;   //数组行数和列数
    ArrayOneD<T>* row;  //数组存放空间
};

//实现构造函数
template<class T>
ArrayTwoD<T>::ArrayTwoD(int rsz,int csz){
    assert(rsz>=0 && csz>=0);  //检查下表
    rsize = rsz;
    csize = csz;
    row = new ArrayOneD<T>[rsize];  //创建rsize个一维数组
    for(int i=0;i<rsize;i++){
        row[i].Resize(csize);
    }
}

//实现拷贝构造函数
template<class T>
ArrayTwoD<T>::ArrayTwoD(const ArrayTwoD<T>& M){
    rsize = M.rsize;
    csize = M.csize;
    row = new ArrayOneD<T>[rsize];
    for(int i=0;i<rsize;i++){
        row[i] = M.row[i];
    }
}

//实现析构函数
template<class T>
ArrayTwoD<T>::~ArrayTwoD(){
    delete []row;
}

//实现重载下标运算符
template<class T>
ArrayOneD<T>& ArrayTwoD<T>::operator[](int index) const{
    assert(index>=0 && index<rsize);
    return row[index];
}

//实现重载赋值运算符
template<class T>
ArrayTwoD<T>& ArrayTwoD<T>::operator=(const ArrayTwoD<T>& M){
    if(this != &M){   //如果不是给自己赋值
        delete []row;
        rsize = M.rsize;
        csize = M.csize;
        row = new ArrayOneD<T>[rsize];
        for(int i=0;i<rsize;i++){
            row[i] = M.row[i];
        }
    }
    return *this;
}

//实现取数组的行数
template<class T>
int ArrayTwoD<T>::Rows(){
    return rsize;
}

//实现数组的列数
template<class T>
int ArrayTwoD<T>::Columns(){
    return csize;
}

//实现二维数组的输出
template<class T>
void ArrayTwoD<T>::OutPut(ostream& out) const{
    for(int i=0;i<rsize;i++){
        out<<row[i];
    }
    out<<endl;
}

//实现重载插入运算符
template<class T>
ostream& operator<<(ostream& out,const ArrayTwoD<T>& x){
    x.OutPut(out);
    return out;
}
#endif //DATA_STRUCTURE_ARRAYTWOD_H

这段代码实现了一个二维数组类ArrayTwoD，可以通过该类创建并操作二维数组。主要包括以下功能：

构造函数：通过指定二维数组的行数和列数创建一个二维数组。

拷贝构造函数：创建一个新的二维数组，与已有的二维数组具有相同的行数和列数，并将已有二维数组中的元素复制到新的数组中。

析构函数：释放数组所占用的内存空间。重载下标运算符：通过该运算符可以像操作二维数组一样使用下标访问二维数组中的元素。

重载赋值运算符：将一个二维数组的值赋给另一个二维数组。

取数组的行数：获取二维数组的行数。

取数组的列数：获取二维数组的列数。

输出运算符重载：可以通过该运算符将二维数组的内容输出到输出流中。

该二维数组类是通过使用一个一维数组的集合来模拟一个二维数组的，因此还包括一个一维数组类ArrayOneD的头文件

ArrayIOneD.h。

3、矩阵：Matrix.h

#ifndef DATA_STRUCTURE_MATRIX_H
#define DATA_STRUCTURE_MATRIX_H
#include<iostream>

using namespace std;

template<class T>
class Matrix{
public:
    Matrix(int rsz=1,int csz=1);   //构造函数，创建矩阵
    Matrix(const Matrix<T>& M);  //拷贝构造函数
    ~Matrix();        //析构函数，删除矩阵
    T& operator()(int i,int j)const;  //重载下标运算符
    Matrix<T>& operator=(const Matrix<T>& M);   //重载赋值运算符
    int Rows();    //取矩阵的行数
    int Columns();  //取矩阵的列数
    template<class U>
            friend Matrix<T> operator+(const Matrix<T>& A,const Matrix<T>& B);  //矩阵相加，友元函数

    template<class U>
            friend Matrix<T> operator-(const Matrix<T>& A,const Matrix<T>& B);  //矩阵相减，友元函数

    template<class U>
            friend Matrix<T> operator*(const Matrix<T>& A,const Matrix<T>& B); //矩阵相乘，友元函数

    template<class U>
            friend Matrix<T> Transpose(const Matrix<T>& A);   //矩阵装置，友元函数

    void OutPut(ostream& out) const;   //将矩阵放到输出流out中输出

private:
    int rsize,csize;   //矩阵行数和列数
    T* element;     //矩阵存放空间
};

/* 补充的知识点:
 * 类的友元函数是定义在类外部，但有权访问类的所有私有（private）成员和保护（protected）成员。尽管友元函数的原型有在类的定义中出现过，但是友元函数并不是成员函数。
 * 友元可以是一个函数，该函数被称为友元函数；友元也可以是一个类，该类被称为友元类，在这种情况下，整个类及其所有成员都是友元。如果要声明函数为一个类的友元，需要在类定义中该函数原型前使用关键字 friend
 */

template<class T>
Matrix<T>::Matrix(int rsz,int csz){
    rsize = rsz;
    csize = csz;
    element = new T[rsize * csize];
}

// 实现拷贝构造函数
template<class T>
Matrix<T>::Matrix(const Matrix<T>& M){
    rsize = M.rsize;
    csize = M.csize;
    element = new T[rsize*csize];
    for(int i=0;i<rsize*csize;i++){
        element[i] = M.element[i];
    }
}

//实现析构函数
template<class T>
Matrix<T>::~Matrix(){
    delete []element;
}

//实现下标运算符，方便矩阵元素的赋值和取值
template<class T>
T& Matrix<T>::operator()(int i,int j)const{
    return element[(i-1)*csize + j -1];
}

//重载赋值运算符
template<class T>
Matrix<T>& Matrix<T>::operator=(const Matrix<T>& M){
    if(this!=&M){  //如果不是自己给自己赋值
        delete [] element;   //先释放原来的内存空间
        rsize = M.rsize;
        csize = M.csize;
        element = new T[rsize*csize];   //重新申请内存空间
        for(int i=1;i<rsize*csize;i++){
            element[i] = M.element[i];
        }
    }
}

//实现取矩阵的行数
template<class T>
int Matrix<T>::Rows(){
    return rsize;
}

//实现取矩阵的列数
template<class T>
int Matrix<T>::Columns(){
    return csize;
}

//实现矩阵相加
template<class T>
Matrix<T> operator+(const Matrix<T>& A,const Matrix<T>& B){
    Matrix<T> C(A.rsize,A.csize);   //存放结果矩阵
    for(int i=0;i<A.rsize;i++){
        for(int j=0;j<A.csize;j++){
            C(i,j) = A(i,j) + B(i,j);
        }
    }
    return C;
}

//实现矩阵相减
template<class T>
Matrix<T> operator-(const Matrix<T>& A,const Matrix<T>& B){
    Matrix<T> C(A.rsize,A.csize);   //存放结果矩阵
    for(int i=0;i<A.rsize;i++){
        for(int j=0;j<A.csize;j++){
            C(i,j) = A(i,j) - B(i,j);
        }
    }
    return C;
}

//实现矩阵相乘
template<class T>
Matrix<T> operator*(const Matrix<T>& A,const Matrix<T>& B){
    Matrix<T> C(A.rsize,B.csize);
    for(int i=0;i<A.rsize;i++){
        for(int j=0;j<B.csize;j++){
            T sum=0;
            for(int k=0;k>A.csize;k++){
                sum = sum + A(i,k)*B(k,j);
            }
            C(i,j) = sum;
        }
    }
}

//实现装置
template<class T>
Matrix<T> Transpose(const Matrix<T>& A){
    Matrix<T> AT(A.csize,A.rsize);
    for(int i=0;i<A.rsize;i++){
        for(int j=0;j<A.csize;j++){
            AT(j,i) = A(i,j);
        }
    }
    return AT;
}

//实现矩阵得输出
template<class T>
void Matrix<T>::OutPut(ostream &out) const {
    for(int i=0;i<rsize;i++){
        for(int j=0;j<csize;j++){
            out<<element[i*csize+j]<<' ';
        }
        cout<<endl;
    }
}

//重载插入运算符
template<class T>
ostream& operator<<(ostream& out,const Matrix<T>& x){
    x.OutPut(out);
    return out;
}
#endif //DATA_STRUCTURE_MATRIX_H

上面的代码实现了一个矩阵类(Matrix)，该类包含了以下功能：

构造函数，用于创建矩阵，并可以指定行数和列数。

拷贝构造函数，用于创建一个与已有矩阵相同的新矩阵。

析构函数，用于删除矩阵对象。

重载下标运算符，可以通过矩阵的行号和列号获取或设置矩阵元素的值。

重载赋值运算符，可以将一个矩阵赋值给另一个矩阵。取矩阵的行数和列数。

矩阵相加，可以将两个矩阵相加，返回相加后的矩阵。

矩阵相减，可以将两个矩阵相减，返回相减后的矩阵。

矩阵相乘，可以将两个矩阵相乘，返回相乘后的矩阵。

矩阵转置，可以将一个矩阵转置，返回转置后的矩阵。

将矩阵输出到输出流中。

这个矩阵类支持模板，因此可以用于存储任何类型的数据。其中，矩阵相加、相减、相乘和转置的实现都采用了友元函数的方式，可以访问类的私有成员。

4、字符串–顺序串：LinearString.h

#ifndef DATA_STRUCTURE_LINEARSTRING_H
#define DATA_STRUCTURE_LINEARSTRING_H

#include<iostream>

using namespace std;


class LinearString{
public:
    LinearString(int LSMaxSize=100);  //构造函数，创建空串
    LinearString(const char* str);   //由字符串常量str创建串的构造函数
    LinearString(const LinearString& str);   //拷贝构造函数
    ~LinearString();    //析构函数

    bool IsEmpty() const;
    int Length() const;
    bool StrCat(const LinearString& str);   //将串连接到穿后形成新串
    bool SubStr(int pos,int len,LinearString& sub);   //将从第pos个字符起长度为len的字串放到sub中
    bool operator==(const LinearString& str);   //判断串是否与str相等

    int index(const LinearString& str);  //如果str是当前的字串，返回它在串中第一次出现的位置，不是字串则返回0
    void OutPut(ostream& out) const;   //输出字符串

private:
    int length;
    int MaxSize;
    char* string;   //一维数组
};

//实现创建空串的构造函数
LinearString::LinearString(int LSMaxSize){
    MaxSize = LSMaxSize;
    string = new char[LSMaxSize];
    length = 0;
}

//实现由字符串常量str创建串的构造函数
LinearString::LinearString(const char* str){
    int len = 0;
    while (str[len]) len++;   //计算字符串常量的长度
    MaxSize = len;
    length = len;
    string = new char[len];
    for(int i=0;i<len;i++){
        string[i] = str[i];
    }
}

//实现拷贝构造函数
LinearString::LinearString(const LinearString& str){
    MaxSize = str.MaxSize;
    length = str.length;
    string = new char[MaxSize];
    for(int i=0;i<length;i++){
        string[i] = str.string[i];
    }
}

//实现析构函数
LinearString::~LinearString(){
    delete []string;
}

//实现判断是否为空串
bool LinearString::IsEmpty() const{
    return length==0;
}

//实现求串的长度
int LinearString::Length() const{
    return length;
}

//实现将串str连接到串后形成新串
bool LinearString::StrCat(const LinearString& str){
    if(MaxSize<length+str.length){
        return false;
    }
    for(int i=0;i<str.length;i++){
        string[length+i] = str.string[i];
    }
    length = length+str.length;
    return true;
}

//实现求第pos个字符起长度为len的字串
bool LinearString::SubStr(int pos,int len,LinearString& sub){
    if(pos<1 || pos>length || len<0 || len>(length-pos+1)){   //参数非法
        return false;
    }
    if(len>sub.MaxSize){
        return false;     //字串长度超出sub串的最大长度
    }
    sub.length = len;   //计算字串的长度
    for(int i=0;i<len;i++){
        sub.string[i] = string[pos-1+i];  //逐个字符复制得到字串
    }
    return true;
}

//实现判断当前串是否和str相等
bool LinearString::operator==(const LinearString& str){
    if(length!=str.length){     //长度不等
        return false;
    }
    for(int i=0;i<length;i++){    //长度相等的情况下，逐个字符检查是否相等
        if(string[i]!=str.string[i]){
            return false;
        }
    }
    return true;
}

//实现如果str是当前串的字串
int LinearString::index(const LinearString& str){
    LinearString sub(MaxSize);    //创建一个临时串
    for(int i=1;i<length-str.length+1;i++){   //扫描可能存在字串的区域
        if(!SubStr(i,str.length,sub)){
            return 0;
        }
        if(sub == str){
            return i;
        }
    }
    return 0;
}

//实现顺序串的输出
void LinearString::OutPut(ostream& out) const{
    for(int i=0;i<length;i++){
        out<<string[i];
    }
    cout<<endl;
}

//重载插入运算符
ostream& operator<<(ostream& out,const LinearString& x){
    x.OutPut(out);
    return out;
}
#endif //DATA_STRUCTURE_LINEARSTRING_H

这段代码实现了一个线性串（LinearString）的类，可以进行以下操作：

构造函数：创建空串或由字符串常量创建串。

拷贝构造函数：根据已有的串创建一个新的串。

析构函数：删除动态分配的内存。

判断是否为空串：判断一个串是否为空。

求串的长度：获取一个串的长度。

将串连接到串后形成新串：将一个串连接到另一个串的末尾形成新串。

求第pos个字符起长度为len的字串：获取一个串中指定位置和长度的字串。

判断当前串是否和str相等：判断一个串是否和另一个串相等。

如果str是当前串的字串：在一个串中查找另一个串，返回它在原串中第一次出现的位置。

输出字符串：输出一个串的内容。

重载插入运算符：将串插入到输出流中。

5、字符串–链接串：LinkString.h

功能同LinearString.h一样，只是实现的方式不一样

#ifndef DATA_STRUCTURE_LINKSTRING_H
#define DATA_STRUCTURE_LINKSTRING_H

#include <iostream>
using namespace std;

//存储结点类
class StrNode{
    friend class LinkString;
public:
    StrNode(){
        next = NULL;
    }
private:
    char data;   //存放字符
    StrNode *next;   //指向下一个字符
};

//链接串类
class LinkString{
public:
    LinkString();  //构造函数，创建空串
    LinkString(const char* str);   //由字符串常量str创建串的构造函数
    LinkString(const LinkString& str);   //拷贝构造函数
    ~LinkString();     //析构函数

    bool IsEmpty() const;
    int Length() const;

    void Delete();   //置空串

    bool StrCat(const LinkString& str);     //将串连接到穿后形成新串
    bool SubStr(int pos,int len,LinkString& sub);    //将从第pos个字符起长度为len的字串放到sub中
    bool operator==(const LinkString& str);    //判断串是否与str相等

    int index(const LinkString& str);     //如果str是当前的字串，返回它在串中第一次出现的位置，不是字串则返回0
    void OutPut(ostream& out) const;   //输出字符串

private:
    StrNode* head;   //指向链接串第一个头节点的指针
    int length;    //串的长度
};

//实现创建空串的构造函数
LinkString::LinkString(){
    head = new StrNode();       //创建头结点
    length =0;
}

//实现由字符串常量str创建串的构造函数
LinkString::LinkString(const char* str){
    StrNode *p,*q;
    int i=0;
    head = new StrNode();    //创建头结点
    p = head;
    while (str[i]){
        q = new StrNode();   //创建新节点  q指向新节点
        q->data = str[i];   //给新结点赋值
        p->next = q;     //将结点插入到串中  新结点入链
        p = q;    //p指向最后一个结点
        i++;
    }
    length = i;   //设置链的长度
}

//实现拷贝构造函数
LinkString::LinkString(const LinkString& str){
    StrNode * p;
    StrNode * q;
    StrNode * w;
    int i;
    head = new StrNode();    //创建头结点
    p = head;
    w = str.head->next;   //指向str字符串的第一个字符
    for(i=0;i<str.length;i++){
        q = new StrNode();    // q指向新结点
        q->data = w->data;   //赋值
        p->next = q;       //新结点入链
        p = q;     //p指向最后一个结点
        w = w->next;
    }
    length = i;
}

//实现析构函数
LinkString::~LinkString(){
    StrNode *p,*q;
    p = head->next;
    for(int i=0;i<length;i++){
        q = p;         //指向待删除结点
        p = p->next;   //指向下一结点
        delete q;  //删除结点
    }
}

// 实现判断为空
bool LinkString::IsEmpty() const{
    return length ==0;
}

//实现求串的长度
int LinkString::Length() const{
    return length;
}

//实现置空串函数
void LinkString::Delete(){
    StrNode *p,*q;
    p = head->next;  //指向str字符串的第一个字符
    head->next = NULL;   //将链断开
    for(int i=0;i<length;i++){
        q=p;   //指向待删除的结点
        p = p->next;  //p指向下一个结点
        delete q;   //删除结点
    }
    length =0;
}

//实现将串str连接到串后形成新串
bool LinkString::StrCat(const LinkString& str){
    StrNode *p,*q,*w;
    p = head;
    for(int i=0;i<length;i++){
        p=p->next;            // p指向最后一个结点
    }
    w=str.head->next;   // 指向str字符串的第一个字符
    for(int i=0;i<str.length;i++){
        q = new StrNode();   //q指向新结点
        q->data = w->data;   //赋值
        p->next = q;     //新结点入链
        p = q;           //p指向最后一个结点
        w = w->next;
    }
    length = length+str.length;
}

//实现求从第pos个字符起长度为len的字串
bool LinkString::SubStr(int pos,int len,LinkString& sub){
    StrNode *p,*q,*w;
    if(pos<1||pos>length||len<0||len>(length-pos+1)){       //参数非法
        return false;
    }
    w = head;
    for(int i=0;i<pos;i++){
        w = w->next;     //w指向pos的结点位置
    }
    p =sub.head;
    if(!sub.IsEmpty()){          //sub不是空串则置为空串
        sub.Delete();
    }
    for(int i=0;i<len;i++){
        q = new StrNode();     //q指向新结点
        q->data = w->data;   //赋值
        p->next = q;   //新结点入链
        p= q;   //p指向最后一个结点
        w =w->next;
    }
    sub.length = len;
    return true;
}

//实现判断串是否与str相等
bool LinkString::operator==(const LinkString& str){
    StrNode *p,*q;
    if(length!=str.length){
        return false;
    }
    p = head->next;
    q = str.head->next;
    for(int i=0;i<length;i++){
        if(p->data!=q->data){
            return false;
        }
        p=p->next;
        q=q->next;
    }
    return true;
}

//如果str是当前的字串，返回它在串中第一次出现的位置，不是字串返回0
int LinkString::index(const LinkString& str){
    LinkString sub;  //创建一个空串
    for(int i=1;i<length-str.length+1;i++){    //扫描可能存在的字串
        if(!SubStr(i,str.length,sub)){        //取长度与str的长度一致的字串
            return 0;     //字串中不存在与str长度一致的子串
        }
        if(sub==str){
            return i;
        }
    }
}

//实现连接串的输出
void LinkString::OutPut(ostream& out) const{
    StrNode *p;
    p = head->next;
    for(int i=0;i<length;i++){
        out<<p->data;
        p=p->next;
    }
    cout<<endl;
}

//重载插入运算符
ostream& operator<<(ostream& out,const LinkString& x){
    x.OutPut(out);
    return out;
}