热门标签
热门文章
- 1jupyter训练模型后C盘内存减少的问题_运行jupyter会让c盘减少
- 2CentOS7安装Oracle完整教程（超级详细，亲测完美）(1)_centos 安装oracle
- 3计算机视觉三大会议_计算机视觉三大顶级会议
- 4在arm板Ubuntu系统上安装mediapipe简单记录_mediapipe arm linux
- 5Charles修改响应参数_charles工具修改响应参数值的分享
- 6C# & Unity 面向对象补全计划 之 画UML类图（持续更新）
- 7springcloud之eureka服务注册中心POM配置
- 8git 如何回滚到某个节点_git 回退到某个节点
- 9是什么原因导致程序员写代码的效率很低_敲代码效率低
- 10[Share]17个免费下载电子书的网站
当前位置: article > 正文
数据结构——栈的链式存储（优缺点及代码实现:C语言）_链栈的特点
作者：一键难忘520 | 2024-07-30 23:46:02
赞
踩
链栈的特点
链式存储优缺点
链栈(运算受限的单链表)，只能在栈的一端（栈顶）进行入栈和出栈，所以是先进后出或是后进先出的链表。
优点：
1.基本不会出现栈满上溢情况
2.灵活性高：链栈的容量可以动态调整，不受固定大小的限制。
3.插入和删除操作效率高：由于链栈是基于链表实现的，插入和删除操作的时间复杂度为O(1)，效率较高，都在栈顶直接操作。
缺点：
1.存储空间消耗较大：链栈需要额外的空间来存储指针，使得存储空间的消耗相对于顺序栈来说较大。
2.访问元素的效率较低：由于链栈是基于链表实现的，访问元素的时间复杂度为O(n)，效率较低。
3.对内存的要求较高：由于链栈需要动态分配内存空间，对内存的要求较高。
代码实现（C语言）
定义链栈
/*栈子系统*/
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 100 /*数组最大长度为100*/
typedef int DataType; /*定义DataType为int类型*/
typedef struct StackNode /*链栈存储类型*/
{
DataType data; /*定义结点的数据域*/
struct StackNode *next; /*定义结点的指针域*/
} LinkStack;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
初始化链栈
不需要定义头节点，*S既代表链栈又代表头指针
LinkStack *InitStack()
{
LinkStack *S;
S = NULL;
return S;
}
- 1
- 2
- 3
- 4
- 5
- 6
判栈空
int EmptyStack(LinkStack *S)
{
if(S == NULL)
return 1;
else
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
入栈
LinkStack *Push(LinkStack *S,DataType x)
{ /*进栈函数*/
LinkStack *p = (LinkStack *)malloc(sizeof(LinkStack));/*生成新结点*/
if(!p)
{
printf("内存分配失败");
return 0;
}
p->data=x; /*将x放入新结点的数据域*/
p->next=S; /*将新结点插入链表表头之前*/
S=p; /*新结点作为栈顶*/
return S; /*返回栈顶S*/
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
出栈
LinkStack *Pop(LinkStack *S,DataType *x) { /*出栈函数*/ LinkStack *p; if(EmptyStack(S)) /*调用判空函数EmptyStack(S)，判断栈是否为空*/ { printf("\t栈空，不能出栈!"); return NULL; /*栈空不能出栈*/ } else /*栈不为空*/ { *x=S->data; /*栈顶元素取出赋给x*/ p=S; /*p结点指向原栈顶S*/ S=S->next; /*原栈顶S指向其下一个结点*/ free(p); /*释放原栈顶空间*/ return S; /*返回栈顶S*/ } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
获取栈顶
int GetTop(LinkStack *S, DataType *x)
{
if(EmptyStack(S))
{
printf("栈空，不能取栈顶！");
return 0;
}
*x = S->data;
return 1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
获取栈中元素
void ShowStack(LinkStack *S) { LinkStack *p = S; if(p == NULL) printf("栈空！"); else { printf("从栈顶元素起栈中各元素为："); while(p != NULL) { printf("%d",p->data); p = p->next; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
十、二进制数转换
void D_B(LinkStack *S,DataType x)
{
while(x)
{
S=Push(S,x%2); /*余数入栈*/
x/=2; /*被除数data整除以2，得到新的被除数*/
}
printf("转换后的二进制为：");
while (!EmptyStack(S))
{
S=Pop(S,&x); /*依次从栈中弹出每一个余数并输出*/
printf("%d",x);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
表达式转换并求值
void trans(char *exp,char *postexp) { /*将中缀表达式转换成后缀表达式函数*/ struct { char data[MAXSIZE]; int top; } op; /*运算符栈*/ int i=0; op.top=-1; while(*exp!='#') /*当表达式没结束时*/ { switch(*exp) /*判断表达式的每个字符*/ { case '(': /*当字符为'('时*/ op.top++;op.data[op.top]=*exp; /*栈顶指针增1，运算符入栈*/ exp++; /*中缀表达式指针增1*/ break; case ')': /*当字符为')'时*/ while(op.data[op.top]!='(') /*只要运算符栈顶元素不是'('时*/ { postexp[i++]=op.data[op.top]; /*将栈顶运算符写入后缀表达式数组中*/ op.top--; /*栈顶指针减1*/ } op.top--;exp++; /*栈顶指针减1，表达式指针加1*/ break; case '+': case '-': while(op.top!=-1&&op.data[op.top]!='(') /*运算符栈不为空且栈顶元素不为'('时*/ { postexp[i++]=op.data[op.top]; /*将栈顶运算符写入后缀表达式数组中*/ op.top--; /*运算符栈顶指针减1*/ } op.top++; /*运算符栈顶指针加1*/ op.data[op.top]=*exp; /*将中缀表达式元素入符号栈*/ exp++; /*中缀表达式指针加1*/ break; case '*': case '/': while(op.data[op.top]=='*'||op.data[op.top]=='/') /*当栈顶元素不是'*'和'/'时*/ { postexp[i++]=op.data[op.top]; /*栈顶运算符写到后缀表达式数组中*/ op.top--; /*栈顶指针减1*/ } op.top++;/*栈顶指针加1*/ op.data[op.top]=*exp; /*中缀表达式的元素入栈*/ exp++; /*表达式指针加1*/ break; case ' ':break; default: while(*exp>='0'&&*exp<='9') /*当表达式对象是数字时*/ { postexp[i++]=*exp; /*将数字写到后缀表达式数组中*/ exp++; /*中缀指针加1*/ } postexp[i++]='#'; /*将每个操作数之间增加分隔符'#'*/ } } while(op.top!=-1) /*当运算符栈不为空时*/ { postexp[i++]=op.data[op.top]; /*将栈顶运算符写入后缀表达式数组中*/ op.top--; /*栈顶指针减1*/ } postexp[i]='\0'; /*为后缀表达式加一个结束标志*/ } float compvalue(char *postexp) { /*根据后缀表达式求值函数*/ struct { float data[MAXSIZE]; int top; } st; /*数栈结点类型*/ float a,b,c,d; st.top=-1; /*栈顶指针赋初值-1*/ while(*postexp!='\0') /*当后缀表达式没结束时*/ { switch(*postexp) { case '+': a=st.data[st.top]; /*数栈顶元素赋给变量a*/ st.top--; /*栈顶指针减1*/ b=st.data[st.top]; /*数栈顶元素赋给变量b*/ st.top--; /*栈顶指针减1*/ c=b+a; /*将a加b的结果存入变量c*/ st.top++; /*栈顶指针加1*/ st.data[st.top]=c; /*将变量c入栈*/ break; case '-': a=st.data[st.top]; st.top--; b=st.data[st.top]; st.top--; c=b-a; st.top++; st.data[st.top]=c; break; case '*': a=st.data[st.top]; st.top--; b=st.data[st.top]; st.top--; c=b*a; st.top++; st.data[st.top]=c; break; case '/': a=st.data[st.top]; st.top--; b=st.data[st.top]; st.top--; if(a!=0) { c=b/a; st.top++; st.data[st.top]=c; } else printf("\n\t除零错误!\n"); break; default: /*后缀表达式的字符是数字字符时，将其转换为整数*/ d=0; while(*postexp>='0'&&*postexp<='9') { d=10*d+*postexp-'0'; postexp++; } st.top++; st.data[st.top]=d; /*将转换之后的整数入栈*/ break; } postexp++; } return st.data[st.top]; /*返回数栈的栈顶元素即为所求的结果*/ }
- 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
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
完整示例（C语言实现）
/*栈子系统*/ #include <stdio.h> #include <malloc.h> #define MAXSIZE 100 /*数组最大长度为100*/ typedef int DataType; /*定义DataType为int类型*/ typedef struct StackNode /*链栈存储类型*/ { DataType data; /*定义结点的数据域*/ struct StackNode *next; /*定义结点的指针域*/ } LinkStack; LinkStack *InitStack() { /*初始化链栈函数*/ LinkStack *S; S=NULL; return S; /*初始化栈为空*/ } int EmptyStack(LinkStack *S) { /*判断栈空函数*/ if(S==NULL) /*栈为空*/ return 1; else return 0; } LinkStack *Push(LinkStack *S,DataType x) { /*进栈函数*/ LinkStack *p; p=(LinkStack *)malloc(sizeof(LinkStack));/*生成新结点*/ if(!p) { printf("内存分配失败"); return 0; } p->data=x; /*将x放入新结点的数据域*/ p->next=S; /*将新结点插入链表表头之前*/ S=p; /*新结点作为栈顶*/ return S; /*返回栈顶S*/ } LinkStack *Pop(LinkStack *S,DataType *x) { /*出栈函数*/ LinkStack *p; if(EmptyStack(S)) /*调用判空函数EmptyStack(S)，判断栈是否为空*/ { printf("\t栈空，不能出栈!"); return NULL; /*栈空不能出栈*/ } else /*栈不为空*/ { *x=S->data; /*栈顶元素取出赋给x*/ p=S; /*p结点指向原栈顶S*/ S=S->next; /*原栈顶S指向其下一个结点*/ free(p); /*释放原栈顶空间*/ return S; /*返回栈顶S*/ } } int GetTop(LinkStack *S,DataType *x) { /*获取栈顶元素函数*/ if(EmptyStack(S)) /*调用判空函数EmptyStack(S)，判断栈是否为空*/ { printf("栈空!"); return 0; } else /*栈不为空*/ { *x=S->data; /*栈顶元素赋给变量x*/ return 1; } } void ShowStack(LinkStack *S) { LinkStack *p=S; if(p==NULL) printf("\t栈空！"); else { printf("从栈顶元素起栈中各元素为："); while(p!=NULL) { printf("%d ",p->data); p=p->next; } } } void D_B(LinkStack *S,DataType x) { while(x) { S=Push(S,x%2); /*余数入栈*/ x/=2; /*被除数data整除以2，得到新的被除数*/ } printf("转换后的二进制为："); while (!EmptyStack(S)) { S=Pop(S,&x); /*依次从栈中弹出每一个余数并输出*/ printf("%d",x); } } void trans(char *exp,char *postexp) { /*将中缀表达式转换成后缀表达式函数*/ struct { char data[MAXSIZE]; int top; } op; /*运算符栈*/ int i=0; op.top=-1; while(*exp!='#') /*当表达式没结束时*/ { switch(*exp) /*判断表达式的每个字符*/ { case '(': /*当字符为'('时*/ op.top++;op.data[op.top]=*exp; /*栈顶指针增1，运算符入栈*/ exp++; /*中缀表达式指针增1*/ break; case ')': /*当字符为')'时*/ while(op.data[op.top]!='(') /*只要运算符栈顶元素不是'('时*/ { postexp[i++]=op.data[op.top]; /*将栈顶运算符写入后缀表达式数组中*/ op.top--; /*栈顶指针减1*/ } op.top--;exp++; /*栈顶指针减1，表达式指针加1*/ break; case '+': case '-': while(op.top!=-1&&op.data[op.top]!='(') /*运算符栈不为空且栈顶元素不为'('时*/ { postexp[i++]=op.data[op.top]; /*将栈顶运算符写入后缀表达式数组中*/ op.top--; /*运算符栈顶指针减1*/ } op.top++; /*运算符栈顶指针加1*/ op.data[op.top]=*exp; /*将中缀表达式元素入符号栈*/ exp++; /*中缀表达式指针加1*/ break; case '*': case '/': while(op.data[op.top]=='*'||op.data[op.top]=='/') /*当栈顶元素不是'*'和'/'时*/ { postexp[i++]=op.data[op.top]; /*栈顶运算符写到后缀表达式数组中*/ op.top--; /*栈顶指针减1*/ } op.top++;/*栈顶指针加1*/ op.data[op.top]=*exp; /*中缀表达式的元素入栈*/ exp++; /*表达式指针加1*/ break; case ' ':break; default: while(*exp>='0'&&*exp<='9') /*当表达式对象是数字时*/ { postexp[i++]=*exp; /*将数字写到后缀表达式数组中*/ exp++; /*中缀指针加1*/ } postexp[i++]='#'; /*将每个操作数之间增加分隔符'#'*/ } } while(op.top!=-1) /*当运算符栈不为空时*/ { postexp[i++]=op.data[op.top]; /*将栈顶运算符写入后缀表达式数组中*/ op.top--; /*栈顶指针减1*/ } postexp[i]='\0'; /*为后缀表达式加一个结束标志*/ } float compvalue(char *postexp) { /*根据后缀表达式求值函数*/ struct { float data[MAXSIZE]; int top; } st; /*数栈结点类型*/ float a,b,c,d; st.top=-1; /*栈顶指针赋初值-1*/ while(*postexp!='\0') /*当后缀表达式没结束时*/ { switch(*postexp) { case '+': a=st.data[st.top]; /*数栈顶元素赋给变量a*/ st.top--; /*栈顶指针减1*/ b=st.data[st.top]; /*数栈顶元素赋给变量b*/ st.top--; /*栈顶指针减1*/ c=b+a; /*将a加b的结果存入变量c*/ st.top++; /*栈顶指针加1*/ st.data[st.top]=c; /*将变量c入栈*/ break; case '-': a=st.data[st.top]; st.top--; b=st.data[st.top]; st.top--; c=b-a; st.top++; st.data[st.top]=c; break; case '*': a=st.data[st.top]; st.top--; b=st.data[st.top]; st.top--; c=b*a; st.top++; st.data[st.top]=c; break; case '/': a=st.data[st.top]; st.top--; b=st.data[st.top]; st.top--; if(a!=0) { c=b/a; st.top++; st.data[st.top]=c; } else printf("\n\t除零错误!\n"); break; default: /*后缀表达式的字符是数字字符时，将其转换为整数*/ d=0; while(*postexp>='0'&&*postexp<='9') { d=10*d+*postexp-'0'; postexp++; } st.top++; st.data[st.top]=d; /*将转换之后的整数入栈*/ break; } postexp++; } return st.data[st.top]; /*返回数栈的栈顶元素即为所求的结果*/ } void MenuStack() { /*显示菜单子函数*/ printf("\n 栈子系统"); printf("\n=================================================="); printf("\n| 1——初始化栈 |"); printf("\n| 2——入栈操作 |"); printf("\n| 3——出栈操作 |"); printf("\n| 4——求栈顶元素 |"); printf("\n| 5——显示栈中元素 |"); printf("\n| 6——十、二进制数转换 |"); printf("\n| 7——表达式转换并求值 |"); printf("\n| 0——返回 |"); printf("\n=================================================="); printf("\n请输入菜单号（0-7）:"); } main() { int i,n,flag; LinkStack *S; DataType x; char ch1,ch2,a; char exp[MAXSIZE],postexp[MAXSIZE]; /*求表达式值的两个数组*/ ch1='y'; while(ch1=='y'||ch1=='Y') { MenuStack(); scanf("%c",&ch2); getchar(); switch(ch2) { case '1': S=InitStack(); printf("栈的初始化完成！"); break; case '2': printf("请输入要入栈的元素个数："); scanf("%d",&n); printf("请输入%d个整数进行入栈：",n); for(i=0;i<n;i++) { scanf("%d",&x); S=Push(S,x); } printf("入栈成功！"); break; case '3': printf("请输入要出栈的元素个数："); scanf("%d",&n); printf("出栈的元素为："); for(i=0;i<n;i++) { S=Pop(S,&x); if(S!=NULL) printf("%5d",x); } break; case '4': if(flag=GetTop(S,&x)) printf("当前的栈顶元素值为：%d",x); break; case '5': ShowStack(S); break; case '6': S=InitStack(); printf("请输入十进制正整数为:"); scanf("%d",&x); /*输入十进制正整数*/ D_B(S,x); /*调用进制转换函数*/ break; case '7': printf("请输入算术表达式（只有+、-、*、/四种运算符），以'#'结束："); scanf("%s",&exp); trans(exp,postexp); printf("则该表达式的中缀表达式为：%s\n",exp); printf("转换之后的后缀表达式为（每个操作数用“#”分隔）：%s\n",postexp); printf("表达式的值为:%.2f\n",compvalue(postexp)); break; case '0': ch1='n';break; default: printf("输入有误，请输入0-5进行选择！"); } if(ch2!='0') { printf("\n按回车键继续，按任意键返回主菜单！\n"); a=getchar(); if(a!='\xA') { getchar();ch1='n'; } } } }
- 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
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
结语
敬请各位大佬批评指正 日后也会持续更新数据结构相关内容，互相学习声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/905870推荐阅读
相关标签
Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。
