文章目录
1. 相关结构体定义
1.1 顺序栈
typedef struct{
int data[maxSize]; //存放栈中元素
int top; //栈顶指针
}SqlStack; //顺序栈类型定义
1.2 链栈结点定义
typedef struct LNode{
int data; //数据域
struct LNode *next; //指针域
}LNode; //链栈结点定义
1.3 顺序队列
typedef struct{
int data[maxSize];
int front; //队首指针
int rear; //队尾指针
}SqQueue; //顺序队列类型定义
1.4 链队定义
/**
队列头结点定义
*/
typedef struct QNode{
int data; //数据域
struct QNode *next; //指针域
}QNode; //队结点类型定义
/**
链队类型定义
*/
typedef struct{
QNode *front; //队头指针
QNode *rear; //队尾指针
}LiQueue; //链队类型定义
2. 顺序栈相关操作
- 初始化栈空
void initStack(SqStack &St){
st.top=-1; //只需要将栈顶指针设置为1
}
- 判断栈空
/**
栈空返回1,否则返回0
*/
int isEmpty(SqStack st){
if(st.top==-1)
return 1;
else
return 0;
}
- 进栈
int push(SqStack &st,int x){
if(s.top==maxSize-1) //栈满
return 0;
++(st.top); //先移动指针,再进栈
st.data[st.top]=x;
return 1;
}
- 出栈
int pop(SqStack &st,int &x){
if(st.top==-1) //栈空,不能出栈
return 0;
x=st.data[s.top]; //先取出元素,再移动指针
--(s.top);
return 1;
}
但试题中一般以以下形式居多:
int stack[maxSize]; int top; //即完成栈的定义及初始化
stack[++top]=x; //元素进栈
x=stack[top--]; //元素出栈
3. 链栈相关操作
- 链栈初始化
void initStack(LNode *&lst){
lst=(LNode*)malloc(sizeof(LNode)); //制造一个头结点
lst->next=NULL;
}
- 判断栈空
int isEmpty(LNode *lst){
if(lst->next==NULL)
return 1;
else
return 0;
}
- 进栈
void push(LNode *lst,int x){
LNode *p;
p=(LNode*)malloc(sizeof(LNode)); //为进栈元素申请结点空间
p->next=NULL; //指针域设为NULL
/*链表的头插法*/
p->data=x;
p->next=lst->next;
lst->next=p;
}
- 出栈
int pop(LNode *lst,int &x){
LNode *p;
if(lst->next==NULL)
return 0;
/*单链表的删除*/
p=lst->next;
x=p->data;
lst->next=p->next;
free(p);
return 1;
}
4. 顺序栈的应用
1. 判断一个表达式中的括号是否正确配对
/**
表达式存放在expr[]中,字符个数为n
*/
int match(char expr[],int n){
char stack[maxSize];int top=-1;
for(int i=0;i<n;i++){
if(expr[i]=='(') //遇到(入栈,
stack[++top]='(';
if(expr[i]==')'){
if(top==-1)
return 0;
else //栈不空,则出栈,
--top;
}
}
if(top==-1) //栈空,匹配
return 1;
else
return 0;
}
2. 编写一个求后缀式的数值的函数
/**
后缀式存储在expr中,最后一个字符为"\0",作为结束符,后缀式中数字只有一位
*/
int op(int a,char opt,int b){
if(opt=='+') return a+b;
if(opt=='-') return a-b;
if(opt=='*') return a*b;
if(opt=='/') {
if(b==0){
return 0;
}
else
return a/b;
}
}
int com(char expr[]){
int stack[maxSize];int top=-1;
int a,b,c;
char opt;
for(int i=0;expr[i]!='\0';i++){
if(expr[i]>='0'&&expr[i]<='9')
stack[++top]=expr[i]-'0';
else{
opt=expr[i]; //取运算符
b=stack[top--]; //取第二个操作数
a=stack[top--]; //取第一个操作数
c=op(a,opt,b);
stack[++top]=c; //运算结果入栈
}
}
return stack[top];
}
5. 顺序队
5.1 循环队列
两个状态:
队空状态:qu.rear== qu.front
队满状态:(qu.rear+1)%maxSize==qu.front
两个操作:
入队:
qu.rear=(qu.rear+1)%maxSize; qu.data[qu.rear]=x;
出队:
qu.front=(qu.front+1)%maxSize; x=qu.data[qu.front];
- 初始化队列
void initQueue(SqQueue &qu){
qu.front=qu.rear; //队首和队尾指针重合,并且指向0
}
- 判断队空
int isEmpty(SqQueue qu){
if(qu.front==qu.rear)
return 1;
else
return 0;
}
- 进队
int enQueue(SqQueue &qu,int x){
if((qu.rear+1)%maxSize==qu.front) //队满
return 0;
qu.rear=(qu.rear+1)%maxSize; //队未满,先移动指针
qu.data[qu.rear]=x; //再存入元素
return 1;
}
- 出队
int Dequeue(Squeue &qu,int &x){
if(qu.front==qu.rear) //队空,不能出队
return 0;
qu.front=(qu.front+1)%maxSize;
x=qu.data[qu.front]; //取出元素
return 1;
}
5.2 链队
-
两个状态
队空:
lqu->rear== NULL或者lqu->front== NULL
-
两个操作
进队:
lqu->rear->next=p;lqu->rear=p;
出队:
p=lqu->front;lqu->front=p->next;x=p->data;free(p);
- 初始化队列
void initQueue(LiQueue *&lqu){
lqu=(LiQueue*)malloc(sizeof(LiQueue));
lqu->front=lqu->rear=NULL;
}
- 判断队空
int isEmpty(LiQueue *lqu){
if(lqu->rear==NULL||lqu->front==NULL)
return 1;
else
return 0;
}
- 入队
void enQueue(LiQueue *lqu,int x){
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
p->data=x;
p->next=NULL;
if(lqu->rear==NULL) //队列空,则新结点是队首结点,也是队尾结点
lqu->front=lqu->rear=p;
else
lqu->rear->next=p; //将新结点链接到队尾,rear指向它
lqu->rear=p;
}
- 出队
int deQueue(LiQueue *lqu,int &x){
QNode *p;
if(lqu->rear==NULL)
return 0;
else
p=lqu->front;
if(lqu->front==lqu->rear) //队列中只有一个结点时
lqu->front=lqu->rear=NULL;
else
lqu->front=lqu->front->next;
x=p->data;
free(p);
return 1;
}
版权声明:本文为weixin_38339025原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。