linkstack.cpp

这是一个本人刚接触数据结构时仿编的一个简单的程序,希望对大家有所帮助!

// LinkStack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "LinkStack.h"
#include "conio.h"
#include "stdlib.h"
#include "iostream.h"

Status LinkStack::InitStack()
			{//若已初始化则直接返回OK
			 if(top!=NULL) return OK;
			 top=(SNodePtr)malloc(sizeof(SNode));
			 if(!top) return OVERFLOW;
			 top->Next=NULL;
			
			 Length=0;
			 return OK;
			}
 Status LinkStack::GetTop(SElemType &e)
			{//若栈不空，用e返回栈顶元素，并返回OK；否则返回ERROR
			 //若栈没有初始化，返回ERROR
			 if(top==NULL) return ERROR;
			 //若栈为空则直接返回ERROR
			 if(top->Next) return ERROR;
			 e=top->Next->data;
			 return OK;
			}
 Status LinkStack::Push(SElemType e)
			{//插入新元素e,若栈未初始化，返回ERROR，若当前栈为空，令base指向新插入
			 //的节点
			 if(top==NULL) return ERROR;
			 SNodePtr s=(SNodePtr)malloc(sizeof(SNode));
			 s->data=e;
			 s->Next=top->Next;
			 if(!s) return OVERFLOW;
			 top->Next=s;			
			 Length++;
			 return OK;
			}
 Status LinkStack::Pop(SElemType &e)
			{//若栈不空，删除栈顶元素，用e返回其值，并返回OK；否则返回ERROR
			 //若栈没有初始化直接返回ERROR
			 if(top==NULL) return ERROR;
			 e=top->Next->data;
			 SNodePtr p=top->Next;
			 top->Next=p->Next;
			 free(p);
			 Length--;
			 return OK;
			}
 Status LinkStack::ClearStack()
			{
			 //若没有初始化，直返回ERROR
			 if(top==NULL) return ERROR;
			 //若栈为空直接返回OK
			 if(top->Next==NULL)
			  return OK;
			 SNodePtr p=top->Next,q;
			 q=p;
			 while(p)
			 {
			  p=p->Next;
			  free(q);
			  q=p;
			 }
			top->Next=NULL;
			Length=0;
			return OK;
		    }
 Status LinkStack::DestroyStack()
			{//若没有初始化直接返OK
			 if(top==NULL) return OK;
			 //调用ClearStack()清空栈，然后释放头结点
			 ClearStack();
			 free(top);
			 top=NULL;
			 Length=0;
			 return OK;
			}
 Status LinkStack::StackEmpty()
			{//若没有始化，返回ERROR
			 if(top==NULL) return TRUE;
			 else
			  return FALSE;
			}
 int  LinkStack::StackLength()
			{
			 return Length;
			}
 Status LinkStack::StackTraverse()
			{//若没有初始化，返回ERROR
			//麻烦就在这里，如果是双向链表还好，可单向的如果从头
		//到尾遍历，还容易，要是从尾到头遍历就要用双向链表，
	   //这里只好从头到尾遍历了。这也是后来才发现的
		 	 if(top==NULL) return ERROR;
			 if(top->Next==NULL) 
			   {
				cout<<"当前栈中没有任何元素。"<<endl;
				return OK;
			   }
			SNodePtr p=top->Next;
			
			while(p)
			 {
			  cout<<" "<<p->data;
			  p=p->Next;
			 }
			cout<<endl;
			return OK;
			}
 LinkStack::~LinkStack()
 {
	 if(top!=NULL)
		 DestroyStack();
	 top=NULL;
 }

void main(int argc, char* argv[])
{
 char select[2];
	LinkStack MyStack;
	
	 SElemType e;
    while(1)
	{
		system("cls");//执行清屏命令
		cout<<"   ====================链式存储结构的栈==================\n";
		cout<<"\t1、初始化\t2、清空\n";
		cout<<"\t3、进栈\t        4、出栈 \n";
		cout<<"\t5、判空\t        6、取长度\n";
		cout<<"\t7、遍历\t        8、销毁\n";
		cout<<"\t9、退出"<<endl;
		cout<<"  ===========================================================\n";

		cout<<"\t请选择(1~9):";
		cin>>select;
		int selected=atoi(select);
		switch(selected)
		{
		case 1:
			system("cls");//清屏
			MyStack.InitStack();
			cout<<"初始化成功!"<<endl;
	     	getch();
			break;
	
		case 2:
			system("cls");
			MyStack.ClearStack ();
			cout<<"栈已清空!"<<endl;
		 	getch();
			break;
		case 3:
			system("cls");
			cout<<"请输入您要压入的元素：";
			cin>>e;
			if(MyStack.Push(e)==OK)
				cout<<"压栈成功!"<<endl;
			else
				cout<<"压栈失败，栈未初始化或重新分配空间时失败！"<<endl;
		 	getch();
			break;
		case 4:
			system("cls");
			if(MyStack.Pop(e)==OK)
			 cout<<"从栈中退出的元素为："<<e<<endl;
			else
				cout<<"退栈失败，栈未初始化或栈已空。"<<endl;
		 	getch();
			break;
		case 5:
			system("cls");
			if(MyStack.StackEmpty ()==TRUE)
				cout<<"栈已空。"<<endl;
			else
				cout<<"栈非空。"<<endl;
	 		getch();
			break;
		case 6: 
			system("cls");
			cout<<"当前栈中有"<<MyStack.StackLength ()<<"个元素。" <<endl;
			getch();
			break;
		case 7:
			system("cls");
		 	if(MyStack.StackEmpty ()==TRUE)
				cout<<"当前栈为空栈："<<endl;
			else
				MyStack.StackTraverse();
		 	getch();
			break;
		case 8:
			system("cls");
			if(MyStack.DestroyStack()==OK)
				cout<<"栈已销毁。"<<endl;
			getch();
			break;
		case 9:
			exit(0);
			break;	
		default:
			cout<<"选择错误!请重新选择!"<<endl;
		}
	}
	return;

}