要求编写功能函数实现堆栈的定义,基于链栈:按用户要求输入元素,编写进栈函数push();编写出栈函数pop();编写判断栈满和栈空的函数 ;遍历栈,并输出元素;输入数据实现十进制到二进制的转换。c语言实现完整代码,并给出算法流程
时间: 2024-05-14 09:13:59 浏览: 7
以下是基于链栈的堆栈定义的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 定义栈的最大容量
typedef struct Node {
int data;
struct Node *next;
} Node, *Stack;
// 初始化栈
void InitStack(Stack *S) {
*S = NULL;
}
// 判断栈是否为空
int IsEmpty(Stack S) {
return S == NULL;
}
// 判断栈是否已满(链栈不存在满栈的情况)
int IsFull(Stack S) {
return 0;
}
// 进栈
void Push(Stack *S, int x) {
Node *p = (Node*)malloc(sizeof(Node));
p->data = x;
p->next = *S;
*S = p;
}
// 出栈
void Pop(Stack *S, int *x) {
if (IsEmpty(*S)) {
printf("Stack is empty.\n");
return;
}
Node *p = *S;
*x = p->data;
*S = p->next;
free(p);
}
// 遍历栈
void Traverse(Stack S) {
printf("Stack elements: ");
while (S != NULL) {
printf("%d ", S->data);
S = S->next;
}
printf("\n");
}
// 十进制转二进制
void Dec2Bin(Stack *S, int n) {
while (n != 0) {
Push(S, n % 2);
n = n / 2;
}
}
int main() {
Stack S;
InitStack(&S);
int x;
printf("Enter the elements of stack (end with -1):\n");
while (1) {
scanf("%d", &x);
if (x == -1) break;
Push(&S, x);
}
Traverse(S);
Pop(&S, &x);
printf("Pop element: %d\n", x);
Traverse(S);
printf("Enter a decimal number: ");
scanf("%d", &x);
Dec2Bin(&S, x);
printf("Binary number: ");
Traverse(S);
return 0;
}
```
算法流程:
1. 定义一个结构体Node,包含数据域和指向下一个节点的指针;
2. 定义一个Stack类型的指针,代表链栈;
3. 初始化栈,将栈顶指针置为NULL;
4. 判断栈是否为空,如果栈顶指针为NULL,则栈为空;
5. 判断栈是否已满,链栈不存在满栈的情况,直接返回0;
6. 进栈,新建一个节点,将数据域赋值为x,将节点的next指针指向栈顶,将栈顶指针指向新节点;
7. 出栈,判断栈是否为空,如果为空,则输出提示信息并返回;否则,取出栈顶元素,将栈顶指针指向下一个节点,释放原栈顶节点;
8. 遍历栈,从栈顶开始遍历链表,输出每个节点的数据域;
9. 十进制转二进制,将十进制数n不断除以2,将余数进栈,直到n为0;
10. 主函数调用以上函数实现堆栈的各种操作。