- 浏览: 128660 次
- 性别:
- 来自: 成都
最新评论
-
yi_chao_jiang:
你好,多谢分享,问个问题,在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709:
为什么我的tabhost显示不出来? 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴:
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501:
牛死人了!!!
B-树 -
mengsina:
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
1.算法描述
a.实现二个栈,在一个数组里面,除非没有任何空间剩余,否则不能有溢出声明
b.实现一个没有头尾结点的栈(单链表)
c.实现带有头结点的栈(单链表)
2.双栈
对于双栈,我们还可以添加resize()方法,当空间满了重新自动分配空间(new),就是将原来的两个栈,拷贝到新建立的数组上面去
a.dsexceptions.h
#ifndef DSEXCEPTIONS_H #define DSEXCEPTIONS_H //栈溢出异常 class StackOverFlowException{ //public: exception public: const char* what() const throw() { return "stack over flow exception, the size<=0 !\n"; } }; //数组越界异常 class ArrayOverFlowException{ public: const char* what() const throw() { return "array over flow exception, the size over array length !\n"; } }; //栈索引异常(栈序号只能是1,2) class ErrorIndexException{ public: const char* what() const throw() { return "the stack index only be 1 and 2 !\n"; } }; #endif
b.stack2.h
/** *实现二个栈,在一个数组里面,除非没有任何空间剩余,否则不能有溢出声明 **/ #ifndef STACK2_H #define STACK2_H #include <iostream> #include "dsexceptions.h" enum{ LEFT = 1, //左栈 RIGHT = 2 //右栈 }; template<class T> class stack2{ public: stack2(int len){ array = new T[len]; leftTop = -1; rightTop = len; max = len; } ~stack2(){ delete [] array; } //出栈,flag为栈编号(1为栈1,2为栈2) T pop(int flag){ if(flag == LEFT){ if(leftTop == -1) throw StackOverFlowException(); return array[leftTop--]; }else if(flag == RIGHT){ if(rightTop == max) throw StackOverFlowException(); return array[rightTop++]; }else{ throw ErrorIndexException(); } } void push(int flag, T x){ if(leftTop == rightTop) throw ArrayOverFlowException(); if(flag == LEFT){ array[++leftTop] = x; }else if(flag == RIGHT){ array[--rightTop] = x; }else{ throw ErrorIndexException(); } } T top(int flag) const{ if(flag == LEFT){ if(leftTop == -1) throw StackOverFlowException(); return array[leftTop]; }else if(flag == RIGHT){ if(rightTop == max) throw StackOverFlowException(); return array[rightTop]; }else{ throw ErrorIndexException(); } } bool empty(int flag) const{ if(flag == LEFT){ if(leftTop == -1) return true; }else if(flag == RIGHT){ if(rightTop == max) return true; }else{ throw ErrorIndexException(); } return false; } void printStack(int flag) const{ if(flag == LEFT){ std::cout<<"["; for(int i=leftTop; i>-1; i--){ std::cout<<array[i]<<" "; } std::cout<<"]"<<std::endl; }else if(flag == RIGHT){ std::cout<<"["; for(int i=rightTop; i<max; i++){ std::cout<<array[i]<<" "; } std::cout<<"]"<<std::endl; }else{ throw ErrorIndexException(); } } int size(int flag) const{ if(flag == LEFT){ return leftTop+1; }else if(flag == RIGHT){ return max-rightTop; }else{ throw ErrorIndexException(); } } private: int leftTop; //左边数组栈顶 int rightTop; //右边数组栈顶 int max; //数组长度 T* array; //数组 }; #endif
c.main.cpp
#include <iostream> #include "stack2.h" using namespace std; int main(){ try{ stack2<int> s(10); for(int i=0; i<4; i++){ s.push(1, i); s.push(2, i); } cout<<"stack1:"<<endl; s.printStack(1); cout<<s.top(1)<<endl; cout<<s.pop(1)<<endl; cout<<s.size(1)<<endl; cout<<s.empty(1)<<endl; s.push(1, 9); s.push(1, 9); s.push(1, 9); cout<<s.size(1)<<endl; s.printStack(1); cout<<"stack2:"<<endl; s.printStack(2); cout<<s.top(2)<<endl; for(int i=0; i<4; i++) s.pop(2); cout<<s.size(2)<<endl; cout<<s.empty(2)<<endl; s.printStack(2); }catch(StackOverFlowException &e){ cout<<e.what(); }catch(ArrayOverFlowException &e){ cout<<e.what(); }catch(ErrorIndexException &e){ cout<<e.what(); } return 0; }
3.单链表实现没有头尾结点的栈
stack.h
#ifndef STACK_H #define STACK_H #include <iostream> #include "dsexceptions.h" template<class T> struct Node{ Node<T>* next; T data; }; template<class T> class stack{ public: stack(){ first = new Node<T>; first->next = NULL; length = 0; } stack(T a[], int n){ first = new Node<T>; first->next = NULL; length = n; first->data = a[0]; for(int i=1; i<n; i++){ Node<T> *t = new Node<T>; t->data = a[i]; t->next = first; first = t; } } ~stack(){ freeStack(); } T pop(){ T data; if(length != 0){ Node<T> *r = first; data = r->data; if(length == 1) //当只剩下一个节点的时候不删除,保留方便下次push first->data = 0; else{ first = first->next; delete r; } length--; }else{ throw StackOverFlowException(); } return data; } void push(T x){ if(length == 0) first->data = x; else{ Node<T> *r = new Node<T>; r->data = x; r->next = first; first = r; } length++; } T top() const{ if(length == 0) throw StackOverFlowException(); return first->data; } bool empty() const{ if(length == 0) return true; return false; } int size() const{ return length; } void printStack() const{ std::cout<<"["; Node<T> *r = first; while(r){ if(length == 0) break; //当没有元素的时候,first并没删除!故而会输出data std::cout<<r->data<<" "; r = r->next; } std::cout<<"]"<<std::endl; } private: Node<T>* first;//栈顶(指向栈顶) int length; void freeStack(){ Node<T> *r = first, *t; while(r){ t = r; r = r->next; delete t; } } }; #endif
main.cpp
#include <iostream> #include "stack.h" using namespace std; int main(){ stack<int> k; k.push(2); cout<<k.size()<<endl; k.pop(); k.printStack(); int a[] = {1,2,3,4,5,6}; stack<int> s(a, 6); s.printStack(); s.push(7); s.printStack(); cout<<"size:"<<s.size()<<endl; s.pop(); s.printStack(); try{ for(int i=0; i<6; i++){ s.pop(); } s.push(7); s.push(8); s.printStack(); cout<<"size:"<<s.size()<<endl; s.pop(); s.pop(); s.pop(); s.printStack(); }catch(StackOverFlowException &e){ cout<<e.what(); } return 0; }
4.带有头结点的栈
stack.h
#ifndef STACK_H #define STACK_H #include <iostream> #include "dsexceptions.h" template<class T> struct Node{ Node<T>* next; T data; }; template<class T> class stack{ public: stack(){ first = new Node<T>; first->next = NULL; end = first; length = 0; } stack(T a[], int n){ first = new Node<T>; length = n; Node<T> *r = first; for(int i=0; i<n; i++){ Node<T> *t = new Node<T>; t->data = a[i]; t->next = r; r = t; } end = r; } ~stack(){ freeStack(); } T pop(){ T data; if(length != 0){ Node<T>* r = end; end = end->next; data = r->data; delete r; length--; }else{ throw StackOverFlowException(); } return data; } void push(T x){ Node<T> *r = new Node<T>; r->data = x; r->next = end; end = r; length++; } T top() const{ if(length == 0) throw StackOverFlowException(); return end->data; } bool empty() const{ if(length == 0) return true; return false; } int size() const{ return length; } void printStack() const{ std::cout<<"["; Node<T> *r = end; while(r != first){ std::cout<<r->data<<" "; r = r->next; } std::cout<<"]"<<std::endl; } private: Node<T>* first;//栈底(不存储元素) Node<T>* end;//栈顶(指向栈顶) int length; void freeStack(){ Node<T> *r = end, *t; while(r != first){ t = r; r = r->next; delete t; } delete r; } }; #endif
发表评论
-
排序方法总结
2012-08-12 11:34 1131这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14161.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2774一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11741.堆的概念 这里只需要注意两点: a.堆的存储方式:就是 ... -
set和map的简单实现
2012-08-10 11:35 12761.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9071.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15871.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 27941.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14161.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56101.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11871.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12371.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25541.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14921.算法描述 a.数据结构与算法(Mark Allen We ... -
中缀表达式转换为后缀
2012-06-28 11:10 17501.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 12891.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9531.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接: a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 9991.算法描述 有序(行有序,列有序,且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2231算法描述:生成前N个整 ...
相关推荐
栈中数据用数组储存,通过top(),push(),pop()基本的函数用以实现其功能。 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748152
实现链式栈和顺序栈的定义,分别创建一个栈。
编写一个程序,实现顺序栈的各种基本运算,并在基础上完成以下功能: 1)初始化顺序栈; 2)判断顺序栈是否为空; 3)依次进栈元素a,b,c,d,e; 4)判断顺序栈是否为空; 5)输出栈长度; 6)输出从栈顶到栈底的元素; 7)...
顺序栈的基本操作的实现,这个程序中演示了顺序栈的初始化、顺序栈的创建、删除、查找以及输出等功能。使用c语言所写。
数据结构课程中顺序栈和链栈的操作实现,实现语言为C语言
用顺序结构表示栈并实现栈的各种基本操作.doc
栈的定义和实现。栈中数据成员是指向栈顶的指针*top_node。成员函数是实现栈最基本的操作——push()向栈中加入元素,pop()移出栈顶元素,top()得到栈顶元素,empty()判断栈是否为空。 参见博客:...
顺序栈的实现,有一个很好栈数据结构,算法简单,能实现栈的各种操作
1、实现顺序栈的各种基本运算的算法,并在此基础上设计一个主程序完成如下功能: ①初始化栈; ②判断栈是否非空; ③依次进栈各元素; ④输出栈的长度; ⑤输出从栈顶到栈底的元素; ⑥输出出栈序列; ⑦...
数据结构各种算法实现,有示例程序。 包括顺序表 单链表 双向链表 循环链表 顺序栈 链式栈 顺序队列 链式队列 串 二叉树 线索二叉树 堆 哈夫曼树 B+树 图 排序算法
NULL 博文链接:https://448230305.iteye.com/blog/2193377
1个班的50份java作业:类设计 实现栈的基本结构 小型计算器
数据结构各种算法实现(C++模板)链表 栈 队的各种操作 图树
2、 实现如下算法: 1) 创建顺序栈; 2)插入操作:向栈顶压入值为 x 的元素; 3) 删除操作: 弹出栈顶元素,将数据输出在屏幕上; 4) 存取操作:读取栈顶元素,将数据输出在屏幕上;。 3、 为了增强程序的可读性...
顺序栈与链栈的实现
实验内容:栈的顺序表示和实现编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能。初始化顺序栈插入一个元素删除栈顶元素取栈顶元素便利顺序栈置空顺序栈#include<stdio.h>#include...
关于队列与栈的各种算法,其中包括,用两个栈实现一个队列,用两个队列实现一个栈
本文在ZigBee2007协议栈基础上设计开发了一个应用层ZigBee协议,实现了协调器和终端模块之间的双向传输预设格式的数据。ZigBee协议通过对无线模块内的各种硬件资源标准化编码,实现了使用统一的的方法来访问控制模块...
双向顺序栈(Double-ended sequential stack)是一种栈数据结构,它允许在两个方向上进行入栈和出栈操作。...通过在头部和尾部进行入栈和出栈操作,可以方便地实现队列的各种操作,如队列的插入、删除和访问等。
c++顺序栈实现,定义链式栈类 验证如下算法的正确性,各种功能及指标 包括压栈和弹栈操作 为增强程序可读性,有适当注释