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

简介:

说明:

    往前学习数据结构,想运行一个完整的顺序栈的程序都运行不了,因为书上给的都是一部分一部分的算法,并没有提供一个完整可运行的程序,听了实验课,自己折腾了一下,总算可以写一个比较完整的顺序栈操作的小程序,对于栈也慢慢开始有了感觉。下面我会把整个程序拆开来做说明,只要把这些代码放在一个文件中,用编译器就可以直接编译运行了。





一、实现


1.程序功能

  关于栈操作的经典程序,首当要提及进制数转换的问题,利用栈的操作,就可以十分快速地完成数的进制转换。




2.预定义、头文件导入和类型别名

    代码如下:

1
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;

    除了两个头文件的导入是必须的之外,下面做两点说明:

(1)其余的常量定义都是可选的,为的就是在下面的代码书写过程中可以尽量使用英文来表达程序的意思,而不是在代码的实现过程中直接使用数字,依个人喜欢,也可以直接使用数字;

(2)使用typedef做类型的别名也仅仅是为了程序中代码的意思更加清晰明了而已,实际也可以不这样使用;




3.顺序栈的定义

    代码如下:

1
2
3
4
5
6
typedef struct{
     ElemType *elem;      //存储空间的基址
     int  top;             //栈顶元素的下一个元素,简称栈顶位标
     int  size;            //当前分配的存储容量,作用看入栈操作就可以知道
     int  increment;       //扩容时,增加的存储容量,作用看入栈操作就可以知道
} SqStack;                   //顺序栈名称




4.栈的初始化

    代码如下:

1
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
}




5.空栈的判断

    代码如下:

1
2
3
4
5
6
7
8
Status StackEmpty_Sq(SqStack S){
     if (S.top ==  0 )
         return  TRUE;
     else
         return  FALSE;
}
//空栈的决断是,如果栈为空就返回1,否则就返回0,当然可以不这样规定;
//至于为什么要做空栈的判断,自然是有原因的,下面再看程序的代码时就可以知道了。




6.入栈

    代码如下:

1
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
}




7.出栈

    代码如下:

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;
}




8.进制转换的函数

    其实上面的步骤操作都是为了创建一个顺序栈和定义顺序栈的操作而已,并对可能出现的各种情况做一些相应的举措,完毕后,下面就要使用上面创建的顺序栈以及栈的操作接口了,即在数制转换函数(这里是十进制转八进制)中使用上面的操作接口,代码如下:

1
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);  //打印元素
     }




9.main函数

    进制转换函数调用栈操作的接口函数,以实现在数制转换过程中栈的操作;main函数调用数制转换函数,以实现数制的转换,代码如下:

1
2
3
4
5
int  main( void ){
     printf( "Enter a number:" );scanf( "%d" ,&num);
     Converstion(num);
     printf( "\n" );
}





二、执行

    有了上面的代码后,就可以在编译器中编译执行了,这里我是用c free 5来进行程序代码的编译:


(1)输入的数为1348时的结果:

wKiom1X-bHCSWO55AADAAgjs3ew463.jpg


(2)输入的数为2526时的结果:

wKioL1X-bsDTXhERAADDp63JNCE633.jpg





三、完整的代码

    下面把代码都放在一起:

1
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" );
}

相关文章
|
6月前
|
存储 算法
数据结构— —栈的基本操作(顺序栈和链栈)
数据结构— —栈的基本操作(顺序栈和链栈)
|
6月前
|
存储 NoSQL C语言
数据结构——顺序栈与链式栈的实现-2
数据结构——顺序栈与链式栈的实现
数据结构——顺序栈与链式栈的实现-2
|
6月前
|
存储 C语言
数据结构——顺序栈与链式栈的实现-1
数据结构——顺序栈与链式栈的实现
数据结构——顺序栈与链式栈的实现-1
|
6月前
|
C++
数据结构(顺序栈
数据结构(顺序栈
29 2
|
5月前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
36 0
|
6月前
|
C语言
数据结构中顺序栈的进栈和出栈用C语言表示
数据结构中顺序栈的进栈和出栈用C语言表示
47 1
|
6月前
|
存储 编译器 C语言
【数据结构】C语言实现顺序栈(附完整运行代码)
【数据结构】C语言实现顺序栈(附完整运行代码)
221 0
|
C语言
【数据结构】链栈的基本操作C语言完整代码(初始化,判栈空,入栈,出栈,取栈顶元素,求栈长)
【数据结构】链栈的基本操作C语言完整代码(初始化,判栈空,入栈,出栈,取栈顶元素,求栈长)
495 0
|
测试技术
【数据结构】顺序栈的原理及实现
【数据结构】顺序栈的原理及实现
【数据结构】顺序栈的原理及实现