算法设计学习7

实验目的及要求：
目标是通过实验深入理解堆栈（Stack）和队列（Queue）这两种常见的数据结构，掌握它们的基本操作及应用场景，提高对数据结构的认识和应用能力。通过本实验，学生将深化对堆栈和队列等数据结构的理解，提高编程能力和问题解决能力，为进一步学习算法和数据结构打下基础。

实验设备环境：
1.微型计算机
2.DEV C++(或其他编译软件)

实验步骤：
任务一：
假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写个函数，用来判别表达式中的括号是否正确配对，并设计一个测试主函数。
[算法思想] 在算术表达式中，右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共有以下 4 种情况:左、右括号配对次序不正确;2 右括号多于左括号;3 左括号多于右括号;左、右括号匹配正确。具体方法如下。顺序扫描算术表达式(表现为一个字符串)，当遇到三种类型括号的左括号时，让该括号入栈。当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配，则出栈继续进行判断;若当前栈顶括号与当前扫描的括号不匹配，则左、右括号配对次序不正确;若字符串当前为某种类型右括号而堆栈已空，则右括号多于左括号;字符串循环扫描结束时，若堆栈非空(即堆栈中尚有某种类型左括号)，则说明左括号多于右括号:如果未出现上述三种情况，则说明左、右括号匹配正确。
代码如下：

#include<string.h>
#include<stdio.h>
#define MaxStackSize 100
typedef char DataType;
#include "SeqStack.h"
void ExpIsCorrect(char exp[],int n){SeqStack 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;}else if(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}'))&&!StackNotEmpty(myStack)){printf("右括号多余左括号！\n");return;}}if(StackNotEmpty(myStack))printf("左括号多于右括号！\n");elseprintf("左右括号匹配正确!\n");
}
int main(void){char a[]="(())abc[{)(]}";//定义字符串 char b[]="(()))abc{[]}";char c[]="(()()abc{[]}";char d[]="(())abc{[]}";int n1=strlen(a);//求字符串的长度 int n2=strlen(b);int n3=strlen(c);int n4=strlen(d);ExpIsCorrect(a,n1);ExpIsCorrect(b,n2);ExpIsCorrect(c,n3);ExpIsCorrect(d,n4);
}
头文件：
typedef struct{DataType stack[MaxStackSize];int top;
}SeqStack;
void StackInitiate(SeqStack*S){S->top=0;
}
int StackNotEmpty(SeqStack S){if(S.top<=0)return 0;elsereturn 1;
}
int StackPush(SeqStack*S,DataType x){if(S->top>=MaxStackSize){printf("堆栈已满无法插入！\n");return 0;}else{S->stack[S->top]=x;S->top++;return 1;}
}
int StackPop(SeqStack*S,DataType*d){if(S->top<=0){printf("堆栈已空无元素出栈！\n");return 0;}else{S->top--;*d=S->stack[S->top];return 1;}
}
int StackTop(SeqStack S,DataType*d){if(S.top<=0){printf("堆栈已空！\n");return 0;}else{*d=S.stack[S.top-1];return 1;}
}

任务二：
设有后缀表达式ABCD/-E*+，其中，变量A等于3，变量B等于6，变量C等于4，变量D等于2，变量E等于5，设计一个程序，求出该后缀表达式的值。
[算法思想] 定义了一个堆栈结构和相关的操作（初始化、入栈、出栈），然后使用堆栈来计算后缀表达式的值。在主函数中，定义了后缀表达式为"ABCD/-E*+"，并调用 evaluatePostfix 函数计算表达式的值。注意，这个程序中假设变量 A 等于 3，变量 B 等于 6，变量 C 等于 4，变量 D 等于 2，变量 E 等于 5。
代码如下：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<ctype.h>
typedef int DataType;
#include "LinStack.h"
int PostExp(char str[]){DataType x,x1,x2;int i;LSNode *head;StackInitiate(&head);for(i=0;str[i]!='#';i++){if(isdigit(str[i])){x=(int)(str[i]-48);StackPush(head,x);}else{StackPop(head,&x2);StackPop(head,&x1);switch(str[i]){case'+':{x1+=x2;break;}case'-':{x1-=x2;break;}case'*':{x1*=x2;break;}case'/':{if(x2==0.0){printf("除数为0错!\n");exit(0);}else{x1/=x2;break;}}}StackPush(head,x1);}}StackPop(head,&x);return x;
}
int main(void){char str[]="3642/-5*+#";int result;result=PostExp(str);printf("后缀表达式计算结果为：%d",result); 
}
头文件：
typedef struct snode{DataType data;struct snode*next;
}LSNode;
void StackInitiate(LSNode**head){*head=(LSNode*)malloc(sizeof(LSNode));(*head)->next=NULL;
}
int StackNOtEmpty(LSNode*head){if(head->next==NULL)return 0;else return 1;
}
void StackPush(LSNode*head,DataType x){LSNode*p;p=(LSNode *)malloc(sizeof(LSNode));p->data=x;p->next=head->next;head->next=p;
}
int StackPop(LSNode*head,DataType *d){LSNode*p=head->next;if(p==NULL){printf("堆栈已空出错！");return 0;}head->next=p->next;*d=p->data;free(p);return 1;
}
int StackTop(LSNode*head,DataType *d){LSNode*p=head->next;if(p==NULL){printf("堆栈已空出错！");return 0;}*d=p->data;return 1;
}
void Destroy(LSNode*head){LSNode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;free(p1);}
}

任务三 ：
链式队列设计。要求: 
(1)以带头结点的循环单链表实现，并只设尾指针，不设头指针。
(2) 编写实现这种链式队列的初始化、入队列、出队列、取元素、判断非空函数。
代码如下：

（1）

#include<stdio.h>
#include<malloc.h>
typedef int DataType;
#include"LinListO.h"                      
int QueueGet(SLNode *head,SLNode*rear,DataType*d){if(rear==NULL){printf("队列已空无元素出列表！\n");return 0;}else{*d=rear->next->data;return 1;}
}
int QueueDelete(SLNode *head,SLNode*rear,DataType*d){SLNode*p;if(rear==NULL){printf("队列已空无元素出列表！\n");return 0;}else{*d=rear->next->data;p=rear->next;rear->next=p->next;free(p);return 1;}
}
int main(void){SLNode *head,*rear;DataType d;int i,x;ListInitiate(&head);for(i=0;i<10;i++){ListInsert(head,i,i+1);}rear=head;while(rear->next!=head){rear=rear->next;}QueueDelete(head,rear,&d);for(i=0;i<10;i++){QueueGet(head,rear,&d);printf("%d  ",d);QueueDelete(head,rear,&d);}Destroy(&head);
}
头文件：
typedef struct Node{DataType data;struct Node *next;
}SLNode;
void ListInitiate(SLNode**head){*head=(SLNode *)malloc(sizeof(SLNode));(*head)->next=*head;
}
int ListLength(SLNode *head){SLNode *p=head;int size=0;while(p->next!=head){p=p->next;size++;}return size;
}
int ListInsert(SLNode *head,int i,DataType x){SLNode *p,*q;int j;p=head;j=-1;while(p->next!=head&&j<i-1){p=p->next;j++;}if(j!=i-1){printf("插入元素位置参数错！");return 0;}q=(SLNode *)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q;return 1;
}
int ListDelete(SLNode *head,int i,DataType *x){SLNode *p,*s;int j;p=head;j=-1;while(p->next!=head&&p->next->next!=head&&j<i-1){p=p->next;j++;}if(j!=i-1){printf("删除元素位置参数错！");return 0;}s=p->next;*x=s->data;p->next=p->next->next;free(s);return 1;
}
int ListGet(SLNode *head,int i,DataType *x){SLNode *p;int j;p=head;j=-1;while(p->next!=head&&j<i){p=p->next;j++;}if(j!=i){printf("取出元素位置参数错！");return 0;}*x=p->data;return 1;
}
void Destroy(SLNode **head){SLNode *p,*p1;p=*head;while(p!=NULL){p1=p;p=p->next;free(p1);}*head=NULL;
}

（2）

#include<stdio.h>
#include<malloc.h>
typedef int DataType;
#include"LQueue.h"
int main(void){LQueue Q;DataType d;QuenuInitiate(&Q);if(QueueNotEmpty(&Q)){//判断是否为空 printf("队列为空. \n");}else{printf("队列非空.\n");}for(int i=0;i<9;i++){QueueAppend(&Q,i+2);}//QueueDelete(&Q,&d);for(int i=0;i<9;i++){QueueGet(Q,&d);printf("%d \n",d);QueueDelete(&Q,&d);}Destroy(&Q);
}
头文件：
typedef struct qnode{DataType data;struct qnode*next;
}LQNode;
typedef struct{LQNode*rear;
}LQueue;
void QuenuInitiate(LQueue *Q){Q->rear=NULL;}
int QueueNotEmpty(LQueue *Q){if(Q->rear==NULL)return 1;elsereturn 0; 
}
void QueueAppend(LQueue*Q,DataType x){LQNode*p;p=(LQNode*)malloc(sizeof(LQNode));p->data=x;p->next=NULL;if(Q->rear==NULL){Q->rear=p;Q->rear->next=Q->rear;}else{p->next=Q->rear->next;Q->rear->next=p;Q->rear=p;}}
int QueueDelete(LQueue*Q,DataType*d){LQNode*p,*q;if(Q->rear==NULL){printf("队列已空无元素出列表！\n");return 0;}else{if(Q->rear->next==Q->rear){Q->rear=NULL; p=Q->rear;}else{*d=Q->rear->next->data;p=Q->rear->next;Q->rear->next=p->next;}free(p);return 1;}
}
int QueueGet(LQueue Q,DataType*d){LQNode*p;if(Q.rear==NULL){printf("队列已空无元素出列表！\n");return 0;}else{p=Q.rear->next;*d=p->data;return 1;}
}
void Destroy(LQueue*Q){LQNode*p,*p1;p=Q->rear->next;while(p!=NULL){p1=p;p=p->next;free(p1);}
}