数据结构篇——队列
队列的定义
是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。与栈相反，队列是 一种先进先出（First In First Out，FIFO）的线性表。
队列的链式存储结构
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct Node{
ElemType data;
struct Node *next;
}Node,LinkQueue;
Node *R;
void init(LinkQueue *Q){
Q->data=0;
Q->next=NULL;
R=Q;
for(int i=1;i<=5;i++){
Node *n=malloc(sizeof(Node));
n->data=i;
n->next=R->next;
R->next=n;
R=n;
Q->data++;
}
}
void show(LinkQueue *Q){
if(Q->data==0){
printf(">>>队列为空！\n");
return;
}
Node *p=Q;
printf("[");
while(1){
p=p->next;
if(p=R){
printf("%d]\n",p->data);
break;
}else{
printf("%d,",p->data);
}
}
}
void enqueue(LinkQueue *Q,ElemType e){
Node *n=malloc(sizeof(Node));
n->data=e;
n->next=R-next;
R->next=n;
R=n;
Q->data++;
}
int dequeue(LinkQueue *Q,int *e){
if(Q->data==0){
printf(">>>队列为空！\n");
return 0;
}
Node *n=Q->next;
Q->next=n->next;
*e=n->data;
free(n);
Q->data--;
if(Q->data==0){
R=Q;
}
return 1;
}
void main(){
LinkQueue Q; //L S Q T
int choice;
ElemType e;
printf("----------单链队列-----\n");
print("1.初始化\n");
printf("2.入队\n");
printf("3.出队\n");
printf("4.长度\n");
printf("5.打印\n");
printf("0.退出\n");
while(1){
printf(">>>请选择：");
scanf("%d",&choice);
switch(choice){
case 1:
break;
case 2:
print(">>>请输入入队的元素:");
scanf("%d",&e);
enqueue(&Q,e);
break;
case 3:
if(dequeue(&Q,e)){
printf(">>>出队元素为%d",e);
}
break;
case 4:
printf(">>>长度为%d\n",Q.data);
break;
case 5:
show(&Q);
break;
case 0:
break;
}
}
}循环队列的定义
循环队列它的容量是固定的，并且它的队头和队尾指针都可以随着元素入出队列而发生 改变，这样循环队列逻辑上就好像是一个环形存储空间，但是要注意的是，在实际的内存当 中，不可能有真的环形存储区，我们只是用顺序表模拟出来的逻辑上的循环。
/*
64个盘子x->z
先63 x->y 借助z
先62 x->z 借助y
先61 x->y 借助z
...
第62 x->z
后61 y->z 借助x
...
第63 x->y
后62 z->y 借助x
第64 x->z
后63 y->z 借助x
先62 y->x 借助z
先61 y->z 借助x
第62 y->x
后61 z->x 借助y
第62 y->z
后62 x->z 借助y
一共num
先移动num-1 x->y 借助z
先移动num-2 x->y 借助z
再移动num-1 x->z
后移动num-2 y->z 借助x
再移动num x->z
后移动num-1 y->z 借助x
num=64
void move(num,x,y,z){
if(num==1){
x->z
}else{
move(num-1,x,z,y)
num x->z
move(num-1,y,x,z)
}
}
*/
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct Node{
ElemType data;
struct Node *next;
}Node,LinkStack;
void init(LinkStack *S,int num){
S->data=0;
S->next=NULL;
for(int i=1;i<=num;i++){
Node *n=malloc(sizeof(Node));
n->data=i;
n->next=R->next;;
R->next=n;
R=n;
S->data++;
}
}
void show(LinkStack *S){
if(S->data==0){
printf("[]\n");
return;
}
printf("[");
Node *p=S;
while(1){
p=p->next;
if(p->next==NULL){
printf("%d]\n",p->data);
break;
}else{
printf("%d,",p->data);
}
}
}
void push(LinkStack *L,Node *n){
// 先找尾指针
Node *p=S;
while(1){
p=p->next;
if(p->next=NULL){
break;
}
p=p->next;
}
n->next=p->next;
p->next=n;
S->data++;
}
Node* pop(LinkStack *s){
Node *p=S;
while(1){
p=p->next;
if(p->next->next==NULL){
break;
}
p=p->next;
}
Node *n=p->next;
p->next=NULL;
S->data--;
return;
}
void move(int num,LinkStack *from LinkStack *mid,LinkStack *to){
if(num==1){
//printf("%c->%c",from,to);
push(to,n);
}else{
move(num-1,from,to,mid);
//printf("%c->%c",from,to);
push(to,pop(from));
move(num-1,mid,from,to);
}
}
void main(){
printf(">>>请输入盘子个数:");
scanf("%d",&num);
move(num,'x','y','z');
LinkStack L1,L2,L3;
init(&L1,num);
init(&L2,0);
init(&L3,0);
show(&L1);
printf("&L1:");
show(&L2);
printf("&L2:");
show(&L3);
printf("&L3:");
scanf("%d",&num,&L2,&L3);
printf("===============\n");
printf("&L1:");
show(&L1);
printf("&L1:");
show(&L2);
printf("&L2:");
show(&L3);
printf("&L3:");
}// 八皇后
/*
*/
#include<stdio.h>
#define TRUE 1
#define FALSE 0
typedef int Status;
int count=0;// 统计次数
Status hasAttack(int row,int col,int arr[8][8]){
//北
for(int x=row-1;x>=0;x--){
if(arr[x][col]==1){
return TRUE;
}
}
//南
for(int x=row+1;x<8;x++){
if(arr[x][col]==1){
return TRUE;
}
}
//东
for(int y=col;y<8;y++){
if(arr[row][y]==1){
return TRUE;
}
}
//西
for(int y=col-1;y>=0;y--){
if(arr[row][y]==1){
return TRUE;
}
}
//东北
for(int x=row-1;y=col+1;x>=0&&y<8;x--,y++){
if(arr[row][y]==1){
return TRUE;
}
}
//西北
for(int x=row-1;y=col-1;x>=0&&y<8;x--,y--){
if(arr[row][y]==1){
return TRUE;
}
}
//东南
for(int x=row+1;y=col+1;x>=8&&y<8;x++,y++){
if(arr[row][y]==1){
return TRUE;
}
}
//西南
for(int x=row+1;y=col-1;x>=8&&y<0;x++,y--){
if(arr[row][y]==1){
return TRUE;
}
}
return FALSE;
}
#include<stdlib.h>
void eightQeen(int row,int col,int arr[8][8]){
/*
在当前row寻找可能出现的皇后，在此基础之上进行下一行的寻找
如果行数到9，说明前8行排布完毕，直接打印或退出即可
*/
int newArr[8][8];
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
newArr[i][j]=arr[i][j];
}
}
if(row>7){
count++;
printf("%d种:\n");
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
printf("%d ",newArr[i][j]);
}
printf("\n");
}
printf("\n");
}else{
for(int c=0;c<col;c++){
// true 有冲突 false 没冲突
if(!hasAttack(row,c,newArr)){
for(int k=0;k<col;k++){
newArr[row][k]=0;
}
newArr[row][c]=1;
eightQeen(row+1,8,new333wArr);
}
}
}
}
void main(){
// 先将空二维数组建立
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
a[i][j]=0;
}
}
eightQeen(0,8,arr);
printf("一共%d",count);
}
/*
eq(0,8)
0,0
eq(1,8)
1,2
eq(2,8)
2,4
eq(3,8)
3,1
eq(4,8) X
4,3
eq(5,8) X
4,7
eq(5,8) X
3,6
eq(4,8)
4,1X
eq(5,8)X
5,3X
eq(6,8)X
6,5X
eq(7,8) X
4,3
eq
3,7
2,5
2,6
2,7
1,3
1,4
1,5
1,6
1,7
0,1
0,2
0,3
0,4
0,5
0,6
0,7
*/
队列的顺序存储
#include<stdio.h>
#define MAx_SIZE 10
typedef int ElemType;
typedef struct{
ElemType datas[MAx_SIZE];
int front;//头
int rear;// 尾
int Length; // 长度
}SeqQueue;
void init(SeqQueue *Q){
Q->front=0;
Q->rear=0;
Q->length=0;
for(int i=1;i<=5;i++){
Q->datas[Q->rear++]=i;
Q->length++;
}
}
void show(SeqQueue *Q){
if(Q->length==0){
printf("[]\n");
return;
}
printf("[");
for(int i=Q->front;i!=Q->rear;i=(i+1)%MAx_SIZE){
if((i+1)%MAx_SIZE==Q->rear){
printf("%d]\n",Q->datas[i]);
break;
}else{
printf("%d",Q->datas[i]);
}
i=(i+1)%MAx_SIZE;
}
}
void enqueue(SeqQueue *Q,ElemType e){
if((Q->rear+1)%MAx_SIZE==Q->front){
printf(">>>队列已满！\n");
return;
}
Q->datas[Q->rear]=e;
Q->rear=(Q->rear+1)%MAx_SIZE;
Q->length++;
}
int dequeue(SeqQueue *Q,ElemType e){// Q->front==Q->rear
if(Q->length==0){
printf(">>>队列为空！\n");
return 0;
}
*e=Q->datas[Q->front];
Q->front=(Q->front+1)%MAx_SIZE;
Q->length--;
return 1;
}
void main(){
SeqQueue Q; //L S Q T
int choice;
ElemType e;
printf("----------顺序循环队列-----\n");
print("1.初始化\n");
printf("2.入队\n");
printf("3.出队\n");
printf("4.长度\n");
printf("5.打印\n");
printf("0.退出\n");
while(1){
printf(">>>请选择：");
scanf("%d",&choice);
switch(choice){
case 1:
break;
case 2:
print(">>>请输入入队的元素:");
scanf("%d",&e);
enqueue(&Q,e);
break;
case 3:
if(dequeue(&Q,e)){
printf(">>>出队元素为%d",e);
}
break;
case 4:
printf(">>>长度为%d\n",Q.Length);
break;
case 5:
show(&Q);
break;
case 0:
break;
}
}
}队列的链式存储
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct Node{
ElemType data;
struct Node *next;
}Node,LinkQueue;
Node *R;
void init(LinkQueue *Q){
Q->data=0;
Q->next=NULL;
R=Q;
for(int i=1;i<=5;i++){
Node *n=malloc(sizeof(Node));
n->data=i;
n->next=R->next;
R->next=n;
R=n;
Q->data++;
}
}
void show(LinkQueue *Q){
if(Q->data==0){
printf(">>>队列为空！\n");
return;
}
Node *p=Q;
printf("[");
while(1){
p=p->next;
if(p=R){
printf("%d]\n",p->data);
break;
}else{
printf("%d,",p->data);
}
}
}
void enqueue(LinkQueue *Q,ElemType e){
Node *n=malloc(sizeof(Node));
n->data=e;
n->next=R-next;
R->next=n;
R=n;
Q->data++;
}
int dequeue(LinkQueue *Q,int *e){
if(Q->data==0){
printf(">>>队列为空！\n");
return 0;
}
Node *n=Q->next;
Q->next=n->next;
*e=n->data;
free(n);
Q->data--;
if(Q->data==0){
R=Q;
}
return 1;
}
void main(){
LinkQueue Q; //L S Q T
int choice;
ElemType e;
printf("----------单链队列-----\n");
print("1.初始化\n");
printf("2.入队\n");
printf("3.出队\n");
printf("4.长度\n");
printf("5.打印\n");
printf("0.退出\n");
while(1){
printf(">>>请选择：");
scanf("%d",&choice);
switch(choice){
case 1:
break;
case 2:
print(">>>请输入入队的元素:");
scanf("%d",&e);
enqueue(&Q,e);
break;
case 3:
if(dequeue(&Q,e)){
printf(">>>出队元素为%d",e);
}
break;
case 4:
printf(">>>长度为%d\n",Q.data);
break;
case 5:
show(&Q);
break;
case 0:
break;
}
}
}