数据结构c语言版第二版(严蔚敏)第三章笔记

目录

栈

顺序栈 

存储结构

InitSqStack(SqStack &S);

DestorySqStack(SqStack &S);

StackEmpty(SqStack &S);

StackLength(SqStack &S);

GetTop(SqStack &S);

Push(SqStack &S);

Pop(SqStack &S);

StackTraverse(SqStack &S);

链式栈 

存储结构

InitSqStack(SqStack &S);

DestorySqStack(SqStack &S);

StackEmpty(SqStack &S);

StackLength(SqStack &S);

GetTop(SqStack &S);

Push(SqStack &S);

Pop(SqStack &S);

StackTraverse(SqStack &S);

---

栈

栈是一种限定仅仅在表尾进行插入或者删除 *** 作的线性表，因此对于栈来说，表尾端拥有着特殊的含义，称为栈顶，相应的，表头称为栈底，不含任何元素的栈称为空栈，栈中元素的特点是后进先出，可以理解为打q时的子d，装在d夹里的子d总是后填入的先射出

顺序栈 

基于顺序存储结构实现栈

存储结构

此段中的Elemtype为int

typedef struct
{
	int *base;
	int *top;
	int stacksize;
}SqStack;

InitSqStack(SqStack &S);

void InitSqStack(SqStack &S)
{
	S.base = new int[MAXSIZE];
	if(!S.base)
	{
		printf("栈动态开辟内存 *** 作失败\n");
		return; 
	}
	S.top = S.base;
	S.stacksize = MAXSIZE;
}

DestorySqStack(SqStack &S);

void DestoryStack(SqStack &S)
{
	delete S.base;
	S.stacksize = 0;
	S.base = S.top = NULL;
}

StackEmpty(SqStack &S);

bool StackEmpty(SqStack &S)
{
	if(S.base == S.top)return true;
	else return false;
}

StackLength(SqStack &S);

int StackLength(SqStack &S)
{
	return (S.top - S.base);
}

GetTop(SqStack &S);

int GetTop(SqStack &S)
{
	if(S.top != S.base)return *(S.top - 1);
	else 
	{
		printf("栈为空，取栈顶元素失败\n");
		return -1; 
	}
}

Push(SqStack &S,int e);

void Push(SqStack &S,int e)
{
	if(S.top - S.base == S.stacksize)
	{
		printf("栈已满，无法推入新的元素\n");
		return;
	}
	*S.top = e;
	S.top ++ ;
}

Pop(SqStack &S,int &e);

void Pop(SqStack &S,int &e)
{
	if(S.base == S.top)
	{
		printf("删除失败，栈已制空\n");
		return;
	}
	-- S.top;
	e = *S.top;
}

StackTraverse(SqStack &S);

void Print(SqStack &S)
{
	int *p = S.top - 1;
	while(p >= S.base)
	{
		cout << *p << endl;
		p -- ;
	}
}

链式栈 

基于链式存储结构实现栈

存储结构

typedef struct StackLNode
{
	int data;
	struct StackLNode *next;
}StackLNode,*LinkStack;

InitSqStack(SqStack &S);

void InitLinkStack(LinkStack &S)
{
	S = NULL; 
} 

DestorySqStack(SqStack &S);

void DestoryStack(LinkStack &S)
{
	StackLNode *p = S;
	ClearStack(S);
	delete p;
}

StackEmpty(SqStack &S);

bool StackEmpty(LinkStack &S)
{
	if(S == NULL)return true;
	else return false;
}

StackLength(SqStack &S);

int StackLength(LinkStack &S)
{
	int j = 0;
	StackLNode *p = S;
	while(p)
	{
		j ++ ;
		p = p -> next;
	}
	return j;
}

GetTop(SqStack &S);

int GetTop(LinkStack &S)
{
	if(S != NULL)return S -> data;
	else 
	{
		printf("该栈为空，取栈顶元素失败\n");
		return -1; 
	}
}

Push(SqStack &S,int e);

void Push(LinkStack &S,int e)
{
	StackLNode *p = new StackLNode;
	p -> data = e;
	p -> next = S;
	S = p;
}

Pop(SqStack &S,int &e);

void Pop(LinkStack &S,int &e)
{
	if(S == NULL)
	{
		printf("该栈为空，出栈失败\n");
		return;
	}
	e = S -> data;
	StackLNode *p = S;
	S = S -> next;
	delete p;
}

StackTraverse(SqStack &S);

void StackTraverse(LinkStack &S)
{
	if(S == NULL)
	{
		printf("该栈为空\n");
		return;
	}
	StackLNode *p = S;
	while(p)
	{
		cout << p -> data << ' ';
		p = p -> next;
	}
}