服务器之家

服务器之家 > 正文

C语言数据结构 栈的基础操作

时间：2021-05-12 16:06     来源/作者：c406495762

C语言数据结构 栈的基础操作

实现了栈的基本操作，包括入栈出栈，以及书上没有写的销毁栈等操作，并对代码进行了详细的注释

MyStack.h

?
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
/*
 * Include.h
 *
 * Created on: 2016.11.23
 *   Author: Jack Cui
 */
 
#ifndef MYSTACK_H_
#define MYSTACK_H_
 
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
/*栈(Stack)是限定仅在表尾进行插入或删除操作的线性表
**栈顶(top)和栈底(bottom)相等，代表为空栈
**
*/
 
//SElemType是某个确定的、将由用户自行定义的、含某个关系运算的数据对象
typedef int SElemType;
 
//函数结果状态代码
#define TRUE    1 
#define FALSE    0
#define OK     1
#define ERROR    0
#define INFEASIBLE -1   //不可行
#define MY_OVERFLOW -2   //溢出
 
/**********栈的顺序存储表示**********/
#define STACK_INIT_SIZE 100   //存储空间初始分配量
#define STACKINCREMENT 10   //存储空间分配增量
 
typedef struct{
  SElemType *base;  //在栈构造之前和销毁之后，base的值为NULL
  SElemType *top;   //栈顶指针
  int stacksize;   //当前已分配
}SqStack;
/**********基本操作的函数原型说明**********/
//构造一个空栈S
Status InitStack(SqStack &S);     
//销毁栈S，S不再存在
Status DestroyStack(SqStack &S);
//把S置为空栈
Status ClearStack(SqStack &S);
//若栈S为空栈，则返回TURE，否则返回FALSE
Status StackEmpty(SqStack S);
//返回S的元素个数，即栈的长度
int StackLength(SqStack S);
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
Status GetTop(SqStack S, SElemType &e);
//插入元素e为新的栈顶元素
Status Push(SqStack &S, SElemType e);
//若栈不空，则删除S的栈顶元素，用e新栈顶的值，并返回OK;否则返回ERROR;
Status Pop(SqStack &S, SElemType &e);
//从栈底到栈顶依次对栈中每个元素调用函数visit();一旦visit()失败，则操作失败
Status StackTraverse(SqStack S, Status(* visit)(SElemType));
//visit()函数
Status visit(SElemType e);
//测试函数
Status TestMyStack();
 
#endif MYSTACK_H_

MyStack.c

?
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "MyStack.h"
 
Status InitStack(SqStack &S){
  //构造一个空栈S
  S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
  if(!S.base){    //存储分配失败
    printf("InitStack: malloc err\n");
    exit(MY_OVERFLOW);
  }
  S.top = S.base;
  S.stacksize = STACK_INIT_SIZE;
  return OK;
}//InitStack
 
Status DestroyStack(SqStack &S){
  if(!S.base){
    printf("DestroyStack: Stack does not exist\n");
    exit(MY_OVERFLOW);
  }
//在调用malloc的时候，系统会记住你申请的这块连续空间的起始地址以及这块空间的大小，
//释放free的时候，只要把这个起始地址告诉系统，系统自然就知道要释放多大的空间。
  free(S.base);   
  S.top = NULL;
  S.base = NULL;
  S.stacksize = 0;
  return OK;
}//DestroyStack
 
Status ClearStack(SqStack &S){
  if(!S.base){
    printf("ClearStack: Stack does not exist\n");
    exit(MY_OVERFLOW);
  }
  S.top = S.base;
  return OK;
}//ClearStack
 
Status StackEmpty(SqStack S){
  if(S.top == S.base){
    return TRUE;
  }
  else{
    return FALSE;
  }
}//StackEmpty
 
int StackLength(SqStack S){
  return S.top - S.base;
}//StackLength
 
Status GetTop(SqStack S, SElemType &e){
  ////若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
  if(S.top == S.base){
    printf("GetTop: Stack is empty\n");
    return ERROR;
  }
  e = *(S.top - 1);
  return OK;
}//GetTop
 
Status Push(SqStack &S, SElemType e){
  //插入元素e为新的栈顶元素
  if(S.top - S.base >= S.stacksize){ //栈满，追加存储空间
    S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
    if(!S.base){
      printf("Push: realloc error\n");
    }
    S.top = S.base + S.stacksize;
    S.stacksize += STACKINCREMENT;
  }
  *S.top++ = e;    //*S.top = e; S.top++;
  return OK;
}//Push
 
Status Pop(SqStack &S, SElemType &e){
  //若栈不空，则删除S的栈顶元素，用e返回新栈顶的值，并返回OK，否则返回ERROR;
  if(S.top == S.base){
    printf("Pop: Stack is empty\n");
    return ERROR;
  }
  e = *--S.top;    //S.top--; e = *S.top;
  return OK;
}//Pop
 
Status StackTraverse(SqStack S, Status(* visit)(SElemType)){
  while(S.top > S.base){
    visit(*S.base++);
  }
  printf("\n");
  return OK;
}//StackTraverse
 
Status visit(SElemType e){
  printf("%d ",e) ;
  return OK;
}//visit
 
Status TestMyStack(){
  SElemType j;
  SqStack s;
  SElemType e;
 
  if(InitStack(s) == OK)
  for(j = 1; j <= 12; j++)
  {
    Push(s,j);
  }
  printf("栈中的元素依次为：");
  StackTraverse(s,visit);
  Pop(s, e);
  printf("弹出的栈顶元素 e=%d\n", e);
  printf("栈空否：%d(1：是 0：否)\n", StackEmpty(s));
  GetTop(s, e);
  printf("栈顶元素 e=%d,栈的长度为%d\n", e, StackLength(s));
  ClearStack(s);
  printf("清栈后，栈是否为空：%d(1：空 0：否)\n",StackEmpty(s));
  DestroyStack(s);
  printf("销毁栈后，s.top = %u s.base= %u s.stacksize=%d\n",s.top,s.base,s.stacksize);
  return 0;
}//TestMyStack
 
//主函数
int main(){
  TestMyStack();
  system("pause");
  return 0;
}

运行结果

C语言数据结构 栈的基础操作

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

原文链接：http://blog.csdn.net/c406495762/article/details/53326915

标签：
C语言 栈 

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部