赞
踩
栈是一种重要的数据结构,它广泛应用于各种软件系统中,这种数据结构与线性表有密切的联系。从逻辑上看,栈属于线性结构,是一种特殊的线性表。其特殊性在于栈的基本操作是线性表操作的子集,它是限定公在表尾进行插入或删除操作的线性表,是操作受限的线性表。
学习要点:
1.了解栈的概念。
2.掌握栈的数据结构定义方法和基本运算的实现方法。
3.能够使用栈这种数据结构来解决具体的问题
栈的定义
栈(Stack)是一种特殊的线性表,是限定公在表尾进行插入或删除操作的线性表。栈的表尾称为栈顶(top),处于栈顶位置的数据元素称为栈顶元素。栈的表头称为栈底(bottom),处于栈底位置的数据元素称为栈底元素。不含任何元素的表称为空栈。
下面来看栈的使用代码实现
1. 栈的顺序存储的实现
【问题描述】
实现栈的顺序存储结构的基本运算。
【算法描述】
要求通过具体的算法来实现栈的顺序存储。首先建立栈的顺序结构,对栈的各个运算的算法做详细的描述,然后在主函数中通过函数调用实现顺序栈的置空、数据元素进栈、出栈等。
- #include<stdio.h>
- #include<malloc.h>
- #include<conio.h>
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- #define OK 1
- #define EQUAL 1
- #define OVERFLOW -1
- #define STACK_INIT_SIZE 100
- #define STACKINCREMENT 10
-
- typedef int ElementType ;
- struct STU
- {
- char name[20];
- char stuno[10];
- int age;
- int score;
- };
- typedef struct STU SElemType;
- struct STACK
- {
- SElemType *base;
- SElemType *top;
- int stacksize;
- };
- typedef struct STACK SqStack;
- typedef struct STACK *pSqstack;
- ElementType InitStack(SqStack **S);
- void DestroyStack(SqStack *S);
- void ClearStack(SqStack *S);
- ElementType StackEmpty(SqStack S);
- int StackLength(SqStack S);
- ElementType GetTop(SqStack S,SElemType *e);
- ElementType Push(SqStack *S,SElemType e);
- ElementType Pop(SqStack *S,SElemType *e);
- ElementType StackTraverse(SqStack S,ElementType (*visit)());
-
-
- ElementType InitStack(SqStack **S) /* 栈的初始化 */
- {
- (*S)=(SqStack *) malloc(sizeof(SqStack));
- (*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
- if(!(*S)->base)
- exit(OVERFLOW);
- (*S)->top=(*S)->base;
- (*S)->stacksize=STACK_INIT_SIZE;
- return OK;
- }
- void DestroyStack(SqStack *S) /* 栈的释放 */
- {
- free(S->base);
- free(S);
- }
-
- void ClearStack(SqStack *S) /* 栈的置空 */
- {
- S->top=S->base;
- }
-
- ElementType StackEmpty(SqStack S)
- {
- if(S.top==S.base)
- return TRUE;
- else
- return FALSE;
- }
-
- int StackLength(SqStack S)
- {
- int i;
- SElemType *p;
- i=0;
- p=S.top;
- while(p!=S.base)
- {
- p++;
- i++;
- }
-
- return i;
- }
-
- ElementType GetTop(SqStack S,SElemType *e)
- {
- if(S.top==S.base) return ERROR;
- *e=*(S.top-1);
- return OK;
- }
-
- ElementType Push(SqStack *S,SElemType e)
- {
- *(S->top++)=e;
- return OK;
- }
-
- ElementType Pop(SqStack *S,SElemType *e)
- {
- if(S->top==S->base) return ERROR;
- *e=*--S->top;
- return OK;
- }
-
- ElementType StackPrintElem(SElemType * e)
- {
- printf("%s %s %d %d\n",e->name,e->stuno,e->age,e->score);
- }
-
- ElementType StackTraverse(SqStack S, ElementType (*visit)())
- {
- while(S.top!=S.base)
- visit(--S.top);
- }
-
- int main(void) /* 顺序栈的主函数 */
- {
- SElemType e;
- SqStack *Sa;
-
- printf("\n\n------------SqStack Demo is running...-----------\n\n");
- printf("First is Push function.\n");
- InitStack(&Sa);
- strcpy(e.name,"stu1");
- strcpy(e.stuno,"100001");
- e.age=80;
- e.score=1000;
- printf("Now Stack is Empty.\n");
- StackTraverse(*Sa,StackPrintElem);
- Push(Sa,e);
- printf("Now Stack has one element.\n");
- StackTraverse(*Sa,StackPrintElem);
- strcpy(e.name,"stu3");
- strcpy(e.stuno,"100002");
- e.age=80;
- e.score=1000;
- Push(Sa,e);
- printf("Now Stack has another element.\n");
- StackTraverse(*Sa,StackPrintElem);
- printf("Now Pop Stack,the top elem put into variable e.\n");
- Pop(Sa,&e);
- printf("%s\n%s\n%d\n%d\n",e.name,e.stuno,e.age,e.score);
- printf("Let's see the left of Stack's elem:\n");
- StackTraverse(*Sa,StackPrintElem);
-
- printf("\n\n\nWelcom to visit http://zmofun.topcool.net\n\n");
-
- return 0;
- }
运行结果
2. 栈的链式存储的实现
【问题描述】
链栈是栈的另一种存储方式,要求通过具体的算法实现链栈的倒置、出栈等运算。
【算法描述】
在设计链栈的基本运算之前,首先定义链栈的存储类型、结点类型,然后分别设计各种运算的具体函数。最后在主函数中实现链栈的各种运算时,分别调用相应的函数即可。
- #include <stdio.h>
- #include <malloc.h>
- #include <stdlib.h>
-
- #define NULL 0
-
- typedef char ElementType;
-
- typedef struct stacknode
- {
- ElementType data;
- struct stacknode *next;
- }StackNode;
-
- typedef struct
- {
- StackNode *top;
- }LinkStack;
-
- void InitStack(LinkStack *s)
- {
- s->top=NULL;
- }
-
- int StackEmpty(LinkStack *s)
- {
- return s->top==NULL;
- }
- /* 链栈的节点是动态分配的,无须判断 Full(上溢) */
- void Push(LinkStack *s, ElementType x)
- {
- StackNode *p;
- p=malloc(sizeof(StackNode));
- p->next=s->top; /* 由于是在栈顶 PUSH,所以要指向栈顶 */
- p->data=x;
- s->top=p; /* 插入 */
- }
-
- ElementType Pop(LinkStack *s)
- {
- ElementType x;
- StackNode *p=s->top; /* 指向栈顶 */
- if (StackEmpty(s))
- {
- printf("栈为空,不能出栈...\n");
- exit(-1);
- }
- x=p->data;
- s->top=p->next; /* 当前的栈顶指向原栈的 next */
- free(p);
- return x;
- }
-
- ElementType StackTop(LinkStack *s)
- {
- if (StackEmpty(s))
- {
- printf("栈为空,不能出栈...\n");
- exit(-1);
- }
- return s->top->data;
- }
-
- void Disp(LinkStack *s)
- {
- StackNode *p=s->top;
- printf("=======================================\n");
- while (p!=NULL)
- {
- printf("\n%c",p->data);
- p=p->next;
- }
- printf("=======================================\n");
- }
-
- void RevStack(LinkStack *s)
- {
- int i, n=0;
- char dat[50];
- while(!StackEmpty(s))
- {
- dat[n]=Pop(s); /* 保存退栈后的数据到数组 */
- n++;
- }
- for (i=0;i<n;i++)
- Push(s,dat[i]);
- }
-
- int main(void)
- {
- LinkStack * s=(LinkStack *)malloc(sizeof(LinkStack));
- char ch,ch2,ch3;
- printf("================= 链栈操作 DEMO =================\nn");
- InitStack(s);
- printf("依次压栈 a,b,c,d,e 后,栈中的数据为:\n");
- Push(s,'a');
- Push(s,'b');
- Push(s,'c');
- Push(s,'d');
- Push(s,'e');
- Disp(s);
- printf("\n 将此栈倒置,栈中的数据序列为:\n");
- RevStack(s);
- Disp(s);
- ch=Pop(s);
- printf("\n 出栈操作开始,第一次出栈得到的数据:%c",ch);
- ch2=Pop(s);
- printf("\n 第二次出栈得到的数据:%c",ch2);
- ch3=StackTop(s);
- printf("\n 此时的栈顶元素为:%c",ch3);
-
- return 0;
- }
-
-
运行结果:
3. 计算表达式的值
【问题描述】
计算用运算符后缀法表示的表达式的值。后缀表达式也称逆波兰表达式,比中缀表达式计算起来更方便简单些,中缀表达式计算存在着括号的匹配问题,所以在计算表达式值时一般都是先转换成后缀表达式,再用后缀法计算表达式的值。如表达式(a+b*c)/d-e 用后缀法表示应为 abc*+d/e-1。只考虑四则算术运算,且假设输入的操作数均为 1 位十进制数(0~9),并且输入的后缀形式表达式不含语法错误。
- #include<stdio.h>
- #include<stdlib.h>
-
- #define add 43
- /* 运算符加号'+'的 ASCII 码 */
- #define subs 45
- /* 运算符减号'-'的 ASCII 码 */
- #define mult 42
- /* 运算符乘号'*'的 ASCII 码 */
- #define div 47
- /* 运算符除号'/'的 ASCII 码 */
- #define MAXSIZE 100
- typedef struct
- {
- int stkdata[MAXSIZE];
- /* 用数组来表示栈空间,定义长度为 MAXSIZE 的堆栈 */
- int top ;
- /* 栈顶 */
- }STKzone;
- typedef STKzone *STK;
-
- typedef enum{ok,error} status;
- STKzone expSTKzone;
- STK expSTK;
- STK initSTK(STKzone *stack_zone)
- {
- /* 执行栈初始化,建栈指针 */
- STK p;
- p=stack_zone;
- p->top=0;
-
- return p;
- }
-
- status push(int *term,STK pstk)
- {
- /* 将一结构型数据送入栈中 */
- if(pstk->top==MAXSIZE)
- return error; /* 栈满,进栈失败 */
- pstk->stkdata[pstk->top] =*term;
- (pstk->top)++;/* 栈顶指针移动 */
- return ok;
- }/* push */
- bool emptySTK(STK pstk)
- {
-
- return(pstk->top==0);
- }
- status pop(int *pdata, STK pstk)
- {
- /* 从栈中取出一结构型数据 */
- if(emptySTK(pstk))
- return error;
- (pstk->top)--; /* 退栈 */
- *pdata =pstk->stkdata[pstk->top];
- return ok;
- }
- void synerror()
- {
- printf("\n 表达式语法错!");
- exit(-1);
- }
- int eval(char tag,int a1,int a2)
- {
- switch(tag)
- {
- case add:return(a1+a2);
- case subs:return(a1-a2);
- case mult:return(a1*a2);
- case div:return(a1/a2);
- }
- }
-
- int main()
- {
- char c;
- int opd1,opd2,temp,c1;
- expSTK=initSTK(&expSTKzone);
- printf("\n 后置表达式: ");
- while((c=getchar())!='\n')
- {
- if(c== ' ')
- continue;
- if((c>47)&&(c<58))
- /* 判断是否是 0~9 的字符 */
- {
- putchar(c);
- c1=c-48;
- /* 把输入的字符型数字转换成数字 */
- if(push(&c1,expSTK)==error) /* 运算分量进栈 */
- {
- printf("\n 表达式太长\n");
- exit(-1);
- }
- }
- else if((c==add)||(c==subs)||(c==mult)||(c==div))
- {
- putchar(c);
- if(pop(&opd1,expSTK)==error) /* 将运算量 1 出栈 */
- synerror();
- if(pop(&opd2,expSTK)==error) /* 将运算量 2 出栈 */
- synerror();
- temp=eval(c,opd2,opd1); /* 计算得到结果 */
- push(&temp,expSTK); /* 将运算结果进栈 */
- }
- else synerror(); /* 出现非法字符 */
- } /* while */
- if(pop(&opd1,expSTK)==error) synerror();
- if(!(emptySTK(expSTK))) synerror();
- printf("=%-3d\n",opd1);
-
- return 0;
- }
运行结果:
4. 递归程序设计实训例题:求 Fibonacci 数列函数的实现前 n 项的值,n 由键盘输入,每行输出 4 项。
【问题描述】
由题意可知,Fibonacci 数列的第一项、第二项的值都为 1,从第三项起,每一项的值均是其前面两项值之和。
- #include<stdio.h>
- #include<malloc.h>
-
- long fib(int i)
- {
- if(i==1||i==2)
- return(1);
- else
- return(fib(i-1)+fib(i-2));
- }
-
- int main()
- {
- int i,n;
- long fib();
- printf("Please input fibnacci number:");
- scanf("%d",&n);
- for(i=1;i<=n;i++)
- {
- printf("fib(%d)=%2ld ",i,fib(i));
- if(i%4==0)
- printf("\n");
- }
-
- return 0;
- }
运行结果:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。