设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 求大神帮忙解决
返回列表 发新帖
查看: 2905|回复: 11

[已解决]求大神帮忙解决

[复制链接]
kykio
发表于 2018-5-2 20:49:30 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
这个程序太困难了，求大神帮忙解决！
以下问题要求统一在一个大程序里解决。
按先序遍历的扩展序列建立二叉树的存储结构
二叉树先序、中序、后序遍历的递归算法
二叉树中序遍历的非递归算法
二叉树层次遍历的非递归算法
求二叉树的深度(后序遍历)
建立树的存储结构
求树的深度
最佳答案
月排行榜 / 总排行榜
溯影
2018-5-5 10:05:38
二叉树的那个帖子我想回复你但是不知道为什么我的帖子没有办法发出去。。。。。
层次遍历要用到队列，非递归中序遍历要用到栈
我用宏定义引用了上面的顺序队列和顺序栈的模板
主程序：
#include <iostream>
#include <assert.h>
#include <cstdbool>
using namespace std;

//宏定义，嵌入队列文件模板
#ifndef SQQUEUE_H
#define SQQUEUE_H
#include "C:\Users\pc\Desktop\ConsoleApplication1\ConsoleApplication1\SqQueue.cpp"
#endif

//宏定义，嵌入顺序栈文件模板
#ifndef SQSTACK_H
#define SQSTACK_H
#include "C:\Users\pc\Desktop\ConsoleApplication1\ConsoleApplication1\SqStack.cpp"
#endif


template <typename elemtype>
class BiTree{
public:
        class Node{
        public:
                Node *left;                //指向左结点
                Node *right;        //指向右结点
                elemtype data;        //数据域

                Node(){                        //构造函数
                        left = NULL;
                        right = NULL;
                }
        };

        typedef Node* NodePointer;

protected:
        NodePointer root;        //根节点

public:
        BiTree(){                        //二叉树构造函数
                root = NULL;
        }

        void createBiTree();
        void createBiTree_aux(NodePointer &p);                        //创建二叉树辅助函数
        void preOrderTraverse();                                                //前序递归遍历二叉树
        void preOrderTraverse_aux(NodePointer p);                //前序递归遍历二叉树辅助函数

        void inOrderTraverse();                                                        //中序递归遍历二叉树
        void inOrderTraverse_aux(NodePointer p);                //中序递归遍历二叉树辅助函数

        void postOrderTraverse();                                                //后序递归遍历二叉树
        void postOrderTraverse_aux(NodePointer p);                //后序递归遍历二叉树辅助函数

        int depth();                                                                        //求二叉树深度
        int depth_aux(NodePointer p);                                        //求二叉树深度的辅助函数


        void layOrderTraverse();                                                //按层次顺序遍历二叉树

        void noRecursionInOrderTraverse();                                //非递归中序遍历二叉树

};

//创建二叉树
template <typename elemtype>
void BiTree<elemtype>::createBiTree(){
        createBiTree_aux(root);
}

//创建二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::createBiTree_aux(NodePointer &p){
        elemtype value;
        cout << "请输入数据域的值，输入0时代表叶子的生成:";
        cin >> value;
        if (value == 0){
                p = NULL;
        }
        else{
                p = new Node;
                assert(p != 0);
                p->data = value;                        //先序创建二叉树
                createBiTree_aux(p->left);                //左子树递归
                createBiTree_aux(p->right);                //右子树递归
        }
}

//先序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse(){
        preOrderTraverse_aux(root);
}
//先序遍历二叉树的辅助函数
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse_aux(NodePointer p){
        if (p){
                cout << p->data << "\t";
                preOrderTraverse_aux(p->left);
                preOrderTraverse_aux(p->right);
        }
}


//中序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse(){
        inOrderTraverse_aux(root);
}

//中序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse_aux(NodePointer p){
        if (p){
                inOrderTraverse_aux(p->left);
                cout << p->data << "\t";
                inOrderTraverse_aux(p->right);
        }
}


//后续递归遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse(){
        postOrderTraverse_aux(root);
}

//后序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse_aux(NodePointer p){
        if (p){
                postOrderTraverse_aux(p->left);
                postOrderTraverse_aux(p->right);
                cout << p->data << "\t";
        }
}


//求二叉树的深度
template <typename elemtype>
int BiTree<elemtype>::depth(){
        return depth_aux(root);
}

//求二叉树深度的辅助函数
template <typename elemtype>
int BiTree<elemtype>::depth_aux(NodePointer p){
        int lDep;                        //左子树深度
        int rDep;                        //右子树深度
        if (!p){                        //如果是空树，返回深度为0
                return 0;
        }
        else{                                //后序递归求二叉树深度
                lDep = depth_aux(p->left);
                rDep = depth_aux(p->right);

                return (lDep > rDep ? lDep : rDep) + 1;
        }
}

//按层次顺序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::layOrderTraverse(){
        NodePointer p;                                                //预指向当前那遍历结点的指针
        SqQueue<NodePointer> Q;                                //顺序队列的类模板，预存放待遍历结点的指针队列
        if (root){
                Q.enQueue(root);                                //根指针进入队列
        }

        //逐一遍历队列每个指针所指向的结点
        while (!Q.isEmpty()){
                Q.deQueue(p);                                        //出队列指针p
                cout << p->data << "\t";                //输出数据域
                if (p->left){
                        Q.enQueue(p->left);                        //左孩子进队列
                }
                if (p->right){
                        Q.enQueue(p->right);                //右孩子进队列
                }
        }
}

//非递归中序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::noRecursionInOrderTraverse(){
        NodePointer p = root;
        SqStack<NodePointer> S;                                //预存放左子树上所有待遍历的结点
        while (p || !S.isEmpty()){
                if (p){
                        S.push(p);                                        //结点进栈
                        p = p->left;
                }
                else{
                        S.pop(p);                                        //如果当前结点为空，左子树走完，弹栈
                        cout << p->data << "\t";
                        p = p->right;
                }
        }
}


int main(void){
        BiTree<int> bt1;
        bt1.createBiTree();
        cout << "先序遍历二叉树：" << endl;
        bt1.preOrderTraverse();
        cout << endl;

        cout << "二叉树的深度:" << bt1.depth() << endl;
        cout << "层次遍历二叉树:";
        bt1.layOrderTraverse();
        cout << endl;
        cout << "非递归中序遍历二叉树:" << endl;
        bt1.noRecursionInOrderTraverse();


        return 0;
}

顺序队列：
#include <iostream>
#include <cstdlib>
#include <cstdbool>
#include <assert.h>
using namespace std;

template <typename elemtype>
class SqQueue{
public:
        //循环队列置空
        void clear();

        //出队列
        bool deQueue(elemtype &e);

        //进队列
        bool enQueue(elemtype e);

        //读取循环队列队头元素
        bool getFront(elemtype &e);

        //求循环队列的元素的个数
        int getLength();

        //判断队列是否为空
        bool isEmpty();

        //判断队列是否已满
        bool isFull();

        //重载赋值运算符
        SqQueue operator=(SqQueue right);

        //构造函数
        SqQueue(int size = 10);

        //析构函数
        virtual ~SqQueue();

        //拷贝构造函数
        SqQueue(SqQueue &other);

        //重载输出运算符
        template <typename out_put>
        friend ostream& operator <<(ostream& out, SqQueue<out_put> other);

protected:
        int rear;//队尾指针
        int front;//对头指针
        int queueSize;//循环队列最大存储空间
        elemtype *base;//队列动态存储空间的首地址
};


template <typename elemtype>
void SqQueue<elemtype>::clear(){
        front = rear;
}

//出队列
template <typename elemtype>
bool SqQueue<elemtype>::deQueue(elemtype &e){
        if (isEmpty()){
                return false;
        }
        e = base[front];
        front = (front + 1) % queueSize;//这里要取模，形成循环队列
        return true;
}

//进队列
template <typename elemtype>
bool SqQueue<elemtype>::enQueue(elemtype e){
        if (isFull()){
                return false;
        }
        base[rear] = e;
        rear = (rear + 1) % queueSize;
        return true;
}

//读取队头元素
template <typename elemtype>
bool SqQueue<elemtype>::getFront(elemtype &e){
        if (isEmpty()){
                return false;
        }
        e = base[front];
        return true;
}

//求队列中元素的个数
template <typename elemtype>
int SqQueue<elemtype>::getLength(){
        return (rear - front + queueSize) % queueSize;
}

//判断是否为空
template <typename elemtype>
bool SqQueue<elemtype>::isEmpty(){
        return front == rear ? true : false;
}

//判断队列是否已满
template <typename elemtype>
bool SqQueue<elemtype>::isFull(){
        return (rear + 1) % queueSize == front ? true : false;
}

//重载赋值运算符
template <typename elemtype>
SqQueue<elemtype> SqQueue<elemtype>::operator=(SqQueue<elemtype> right){
        if (this != &right){
                if (queueSize != right.queueSize){
                        delete[] base;
                        base = new elemtype[right.queueSize];
                        assert(base != 0);
                        queueSize = right.queueSize;
                }

                front = right.front;
                rear = right.rear;

                for (int i = front; i%queueSize != rear;){
                        base[i] = right.base[i];
                        i = (i + 1) % queueSize;
                }
        }
        return *this;
}

template <typename elemtype>
SqQueue<elemtype>::SqQueue(int size = 10){
        base = new elemtype[size];
        assert(base != 0);
        front = rear = 0;
        queueSize = size;
}

template <typename elemtype>
SqQueue<elemtype>:: ~SqQueue(){
        delete[]base;
}

//拷贝初始化构造函数
template <typename elemtype>
SqQueue<elemtype>::SqQueue(SqQueue &other){
        base = new elemtype[other.queueSize];
        assert(base != 0);
        queueSize = other.queueSize;

        front = other.front;
        rear = other.rear;

        for (int i = front; i%queueSize != rear;){
                base[i] = other.base[i];
                i = (i + 1) % queueSize;
        }
}

//重载输出运算符
template <typename out_put>
ostream& operator<<(ostream& out, SqQueue<out_put> other){
        for (int i = other.front; i%other.queueSize != other.rear;){
                out << other.base[i] << "\t";
                i = (i + 1) % other.queueSize;
        }
        return out;
}

顺序栈：
#include <iostream>
#include <assert.h>
#include <cstdlib>
#include <cstdbool>
#define STACK_MAX_SIZE 100
#define STACKINCREAMENT 10
using namespace std;

template <typename elemtype>
class SqStack{
public:
        //顺序栈置空
        void clear();

        //求顺序栈中元素的个数
        int getLength();

        //返回档期那已经分派的存储空间的大小
        int getStackSize();

        //读取栈顶元素
        bool getTop(elemtype &e);

        //判断顺序栈是否为空
        bool isEmpty();

        //重载赋值运算符
        SqStack operator=(SqStack right);

        //弹出栈顶元素
        bool pop(elemtype &e);

        //在栈顶压入元素e
        void push(elemtype e);

        //构造函数
        SqStack();

        //析构函数
        virtual ~SqStack();

        //拷贝构造函数
        SqStack(SqStack &other);

        //重载输出运算符
        template <typename out_put>
        friend ostream& operator <<(ostream& out, SqStack<out_put> other);

protected:
        elemtype *base;//栈底指针，就是顺序栈动态存储空间的首地址
        elemtype *top;//栈顶指针
        int stackSize;//顺序栈当前已经分配的存储空间的大小
};


template <typename elemtype>
void SqStack<elemtype>::clear(){
        top = base;
        cout << "顺序栈已经清空" << endl;
}

template <typename elemtype>
int SqStack<elemtype>::getLength(){
        return top - base;
}

template <typename elemtype>
int SqStack<elemtype>::getStackSize(){
        return stackSize;
}

//读取栈顶的元素
template <typename elemtype>
bool SqStack<elemtype>::getTop(elemtype &e){
        if (isEmpty()){
                return false
        }
        else{
                e = *(top - 1);
        }
        return true;
}

template <typename elemtype>
bool SqStack<elemtype>::isEmpty(){
        return top == base ? true : false;
}

//重载赋值运算符
template <typename elemtype>
SqStack<elemtype> SqStack<elemtype>::operator =(SqStack<elemtype> right){
        int length = right.getLength();

        if (this != &right){
                if (stackSize < right.stackSize){
                        delete[] base;  //回收左边的顺序栈的存取空间
                        base = new elemtype[right.stackSize];
                        assert(base != 0);
                        stackSize = right.stackSize;//进行属性的一些重新的赋值
                }

                for (int i = 0; i < length; i++){
                        *(base + i) = *(right.base + i);
                }
                top = base + length();
        }
        return *this;//返回对象
}

//弹出栈顶元素到e
template <typename elemtype>
bool SqStack<elemtype>::pop(elemtype &e){
        if (isEmpty()){
                return false;
        }
        else{
                e = *--top;
        }
        return true;
}

//在栈顶压入元素e
template <typename elemtype>
void SqStack<elemtype>::push(elemtype e){
        int length = top - base;//顺序栈中元素的个数
        elemtype *newBase;//预指向新顺序栈的栈底指针
        //判断当前顺序栈是否已满，如果满了，则需要另外申请存储空间
        if (top - base >= stackSize){
                newBase = new elemtype[stackSize + STACKINCREAMENT];
                assert(newBase != 0);

                for (int j = 0; j < length; j++){
                        *(newBase + j) = *(base + j);
                }

                delete[] base;//回收当前已经满了的栈空间
                base = newBase;
                top = base + length;
        }

        //如果当前顺序栈没有满，就不用重新申请空间了，就直接以下两个语句就行了
        *top = e;
        top++;
}


template <typename elemtype>
SqStack<elemtype>::SqStack(){
        base = new elemtype[STACK_MAX_SIZE];//申请空间
        assert(base != 0);
        stackSize = STACK_MAX_SIZE;//属性的赋值
        top = base;//栈的初始为空
}

//你懂的
template <typename elemtype>
SqStack<elemtype>::~SqStack(){
        if (base){
                delete[]base;
        }
        stackSize = 0;
        top = base = NULL;
}

template <typename elemtype>
SqStack<elemtype>::SqStack(SqStack &other){
        int length = other.top - other.base;
        base = new elemtype[other.stackSize];

        assert(base != 0);

        stackSize = other.stackSize;
        for (int i = 0; i < length; i++){
                *(base + i) = *(other.base + i);
        }
        top = base + length;
}

template <typename out_put>
ostream& operator<<(ostream& out, SqStack<out_put> other){
        int length = other.top - other.base;
        for (int i = 0; i < length; i++){
                out << *(other.base + i) << "\t";
        }

        return out;
}

/*
int main(void){
        SqStack<int> s1;
        for (int i = 1; i <= 10; i++){
                s1.push(i);
        }
        cout << "顺序栈为:";
        cout << s1 << endl;//应用的重载的输出运算符
        cout << "####################################" << endl;
        int e;
        while (s1.pop(e)){
                cout << "弹出栈顶元素为:" << e << endl;
        }

        return 0;
}
*/



想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

溯影
发表于 2018-5-5 10:05:38 | 显示全部楼层    本楼为最佳答案   
二叉树的那个帖子我想回复你但是不知道为什么我的帖子没有办法发出去。。。。。
层次遍历要用到队列，非递归中序遍历要用到栈
我用宏定义引用了上面的顺序队列和顺序栈的模板
主程序：
#include <iostream>
#include <assert.h>
#include <cstdbool>
using namespace std;

//宏定义，嵌入队列文件模板
#ifndef SQQUEUE_H
#define SQQUEUE_H
#include "C:\Users\pc\Desktop\ConsoleApplication1\ConsoleApplication1\SqQueue.cpp"
#endif

//宏定义，嵌入顺序栈文件模板
#ifndef SQSTACK_H
#define SQSTACK_H
#include "C:\Users\pc\Desktop\ConsoleApplication1\ConsoleApplication1\SqStack.cpp"
#endif


template <typename elemtype>
class BiTree{
public:
        class Node{
        public:
                Node *left;                //指向左结点
                Node *right;        //指向右结点
                elemtype data;        //数据域

                Node(){                        //构造函数
                        left = NULL;
                        right = NULL;
                }
        };

        typedef Node* NodePointer;

protected:
        NodePointer root;        //根节点

public:
        BiTree(){                        //二叉树构造函数
                root = NULL;
        }

        void createBiTree();
        void createBiTree_aux(NodePointer &p);                        //创建二叉树辅助函数
        void preOrderTraverse();                                                //前序递归遍历二叉树
        void preOrderTraverse_aux(NodePointer p);                //前序递归遍历二叉树辅助函数

        void inOrderTraverse();                                                        //中序递归遍历二叉树
        void inOrderTraverse_aux(NodePointer p);                //中序递归遍历二叉树辅助函数

        void postOrderTraverse();                                                //后序递归遍历二叉树
        void postOrderTraverse_aux(NodePointer p);                //后序递归遍历二叉树辅助函数

        int depth();                                                                        //求二叉树深度
        int depth_aux(NodePointer p);                                        //求二叉树深度的辅助函数


        void layOrderTraverse();                                                //按层次顺序遍历二叉树

        void noRecursionInOrderTraverse();                                //非递归中序遍历二叉树

};

//创建二叉树
template <typename elemtype>
void BiTree<elemtype>::createBiTree(){
        createBiTree_aux(root);
}

//创建二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::createBiTree_aux(NodePointer &p){
        elemtype value;
        cout << "请输入数据域的值，输入0时代表叶子的生成:";
        cin >> value;
        if (value == 0){
                p = NULL;
        }
        else{
                p = new Node;
                assert(p != 0);
                p->data = value;                        //先序创建二叉树
                createBiTree_aux(p->left);                //左子树递归
                createBiTree_aux(p->right);                //右子树递归
        }
}

//先序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse(){
        preOrderTraverse_aux(root);
}
//先序遍历二叉树的辅助函数
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse_aux(NodePointer p){
        if (p){
                cout << p->data << "\t";
                preOrderTraverse_aux(p->left);
                preOrderTraverse_aux(p->right);
        }
}


//中序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse(){
        inOrderTraverse_aux(root);
}

//中序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse_aux(NodePointer p){
        if (p){
                inOrderTraverse_aux(p->left);
                cout << p->data << "\t";
                inOrderTraverse_aux(p->right);
        }
}


//后续递归遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse(){
        postOrderTraverse_aux(root);
}

//后序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse_aux(NodePointer p){
        if (p){
                postOrderTraverse_aux(p->left);
                postOrderTraverse_aux(p->right);
                cout << p->data << "\t";
        }
}


//求二叉树的深度
template <typename elemtype>
int BiTree<elemtype>::depth(){
        return depth_aux(root);
}

//求二叉树深度的辅助函数
template <typename elemtype>
int BiTree<elemtype>::depth_aux(NodePointer p){
        int lDep;                        //左子树深度
        int rDep;                        //右子树深度
        if (!p){                        //如果是空树，返回深度为0
                return 0;
        }
        else{                                //后序递归求二叉树深度
                lDep = depth_aux(p->left);
                rDep = depth_aux(p->right);

                return (lDep > rDep ? lDep : rDep) + 1;
        }
}

//按层次顺序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::layOrderTraverse(){
        NodePointer p;                                                //预指向当前那遍历结点的指针
        SqQueue<NodePointer> Q;                                //顺序队列的类模板，预存放待遍历结点的指针队列
        if (root){
                Q.enQueue(root);                                //根指针进入队列
        }

        //逐一遍历队列每个指针所指向的结点
        while (!Q.isEmpty()){
                Q.deQueue(p);                                        //出队列指针p
                cout << p->data << "\t";                //输出数据域
                if (p->left){
                        Q.enQueue(p->left);                        //左孩子进队列
                }
                if (p->right){
                        Q.enQueue(p->right);                //右孩子进队列
                }
        }
}

//非递归中序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::noRecursionInOrderTraverse(){
        NodePointer p = root;
        SqStack<NodePointer> S;                                //预存放左子树上所有待遍历的结点
        while (p || !S.isEmpty()){
                if (p){
                        S.push(p);                                        //结点进栈
                        p = p->left;
                }
                else{
                        S.pop(p);                                        //如果当前结点为空，左子树走完，弹栈
                        cout << p->data << "\t";
                        p = p->right;
                }
        }
}


int main(void){
        BiTree<int> bt1;
        bt1.createBiTree();
        cout << "先序遍历二叉树：" << endl;
        bt1.preOrderTraverse();
        cout << endl;

        cout << "二叉树的深度:" << bt1.depth() << endl;
        cout << "层次遍历二叉树:";
        bt1.layOrderTraverse();
        cout << endl;
        cout << "非递归中序遍历二叉树:" << endl;
        bt1.noRecursionInOrderTraverse();


        return 0;
}

顺序队列：
#include <iostream>
#include <cstdlib>
#include <cstdbool>
#include <assert.h>
using namespace std;

template <typename elemtype>
class SqQueue{
public:
        //循环队列置空
        void clear();

        //出队列
        bool deQueue(elemtype &e);

        //进队列
        bool enQueue(elemtype e);

        //读取循环队列队头元素
        bool getFront(elemtype &e);

        //求循环队列的元素的个数
        int getLength();

        //判断队列是否为空
        bool isEmpty();

        //判断队列是否已满
        bool isFull();

        //重载赋值运算符
        SqQueue operator=(SqQueue right);

        //构造函数
        SqQueue(int size = 10);

        //析构函数
        virtual ~SqQueue();

        //拷贝构造函数
        SqQueue(SqQueue &other);

        //重载输出运算符
        template <typename out_put>
        friend ostream& operator <<(ostream& out, SqQueue<out_put> other);

protected:
        int rear;//队尾指针
        int front;//对头指针
        int queueSize;//循环队列最大存储空间
        elemtype *base;//队列动态存储空间的首地址
};


template <typename elemtype>
void SqQueue<elemtype>::clear(){
        front = rear;
}

//出队列
template <typename elemtype>
bool SqQueue<elemtype>::deQueue(elemtype &e){
        if (isEmpty()){
                return false;
        }
        e = base[front];
        front = (front + 1) % queueSize;//这里要取模，形成循环队列
        return true;
}

//进队列
template <typename elemtype>
bool SqQueue<elemtype>::enQueue(elemtype e){
        if (isFull()){
                return false;
        }
        base[rear] = e;
        rear = (rear + 1) % queueSize;
        return true;
}

//读取队头元素
template <typename elemtype>
bool SqQueue<elemtype>::getFront(elemtype &e){
        if (isEmpty()){
                return false;
        }
        e = base[front];
        return true;
}

//求队列中元素的个数
template <typename elemtype>
int SqQueue<elemtype>::getLength(){
        return (rear - front + queueSize) % queueSize;
}

//判断是否为空
template <typename elemtype>
bool SqQueue<elemtype>::isEmpty(){
        return front == rear ? true : false;
}

//判断队列是否已满
template <typename elemtype>
bool SqQueue<elemtype>::isFull(){
        return (rear + 1) % queueSize == front ? true : false;
}

//重载赋值运算符
template <typename elemtype>
SqQueue<elemtype> SqQueue<elemtype>::operator=(SqQueue<elemtype> right){
        if (this != &right){
                if (queueSize != right.queueSize){
                        delete[] base;
                        base = new elemtype[right.queueSize];
                        assert(base != 0);
                        queueSize = right.queueSize;
                }

                front = right.front;
                rear = right.rear;

                for (int i = front; i%queueSize != rear;){
                        base[i] = right.base[i];
                        i = (i + 1) % queueSize;
                }
        }
        return *this;
}

template <typename elemtype>
SqQueue<elemtype>::SqQueue(int size = 10){
        base = new elemtype[size];
        assert(base != 0);
        front = rear = 0;
        queueSize = size;
}

template <typename elemtype>
SqQueue<elemtype>:: ~SqQueue(){
        delete[]base;
}

//拷贝初始化构造函数
template <typename elemtype>
SqQueue<elemtype>::SqQueue(SqQueue &other){
        base = new elemtype[other.queueSize];
        assert(base != 0);
        queueSize = other.queueSize;

        front = other.front;
        rear = other.rear;

        for (int i = front; i%queueSize != rear;){
                base[i] = other.base[i];
                i = (i + 1) % queueSize;
        }
}

//重载输出运算符
template <typename out_put>
ostream& operator<<(ostream& out, SqQueue<out_put> other){
        for (int i = other.front; i%other.queueSize != other.rear;){
                out << other.base[i] << "\t";
                i = (i + 1) % other.queueSize;
        }
        return out;
}

顺序栈：
#include <iostream>
#include <assert.h>
#include <cstdlib>
#include <cstdbool>
#define STACK_MAX_SIZE 100
#define STACKINCREAMENT 10
using namespace std;

template <typename elemtype>
class SqStack{
public:
        //顺序栈置空
        void clear();

        //求顺序栈中元素的个数
        int getLength();

        //返回档期那已经分派的存储空间的大小
        int getStackSize();

        //读取栈顶元素
        bool getTop(elemtype &e);

        //判断顺序栈是否为空
        bool isEmpty();

        //重载赋值运算符
        SqStack operator=(SqStack right);

        //弹出栈顶元素
        bool pop(elemtype &e);

        //在栈顶压入元素e
        void push(elemtype e);

        //构造函数
        SqStack();

        //析构函数
        virtual ~SqStack();

        //拷贝构造函数
        SqStack(SqStack &other);

        //重载输出运算符
        template <typename out_put>
        friend ostream& operator <<(ostream& out, SqStack<out_put> other);

protected:
        elemtype *base;//栈底指针，就是顺序栈动态存储空间的首地址
        elemtype *top;//栈顶指针
        int stackSize;//顺序栈当前已经分配的存储空间的大小
};


template <typename elemtype>
void SqStack<elemtype>::clear(){
        top = base;
        cout << "顺序栈已经清空" << endl;
}

template <typename elemtype>
int SqStack<elemtype>::getLength(){
        return top - base;
}

template <typename elemtype>
int SqStack<elemtype>::getStackSize(){
        return stackSize;
}

//读取栈顶的元素
template <typename elemtype>
bool SqStack<elemtype>::getTop(elemtype &e){
        if (isEmpty()){
                return false
        }
        else{
                e = *(top - 1);
        }
        return true;
}

template <typename elemtype>
bool SqStack<elemtype>::isEmpty(){
        return top == base ? true : false;
}

//重载赋值运算符
template <typename elemtype>
SqStack<elemtype> SqStack<elemtype>::operator =(SqStack<elemtype> right){
        int length = right.getLength();

        if (this != &right){
                if (stackSize < right.stackSize){
                        delete[] base;  //回收左边的顺序栈的存取空间
                        base = new elemtype[right.stackSize];
                        assert(base != 0);
                        stackSize = right.stackSize;//进行属性的一些重新的赋值
                }

                for (int i = 0; i < length; i++){
                        *(base + i) = *(right.base + i);
                }
                top = base + length();
        }
        return *this;//返回对象
}

//弹出栈顶元素到e
template <typename elemtype>
bool SqStack<elemtype>::pop(elemtype &e){
        if (isEmpty()){
                return false;
        }
        else{
                e = *--top;
        }
        return true;
}

//在栈顶压入元素e
template <typename elemtype>
void SqStack<elemtype>::push(elemtype e){
        int length = top - base;//顺序栈中元素的个数
        elemtype *newBase;//预指向新顺序栈的栈底指针
        //判断当前顺序栈是否已满，如果满了，则需要另外申请存储空间
        if (top - base >= stackSize){
                newBase = new elemtype[stackSize + STACKINCREAMENT];
                assert(newBase != 0);

                for (int j = 0; j < length; j++){
                        *(newBase + j) = *(base + j);
                }

                delete[] base;//回收当前已经满了的栈空间
                base = newBase;
                top = base + length;
        }

        //如果当前顺序栈没有满，就不用重新申请空间了，就直接以下两个语句就行了
        *top = e;
        top++;
}


template <typename elemtype>
SqStack<elemtype>::SqStack(){
        base = new elemtype[STACK_MAX_SIZE];//申请空间
        assert(base != 0);
        stackSize = STACK_MAX_SIZE;//属性的赋值
        top = base;//栈的初始为空
}

//你懂的
template <typename elemtype>
SqStack<elemtype>::~SqStack(){
        if (base){
                delete[]base;
        }
        stackSize = 0;
        top = base = NULL;
}

template <typename elemtype>
SqStack<elemtype>::SqStack(SqStack &other){
        int length = other.top - other.base;
        base = new elemtype[other.stackSize];

        assert(base != 0);

        stackSize = other.stackSize;
        for (int i = 0; i < length; i++){
                *(base + i) = *(other.base + i);
        }
        top = base + length;
}

template <typename out_put>
ostream& operator<<(ostream& out, SqStack<out_put> other){
        int length = other.top - other.base;
        for (int i = 0; i < length; i++){
                out << *(other.base + i) << "\t";
        }

        return out;
}

/*
int main(void){
        SqStack<int> s1;
        for (int i = 1; i <= 10; i++){
                s1.push(i);
        }
        cout << "顺序栈为:";
        cout << s1 << endl;//应用的重载的输出运算符
        cout << "####################################" << endl;
        int e;
        while (s1.pop(e)){
                cout << "弹出栈顶元素为:" << e << endl;
        }

        return 0;
}
*/



想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

kykio
 楼主| 发表于 2018-5-8 19:57:10 | 显示全部楼层
溯影 发表于 2018-5-5 10:05
二叉树的那个帖子我想回复你但是不知道为什么我的帖子没有办法发出去。。。。。
层次遍历要用到队列，非递 ...

不知道为什么，一直没有提醒我有回复，所以看晚了，抱歉！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

刘亮
发表于 2018-5-10 08:37:33 | 显示全部楼层

回帖奖励 +5 鱼币

没怎么看懂，这是C++写的吧！我还没学呢
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

段坤11
发表于 2018-5-15 23:50:15 | 显示全部楼层

回帖奖励 +5 鱼币


没怎么看懂，这是C++写的吧！我还没学呢
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

multitate
发表于 2018-7-12 00:14:53 | 显示全部楼层
学习一下
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

独吟月上
发表于 2018-7-16 23:49:14 | 显示全部楼层

回帖奖励 +5 鱼币

这个真的强
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

whdd
发表于 2018-9-16 12:16:12 | 显示全部楼层

回帖奖励 +5 鱼币

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

钱闻韬
发表于 2018-9-16 17:29:01 | 显示全部楼层

回帖奖励 +5 鱼币

666
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

whdd
发表于 2018-9-28 15:13:42 | 显示全部楼层
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

whdd
发表于 2018-10-1 23:59:05 | 显示全部楼层
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

小小小菜菜菜
发表于 2018-12-20 13:46:29 | 显示全部楼层

回帖奖励 +5 鱼币

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-23 17:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表