数据结构4

    科技2025-04-09  27

    文章目录

    栈队列

    定义: 一种可以实现“先进后出”的存储结构。 分类: 静态栈动态栈 算法: 出栈压栈 #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct Node{ int data; struct Node * pNext; }NODE, * PNODE; typedef struct Stack{ PNODE pTop;// pTop永远指向栈顶元素 PNODE pBottom; // pBottom永远指向栈底元素的下一个无意义的元素(类似于头结点,方便操作。) }STACK, * PSTACK; void init(PSTACK); void push(PSTACK,int); void traverse(PSTACK); bool pop(PSTACK,int *); int main(void){ STACK S; int val; init(&S); // 目的是造出一个空栈 push(&S,1); // 压栈 push(&S,2); traverse(&S); // 遍历输出 pop(&S,&val); // 出栈 clear(&S); // 清空 return 0; } void init(PSTACK pS){ pS->pTop = (PNODE)malloc(sizeof(NODE)); if(NULL == pS->pTop){ printf("动态内存分配失败!\n"); ext(-1); }else{ pS->pBottom = pS->pTop; pS->pTop->pNext = NULL; } } void push(PSTACK pS,int val){ PNODE pNew = (PNODE)malloc(sizeof(NODE)); pNew->data = val; pNew->pNext = pS->pTop; // pS->pTop指向头结点的指针赋给pNew->pNext pS->pTop = pNew; return; } void traverse(PSTACK pS){ PNODE p = pS->pTop; while(p != pS->pBottom){ printf("%d",p->data); p = p-pNext; } printf("\n"); return; } bool empty(PSTACK pS){ if(pS->pTop == pS->pBottom){ return true; }else{ reurn false; } } // 把pS所指向的栈出栈一次,并把出栈的元素存入pVal形参所指向的变量中。 bool pop(PSTACK pS,int * pVal){ if(empt(pS)){ return false; }else{ PNODE r= pS->pTop; *pVal = r->data; pS->pTop = r->pNext; free(r); r = NULL; return true; } } void clear(PSTACK pS){ if(empty(pS)){ return; }else{ PNODE p = pS->pTop; PNODE q = NULL; while(p != pS->pBottom){ q = p->pNext; free(p); p = q; } pS->pTop = pS->pBottom; } } 应用 函数调用中断表达式求值(计算器算法)内存分配缓冲处理迷宫

    队列

    定义: 一种可以实现“先进先出”的存储结构。 分类: 链式队列 ——用链表实现静态队列——用数组实现 静态队列通常都必须是循环队列。 应用: 所有和时间有关的操作都有队列的影子。 循环队列

    静态队列为什么必须是循环队列

    循环队列需要几个参数确定

    两个参数(front、rear)

    循环队列各个参数的含义

    - 各个参数在不同场合有不同的含义 - 队列初始化: - front和rear的值都是0。 - 队列非空: - front代表队列的第一个元素,rear代表队列最后一个有效元素的下一个元素。 - 队列空 - front和rear的值相等,但不一定是0。

    循环队列入队伪算法

    循环队列出队伪算法(取余的操作着实很秀,我想不到) 妙啊

    如何判断循环队列是否为空

    front和rear的值相等。

    如何判断循环队列是否已满(更妙了)

    队列算法:

    #include <stdio.h> #include <malloc.h> typedef struct Queue{ int * pBase; int front; int rear; }QUEUE; void init(QUEUE *); bool en_queue(QUEUE *,int); // 入队 void traverse_queue(QUEUE *); bool full_queue(QUEUE *); bool out_queue(QUEUE *,int *); bool emput_queue(QUEUE *); int main(void){ QUEUE Q; init(&Q); en_queue(&Q,1); traverse_queue(&Q); return 0; } void init(QUEUE *pQ){ pQ->pBase = (int *)malloc(sizeof(int) * 6);// 数组 pQ->front = 0; pQ->rear = 0; } bool full_queue(QUEUE *pQ){ if((pQ->rear+1)%6 == pQ->front) return true; else return false; } bool en_queue(QUEUE *pQ,int val){ if(full_queue(pQ)){ printf("入队失败!\n"); return false; }else{ pQ->pBase[pQ->rear] = val; pQ->rear = (pQ->rear+1)%6; return true; } } void traverse_queue(QUEUE * pQ){ int i = pQ->front; while(i != pQ->rear){ printf("%d",pQ->pBase[i]); i = (i+1)%6; } printf("\n"); return; } bool emput_queue(QUEUE * pQ){ if(pQ->front == pQ->rear) return true; else return false; } bool out_queue(QUEUE * pQ,int * pVal){ if(emput_queue(pQ)){ return false; }else{ *pVal = pQ->pBase[pQ->front]; pQ->front = (pQ->front+1)%6; return true; } }
    Processed: 0.011, SQL: 8