数据结构实验三

发布于 2024-09-30  413 次阅读

3-1

#include <iostream>
using namespace std;

#define MAXSIZE 100
typedef int ElemType;

typedef struct STACK{
	//======补充代码======
	ElemType *base;
	ElemType *top;
	int  size;
}SqStack;

//函数声明
int InitStack(SqStack &s);
void ClearStack(SqStack &S);
int StackEmpty(SqStack S);
int StackLength(SqStack S);
int GetTop(SqStack s,ElemType &e);
int Push(SqStack &s,ElemType e);
int Pop(SqStack &s,ElemType &e);
void PrintElem(SqStack S);

//初始化,创建空栈
int InitStack(SqStack &s)
{
	//======补充代码======
	s.base = new ElemType[MAXSIZE];
	//	s.base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
	if (!s.base) return 0;
	s.top = s.base;
	s.size = MAXSIZE;
	return 1;     
}

//清空栈
void ClearStack(SqStack &S)
{
	//======补充代码======
	S.top = S.base;
}

//判栈空
int StackEmpty(SqStack S)
{
	//======补充代码======
	return S.top == S.base;
}

//求栈中元素个数
int StackLength(SqStack S)
{
	//======补充代码======
  	return S.top - S.base;
}

//获取栈顶元素值
int GetTop(SqStack s,ElemType &e)
{
	//======补充代码======
	if (s.top = s.base) return 0;
	e = *(s.top - 1);
	return 1;	
}

//入栈
int Push(SqStack &s,ElemType e)
{
	//======补充代码======
	if (s.top - s.base >= s.size) return 0;
	*s.top = e;
	s.top ++;
    return 1;
}

//出栈
int Pop(SqStack &s,ElemType &e)
{
	//======补充代码======
	if (s.top - s.base == 0) return 0;
	s.top --;
	e = *(s.top - 1); 
	// e = *s.top;
	return  1;
}

//打印栈中元素
void PrintElem(SqStack S)
{
	ElemType *p = S.base;
	while(p<S.top)
	{
		cout<<*p<<" ";
		p++;
	}
}

//主函数
int main(){
	ElemType e;
	SqStack S; 
	int i,n,m;
	InitStack(S);
	cin>>n;//请输入要入栈的元素个数 
	for(i=0;i<n;i++)
	{
		cin>>e;	
		Push(S,e);//入栈 
	}
	PrintElem(S);//输出栈中元素 
	cout<<endl;

	cin>>m;//请输入要出栈的元素个数 
	for(i=0;i<m;i++)
	{
	   Pop(S,e);//出栈 
	}
	GetTop(S,e);//输出栈顶元素 
	cout<<e<<" "<<StackLength(S)<<endl;
	return 0;
}

3-2

#include <iostream>
using namespace std;

#define MAXSIZE 100
typedef int ElemType;

typedef struct STACK{
	//======补充代码======
	ElemType *base;
	ElemType *top;
	int size;
}SqStack;

//函数声明
int InitStack(SqStack &s);
void ClearStack(SqStack &S);
int StackEmpty(SqStack S);
int StackLength(SqStack S);
int GetTop(SqStack s,ElemType &e);
int Push(SqStack &s,ElemType e);
int Pop(SqStack &s,ElemType &e);
void PrintElem(SqStack S);

//初始化,创建空栈
int InitStack(SqStack &s)
{
	//======补充代码======
	s.base = new ElemType[MAXSIZE];
	//	s.base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
	s.top = s.base;
	s.size = MAXSIZE;
	return 1;     
}

//清空栈
void ClearStack(SqStack &S)
{
	//======补充代码======
	S.top = S.base;
}

//判栈空
int StackEmpty(SqStack S)
{
	//======补充代码======
	return S.top - S.base;
}

//求栈中元素个数
int StackLength(SqStack S)
{
	//======补充代码======
  	return S.top - S.base;
}

//获取栈顶元素值
int GetTop(SqStack s,ElemType &e)
{
	//======补充代码======
	if (s.top - s.base == 0) return 0;
	e = *s.top;
	return 1;	
}

//入栈
int Push(SqStack &s,ElemType e)
{
	//======补充代码======
	if (s.top - s.base >= s.size) return 0;
	*s.top = e;
	s.top ++; 
    return 1;
}

//出栈
int Pop(SqStack &s,ElemType &e)
{
	//======补充代码======
	if (s.top == s.base) return 0;
	s.top --;
	e = *s.top;
	return  1;
}

//打印栈中元素
void PrintElem(SqStack S)
{
	ElemType *p = S.base;
	while(p<S.top)
	{
		cout<<*p<<" ";
		p++;
	}
}

//数制转换函数
void conversion()
{
	ElemType e;
	SqStack S;
	InitStack(S);
	int n,R;
	cin>>n>>R;
	//======补充代码======
	while(n){
		e = n % R;
		Push(S, e);
		n = n / R;
	}
	while(StackEmpty(S)){
		Pop(S, e);
		if (e >= 10) {
			cout << char('A' + e - 10);
		}
		else {
			cout << e;
		}
	}
}

//主函数
int main()
{
	conversion();
	return 0;
}

3-3

#include <iostream>
using namespace std;

typedef struct {
	int* base;	//栈空间基址
	int size;	//栈空间大小
	int top1, top2;//top1表示栈1栈顶元素的下一个位置序号，top2表示栈2栈顶元素的下一个位置序号
}DuStack;

//构造一个Size大小的双端空栈
int InitStack(DuStack& S, int Size) { 
	S.base = new int[Size];
	if (!S.base)	
		return 0;
	S.size = Size;
	S.top1 = 0;//栈1为空
	//======补充代码======
	S.top2 = Size - 1;
	//======补充代码======
	return 1;
}

//dir为1表示元素e进入栈1；dir为2表示元素e进入栈2
int Push(DuStack& S, int e, int dir) {
	if (S.top1>S.top2)
		return 0;
	if (dir == 1)
		S.base[S.top1++] = e;
	//======补充代码======
	else if (dir == 2)
		S.base[S.top2--] = e;
	//======补充代码======
	return 1;
}
int Pop(DuStack& S, int& e, int dir) {
	//======补充代码======
	if (dir == 1) {
		if (S.top1 == 0)
			return 0;
		else
			e = S.base[--S.top1];
	}
	//======补充代码======
	else if (dir == 2) {
		if (S.top2 == S.size-1)
			return 0;
		else
			e = S.base[++S.top2];
	}
	return 1;
}
int main(){
	DuStack s;
	int size,n,data,dir,i,PushPop;
	cin >> size >>n;
	InitStack(s, size);
	for (i = 0; i < n; i++) {
		cin >> PushPop;
		if (PushPop == 1) {
			cin >> dir >> data;
			if(Push(s, data, dir)==0)
				cout << "Push Overflow" << endl;
		}
		//======补充代码======
		else if (PushPop == -1) {
			cin >> dir;
			if (Pop(s, data, dir))
				cout << data << endl;
			else
				cout << "Pop Empty" << endl;
		}
		//======补充代码======
	}	
	return 1;
}