• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C++数据结构之LinkedStack(链式栈)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

上一节用连续的方式实现栈,这种方法用一个确定大小的数组存储栈元素,因为当存储达到数组上限时会遇到麻烦。

连续实现的栈与链式实现的栈的最大不同在于,前者使用一个确定大小的数组存储每一个栈元素,后者使用带指针的自定义结构(Node)来存储栈元素,因此可以在后期持续增加栈元素。

链式栈的栈元素存储于自定义的数据结构--Node中,每一个Node均包含两个属性,一个是它里面的元素(栈元素),一个是指向它下一个Node的指针。由此,一个Node包含着栈元素,同时它指向着下一个Node,以此类推,构成一种链式实现的栈。最后,要用顶部指针(指向第一个Node的指针)作为该栈的寻址头。

另外,在这个链式栈的实现当中还实现了几个有用的成员函数--析构函数与重载赋值运算。


代码:

Node.h文件:

/*
 * Node.h
 *
 *  Created on: 2015年8月27日
 *      Author: Lv_Lang
 */

#ifndef NODE_H_
#define NODE_H_

#include "stdio.h"

typedef int Stack_entry;
typedef Stack_entry Node_entry;

struct Node
{
	//	data members
	Node_entry entry; // 存放的元素
	Node *next;		  // 指向下一个元素的指针
	//	Constructors
	Node();
	Node(Node_entry item, Node *add_on = NULL);
};



#endif /* NODE_H_ */

Node.cpp文件:

/*
 * Node.cpp
 *
 *  Created on: 2015年8月27日
 *      Author: Lv_Lang
 */

#include "Node.h"

Node::Node()
{
	next = NULL;
}
Node::Node(Node_entry item, Node *add_on)
{
	entry = item;
	next = add_on;
}

Stack.h文件:

/*
 * Stack
 *
 *  Created on: 2015年8月21日
 *      Author: Administrator
 */

#ifndef STACK
#define STACK

#include "Node.h"

const int maxstack = 10;
enum Error_code {overflow, underflow, success};

class Stack
{
public:
	Stack();
	bool empty()const;
	Error_code pop();
	Error_code top(Stack_entry &item)const;//察看顶部元素,item作为取出值的载体
	Error_code push(const Stack_entry &item);// item是放入的值
	// Safety features for linked structures
	~Stack();
	Stack(const Stack &original);
	void operator = (const Stack &original);
protected:
	Node *top_node;
};



#endif /* STACK_ */

Stack.cpp文件:

/*
 * Stack.cpp
 *
 *  Created on: 2015年8月21日
 *      Author: Administrator
 */
#include "Stack.h"

Stack::Stack()
{
	top_node = NULL;
}
bool Stack::empty()const
{
	if(top_node == NULL)
		return true;
	else
		return false;
}
Error_code Stack::pop()
{
	if(empty())
			return underflow;
	else
	{
		//只需新建一个指针,无须新建空间故不用new
		Node *old_top = top_node;
		top_node = old_top->next;
		delete old_top; //记得要delete掉被删除指针指向的空间
		return success;
	}
}
Error_code Stack::top(Stack_entry &item)const
{
	if(empty())
		return underflow;
	else
		item = top_node->entry;
	return success;
}
Error_code Stack::push(const Stack_entry &item)
{
	//需要先new出一块区域
	Node *new_top = new Node(item,top_node); //new语句返回的是指针
	if(new_top== NULL)
		return overflow;
	else
	{
		top_node = new_top;
		return success;
	}
}
Stack::~Stack()
{
	while(!empty())
	{
		pop();
	}
}
void Stack::operator =(const Stack &original)
{
	Node *new_top, *new_copy, *original_node = original.top_node;
	if(original.top_node == NULL)
		new_top = NULL;
	else
	{
		new_top = 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;
		}
	}
	while(!empty())	//Clean out old Stack entries
		pop();
	top_node = new_top;	// and replace them with new entries
}
Stack::Stack(const Stack &original)
{
	Node *new_copy, *original_node = original.top_node;
	if(original.top_node == NULL)
		top_node = NULL;
	else
	{			// Duplicate(copy) the linked nodes
		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;
		}
	}
}


main函数测试文件:

/*
 * main.cpp
 *
 *  Created on: 2015年8月21日
 *      Author: Administrator
 */
#include "Stack.h"
//using

void test_1();
void test_2();

int main()
{
	Stack mystack;
	bool e = mystack.empty();
	mystack.push(2);
	e = mystack.empty();
	mystack.push(5);
	int a;
	mystack.top(a);
	printf("%s %d\n","Hello",a);

	Stack stack_1(mystack);
	int b;
	stack_1.top(b);
	printf("%s %d\n","Hello1",b);

	Stack stack_2;
	stack_2 = mystack;
	int c;
	stack_2.top(c);
	printf("%s %d\n","Hello2",c);

	return 0;
}



main函数测试文件写的比较粗糙,这里只要测试能成功实现栈的重载赋值操作即可。



鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#中如何只保留小数点后面两位?发布时间:2022-07-13
下一篇:
C++实现编码转换发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap