天天看点
返回

【殷人昆数据结构】第三章3.1 顺序栈的调试SeqStack顺序栈

居然看到有人说指针和数组应该移出教科书，你们说呢？

SeqStack顺序栈

栈是一种只允许在一端插入或删除的线性表。允许插入或删除的一端称为栈顶，另一端称为栈底。

主函数

这个主函数实现了简单的将数据输入栈、打印栈、插入与删除元素、判断是否空、判断是否满的操作。

#include "SeqStack.h"
#include <fstream>
#include <cassert>
using namespace std;
int main(){
	SeqStack<int> sta;
	ifstream fin("data.txt");
	assert(fin);
	int data;
	while (!fin.eof()){
		assert(fin >> data);
		sta.Push(data);		//这里没有重载输入流
	}
	cout << "The initial Stack in the file is:\n" << sta;
	cout << "The current size of the Stack is: " << sta.getSize() << endl;
	sta.getTop(data);
	cout << "The current Top of the Stack is : " << data << endl;
	sta.Pop(data);
	cout << "\nDo a Pop operation, then the stack is:\n" << sta << endl;
	cout << "The data popped is: " << data << endl;
	sta.getTop(data);
	cout << "The current Top of the Stack is : " << data << endl;

	cout << "\nTest the state of the stack:\n";
	if (sta.IsEmpty())	cout << "The stack is empty now!\n";
	else if (sta.IsFull())	cout << "The stack is full now!\n";
		else	cout << "The stack is not empty and not full now!\n";
	cout << "Now make the stack empty, then the state of the stack is:\n";
	sta.MakeEmpty();
	if (sta.IsEmpty())	cout << "The stack is empty now!\n";
	else if (sta.IsFull())	cout << "The stack is full now!\n";
		else	cout << "The stack is not empty and not full now!\n";
	return 0;
}

SeqStack顺序栈类定义 

const int stackIncreament = 20; //栈溢出时扩展空间的增量

template <typename T>class SeqStack{
public:
	SeqStack(int sz =50);
	~SeqStack(){
		delete []elements; 
		elements = NULL;   //我加的，因为听说有野指针的问题。
	}
	void Push(const T &x);    
	bool Pop(T &x);
	bool getTop(T &x)const;
	bool IsEmpty()const{  
	//有了top和maxSize这两个数据成员后，实现下面几个函数都非常容易
		return top == -1;
	}
	bool IsFull()const{
		return top == maxSize-1;
	}
	int getSize()const{
		return top+1;
	}
	void MakeEmpty(){
		top = -1;
	}
	friend ostream& operator << (ostream &out, SeqStack<T> &s)	{
		out << "Index of top is: " << s.top << endl;
		for (int i = 0; i <= s.top; i ++)
			out << i << ": " << s.elements[i] << endl; //顺序表的用法很像数组
		return out;
	}
private:
	T *elements;
	int top;
	int maxSize;
	void overflowProcess();
};

提问1：为什么析构函数中仅仅delete了elements这个数据元素？

析构函数本身会释放该类所申请的内存空间，但调用new运算符是独立申请空间。栈中内存的分配和释放是由系统管理，而堆中内存的分配和释放必须由程序员手动释放。

如：

int a = 3;        //栈中分配
int *p = new int ;//堆中分配

栈是系统数据结构，对于进程/线程是唯一的，它的分配与释放由操作系统来维护，不需要开发者来管理。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时，这些存储单元会被自动释放。栈内存分配运算内置于处理器的指令集中，效率很高，不同的操作系统对栈都有一定的限制。 堆上的内存分配，亦称动态内存分配。程序在运行的期间用malloc申请的内存，这部分内存由程序员自己负责管理，其生存期由开发者决定：在何时分配，分配多少，并在何时用free来释放该内存。这是唯一可以由开发者参与管理的内存。使用的好坏直接决定系统的性能和稳定。

由上可知，但我们需要的内存很少，你又能确定你到底需要多少内存时，请用栈。而当你需要在运行时才知道你到底需要多少内存时，请用堆。

最后针对第三个问题，栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率 比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在 堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会 分 到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。

提问2：关于析构函数，为何析构的时候要将指针置空避免野指针？

野指针指向一个已删除的对象或未申请访问受限内存区域的指针。与空指针不同，野指针无法通过简单地判断是否为 NULL避免，而只能通过养成良好的编程习惯来尽力减少。对野指针进行操作很容易造成程序错误。需对指针进行初始化，有时指针在free或delete后未赋值 NULL，便会使人以为是合法的。别看free和delete的名字（尤其是delete），它们只是把指针所指的内存给释放掉，但并没有把指针本身干掉。此时指针指向的就是“垃圾”内存。释放后的指针应立即将指针置为NULL，防止产生“野指针”。

野指针主要是因为这些疏忽而出现的删除或申请访问受限内存区域的指针。

new开辟空间分为俩种情况：

开辟单变量地址空间：
int *a=new int       //定义一个int类型的指针。
int *a=new int(3)   //定义一个int类型指针并赋予初值3。
           
开辟数组空间：
int *a=new int[5]   //定义一个int类型长度为5的数组并把地址赋给a指针。（注意‘[]’与‘()’的区别） 
释放：        delete []a;

释放完成后需要把指针置为空，防止野指针。

a=null；

构造函数 

template <typename T>SeqStack<T>::SeqStack(int sz){
	top = -1;  //没有元素时topindex是-1，有一个时为0
	maxSize = sz;  
	elements = new T[maxSize];
	assert(elements); 
}

私有函数overflowProcess 

template <typename T>void SeqStack<T>::overflowProcess(){	//扩充栈的内存空间
	T *newArray = new T[maxSize + stackIncreament];
	assert(newArray);
	for (int i = 0; i <= top; i++)
		newArray[i] = elements[i];   //用法和数组类似
	maxSize = maxSize + stackIncreament;  //重设私有变量maxSize
	delete []elements; 
	elements = newArray;   //重新为elements指针赋值
	//这个语句也可以看出，delete之后，elements指针并没有消失
}

Push、Pop和getTop函数 

template <typename T>void SeqStack<T>::Push(const T &x){
	if (IsFull())	overflowProcess();
	elements[++top] = x;  // top++; elements[top] = x;
}


template <typename T>bool SeqStack<T>::Pop(T &x){
	if (IsEmpty()){
		return false;
	}
	x = elements[top--]; // x = elements[top]; top--;
	return true; 
}
 //不像链表，这里去掉一个元素没有立刻删除其空间，而是等到主函数运行结束一并删除

template <typename T>bool SeqStack<T>::getTop(T &x)const{
	if (IsEmpty()){
		return false;
	}
	x = elements[top];
	return true;
}

整一个头文件 

#include <cassert>
#include <iostream>
using namespace std;

const int stackIncreament = 20; //Õ»Òç³öʱÀ©Õ¹¿Õ¼äµÄÔöÁ¿

template <typename T>class SeqStack{
public:
	SeqStack(int sz =50);
	~SeqStack(){
		delete []elements;
	}
	void Push(const T &x);
	bool Pop(T &x);
	bool getTop(T &x)const;
	bool IsEmpty()const{
		return top == -1;
	}
	bool IsFull()const{
		return top == maxSize-1;
	}
	int getSize()const{
		return top+1;
	}
	void MakeEmpty(){
		top = -1;
	}
	friend ostream& operator << (ostream &out, SeqStack<T> &s)	{
		out << "Index of top is: " << s.top << endl;
		for (int i = 0; i <= s.top; i ++)
			out << i << ": " << s.elements[i] << endl;
		return out;
	}
private:
	T *elements;
	int top;
	int maxSize;
	void overflowProcess();
};

template <typename T>SeqStack<T>::SeqStack(int sz){
	top = -1;
	maxSize = sz;
	elements = new T[maxSize];
	assert(elements); 
}

template <typename T>void SeqStack<T>::overflowProcess(){	//˽Óк¯Êý£ºÀ©³äÕ»µÄ´æ´¢¿Õ¼ä¡£
	T *newArray = new T[maxSize + stackIncreament];
	assert(newArray);
	for (int i = 0; i <= top; i++)
		newArray[i] = elements[i];
	maxSize = maxSize + stackIncreament;
	delete []elements;
	elements = newArray;
}


template <typename T>void SeqStack<T>::Push(const T &x){
	if (IsFull())	overflowProcess();
	elements[++top] = x;  // top++; elements[top] = x;
}


template <typename T>bool SeqStack<T>::Pop(T &x){
	if (IsEmpty()){
		return false;
	}
	x = elements[top--]; // x = elements[top]; top--;
	return true; 
}


template <typename T>bool SeqStack<T>::getTop(T &x)const{
	if (IsEmpty()){
		return false;
	}
	x = elements[top];
	return true;
}
数据结构笔记 数据结构 指针
上一篇: 【天勤第三章】栈和队列算法总结
下一篇: 第三章 栈和队列3.1栈3.2队列

继续阅读