（C语言）堆栈和队列实验

1.（1）：判断一个算术表达式中开括号和闭括号是否配对。

实现代码：

#include 
#include 
#define MAXSIZE 100
typedef struct{
	char data[MAXSIZE];
	int top;
}seqstack;
int MatchCheck(char str[]){
	seqstack s;
	int i = 0;
	s.top = -1;
	while (str[i] != ''){
		// 遇到开括号，入栈
		if (str[i] == '(' || str[i] == '[' || str[i] == '{'){
			s.data[++s.top] = str[i];
		}
		// 遇到闭括号，出栈 
		if (str[i] == ')'){
			if (s.data[s.top] == '(') s.top--;
			else return 0;
		}
		if (str[i] == ']'){ 
			if (s.data[s.top] == '[') s.top--;
			else return 0;
		}
		if (str[i] == '}'){
			if (s.data[s.top] == '{') s.top--;
			else return 0;
		}
		i++;
	}
	if (s.top >= 0) return 0;
	else return 1;
}
int main(){
	char str[20];
	int flag;
	printf("请输入一个算术表达式：n");
	gets(str);
	flag = MatchCheck(str);
	if (flag == 1){
		printf("该算术表达式中开括号和闭括号配对！n");
    }else{
		printf("该算术表达式中开括号和闭括号不配对！n");
	}
	return 0;
}

运行结果：

输入的算术表达式为9*{8+[7-(6+5)]}：

输入的算术表达式为9*{8+[7-(6+5)]：

输入的算术表达式为9*{8+[7-(6+5)]}}：

分析：

该程序中用于检查算术表达式中开括号和闭括号是否配对的函数的时间复杂度与空间复杂度均为线性阶O（n）。

（2）：测试“汉诺塔”问题。

这里先说明一下汉诺塔问题：

这里还要说明一点，递归程序执行中需借助栈这种数据结构来实现，递归调用过程其实就是一个进栈和出栈的过程。因此，此处汉诺塔的递归实现其实就是用栈来实现的。

实现代码：

#include 
void move(char x,char y){
     printf("将一个盘子从%c柱移动到%c柱。n",x,y);
}
void Hanoi(int n,char x,char y,char z){
	if (n == 1)
	    move(x,z);
	else{
		Hanoi(n-1,x,z,y);
		move(x,z);
		Hanoi(n-1,y,x,z); 
	}
}
int main(){
	int n;
    printf("请输入x柱上的盘子总数：");    
    scanf("%d",&n);
    printf("开始进行盘子的移动。n"); 
	Hanoi(n,'x','y','z');
	printf("盘子的移动完成。"); 
	return 0;
}

运行结果：

分析：

该程序中用于递归实现汉诺塔的函数的时间复杂度为指数阶O（2^n），空间复杂度为线性阶O（n）。

（3）：假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。

此处要说明一下，我在这里判断回文的方法是将字符序列中的字符逐个入栈以及入队列，然后利用栈后进先出和队列先进先出的性质逐个出栈以及出队列，判断是否相等，以此判断是否是回文。判断回文的方法有很多，此处是利用栈和队列来进行判断，不建议按我这种写法进行判断，有很多更好的方法可以用于进行判断，此处不具体给出。

实现代码：

#include 
#include 
#define MAXSIZE 100
typedef struct{
	char data[MAXSIZE];
	int top;
}seqstack;
typedef struct{
	char data[MAXSIZE];
	int front;
	int rear;
}sequeue;
void SetSeqstackNULL(seqstack *s){
	s->top = -1;
}
void Push(seqstack *s,char x){
	if (s->top == MAXSIZE-1){
		printf("栈上溢！n");
	}else{
	    s->data[++s->top] = x;
	}
} 
char Pop(seqstack *s){
	if (s->top < 0){
		printf("栈下溢！n");
		return 0; 
	}else{
	    return (s->data[s->top--]);
	}
}
void SetSequeueNULL(sequeue *q){
	q->front = 0;
	q->rear = 0;
}
void EnQueue(sequeue *q,char x){
	if (q->front == (q->rear + 1) % MAXSIZE){
 	    printf("队列满！n");	
	}else{
	    q->data[++q->rear] = x;
	}
}
char DeQueue(sequeue *q){
	if (q->rear == q->front){
	    printf("队列空！n");
	    return 0;
	}else{
	    return q->data[++q->front];	 
	}
}
void HuiWenJudge(seqstack *s,sequeue *q){
	while (s->top >= 0){
		// 栈后进先出，队列先进先出，利用此性质进行回文的判断 
		if (Pop(s) != DeQueue(q)){
			printf("该字符序列不是“回文”！");
			return; 
		}
	}
	printf("该字符序列是“回文”！");
}
int main(){
	seqstack *s = (seqstack *)malloc(sizeof(seqstack));
	sequeue *q = (sequeue *)malloc(sizeof(sequeue));
	SetSeqstackNULL(s);
	SetSequeueNULL(q);
	char ch;
	printf("请输入一个字符序列（以’@’为结束符）：n");
	while ((ch = getchar()) != '@'){
		Push(s,ch);
		EnQueue(q,ch);
	}
	HuiWenJudge(s,q);
	return 0;
}

运行结果：


分析：

该程序中用于进行回文判断的函数的时间复杂度为线性阶O（n），假设顺序栈s和顺序队列q中均存放了n个元素，则该函数的空间复杂度为O（n）。

2.在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。

实现代码：

#include 
#include 
#define MAXSIZE 100 
typedef struct{
	int data[MAXSIZE];
	int front;
	int rear;
}sequeue;
void SetNULL(sequeue *q){
	q->front = 0;
	q->rear = 0;
}
void EnQueue(sequeue *q,int x){
	int average;
	if((q->rear + 1) % MAXSIZE == q->front ){
		printf("队列满！n");
		return; 
	} 
	average = (q->data[q->rear] + q->data[(q->front + 1) % MAXSIZE]) / 2;
	if (x < average){
		q->data[q->front] = x;
		q->front = (q->front - 1) % MAXSIZE; 
	}else {
		q->rear = (q->rear + 1) % MAXSIZE; 
		q->data[q->rear] = x;
	}
}
void DeQueue(sequeue *q){
	if (q->front == q->rear){
		printf("队列空！n");
		return ; 
	}
	q->front = (q->front + 1) % MAXSIZE;
}
void PrintElem(sequeue *q){
	int i;
	for (i = q->front + 1;i <= q->rear;i++){
		printf("%d ",q->data[i]);
	}
}
int main(){
	sequeue *q = (sequeue *)malloc(sizeof(sequeue));
	int x,i;
	SetNULL(q);
    // 随便创建一个队列，用于测试入队和出队操作
	q->front = 2; 
	q->data[3] =  6;
	q->data[4] =  9;
	q->data[5] =  3;
	q->data[6] =  2;
	q->data[7] =  7;
	q->rear = 7;
	printf("当前队列中的所有元素值为：");
	PrintElem(q); 
	printf("n连续进行5次入队操作。");
    for (i = 0;i < 5;i++){
    	printf("n第%d次入队操作，请输入想要入队的元素值：",i + 1); 
		scanf("%d",&x);
    	EnQueue(q,x);
    	printf("当前队列中的所有元素值为：");
    	PrintElem(q);
	}
	printf("nn连续进行5次出队操作。");
    for (i = 0;i < 5;i++){
    	printf("n第%d次出队操作。n",i + 1); 
    	DeQueue(q);
    	printf("当前队列中的所有元素值为：");
    	PrintElem(q);
	} 
	return 0;
}

运行结果：

分析：

该程序中输出受限的双端循环队列的入队操作和出队操作的时间复杂度均为常数阶O（1），空间复杂度均为线性阶O（n）。