【数据结构之旅】顺序栈的定义、初始化、空栈判断、入栈、出栈操作

2

3

4

5

6

7

8

9

10

#include<stdio.h>

#include<stdlib.h>

#define OVERFLOW -1

#define ERROR 0

#define FALSE 0

#define TRUE 1

#define OK 1

typedef int ElemType;

typedef int Status;

2

3

4

5

6

typedef struct{

    ElemType *elem;     //存储空间的基址

    int top;            //栈顶元素的下一个元素，简称栈顶位标

    int size;           //当前分配的存储容量，作用看入栈操作就可以知道

    int increment;      //扩容时，增加的存储容量，作用看入栈操作就可以知道

} SqStack;                  //顺序栈名称

2

3

4

5

6

7

8

Status InitStack_Sq(SqStack &S, int size, int inc){     //接受3个参数，&S是对结构体的引用

    S.elem = (ElemType*)malloc(size*sizeof(ElemType));  //分配存储空间

    if(S.elem == NULL) return OVERFLOW;     //判断上一步分配存储空间是否成功

    S.top = 0;            //置S为空栈，S.top为0即表示栈为空栈

    S.size = size;        //栈的空间初始容量值

    S.increment = inc;    //栈的空间初始增量值（如果需要扩容）

    return OK;       //上面的执行正常，返回OK

}

2

3

4

5

6

7

8

Status StackEmpty_Sq(SqStack S){

    if(S.top == 0)

        return TRUE;

    else

        return FALSE;

}

//空栈的决断是，如果栈为空就返回1，否则就返回0，当然可以不这样规定；

//至于为什么要做空栈的判断，自然是有原因的，下面再看程序的代码时就可以知道了。

2

3

4

5

6

7

8

9

10

11

12

13

14

Status Push_Sq(SqStack &S, ElemType e){    //将元素e压入栈，这里e只是一个形参而已

    ElemType *newbase;        //定义中间变量

    if(S.top>= S.size){        //S.top如果指向最后一个不存储元素的地址时，即S.top大于

        newbase = (ElemType*)realloc(S.elem, //等于S.size时，就表示栈满了

    (S.size + S.increment)*sizeof(ElemType)); //通过realloc动态扩容

    if(NULL == newbase) return OVERFLOW; //判断扩容是否成功

    S.elem = newbase;      //扩容成功后才将中间变量的值指向S.elem，防止扩容失败时，

    S.size = S.size + S.increment;     //S.elem指向一个不是原来的位置

    }

    S.elem[S.top] = e;    //将e元素入栈

    S.top++;              //使S.top加1，表示指向的是栈顶位标

    return OK;            //上面操作正常后返回1

}

2

3

4

5

Status Pop_Sq(SqStack &S, ElemType &e){    //栈顶元素出栈，赋给元素e

    if(0 == S.top) return ERROR;    

    e = S.elem[--S.top];    //e出栈，并将S.top减1

    return OK;

}

2

3

4

5

6

7

8

9

10

11

12

13

14

void Converstion(int N){

    SqStack S;

    ElemType e;

    InitStack_Sq(S, 10, 5);    //栈S的初始容量置为10，每次扩容容量为5

    while(N != 0){

        Push_Sq(S, N%8);   //将N除以8的余数入栈

        N /= 8;            //N取值为其除以8的商

    }                          //理论基础为除8取余法

    while(StackEmpty_Sq(S) == FALSE){

        Pop_Sq(S, e);    //依次输出栈中的余数，并赋给元素e

        printf("%d", e); //打印元素

    }

2

3

4

5

int main(void){

    printf("Enter a number:");scanf("%d",&num);

    Converstion(num);

    printf("\n");

}

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

#include<stdio.h>

#include<stdlib.h>

#define OVERFLOW -1

#define ERROR 0

#define FALSE 0

#define TRUE 1

#define OK 1

typedef int ElemType;

typedef int Status;

typedef struct{

    ElemType *elem;

    int top;

    int size;

    int increment;

} SqStack;

Status InitStack_Sq(SqStack &S, int size, int inc){

    S.elem = (ElemType*)malloc(size*sizeof(ElemType));

    if(S.elem == NULL) return OVERFLOW;

    S.top = 0;

    S.size = size;

    S.increment = inc;

    return OK;

}

Status StackEmpty_Sq(SqStack S){

    if(S.top == 0)

        return TRUE;

    else

        return FALSE;

}

Status Push_Sq(SqStack &S, ElemType e){

    ElemType *newbase;

    if(S.top>= S.size){

        newbase = (ElemType*)realloc(S.elem,

    (S.size + S.increment)*sizeof(ElemType));

    if(NULL == newbase) return OVERFLOW;

    S.elem = newbase;

    S.size = S.size + S.increment;

    }

    S.elem[S.top] = e;

    S.top++;

    return OK;

}

Status Pop_Sq(SqStack &S, ElemType &e){

    if(0 == S.top) return ERROR;

    e = S.elem[--S.top];

    return OK;

}

void Converstion(int N){

    SqStack S;

    ElemType e;

    InitStack_Sq(S, 10, 5);

    while(N != 0){

        Push_Sq(S, N%8);

        N /= 8;

    }

    while(StackEmpty_Sq(S) == FALSE){

        Pop_Sq(S, e);

        printf("%d", e);

    }

}

int main(void){

    int num;

    printf("Enter a number:");scanf("%d",&num);

    Converstion(num);

    printf("\n");

}