数据结构-栈、队列及迷宫求解的应用

栈

stack.h

//stack.h   
    
#ifndef _STACK_H   
#define _STACK_H   
    
#include "stack.h"   
#include "data.h"   
    
#define ElemType TREE*   
    
#define STACK_INIT_SIZE 10   
#define STACK_INCREME 10   
    
typedef struct  
{   
    ElemType *base;   
    ElemType *top;   
    int size;   
}STACK;   
    
STACK *InitStack();   
void DestroyStack(STACK *s);   
int Push(STACK *s,ElemType *e);   
int Pop(STACK *s,ElemType *e);   
int IsEmpty(STACK *s);   
    
#endif

stack.c

//stack.c   
    
#include<stdio.h>   
#include<stdlib.h>   
#include "stack.h"   
    
STACK * InitStack() //初始化一个栈   
{   
    STACK *s=(STACK*)malloc(sizeof(STACK));//初始化一个栈   
    if(s==NULL)   
        exit(0);   
    s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//为栈分配一个初始大小   
    if(s->base==NULL) //如果栈底指针指向空   
        exit(0);   
    s->top=s->base; //空栈，使栈底与栈顶指针相同   
    s->size=STACK_INIT_SIZE;   
    return s;   
}   
    
void DestroyStack(STACK *s) //销毁一个栈   
{   
    free(s->base);   
    free(s);   
}   
    
int Push(STACK *s,ElemType *e) //压栈   
{   
    if(s==NULL||e==NULL) //判断传入的参数是否合法   
        return 0;   
    if(s->top-s->base>=s->size)//如果满栈   
    {   
        s->base=(ElemType*)realloc(s->base,   
            (s->size+STACK_INCREME)*sizeof(ElemType));//重新分配栈的大小   
        if(s->base==NULL)//如果分配失败，返回零   
            return 0;   
        s->top=s->base+s->size;//重置栈顶指针   
        s->size=s->size+STACK_INCREME;//重置栈大小   
    }   
    /*  
    //写法一  
    *s->top=*e;//将数据存到栈顶  
    s->top++; //栈顶上移  
    */  
    //写法二   
    *s->top++=*e;   
    return 1;   
}   
    
int Pop(STACK *s,ElemType *e) //出栈   
{   
    if(s==NULL||e==NULL)//判断传入的参数是否合法   
        return 0;   
    if(s->base==s->top) return 0; //如果是空栈，返回   
    *e= *--s->top; //将栈顶元素存到*e中   
    return 1;   
}   
    
int IsEmpty(STACK *s) //判断栈是否为空   
{   
    return s->top==s->base ? 1:0;   
}

data.h

//data.h   
    
#ifndef _DATA_H   
#define _STACK_H   
    
typedef int ElemType; //定义一个ElemType类型   
    
#endif

main.c

//main.c   
//将十进制数转换成八进制数   
#include <stdio.h>   
#include "stack.h"   
    
void main()   
{   
    int num=1348,temp;   
    STACK *s= InitStack();   
    while(num)   
    {   
        temp=num % 8;   
        Push(s,&temp);   
        num/=8;   
    }   
    printf("result is:");   
    while(!IsEmpty(s))   
    {   
        Pop(s,&temp);   
        printf("%d",temp);   
    }   
    printf("\n");   
    DestroyStack(s);   
}

迷宫求解——栈的应用

stack.h

//stack.h   
    
#ifndef _STACK_H   
#define _STACK_H   
    
#include "data.h"   
    
#define STACK_INIT_SIZE 10   
#define STACK_INCREME 10   
    
typedef struct  
{   
    ElemType *base;   
    ElemType *top;   
    int size;   
}STACK;   
    
STACK *InitStack();   
void DestroyStack(STACK *s);   
int Push(STACK *s,ElemType *e);   
int Pop(STACK *s,ElemType *e);   
int IsEmpty(STACK *s);   
    
#endif

stack.c

//stack.c   
    
#include<stdio.h>   
#include<stdlib.h>   
#include "stack.h"   
    
STACK * InitStack() //初始化一个栈   
{   
    STACK *s=(STACK*)malloc(sizeof(STACK));//初始化一个栈   
    if(s==NULL)   
        exit(0);   
    s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//为栈分配一个初始大小   
    if(s->base==NULL) //如果栈底指针指向空   
        exit(0);   
    s->top=s->base; //空栈，使栈底与栈顶指针相同   
    s->size=STACK_INIT_SIZE;   
    return s;   
}   
    
void DestroyStack(STACK *s) //销毁一个栈   
{   
    free(s->base);   
    free(s);   
}   
    
int Push(STACK *s,ElemType *e) //压栈   
{   
    if(s==NULL||e==NULL) //判断传入的参数是否合法   
        return 0;   
    if(s->top-s->base>=s->size)//如果满栈   
    {   
        s->base=(ElemType*)realloc(s->base,   
            (s->size+STACK_INCREME)*sizeof(ElemType));//重新分配栈的大小   
        if(s->base==NULL)//如果分配失败，返回零   
            return 0;   
        s->top=s->base+s->size;//重置栈顶指针   
        s->size=s->size+STACK_INCREME;//重置栈大小   
    }   
    /*  
    //写法一  
    *s->top=*e;//将数据存到栈顶  
    s->top++; //栈顶上移  
    */  
    //写法二   
    *s->top++=*e;   
    return 1;   
}   
    
int Pop(STACK *s,ElemType *e) //出栈   
{   
    if(s==NULL||e==NULL)//判断传入的参数是否合法   
        return 0;   
    if(s->base==s->top) return 0; //如果是空栈，返回   
    *e= *--s->top; //将栈顶元素存到*e中   
    return 1;   
}   
    
int IsEmpty(STACK *s) //判断栈是否为空   
{   
    return s->top==s->base ? 1:0;   
}

data.h

//data.h   
    
#ifndef _DATA_H   
#define _DATA_H   
    
#include "stack.h"   
#include<stdio.h>   
    
//typedef int ElemType;   
typedef struct //位置   
{   
    int x;   
    int y;   
}POS;    
    
typedef struct //要存放在栈中的元素的类型   
{   
    int sno; //编号   
    POS seat; //位置   
    int di; //朝向   
}ElemType;   
    
#endif

main.c

//main.c   
    
#include "stack.h"   
#include "data.h"   
#include <stdio.h>   
#include <conio.h>   
#include <stdlib.h>   
    
int item[10][10]={   
    {1,0,1,1,1,1,1,1,1,1},   
    {1,0,0,1,0,0,0,1,0,1},   
    {1,0,0,1,0,0,0,1,0,1},   
    {1,0,0,0,0,1,1,0,0,1},   
    {1,0,1,1,1,0,0,0,0,1},   
    {1,0,0,0,1,0,0,0,0,1},   
    {1,0,1,0,0,0,1,0,0,1},   
    {1,0,1,1,1,0,1,1,0,1},   
    {1,1,0,0,0,0,0,0,0,1},   
    {1,1,1,1,1,1,1,1,0,1}   
};   
static const POS inPos={1,0},outPos={8,9};   
//入口(开始位置)与出口(结束位置)   
int IsPass(POS curP) //是否可通，为0可通，为1不可通   
{   
    return item[curP.y][curP.x]==0 ? 1:0;   
}   
    
POS NextPos(POS curP,int di)//指向下一个位置,di表示方向   
{   
    POS p=curP;   
    switch(di)   
    {   
    case 0: //向右边   
        p.x++;   
        break;   
    case 1: //向下边   
        p.y++;   
        break;   
    case 2: //向右边   
        p.x--;   
        break;   
    case 3: //指向上一个   
        p.y--;   
        break;   
    }   
    return p;   
}   
    
void PrintItem(POS curP) //打印迷宫   
{   
    int i,j;   
    system("cls"); //清空屏幕   
    for(i=0;i<10;i++)   
    {   
        for(j=0;j<10;j++)   
        {   
            if(i==curP.y && j==curP.x) //如果是开始位置   
            {   
                printf("⊙");   
                continue;   
            }   
            if(item[i][j]==1) //如果不可通   
                printf("■");   
            else            //可通   
                printf("　");   
        }   
        printf("\n");   
    }   
}   
    
void main()   
{   
    ElemType e; //用于存放于栈中的元素结点   
    int step=1; //位置计数，第几步   
    POS curPos=inPos; //当前位置   
    STACK *s=InitStack();//初始化栈   
    PrintItem(inPos); //打印入口点，开始位置   
    getch(); //等待读入字符，暂停作用   
    do  
    {   
        if(IsPass(curPos)) //如果是当前位置可通   
        {   
            e.sno=step; //当前计数赋给结点的编号   
            e.di=0; //朝向，默认向左   
            e.seat=curPos;  //当前位置   
            Push(s,&e); //把当前位置压入栈顶   
            item[curPos.y][curPos.x]=2;//修改item中的值，保存足迹   
            if(curPos.y==outPos.y && curPos.x==outPos.x) //如果是出口   
            {   
                PrintItem(curPos); //打印当前位置   
                printf("OK!迷宫走完！\n"); //完成   
                break;   
            }   
            PrintItem(curPos); //打印当前位置   
            getch(); //等待读入字符，暂停作用   
            curPos=NextPos(curPos,0); //将栈顶位置指向栈顶位置左边的方块   
            step++; //位置计数器加1   
        }   
        else    //当前位置不可通，则   
        {   
            Pop(s,&e);//取出栈顶结点   
            while(e.di==4 && !IsEmpty(s) )//若栈不为空且栈顶方块位置的四周都不可通   
            {   
                item[curPos.y][curPos.x]=3; //修改item的值，把不可通的位置，保存不可通的足迹   
                Pop(s,&e); //出栈，删去栈顶位置   
            }   
            if(e.di<3) //若栈不为空且还有其他方向未经探索   
            {   
                e.di++; //改变方向   
                Push(s,&e); //把出栈的结点重新压入栈   
                curPos=NextPos(e.seat,e.di); //以新的方向往下找   
            }   
        }   
    }while(!IsEmpty(s));   
    getch(); //等待读入字符，暂停作用   
}

简单队列

main.c

//main.c   
    
//利用数组创建队列   
    
#include <stdio.h>   
    
#define MAX_SIZE 10   
    
int queue[MAX_SIZE]; //   
    
int rear = -1; //队尾   
int front = -1; //队头   
    
int InQueue(int value)//进队列   
{   
    if(rear>=MAX_SIZE)   
        return 0;   
    rear++;   
    queue[rear]=value;   
    return 1;   
}   
    
int OutQueue(int *value)//出队列   
{   
    if(front == rear)   
        return 0;   
    front++;   
    *value=queue[front];   
    return 1;   
}   
    
void main()   
{   
    int temp;   
    
    while(1)   
    {   
        printf("1:存入；2：读取；=》：");   
        scanf("%d",&temp);   
        fflush(stdin);   
        if(temp==1)   
        {   
            printf("请输入要存入的值：");   
            scanf("%d",&temp);   
            fflush(stdin);   
            if(InQueue(temp)==1)   
                printf("插入队列成功\n");   
            else  
                printf("队列已满！\n");   
        }   
        else if(temp==2)   
        {   
            if(OutQueue(&temp))   
            {   
                printf("读取队列的值为：%d\n",temp);   
            }   
            else  
            {   
                printf("队列为空!\n");   
            }   
        }   
        else  
            break;   
    }   
}

循环队列

mian.c

//main.c   
    
//利用数组创建队列   
    
#include <stdio.h>   
    
#define MAX_SIZE 10   
    
int queue[MAX_SIZE]; //   
    
int rear = -1; //队尾   
int front = -1; //队头   
    
int InQueue(int value)//进队列   
{   
    if(front==-1 && rear==MAX_SIZE-1||rear+1==front)//判断队列是否已满   
        return 0;   
    rear++;   
    if(rear==MAX_SIZE)  rear=0;   
    queue[rear]=value;   
    return 1;   
}   
    
int OutQueue(int *value)//出队列   
{   
    if(rear==front)//判断队列是否为空   
        return 0;   
    front++;   
    if(front==MAX_SIZE) front=0;   
    *value=queue[front];   
    return 1;   
}   
    
void main()   
{   
    int temp;   
    
    while(1)   
    {   
        printf("1:存入；2：读取；=》：");   
        scanf("%d",&temp);   
        fflush(stdin);   
        if(temp==1)   
        {   
            printf("请输入要存入的值：");   
            scanf("%d",&temp);   
            fflush(stdin);   
            if(InQueue(temp)==1)   
                printf("插入队列成功\n");   
            else  
                printf("队列已满！\n");   
        }   
        else if(temp==2)   
        {   
            if(OutQueue(&temp))   
            {   
                printf("读取队列的值为：%d\n",temp);   
            }   
            else  
            {   
                printf("队列为空!\n");   
            }   
        }   
        else  
            break;   
    }   
}

双队列——示例1

main.c

//main.c   
    
//双队列   
    
#include<stdio.h>   
#include<stdlib.h>   
    
typedef struct _queue   
{   
    int data;   
    struct _queue *next;   
}QUEUE;   
    
QUEUE * rear=NULL;   
QUEUE * front=NULL;   
    
//输入限制型双队列   
int InQueue(int value)   
{   
    QUEUE * q=(QUEUE *)malloc(sizeof(QUEUE));   
    if(q==NULL) return 0;   
    q->data=value;   
    q->next=NULL;   
    if(front==NULL)   
        front=q;   
    else  
        rear->next=q;   
    rear=q;   
    return 1;   
}   
    
int OutQueueByFront(int *value) //从队头取数据   
{   
    QUEUE *p=NULL;   
    if(front==NULL)   
        return 0;   
    p=front;   
    front=front->next;   
    *value=p->data;   
    free(p);   
    return 1;   
}   
    
int OutQueueByRear(int *value) //从队尾取数据   
{   
    QUEUE *p=NULL;   
    if(rear==NULL) //如果队列为空   
        return 0;   
    if(rear==front) //如果队列中只有一个数据   
    {   
        *value=rear->data;   
        free(rear);   
        rear=NULL;   
        front=NULL;   
    }   
    else //   
    {   
        p=front;   
        while(p->next!=rear)//当p不等于最后一个的前一个   
            p=p->next;   
        *value=rear->data;   
        free(rear);   
        rear=p;   
        rear->next=NULL;   
    }   
    return 1;   
}   
    
void main()   
{   
    int res,i,arr[5]={1,2,3,4,5};   
    for(i=0;i<5;i++)   
        InQueue(arr[i]);   
    while(1)   
    {   
        printf("1:从队头取出；2：从队尾取出；3：退出=>");   
        scanf("%d",&res);   
        fflush(stdin);   
        if(res==1)   
        {   
            if(OutQueueByFront(&res)==1)   
                printf("取出的值为：%d\n",res);   
            else  
                printf("队列为空！\n");   
        }   
        else if(res==2)   
        {   
            if(OutQueueByRear(&res)==1)   
                printf("取出的值为：%d\n",res);   
            else  
                printf("队列为空！\n");   
        }   
        else if(res==3)   
            break;   
    }   
}

双队列——示例2

main.c

//main.c   
    
//输出限制型双队列   
    
#include<stdio.h>   
#include<stdlib.h>   
    
typedef struct _queue   
{   
    int data;   
    struct _queue *next;   
}QUEUE;   
    
QUEUE * rear=NULL;   
QUEUE * front=NULL;   
    
//输出限制型双队列   
int OutQueue(int *value)   
{   
    QUEUE * p=NULL;   
    if(front == NULL)   
        return 0;   
    p=front;   
    front=front->next;   
    *value = p->data;   
    free(p);   
    return 1;   
}   
    
int InQueueByRear(int value)   
{   
    QUEUE *q=(QUEUE *)malloc(sizeof(QUEUE));   
    if(q==NULL) return 0;   
    q->data=value;   
    q->next=NULL;   
    if(rear==NULL)   
        front=q;   
    else  
        rear->next=q;   
    return 1;   
}   
    
int InQueueByFront(int value)   
{   
    QUEUE *q=(QUEUE *)malloc(sizeof(QUEUE));   
    if(q==NULL) return 0;   
    q->data=value;   
    q->next=front;   
    front = q;   
    if(rear==NULL)   
        rear=q;   
    return 1;   
}   
    
void PrintQueue() //打印   
{   
    QUEUE *p=front;   
    while(p)   
    {   
        printf("%5d",p->data);   
        p=p->next;   
    }   
    printf("\n");   
}   
    
    
void main()   
{   
    int res;   
    while(1)   
    {   
        printf("1:从队头存入；2：从队尾存入；3：退出 =》");   
        scanf("%d",&res);   
        fflush(stdin);   
        if(res==1)   
        {   
            printf("请输入要存入的值：");   
            scanf("%d",&res);   
            fflush(stdin);   
            if(InQueueByFront(res))   
            {   
                PrintQueue();   
            }   
            else  
                printf("存入失败！\n");   
        }   
        if(res==2)   
        {   
            printf("请输入要存入的值：");   
            scanf("%d",&res);   
            fflush(stdin);   
            if(InQueueByRear(res))   
            {   
                PrintQueue();   
            }   
            else  
                printf("存入失败！\n");   
        }   
        else if(res==3)   
            break;   
    }   
}

版权所有，转载请注明出处 luowei.github.io.