数据结构-----栈（C语言版）

自学出现的问题：

                         1.不明白需要定义栈需要什么（定义两个指针，一个栈顶，一个栈尾，定义栈中元素个数）（定义一个的指针，加个数组）

                         2. 怎么给栈分配空间，或者说 malloc谁（是栈中元素，还是栈本身）

真正开始学习：

前戏：

void f(int m){
    int i;
    double *q = (double *)malloc(sizeof(double));
}
int main()
{
    int k;
    nt *p = (int *)malloc(100);
    return 0;
}

其中， m, i, k ,p为静态分配------栈区分配----操作系统分配

           100为动态分配------堆区分配------程序员手动分配

什么是栈？

                一种可以实现 先进后出 的存储结构

栈的分类：

               静态栈：以数组为基本内核

               动态栈：以链表为基本内核

栈的算法：

               出栈

               入栈

一些操作：

1. 定义栈，并初始化

#include 
#include 
#include 
#include 
 

 
 //栈中节点
typedef struct Node{
    int data;
    struct Node*pNext;
}NODE, *PNODE;


//栈
typedef struct Stack{
    PNODE pTop;
    PNODE pBottom;
}STACK, *PSTACK;


//init函数，使pTop, pBottom都指向头结点，造出一个空栈出来
void init(PSTACK pS){
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if(NULL == pS->pTop){
        printf("内存分配失败n");
        exit(-1);
    }
    else{
        pS->pBottom = pS->pTop; //栈为空时，栈尾 = 栈顶
        pS->pTop->pNext = NULL; //栈为空时，栈顶指向空
    }
}

 2. 判断栈是否为空

bool empty(PSTACK pS){
    if(pS->pTop == pS->pBottom)
        return true;
    else
        return false;
}

3. 元素入栈

void push(PSTACK pS, int val){

    PNODE pNew = (PNODE)malloc(sizeof(NODE)); //创建一节点
    pNew->data = val; //为该节点赋值
    pNew->pNext = pS->pTop; //将该节点指向原来的栈顶
    pS->pTop = pNew; //将现在的栈顶设为该节点
}

4. 元素出栈

//把pS所指向的栈的栈顶元素存入pVal所指向的变量中，并将此元素从栈中删去
bool pop(PSTACK pS, int *pVal){
    if(empty(pS)){
        printf("栈为空n");
    }
    else{
        //将栈顶赋值为p
        PNODE p = pS->pTop;
        *pVal = p->data;
        //将新的栈顶设置为原先栈顶的下一个
        pS->pTop = p->pNext;
        //释放p的空间
       free(p);
       p = NULL;

       return true;
    }

}

  5.测试 

int main()
{
    STACK S;
    int p;
    init(&S);
    push(&S, 1);
    push(&S, 2);
    push(&S, 3);
    traverse(&S);
    pop(&S, &p);

    traverse(&S);
    printf("%d", p);

    return 0;
}

栈的应用：

               1. 函数调用

               2. 中断-----重启

               3. 表达式求值----2个栈可实现个计算器！

               4. 内存分配

               5.缓冲处理

               6. 迷宫

用栈的存储结构解决一些问题                 

1. 数制转换                   

#define N 2

void conversion(){
    int k;
    int e;
    STACK S;
    init(&S);
    printf("请输入需要转化为%d进制的数，请输入：", N);
    scanf("%d", &k);

    while(k){
        push(&S, k%N);
        k = k/N;
    }

    while(!empty(&S)){
        pop(&S, &e);
        printf("%d", e);
    }
    printf("n");
}

2.行编辑程序

题目说明：

  简单的行编辑程序，接受用户从终端输入的程序或数据，存入数据区

输入规则:

 1. #-----表示前一字符无效

2.@-----表示当前行中字符无效

明天肝-----有C语言文件的事------烦死文件流