（1）栈的定义、基本操作的实现，以及典型应用 ①编程实现顺序栈/链栈的基本操作（如：栈的初始化、判断栈空、求栈的长度、取栈顶、入栈、出栈等），并设计菜单调用。（必做） ②利用栈结构，实现将任意的十进制整数N转成r（2≤r≤16）进制并输出。（选做） ③利用栈结构，对键盘输入任意字符串，判断其中的括号是否匹配。（选做） ④编写算法对键盘输入的整数序列a1 a2 …an进行如下操作：当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈(1≤i≤n)。(习题2.3，P85)（选做） ⑤编程实现汉诺塔问题的递归求解，并分析hanio(3,'A','B','C')的执行过程，以及结果分析。（选做） 注：选做题②~⑤中，至少选做1题。 （2）队列的定义、基本操作的实现 编程实现循环队列/链队列的基本操作（如：初始化空队列、判断队空、求队列的长度、取队首、入队列、出队列等），并设计菜单调用。（必做） |
1. 栈的定义、基本操作的实现，以及典型应用
（1）编程实现顺序栈的基本操作
核心代码：
①comdef.h
#include <stdio.h>
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
②spstackdef.H
#define MAXSIZE 100
typedef int SElemType;
typedef struct{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//栈可用的最大容量
}SqStack;
③spstackapp.H
//栈的初始化
Status InitStack(SqStack &S)
{
//构造一个空栈
S.base=new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base)//存储分配失败
exit (OVERFLOW);
S.top=S.base;//top初始为base,空栈
S.stacksize=MAXSIZE;
return OK;
}
//判断栈空
Status StackElemType(SqStack S)
{
return (S.base==S.top);
}
//求栈的长度
int StackLength(SqStack S)
{
return S.top-S.base;
}
//取栈顶
SElemType GetTop(SqStack S)
{
if(S.top!=S.base)
return *(S.top-1);
}
//出栈
Status Pop(SqStack &S,SElemType &e)
{
//删除栈顶元素，用e返回其值
if(S.top==S.base)
return ERROR;
else
{
e=*--S.top;
return OK;
}
}
//入栈
Status Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)//栈满
return ERROR;
else
{
*S.top++=e; //元素e压入栈顶，栈顶指针加一
return OK;
}
}
//输出栈
void StackTraverse(SqStack S)
{
SElemType *p=S.top-1;
while(p>=S.base)
{
cout<<"\n "<<*p;
p--;
}
}
//清空栈
void ClearStack(SqStack &S)
{
S.base=S.top;
}
//栈的销毁
bool DestroyStack(SqStack &S)
{
delete []S.base;
S.base=NULL;
S.top=NULL;
S.stacksize=0;
return true;
}
④main.CPP
#include "comdef.h"
#include "sqstackdef.h"
#include "sqstackapp.h"
int main(){
SqStack S;
SElemType e;
int choice,n,i;
cout<<"\n建立顺序栈：";
if (InitStack(S)==OVERFLOW){
cout<<"顺序栈空间分配失败,程序退出！";
return 0;
}
else{
cout<<"\n数据个数=";
cin>>n;
cout<<"\n输入"<<n<<"个数据: ";
for(int j=0;j<n;j++)
{
cin>>i;
Push(S,i);
}
cout<<"顺序栈建立成功，顺序栈为：";
StackTraverse(S);
}
do {
cout<<"\n\n===================================";
cout<<"\n 顺序栈的基本操作 ";
cout<<"\n===================================";
cout<<"\n 1:判断栈空" ;
cout<<"\n 2:求栈的长度" ;
cout<<"\n 3:取栈顶" ;
cout<<"\n 4:出栈" ;
cout<<"\n 5:入栈" ;
cout<<"\n 6:输出栈" ;
cout<<"\n 7:清空栈" ;
cout<<"\n 0:操作结束" ;
cout<<"\n===================================";
cout<<"\n请输入你的选择:";
cin>>choice;
switch (choice)
{
case 1: if(StackElemType(S))
cout<<"\n数据表为空表";
else
cout<<"\n数据表为非空表";
break;
case 2: cout<<"\n数据栈的长度为："<<StackLength(S);
break;
case 3: if(StackElemType(S))
cout<<"\n栈为空，栈顶元素不存在！";
else
{
cout<<"\n栈顶元素为："<<GetTop(S);
}
break;
case 4: if(!Pop(S,e))
{
cout<<"\n栈为空，栈顶元素不存在！";
}
else
{
cout<<"\n栈顶出栈成功！"<<"\n出栈后的栈为：";
StackTraverse(S);
}
break;
case 5: cout<<"入栈元素为：";
cin>>e;
Push(S,e);
cout<<"\n入栈成功！"<<"\n入栈后的栈为：";
StackTraverse(S);
break;
case 6: cout<<"顺序栈为：";
StackTraverse(S);
break;
case 7: ClearStack(S);
cout<<"成功清空！"<<"\n栈中无元素：";
StackTraverse(S);
break;
case 0: break;
default:cout<<"\n输入错误,重新输入！";
}
} while (choice) ;
DestroyStack(S);
return 0;
}
2. 队列的定义、基本操作的实现
编程实现循环队列的基本操作
核心代码：
- comdef.h
- #include <stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
- SqQueuedef.h
-
typedef int QElemType;
//队列的顺序存储结构
#define MAXQSIZE 100
typedef struct {
QElemType *base; //存储空间的基地址
int front; //头指针
int rear; //尾指针
}SqQueue;
- SqQueueapp.h
-
//初始化空队列
Status InitQueue(SqQueue &Q)
{
//构造空队列
Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间
if(!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0; //头指针和尾指针置空，队列为空
return OK;
}
//打印队列
void OutputQueue(SqQueue Q,int n)
{
if(Q.front==Q.rear) cout<<"队列为空";
while(Q.front!=Q.rear)
{
cout<<Q.base[Q.front]<<" ";
Q.front=(Q.front+1)%(n+1);
}
}
//判断队空
Status QueueEmpty(SqQueue Q)
{
return (Q.front==Q.rear);
}//求队列的长度
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}//取队首
Status GetHead(SqQueue Q,QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front]; //返回队头元素的值，队头元素不变
return OK;
}//出队列
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front]; //保存队头元素
Q.front=(Q.front+1)%MAXQSIZE; //队头指针加一
return OK;
}//入队列
Status EnQueue(SqQueue &Q,QElemType e)
{
//插入e为新的队尾元素
if((Q.rear+1)%MAXQSIZE==Q.front)
//尾指针在循环意义上加一，表明存储空间已满
return ERROR;
Q.base[Q.rear]=e; //新元素为队尾
Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加一
return OK;
}//队列的销毁
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
Q.base=NULL;
Q.front=Q.rear=0;
return OK;
}
- main.CPP
-
#include "comdef.h"
#include "SqQueuedef.h"
#include "SqQueueapp.h"
int main(){
SqQueue Q;
QElemType e;
int choice,n,i;
cout<<"\n建立循环队列：";
if (InitQueue(Q)==OVERFLOW){
cout<<"队列空间分配失败,程序退出！";
return 0;
}
else{
cout<<"\n元素个数=";
cin>>n;
cout<<"\n输入"<<n<<"个队列元素: ";
for(int j=0;j<n;j++)
{
cin>>i;
EnQueue(Q,i);
}
cout<<"顺序队列建立成功，队列为：";
OutputQueue(Q,n);
}
do {
cout<<"\n\n===================================";
cout<<"\n 循环队列的基本操作 ";
cout<<"\n===================================";
cout<<"\n 1:判断队列空" ;
cout<<"\n 2:求队列的长度" ;
cout<<"\n 3:取队首" ;
cout<<"\n 4:出队列" ;
cout<<"\n 5:入队列" ;
cout<<"\n 6:打印队列" ;
cout<<"\n 0:操作结束" ;
cout<<"\n===================================";
cout<<"\n请输入你的选择:";
cin>>choice;
switch (choice){
case 1: if(!QueueEmpty)
cout<<"此队列为空队列！";
else
cout<<"此队列非空！";
break;
case 2: cout<<"此队列的长度为"<<QueueLength(Q);
break;
case 3: GetHead(Q,e);
cout<<"队首为："<<e;
break;
case 4: DeQueue(Q,e);
cout<<"出队列的元素为："<<e<<"\n当前队列为：";
OutputQueue(Q,n);
break;
case 5: cout<<"需要入队列的元素为：";
cin>>e;
EnQueue(Q,e);
cout<<"\n当前队列为：";
OutputQueue(Q,n+1);
break;
case 6:
cout<<"\n队列为：";
OutputQueue(Q,n);
break;
case 0: break;
default:cout<<"\n输入错误,重新输入！";
}
} while (choice) ;
DestoryQueue(Q);
return 0;
}