数据结构实验报告——栈

• 实验目的与要求
• 实验步骤与内容
• 问题与说明
• 备注
• 程序清单

实验目的与要求

1.了解栈的逻辑结构

2.熟悉各种方法构建栈

3.实现栈的基本操作

4.实现栈的应用

实验步骤与内容

栈(stack)由两个端点栈顶(top)和栈底(bottom)构成，遵循“先进后出”(FILO)或“后进先出”(LIFO)的规则，即只允许在一端插入或删除元素。

栈的ADT：

ADT stack{
    数据对象:D={ai|ai∈ElemSet,i=1,2,..,n , n≥0);
    数据关系:R={<ai-1,ai>|ai-1,a∈D,i=2,3,..,n};
    基本操作:初始化，进栈，出栈，取栈顶元素，判断栈空、栈满等
}ADT stack

栈的顺序存储结构

简称顺序栈，使用一维数组来储存，根据使用环境的不同又分为:

• 静态顺序栈
• 动态顺序栈

栈的应用

数制转化

在2,,8,10进制间转化，遵循n = (n div d) * d + n mod d,出数的顺序是由低位到高位，所以用栈来储存数据，计算完成后弹数即为正序。

void conversion(int k,int d){
    sqstack S;
    int k,*e;
    S=Init_stack();
    while(n>0){
        k=n%d;
        push(S,k);
        n=n/d;
    }
    while(S.top!=0){
        pop(S,e);
        printf("%d",*e);
    }
}

括号匹配问题

读左括号入栈，当读到右括号时弹出元素与左括号匹配。

#define TRUE 1
#define FALSE -1
sqstack S;
S=Init_stack();
int Match_Brackets(){
    chat ch,x;
    scanf("%c",&ch);
    while(asc(cj)!=13){
        if(ch=='('||ch=='[') push(S,ch);
        else if(ch==']') {
            x=pop(S);
            if(x!='[') return FALSE;
        }else if(ch==')'){
            x=pop(S);
            if(x!='(') return FALSE;
        }
        if(!S.top) return FALSE;
        return TRUE;
    }
}

递归调用

递归调用，一般遵循这样的规则:

F(n) = | 1 , n=0;
       | n*F(n-1) , n>0

递归栈:
(1)栈为空则执行正常返回
(2)栈顶弹出一个工作记录
(3)赋值
(4)返回地址

表达式求值

表达式由操作数，操作符和分界符构成。算术表达式分为三种分别是前缀表达式(infix)，中缀表达式(prefix)，后缀表达式(postfix)。所有表达式都遵循以下三个规则：

1.优先级高的先计算；
2.优先级相同的从左向右计算；
3.括号从最内层开始计算。

对于中缀表达式我们需要两个栈来求值，而后缀表达式只需要一个栈就可求值。所以计算表达式的值采用后缀表达式比较简单，易于理解。

算法1：后缀表达式求值

a)如果是运算数直接入栈

b)如果是运算符，先计算结果在将结果压栈

算法2：利用转将中缀表达式转后缀表达式

人工方法

(1)首先补全所有括号(A+B)*D-E/(F+A*D)+C=>((((A+B)*D)-(E/(F+(A*D))))+C)

(2)运算符全部提出到对应的括号外面

机器方法

首先表示出各个运算符的优先级

| 操作符ch | # | ( | ^ | * / % | + - | )|
| :——: | :——: | :——: |
| isp栈内优先级 | 0 | 1 | 7 | 5 | 3 | 8 |
| icp栈外优先级 | 0 | 8 | 6 | 4 | 2 | 1 |

操作符优先级相等的情况只出现在括号匹配或栈底的“#”与输入最后的“#”号匹配时。

操作符初始化，“#”进栈，读入中缀表达式首字符ch直到ch=“#”:

a)若ch是操作数，直接输出，读入下一个字符ch;

b)若ch是操作数，判断ch的优先级和位于栈顶的操作符op优先级，若(ch)>(op)，令ch进栈，读入下一个字符(观察后面后是否有更高级的运算符);若(ch)<(op)，退栈并输出(执行前保存栈内优先级最高的op);若(ch)==(op)，退栈但不输出（消括号）。

问题与说明

C语言实现
CLion 集成开发环境

备注

程序清单

动态顺序栈

bottom表示栈底指针，固定不变；top表示栈顶指针。top==bottom表示栈空；top-bottom=stacksize-1表示栈满。
结点进栈时首先将数据元素保存到栈顶(top所指的当前位置)top+1，使top指向栈顶的下一个储存位置。结点出栈时，先top-1取栈顶元素。

动态栈基本操作的实现

栈的类型定义

#define STACKSIZE 100
#define STACKINCRMENT 10
#typedeff int ElemType
typedef struct sqstack{
    ElemType *bottom;
    ElemType *top;
    int stacksize;
}sqstack;

栈的初始化

status Init_stack(void){
    sqstack S;
    s.bottom=(ElemType *)malloc(STACKSIZE*sizeof(ElemType));
    if(!s.bottom) return ERROR;
    S.top=S.bottom;
    S.stacksize=STACKSIZE;
    return OK;
}

压栈

Status push(sqstack s,ElemType e){
    if(S.top-S.bottom==s.stacksize-1){
        S.bottom=(ElemType *)realloc((S.stacksize+STACKINCRMENT)*sizeof(ElemType));
        if(!S.bottom) return ERROR;
        S.top=S.bottom+S.stacksize;
        S.stacksize += STACKINCRMENT;
    }
    *S.top=e;
    S.top++;
    return OK;
}

出栈

Status pop(sqstack S,ElemType e){
    if(S.bottom==S.top) return ERROR;
    S.top--;
    e=*S.top;
    return OK;
}

静态顺序栈

一维数组储存，栈底固定不变，而栈顶则随着进栈出栈而变化。top=0表示栈空，top=stacksize-1为栈满。结点进栈，首先执行top+1，是top指向新的栈顶位置，然后将数据元素保存到栈顶。结点出栈，首先取元素，然后执行top-1。为了避免浪费，可以在初始化时将top和bottom都设为-1。

基本操作的实现

栈的类型定义

#define MAX_STACK_SIZE 100
#typedef int ElemType;
typedef struct sqstack{
    ElemType stack_array[MAX_STAKC_SIZE];
    int top;
}sqstack;

栈的初始化

Status Init_stakc(void){
    sqstack S;
    S.top=S.bottom=0;
    return S;
}

入栈

Status push(sqstack S,ElemType e){
    if(S.top>=MAX_STACK_SIZE) return ERROR
    S.top++;
    S.stack_array[top]=e;
    return OK;
}

出栈

Status pop(sqstack S,ElemType e){
    if(S.top==0) retunr ERROR;
    S.top-1;
    e=S.srray_array[S.top];
    return OK;
}

栈的链式储存表示

运算受限，其插入和删除只能在表头位置进行，栈顶指针top就是链表的头指针。

链表的节点类型

typedef struct Stack_Node{
    ElemType data;
    struct Stacj_Node *next;
}Stack_Node;

基本操作

初始只有一个头节点head，head->next为NULL，栈空的条件为head->next==NULL;由于只有内存溢出时才会出现栈满的情况，通常不考虑这种情况。元素e进栈操作是将包含该元素的一个节点插入作为第一个数据节点，头插入栈删除第一个节点。

链栈的初始化

Stack_Node Init_stack(vodi){
    Stack_Node *top;
    top=(Stack_Node *)malloc(sizeof(Stack_Node));
    if(!top) return ERROR;
    top->next=NULL;
    return top;
}

链栈的压栈

Status push(Stack_Node *top,ElemType e){
    Stack_Node *p;
    p=(Stack_Node *)malloc(sizeof(Stack_Node));
    if(!p) return ERROR;
    p->data=e;
    p->next=top->next;
    top->next=p;
    return OK;
}

链栈的出栈

Status pop(Stack_Node *top,ElemType *e){
    Stack_Node *p;
    ElemType e;
    if(top->next==NULL) return ERROR;
    p=top->next;
    e=p->data;
    top->next=p->next;
    free(p);
    return OK;
}