【数据结构】链式栈 Linked_stack
发布时间:2020-12-15 06:33:11 所属栏目:安全 来源:网络整理
导读:08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://www.jb51.cc/article/p-srsfcefa-vo.html 链式栈各种基本运算算法的实现 栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的
08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://www.52php.cn/article/p-srsfcefa-vo.html 链式栈各种基本运算算法的实现
栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底(push),最后的数据在栈顶(top),需要读数据的时候从栈顶开始弹出数据(top)最后一个数据被第一个读出来。
链式栈中的元素以Node的形式存储,节点Node中存有此节点存于栈中的元素以及指向下个节点的指针。链式栈的数据成员只用保存指向栈顶节点的指针 *top_node. 因为指针的运用,链式栈在实现时尤其重要的一点就是编写自己的析构函数,拷贝构造函数和重载赋值运算符。 【实验说明】我选择的题目是测试链式栈的各种功能1.链式栈中元素以节点形式存储,首先编写结构Node的定义和实现。 2.编写栈的定义和实现。栈中数据成员是指向栈顶的指针*top_node。成员函数是实现栈最基本的操作——push()向栈中加入元素,pop()移出栈顶元素,top()得到栈顶元素,empty()判断栈是否为空。 3.编写链式栈的析构函数~Stack(),拷贝构造函数Stack(const Stack &original),重载赋值运算符operator=(const Stack &original); 4.编写用于测试栈的各种功能的函数 do_comman()和get_command()以及一些辅助的介绍函数introduction(),help()。 5.编写主函数。运行并测试栈的各种功能。 【相关代码】
node.h
#ifndef NODE_H #define NODE_H #include<iostream> using namespace std; enum Error_code{success,overflow,underflow}; typedef char Node_entry; struct Node{ //data members Node_entry entry; Node *next; //constructors Node(); Node(Node_entry item,Node *add_on=NULL); }; #endif node.cpp #include "node.h" Node::Node() { next=NULL; } Node::Node(Node_entry item,Node *add_on) { entry=item; next=add_on; }linked_stack.h #ifndef LINKEDSTACK_H #define LINKEDSTACK_H #include "node.h" typedef char Stack_entry; class Stack{ public: //constructor Stack(); //member functions bool empty()const; Error_code push(const Stack_entry &item); Error_code pop(); Error_code top(Stack_entry &item)const; //destructor ~Stack(); //copy constructor Stack(const Stack &original); //overload assignment void operator=(const Stack &original); protected: //data member Node *top_node; }; #endiflinked_stack.cpp #include "linked_stack.h" //constructor Stack::Stack(){ top_node=NULL; } //function empty() to check if the stack is empty bool Stack::empty() const{ if(top_node==NULL) return true; else return false; } //function pushh(const Stack_entry &item) to push item into the stack Error_code Stack::push(const Stack_entry &item) { Node *new_top=new Node(item,top_node); if(new_top==NULL) return overflow; top_node=new_top; return success; } //function pop() to pop the last item int the stack Error_code Stack::pop() { Node *old_top=top_node; if(top_node==NULL) return underflow; top_node=old_top->next; delete old_top; return success; } //function top(Stack_entry &item) to assig item with the top item in the stack Error_code Stack::top(Stack_entry &item)const{ if(top_node==NULL) return underflow; item=top_node->entry; return success; } //destructor Stack::~Stack() { while(!empty()) pop(); } //overload assignment void Stack::operator=(const Stack &original) { Node *new_top,*new_copy,*original_node=original.top_node; if(original_node==NULL)new_top=NULL; else{ new_copy=new_top=new Node(original_node->entry); while(original_node->next!=NULL){ original_node=original_node->next; new_copy->next=new Node(original_node->entry); new_copy=new_copy->next; } } while(!empty()) pop(); top_node=new_top; } //copy constructor Stack::Stack(const Stack &original) { Node *new_copy,*original_node=original.top_node; if(original_node==NULL) top_node=NULL; else{ top_node=new_copy=new Node(original_node->entry); while(original_node->next!=NULL){ original_node=original_node->next; new_copy->next=new Node(original_node->entry); new_copy=new_copy->next; } } } 【过程记录】
实验截图:
【结果分析】
1.链式栈中以节点的形式存储栈中的元素,每个节点Node由要保存的元素entry和指向下一个节点的指针next组成。这样大大避免了由连续数组实现栈所带来的限制——不用从一开始就限定栈可存储元素的大小,在添加新的元素时再申请空间,而且节省了不必要的空间。因为节点的存储在物理结构上不一定是连续的,只有内存不足时才会达到full的状态(通常情况是够用的)。
2.指针的运用是件巧妙而又危险的工作。在每改变一个元素(添加或删除)都应注意指针知否指向了正确的地址,避免悬空指针和内存泄露。 3.因为指针的运用,编写Stack类时必须编写自己析构函数,拷贝构造函数以及赋值操作符。
|
相关内容
- Docker Nginx 设置header
- GlassFish上开发部署JAX-WS WebService应用( by quqi99 )
- scala – 没有找到密钥“akka.version”的配置设置
- twitter-bootstrap – 如何在Twitter Bootstrap AngularJS模
- 宝塔面板安装强大优秀NextCloud私有云盘
- bash – 捕获远程脚本的退出代码?
- 如何动态调用WebService?
- .NET WebService 调试,允许通过IE输入参数的设置,允许Per
- shell脚本中的$@和$*之间有什么区别?
- activiti自定义流程之整合(二):使用angular js整合uedit