实验四 堆栈的应用

实验四 堆栈的应用

一、实验目的:

1．掌握堆栈的存储方式和基本操作
2．掌握堆栈后进先出运算原则在解决实际问题中的应用

二、实验内容:

1.利用栈结构，编写程序将十进制数转换成N制数（N可以为2、4、8、16等）。

说明:十进制数值转换成二进制使用辗转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。十进制数值转换成八进制算法类似。转换算法要求用一个函数完成。

2.假设算术表达式中允许包含两种括号:圆括号和方括号，其嵌套的顺序随意，即（[][]）

或[（）]等为正确格式，而[(]或()))或 [())均为不正确的格式。请使用栈结构，写一算法检验某表达式中的括号是否匹配，并测试你的算法是否正确。测试表达式为:

(1)[(1+2)*3-1]+[((1+2]*3)-1]

(2) [(1+2)*3-1]+[(1+2)*3-1]

三、实验源代码

//4.c
#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;

typedef struct snode 
{
	ElemType data;
	struct snode *next;
} SingleLinkedNode;

void StackInitiate(SingleLinkedNode **head)
{
	if((*head=(SingleLinkedNode *)malloc(sizeof(SingleLinkedNode)))==NULL) exit(1);
	(*head)->next=NULL;
}

int StackPush(SingleLinkedNode *head, ElemType x)
{
	SingleLinkedNode *p;
	if((p=(SingleLinkedNode*)malloc(sizeof(SingleLinkedNode)))==NULL)
	{
		printf("内存空间不足无法插入！\n");
		return 0;
	}
	p->data=x;
	p->next=head->next;
	head->next=p;
	return 1;
}

int StackNotEmpty(SingleLinkedNode *head)
{
	if(head->next==NULL)
		return 0;
	else
		return 1;
}

int StackPop(SingleLinkedNode *head,ElemType *d)
{
	SingleLinkedNode *p=head->next;
	if(p==NULL)
	{
		printf("堆栈已空出错！\n");
		return 0; 
	}
	head->next=p->next;
	*d=p->data;
	free(p);
	return 1;
 } 

void conversion(ElemType decimal,int N) 
{
	SingleLinkedNode *myStack;
	StackInitiate(&myStack);
	while(decimal)
	{
		StackPush(myStack,decimal%N);
		decimal=decimal/N; 
	}
	while(StackNotEmpty(myStack))
	{
		StackPop(myStack,&decimal);
		printf("%d",decimal);
	}
}
 
void main()
{
	int decimal;
	printf("输入要转化的十进制数：");
	scanf("%d",&decimal);
	int N;
	printf("转化成N制数（输入N）：");
	scanf("%d",&N); 
	printf("转化结果为："); 
	conversion(decimal,N);
}

//4_2.c
#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;

typedef struct snode 
{
	ElemType data;
	struct snode *next;
} SingleLinkedNode;

void StackInitiate(SingleLinkedNode **head)
{
	if((*head=(SingleLinkedNode *)malloc(sizeof(SingleLinkedNode)))==NULL) exit(1);
	(*head)->next=NULL;
}

int StackPush(SingleLinkedNode *head, ElemType x)
{
	SingleLinkedNode *p;
	if((p=(SingleLinkedNode*)malloc(sizeof(SingleLinkedNode)))==NULL)
	{
		printf("内存空间不足无法插入！");
		return 0; 
	}
	p->data = x;
	p->next = head->next;
	head->next = p;
	return 1;
} 

int StackNotEmpty(SingleLinkedNode *head)
{
	return head->next != NULL;
}

int StackTop(SingleLinkedNode *head, ElemType *d)
{
	SingleLinkedNode *p = head->next;
	if(p == NULL)
	{
		printf("堆栈已空出错！");
		return 0;
	}
	*d = p->data ;
	return 1;
}

int StackPop(SingleLinkedNode *head, ElemType *d)
{
	SingleLinkedNode *p = head->next;
	if(p == NULL)
	{
		printf("堆栈已空出错！");
		return 0;
	}
	head->next = p->next;
	*d = p->data;
	free(p);
	return 1;
}

void ExplsCorrect(char exp[],int n)
{
	SingleLinkedNode *myStack;
	int i;
	char c;
	StackInitiate(&myStack);
	for(i=0;i<n;i++)
	{
		if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))
		{
			StackPush(myStack,exp[i]);
		}
		else if((exp[i]==')')&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c=='(')
		{
			StackPop(myStack,&c);
		}
		else if((exp[i]==')')&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c!='(')
		{
			printf("左右括号配对次序不正确！\n");
			return;
		}
		else if((exp[i]==']')&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c=='[')
		{
			StackPop(myStack,&c);
		}
		else if((exp[i]==']')&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c!='[')
		{
			printf("左右括号配对次序不正确！\n");
			return;
		}
		else if((exp[i]=='}')&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c=='{')
		{
			StackPop(myStack,&c);
	
		}
		else if((exp[i]=='}')&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c!='{')
		{
			printf("左右括号配对次序不正确！\n");
			return;
		}
	}
	if(i==n)
	{
		printf("左右括号配对次序正确！\n");
	}
}

int main()
{
	printf("\n请输入你要检验的表达式：");
	char exp[80];
	int i;
	for(i=0;;i++)
	{
		exp[i]=getchar();
		if(exp[i]=='\n')
			break;
	}
	int n;
	n=i;
	ExplsCorrect(exp,n);
	return 0;
}
 

四、实验结果

五、实验心得
1、实验过程中报错：incompatible type for argument 1 of函数名，但凡出现error: incompatible type for argument 1 of ‘函数名’，几乎都是该函数的参数类型不匹配导致的。例如两个.c文件中都定义了SingleLinkedNode类型的指针myStack，在调用StackInitiate函数时形式参数是双指针，所以实际参数要加&，在调用StackNotEmpty、StackPop、StackPush、StackTop函数时，形式参数是指针，所以实际参数不用加&。