數(shù)據(jù)結(jié)構(gòu)教程第十課棧的表示與實(shí)現(xiàn)

本課主題： 棧的表示與實(shí)現(xiàn)
    教學(xué)目的： 棧的數(shù)據(jù)類型定義、棧的順序存儲表示與實(shí)現(xiàn)
    教學(xué)重點(diǎn)： 棧的順序存儲表示與實(shí)現(xiàn)方法
    教學(xué)難點(diǎn)： 棧的定義
    授課內(nèi)容：
    一、棧的定義
    棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。
    棧的表尾稱為棧頂，表頭稱為棧底，不含元素的空表稱為空棧。
    棧的抽象數(shù)據(jù)類型定義：
    ADT Stack{
    數(shù)據(jù)對象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}
    數(shù)據(jù)關(guān)系:R1={|ai-1,ai(- D,i=2,...,n}
    基本操作:
    InitStack(&S) 構(gòu)造一個(gè)空棧S
    DestroyStack(&S) 棧S存在則棧S被銷毀
    ClearStack(&S) 棧S存在則清為空棧
    StackEmpty(S) 棧S存在則返回TRUE,否則FALSE
    StackLength(S) 棧S存在則返回S的元素個(gè)數(shù),即棧的長度
    GetTop(S,&e) 棧S存在且非空則返回S的棧頂元素
    Push(&S,e) 棧S存在則插入元素e為新的棧頂元素
    Pop(&S,&e) 棧S存在且非空則刪除S的棧頂元素并用e返回其值
    StackTraverse(S,visit())棧S存在且非空則從棧底到棧頂依次對S的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()一旦visit()失敗,則操作失敗
    }ADT Stack
    二、棧的表示和實(shí)現(xiàn)
    棧的存儲方式：
    1、順序棧:利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置
    2、鏈棧:利用鏈表實(shí)現(xiàn)
    順序棧的類C語言定義:
    typedef struct{
    SElemType *base;
    SElemType *top; //設(shè)棧頂棧底兩指針的目的是便于判斷棧是否為空
    int StackSize; //棧的當(dāng)前可使用的大容量.
    }SqStack;
    順序棧的的模塊說明:
    struct STACK {
    SElemType *base;
    SElemType *top;
    int stacksize;
    };
    typedef struct STACK Sqstack;
    Status InitStack(SqStack &S);
    Status DestroyStack(SqStack &S);
    Status ClearStack(SqStack &S);
    Status StackEmpty(SqStack S);
    int StackLength(SqStack S);
    Status GetTop(SqStack S,SElemType &e);
    Status Push(SqStack &S,SElemType e);
    Status Pop(SqStack &S,SElemType &e);
    Status StackTraverse(SqStack S,Status (*visit)());
    Status InitStack(SqStack &S) {
    S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
    if(!S.base)exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INI_SIZE;
    return OK;
    }//IniStack
    Status DestroyStack(SqStack &S); {
    }//DestroyStack
    Status ClearStack(SqStack &S); {
    S.top=S.base;
    } //ClearStack
    Status StackEmpty(SqStack S); {
    if(S.top==S.base) return TRUE;
    else return FALSE;
    } //StackEmpty
    int StackLength(SqStack S); {
    int i; SElemType *p;
    i=0;
    p=S.top;
    while(p!=S.base) {p++; i++; }
    } //stackLength
    Status GetTop(SqStack S,SElemType &e); {
    if(S.top==S.base) return ERROR;
    e=*(S.top-1);
    return OK;
    } //GetTop
    Status Push(SqStack &S,SElemType e); {
    if(S.top - s.base>=S.stacksize) {
    S.base=(ElemType *) realloc(S.base,
    (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
    if(!S.base)exit(OVERFLOW);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACKINCREMENT;
    } *S.top++=e;
    return OK;
    } //Push
    Status Pop(SqStack &S,SElemType &e); {
    if(S.top==S.base)
    return ERROR;
    e=*--S.top;
    return OK;
    }//Pop
    Status StackTraverse(SqStack S,Status (*visit)()); {
    }//StackTraverse
    以上偽代碼的C語言源碼
    三、總結(jié)
    棧的定義
    棧的順序存儲實(shí)現(xiàn)