【数据结构学习4】栈（顺序栈与链式栈）【C语言实现】

栈1. 栈的基础知识栈结构只允许从一端进行传入和删除数据的线性存储结构称为栈结构。栈顶数据插入和删除的一端。入栈\压栈数据插入出战\弹栈数据删除。特点先进后出FILO栈的应用1. 解决回溯问题2. 撤销功能3. 网页缓存返回4. 判断成对出现的东西如回文字符串、括号等2. 顺序栈顺序栈分为满增栈、空增栈、满减栈、空减栈。满栈/空栈是一种结构不是传统字面意思的满空根据栈顶所在位置是否存有元素确定。栈顶所在位置一直存有元素称为满栈先移动栈顶再存入数据栈顶所在位置一直没有元素称为空栈先存入数据再移动栈顶。增栈/减栈根据栈的生长方向确定。入栈数据时栈顶向内存高地址移动称为增栈入栈数据时栈顶向内存低地址移动称为减栈3. 链式栈API1. 创建2. 入栈3. 出栈4. 判栈空5. 获取栈顶元素6. 清空栈(删除栈中的所有结点)7. 销毁栈3.1 创建使用malloc创建一个空的链式栈初始化栈顶与长度分配失败返回 NULL。Stack_t*create_stack(){Stack_t*pstackmalloc(sizeof(Stack_t));if(NULLpstack){printf(malloc error\n);returnNULL;}pstack-ptopNULL;pstack-clen0;returnpstack;}3.2 判栈空通过检查栈顶指针ptop是否为NULL为空返回 1 (真)不为空返回 0 (假)。intis_empty_stack(Stack_t*pstack){if(NULLpstack-ptop){return1;}return0;}3.3 入栈先新建栈结点内存分配失败打印错误并返回‑1结点存入数据将新结点指向原来栈顶再更新栈顶为新结点栈长度 1成功返回 0。intpush_stack(Stack_t*pstack,Data_t data){Stacknode_t*ppushmalloc(sizeof(Stacknode_t));if(NULLppush){printf(malloc error\n);return-1;}ppush-datadata;ppush-pnextNULL;ppush-pnextpstack-ptop;pstack-ptopppush;pstack-clen;return0;}3.4 出栈先调用判空函数检查栈是否为空栈空直接返回‑1保存栈顶结点地址若接收数据的指针pdata不为空则把栈顶元素数据带出将栈顶指针向后移动一位释放旧栈顶结点内存栈弹出成功返回 0。intpop_stack(Stack_t*pstack,Data_t*pdata){if(is_empty_stack(pstack)){return-1;}Stacknode_t*pfreepstack-ptop;if(pdata!NULL){*pdatapfree-data;}pstack-ptoppstack-ptop-pnext;free(pfree);return0;}3.5 遍历栈元素用临时指针从栈顶开始循环依次输出每一个结点的数据直到指针为空结束打印换行。voidshow_stack(Stack_t*pstack){Stacknode_t*ptmppstack-ptop;while(ptmp){printf(%d ,ptmp-data);ptmpptmp-pnext;}printf(\n);}3.6 获取栈顶元素先判断栈是否为空空栈打印提示并返回‑1若接收数据的指针pdata有效则取出栈顶数据赋值成功返回 0pdata为 NULL 时返回‑1。intget_data_stack(Stack_t*pstack,Data_t*pdata){if(is_empty_stack(pstack)){printf(stack is empty\n);return-1;}if(pdata!NULL){*pdatapstack-ptop-data;return0;}return-1;}3.7 清空栈(删除栈中的所有结点)循环不断调用出栈函数依次释放所有栈顶结点直到栈顶指针为空栈内所有元素被删除最后返回 0。intclear_stack(Stack_t*pstack){while(pstack-ptop!NULL){pop_stack(pstack,NULL);}return0;}3.8 销毁栈voiddestroy_stack(Stack_t*pstack){clear_stack(pstack);free(pstack);}4. 通过链式栈实现中缀四则运算利用双栈算法计算不带括号的四则运算表达式。is_num_char判断字符是否为数字字符get_num根据运算符完成两个整数的加减乘除运算get_opt_lever返回运算符优先级、-优先级为 1*、/优先级为 2。核心函数get_result创建数字栈与运算符栈遍历表达式字符串遇到连续数字字符时完成多位数拼接压入数字栈运算符栈为空则直接压入当前运算符。若新运算符优先级高于栈顶运算符则入栈否则弹出栈顶运算符再从数字栈先后弹出两个操作数完成运算结果重新压回数字栈循环比较优先级。读到字符串结束符并且运算符栈为空时停止遍历数字栈栈顶即为最终运算结果最后销毁两个栈释放内存。main函数接收用户输入的运算字符串调用计算函数并打印最终结果。intis_num_char(charch){if(ch0ch9){return1;}return0;}intget_num(intnum1,intnum2,intopt){intret0;switch(opt){case:retnum1num2;break;case-:retnum1-num2;break;case*:retnum1*num2;break;case/:retnum1/num2;break;}returnret;}intget_opt_lever(intopt){intret0;switch(opt){case:case-:ret1;break;case*:case/:ret2;break;}returnret;}//1234*5 - 8/2intget_result(char*press,int*result){Stack_t*pnum_stackcreate_stack();Stack_t*popt_stackcreate_stack();if(NULLpnum_stack||NULLpop_stack){return-1;}char*ppress;intnum0;intopt0;intnum10,num20;intret0;while(1){if(\0*pis_empty_stack(popt_stack)){break;}while(is_num_char(*p)){numnum*10(*p-0);p;if(!is_num_char(*p)){push_stack(pnum_stack,num);num0;}}if(is_empty_stack(popt_stack)){push_stack(popt_stack,*p);p;continue;}//* get_stack_top(popt_stack,opt);if(*p!\0get_opt_lever(*p)get_opt_lever(opt)){push_stack(popt_stack,*p);p;}elseif(\0*p||get_opt_lever(*p)get_opt_lever(opt)){pop_stack(popt_stack,opt);pop_stack(pnum_stack,num2);pop_stack(pnum_stack,num1);retget_num(num1,num2,opt);push_stack(pnum_stack,ret);}}get_stack_top(pnum_stack,result);destroy_stack(pnum_stack);destroy_stack(popt_stack);return0;}intmain(void){intresult0;charpress[128]{0};gets(press);intretget_result(press,result);if(0ret){printf(%s %d\n,press,result);}return0;}