OOP实现动态栈、动态队列、单链表 | 若花怨蝶 你会怨着谁
Cobb 584 1

OOP实现动态顺序栈(左值、右值)

#if 0
class SeqStack
{
public:
    // 带参数的构造函数
    SeqStack(int size = 20) 
    {
        cout << " SeqStack(int size = 20) "<<endl;
        this->stack_ = new int[size];
        this->capacity_ = size;
        this->top_ = 0;
    }

    // 析构函数
    ~SeqStack() 
    {
        cout << " ~SeqStack() " << endl;
        delete[]stack_;
        stack_ = NULL;
    }

    // 左值引用的拷贝构造函数
    SeqStack(const SeqStack& src)
    {

        cout << "SeqStack(const SeqStack& src)" << endl;
        this->stack_ = new int[src.capacity_];
        for (int i = 0; i < src.top_; i++)
        {
            this->stack_[i] = src.stack_[i];
        }

        this->capacity_ = src.capacity_;
        this->top_ = src.top_;
    }

    // 右值引用的拷贝构造函数
    SeqStack(SeqStack&& src)
    {
        // 对象指针指向原来的,原来的置空,非常关键
        cout << "SeqStack(SeqStack&& src)" << endl;
        this->stack_ = src.stack_;
        this->capacity_ = src.capacity_;
        this->top_ = src.top_;

        src.stack_ = nullptr;
    }

    //左值引用的赋值函数
    SeqStack& operator=(const SeqStack& src)
    {
        cout << "SeqStack& operator=(const SeqStack& src)" << endl;
        // 防止自赋值
        if (this == &src)
            return *this;

        // this->s1    src->s1
        delete[]this->stack_; // 释放原来占用的堆内存

        this->stack_ = new int[src.capacity_];
        for (int i = 0; i < src.top_; i++)
        {
            this->stack_[i] = src.stack_[i];
        }

        this->capacity_ = src.capacity_;
        this->top_ = src.top_;
        return *this;
    }

    // 右值引用的赋值函数 
    SeqStack& operator=(SeqStack&& src)
    {
        cout << " SeqStack& operator=(SeqStack&& src)" << endl;

        delete[]this->stack_; // 释放原来占用的堆内存
        this->stack_ = src.stack_;       //重指向
        src.stack_ = nullptr; //原来的指向置空

        this->capacity_ = src.capacity_;
        this->top_ = src.top_;
        return *this;
    }
public:
    void Push(int val) // this指针指向了调用该方法的对象
    {
        if (this->full())
            Expand(2 * this->capacity_);
        this->stack_[this->top_] = val;
        this->top_++;
    }
    void Pop()
    {
        if (this->empty())
            return;
        this->top_--;
    }
    int GetTop()
    {
        return stack_[top_ - 1];
    }
    bool empty() 
    {
        return top_ == 0;
    }
    bool full() 
    { 
        return top_ == capacity_;
    }
private:
    // 只给Push服务,不需要用户手动调用 2倍扩容操作
    void Expand(int size)
    {
        int* p = new int[size] {};
        memcpy(p, stack_, sizeof(int) * capacity_);
        delete[]stack_;
        stack_ = p;
        capacity_ = size;
    }
private:
    int* stack_;     // 动态数组
    int capacity_;   // 容量
    int top_;        // 栈顶位置
};
SeqStack test()
{
    cout<<"------------"<<endl;
    SeqStack tmp;
    return tmp;
}
int main()
{

        SeqStack s1(30);//实例化一个对象,构造函数构造s1
        SeqStack s2 = s1;   // s1拷贝构造s2
        // SeqStack s2(s1);//s1拷贝构造s2的另一种形式

        SeqStack s3;//构造函数
        SeqStack s4;
        s4 = test();//等号两边对象生命周期不同时,调用右值赋值函数
        for (int i = 0; i < 20; i++)
        {
            if (!s1.full())
            {

                s1.Push(i);
            }
        }
        s3 = s1; // 调用默认的赋值函数 - 浅拷贝,不重载就默认浅拷贝
        while (!s3.empty())
        {
            int a = s3.GetTop();
            cout << a<<" ";
            s3.Pop();
        }   
        cout << endl;

}
#endif

OOP实现动态环形队列(左值、右值)

#if 0
class Queue
{
public:
    //构造函数
    Queue(int size = 20)
    {
        cout << "Queue(int size = 20)" << endl;
        this->queue = new int[size];
        this->rear_ = 0;
        this->front_ = 0;
        this->capacity_ = size;
    }

   //析构函数
    ~Queue()
    {
        cout << " ~Queue()" << endl;
        delete[]this->queue;
        queue = NULL;
    }

    //左值引用的拷贝构造函数
    Queue(const Queue& src)
    {
        cout << " Queue(const Queue& src)" << endl;
        this->queue = new int[src.capacity_];
        for (int i = src.front_; i != src.rear_; i = (i + 1) % src.capacity_)
        {
            this->queue[i] = src.queue[i];
        }
        this->front_ = src.front_;
        this->rear_ = src.rear_;
        this->capacity_ = src.capacity_;
    }

    //右值引用的拷贝构造函数
    Queue(Queue&& src)
    {
        cout << "Queue(Queue&& src)" << endl;
        this->queue = src.queue;   // 1

        this->capacity_ = src.capacity_;
        this->front_ = src.front_;
        this->rear_ = src.rear_;

        src.queue = nullptr; // 2
    }

    //左值引用的赋值函数
    Queue operator= (const Queue& src)
    {
        cout << "Queue operator= (const Queue& src)" << endl;
        // 防自赋值
        if (this == &src)
            return *this;

        //  =  释放 - 开辟 - 拷贝 - 指针指向
        delete[] this->queue;
        this->queue = new int[src.capacity_];
        for (int i = src.front_; i != src.rear_; i = (i + 1) % src.capacity_)
        {
            this->queue[i] = src.queue[i];
        }

        this->front_ = src.front_;
        this->rear_ = src.rear_;
        this->capacity_ = src.capacity_;
        return *this;
    }

    //右值引用的赋值函数
    Queue& operator=(Queue&& src)
    {
        cout << "右值赋值函数" << endl;
        delete[]this->queue; // 释放原来占用的堆内存

        this->queue = src.queue;    //重指向
        src.queue = nullptr;        //原来的指向置空

        this->capacity_ = src.capacity_;
        this->front_ = src.front_;
        this->rear_ = src.rear_;
        return *this;
    }



public:
    void push(int val)
    {
        if ((this->rear_ + 1) % this->capacity_ == this->front_)
        {
            //扩容
            this->expand(2 * this->capacity_);
        }
        //入队,rear接收
        this->queue[this->rear_] = val;
        this->rear_ = (this->rear_ + 1) % this->capacity_;
    }

    void pop()
    {
        //出队,更新front,相等,全出完
        if (this->front_ == this->rear_)
        {
            return;
        }
        this->front_ = (this->front_ + 1) % this->capacity_;
    }

    int get()
    {
        return this->queue[this->front_];
    }

    bool empty()
    {
        //相等,为空
        return (this->front_ == this->rear_);
    }

    bool full()
    {
        //rear+1后到了front,已满
        return (this->rear_ + 1) % this->capacity_ == this->front_;
    }

private:
void expand(int size)
{
    //扩容
    int* p = new int[size] {};
    //拷贝
    int i = 0;
    int j = this->front_;
    for (; j != this->rear_; i++, j = (j + 1) % this->capacity_)
    {
        p[i] = this->queue[j];
    }
    //释放原内存
    delete[]this->queue;
    //更新下标
    this->front_ = 0;
    this->rear_ = i;
    //更新容量
    this->capacity_ = size;
    //重命名
    this->queue = p;
}

private:
    int* queue;
    int rear_;
    int front_;
    int capacity_;

};
int main()
{

    Queue s1;//构造函数
    for (int i = 0; i < 30; i++)
    {
        s1.push(i);
    }

    Queue s2 = s1;//拷贝构造函数
    Queue s3;
    s3 = s1;//赋值函数
    while (!s3.empty())
    {
        int val = s3.get();
        cout << val << " ";
        s3.pop();
    }
    cout << endl;
}
#endif

OOP实现单链表(左值、右值)

#if 0
class Link
{
public:
    Link()
    {
        //生成一个头结点
        this->head_ = new Node;//由于初始化定义在在了构造函数里,所以生成新节点会自动初始化
        //头结点地址域置空
        //this->head_->next = nullptr;
    }

    ~Link()
    {
        //记录头结点
        Node* p = this->head_;
        Node* q = this->head_;
        while (p != NULL)//判断当前节点,删当前节点
        {
            q = p->next;
            //释放当前节点内存
            delete p;
            //将下一个节点置为待释放节点
            p = q;
        }
    }

    // 左值引用的拷贝构造函数
    Link(Link& src)
    {
        cout << " Link(Link& src)" << endl;

        this->head_ = new Node;    //给头结点开辟地址,然后定义一个指针q指向this的头结点
        Node* q = this->head_;

        Node* p = src.head_; //从被拷贝对象的头节点开始复制数据

        //直到最后一个节点的数据拷贝完后跳出循环
        while (p->next != nullptr)//从第一个节点开始复制数据,头结点不放数据
        {
            q->next = new Node;   //进入循环先为待操作节点开辟地址
            q->next ->data = p->next ->data; //开始复制数据

            //指针后移,当到了最后一个节点时,p和q再后移就表示他们最后一个节点的地址域
            q = q->next;
            p = p->next;
        }
        //跳出循环已经是最后一个节点的地址域,置空
        q = nullptr;
    }

    // 右值引用的拷贝构造函数
    Link(Link&& src)
    {

        this->head_ = new Node;  //为要构造的对象头结点开辟地址
        this->head_->next = src.head_->next;  //将被拷贝对象的头结点替换
        delete src.head_;
    }

    //左值引用的赋值函数
    Link& operator=(Link& src)
    {
        cout << "Link& operator=(Link& src)" << endl;
        // 防止自赋值
        if (this == &src)
        {
            return *this;
        }

        Node* p = this->head_->next;  //定义两个指针指向链表的第一个结点
        Node* q = src.head_->next ;

        //当有任何一个链表节点遍历完就跳出循环,同时遍历完也会跳出循环
        while (p != nullptr && q != nullptr)
        {
            //赋值
            p ->data = q ->data;
            //都往下一个节点移动 
            p = p->next;
            q = q->next;  
        }

        //如果是因为this遍历完跳出循环(跳出循环的是最后一个节点的地址域)
        if (p== nullptr && q!=nullptr)
        {
            //把src剩下的节点补到this上
            while ( q != nullptr)
            {
                p = new Node;//此时的p是尾结点的地址域,先开辟一个新节点
                p->data = q->data; //给这个节点赋值

                //指针后移
                p = p->next;
                q = q->next;
            }
           p = nullptr;  //跳出循环说明是src到了最后一个节点。此时的p和q都表示最后一个节点的地址域
        }

        //如果是因为src遍历完跳出循环,说明this比src长,需要把this中多余的删掉
        if (p != nullptr && q == nullptr)
        {

            Node* p1 = p->next; //先把下个节点记录
            p = nullptr;  //把跳出循环的地址域置空作为this的尾结点

            while (p1 != nullptr)//删掉后面的节点
            {
                Node* p2 = p1->next;//q标记下一个节点
                delete p1;  //删掉当前节点
                p1 = p2;//将p1后移
            }
        }
        //返回新链表
        return *this;
    }

    // 右值引用的赋值函数 
    Link& operator=(Link&& src)
    {
        //先删掉this中除了头结点之外的其他节点
        Node* p = this->head_->next ;
        Node* q = this->head_->next->next ;

        while (p != nullptr)
        {
            delete p; //删掉当前节点
            p = q;  //p移到q
            q = q->next;//q移到下一个位置
        }

        this->head_ = src.head_->next; //再把this的头结点指向src的第一个节点
        delete src.head_; //删掉src的头结点
        //返回新链表
        return *this;
    }

public:
    void InsertHead(int val) // 头插法
    {

        Node* p = new Node;  //生成一个节点
        p->data = val;  //初始化数据域
        p->next = this->head_->next;  //插到头结点后面,先将第一个节点的地址放到新节点的地址域
        this->head_->next = p;  //再将头节点的地址域放入当前节点的地址
    }

    void InsertTail(int val) // 尾插法
    {

        Node* p = new Node;//生成一个节点
        p->data = val; //初始化数据
        p->next = NULL; //新节点的地址域置空

        Node* q = this->head_; //找到最后一个节点
        while (q->next != NULL) //从当前节点地址域开始判断
        {
            q = q->next;
        }

        q->next = p;  //最后一个节点的地址域放新节点的地址

    }

    void Remove(int val)// 删除值为val的节点
    {
        Node* p = this->head_;
        Node* q = this->head_->next;

        //找到值为val的节点
        while (q != nullptr && q->data != val)//一直找到最后一个节点
        {
            p = q;
            q = q->next;
        }
        if (q == nullptr)//说明是找到节点后跳出循环的
        {
            return;
        }
        p->next = q->next;
        delete q;
    }

    void Show()              // 打印链表内容
    {
        Node* p = this->head_->next;
        while (p != NULL)
        {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
private:
    struct Node
    {
        Node(int d = 0, Node* p = nullptr)//将初始化定义成一个构造函数
        {
            this->data = d;
            this->next = p;
        }
        int data;
        Node* next;
    };
    Node* head_; // 指向链表头节点的指针
};



int main()
{
    Link link1;//实例化一个对象
    for (int i = 0; i < 10; i++)
    {
        link1.InsertHead(i);
    }
    link1.Show();
    Link link2 = link1;//左值拷贝构造
    link2.Show();
    Link link3;
    for (int i = 10; i < 20; i++)
    {
        link3.InsertHead(i);
    }
    link3 = link2;//左值赋值函数
    link3.Show();
    link3.InsertTail(90);
    link3.Show();
    link3.Remove(90);
    link3.Show();
}
#endif
评论区

索引目录