文章详情

randy
2022-06-14
2302
原创

数据结构之栈和队列

  • 顺序栈的创建和访问
  • 链栈的创建和访问
  • 循环队列的创建和访问
  • 链队的创建和访问

代码如下

#include <iostream>
#include<stdlib.h>
#define maxSize 100 
typedef struct {//顺序栈定义 
	int data[maxSize];
	int top;
}SqStack; 

typedef struct StNode{//链栈定义 
	int data;
	struct StNode *next;
}StNode;  

typedef struct{//顺序队列定义 
	int data[maxSize];
	int front;
	int rear;
}SqQueue;

typedef struct QNode{//链队结点 
	int data;
	struct QNode *next;
}QNode;

typedef struct {//链队头尾指针结点 
	struct QNode *front;
	struct QNode *rear;
}LiQueue;

void createStack1(SqStack *&s,int arr[],int n){//顺序栈的创建(入栈)
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top=-1;//初始化栈顶指针
	for(int i=0;i<n;i++){//进栈 
		s->top++;//先移指针,再赋值(当top初始值为-1时) 
		s->data[s->top]=arr[i];
	} 
} 

void createStack2(StNode *&s,int arr[],int n){//链栈的创建(入栈)
	s=(StNode *)malloc(sizeof(StNode));
	s->next=NULL;
	StNode *p;
	for(int i=0;i<n;i++){//链栈其实就是只能头插法创建的链表 
		p=(StNode *)malloc(sizeof(StNode));
		p->data=arr[i];
		p->next=s->next;
		s->next=p;
	}
}

void printSt(StNode *p){//链栈的访问(出栈)
	StNode *r;
	r=p->next;
	while(r!=NULL){
		printf("%d ",r->data);
		r=r->next;
	}
	printf("\n");
} 
void printStack(SqStack *s){//顺序栈访问(出栈)
	while(s->top!=-1){//出栈 
		printf("%d ",s->data[s->top]);//先访问数据域
		s->top--;//再移动指针 
	}
	printf("\n");
} 

void createSqQueue(SqQueue *&p,int arr[],int n){//循环队列的创建(入队) 
	p=(SqQueue *)malloc(sizeof(SqQueue));
	p->front=p->rear=0;
	for(int i=0;i<n;i++){
		p->rear=(p->rear+1)%maxSize;//先动指针
		p->data[p->rear]=arr[i];//入队 
	}
} 

void createQNode(LiQueue *&l,int arr[],int n){//链队的创建(入队)
	QNode *r,*s,*p;
	l=(LiQueue *)malloc(sizeof(LiQueue));
	l->front=l->rear=NULL;
	p=(QNode *)malloc(sizeof(QNode));
	p->next=NULL;
	r=p;
	for(int i=0;i<n;i++){
		s=(QNode *)malloc(sizeof(QNode));
		s->data=arr[i];
		r->next=s;
		l->rear=s;//入队 
		r=s;
	}
	r->next=NULL;
	l->front=p->next;
}

void visitLiQue(LiQueue *l){//链队的访问(出队)
	QNode *p;
	while(l->front!=NULL){//出队 
		p=l->front;
		printf("%d ",p->data);
		l->front=p->next;
	}
	printf("\n");
}
void visitSq(SqQueue *p){//循环队列的访问(出队) 
	while(p->front!=p->rear){
		p->front=(p->front+1)%maxSize;
		int data=p->data[p->front];
		printf("%d ",data);
	}
	printf("\n"); 
} 
int main(int argc, char** argv) {
	SqStack *s;
	StNode *p;
	SqQueue *q; 
	LiQueue *l;
	int arr1[]={2,8,9,7,52,30};
	int arr2[]={45,98,45,32,28,5}; 
	int arr3[]={4,96,582,23,4};
	int arr4[]={98,652,33,55,770};
	createStack1(s,arr1,6);//顺序栈 
	printStack(s);
	
	createStack2(p,arr2,6);//链栈 
	printSt(p);
	
	createSqQueue(q,arr3,5); //循环队列 
	visitSq(q);
	
	createQNode(l,arr4,5);//链队 
	visitLiQue(l);
	
	return 0;
}
队列

评论区

  1. 目录
留言