/** * 实验题目: * 实现链栈各种基本运算的算法 * 实验内容: * 编写程序,实现链栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能: * (1)初始化链栈s * (2)判断链栈s是否非空 * (3)依次进链栈元素a,b,c,d,e * (4)判断链栈s是否非空 * (5)输出链栈长度 * (6)输出从栈顶到栈底元素 * (7)输出链栈序列 * (8)判断链栈s是否非空 * (9)释放链栈 */
#include <stdio.h> #include <malloc.h>
typedef char ElemType; typedef struct linknode { ElemType data; // 数据域 struct linknode *next; // 指针域 }LiStack;
/*--------------------------初始化栈s---------------------------*/ void InitStack(LiStack *&s) // 指针的引用 { s = (LiStack *)malloc(sizeof(LiStack)); s->next = NULL; }
/*--------------------------释放栈s---------------------------*/ void ClearStack(LiStack *&s) { LiStack *p = s->next; while(p != NULL) { free(s); s = p; p = p->next; } }
/*--------------------------求栈s的长度---------------------------*/ int StackLength(LiStack *s) { int i = 0; LiStack *p; p = s->next; while(p != NULL) { i++; p = p->next; } return i; }
/*--------------------------判断栈s是否为空栈---------------------------*/ int StackEmpty(LiStack *s) { return (s->next == NULL); }
/*--------------------------进栈元素e---------------------------*/ void Push(LiStack *&s, ElemType e) { LiStack *p; p = (LiStack *)malloc(sizeof(LiStack)); p->data = e; p->next = s->next; s->next = p; }
/*--------------------------出栈一个元素---------------------------*/ int Pop(LiStack *&s, ElemType &e) { LiStack *p; if(s->next == NULL) // 栈空的情况 return 0; p = s->next; // p指向第一个数据结点 e = p->data; s->next = p->next; free(p); return 1; }
/*--------------------------取栈顶元素---------------------------*/ int GetTop(LiStack *s, ElemType &e) { if(s->next == NULL) // 栈空的情况 return 0; e = s->next->data; return 1; }
/*--------------------------从栈顶到栈底输出元素---------------------------*/ void DispStack(LiStack *s) { LiStack *p = s->next; while(p != NULL) { printf("%c ", p->data); p = p->next; } printf("\n"); }
int main(void) { ElemType e; LiStack *s; printf("(1)初始化链栈s\n"); InitStack(s); printf("(2)链栈为%s\n", (StackEmpty(s) ? "空" : "非空")); printf("(3)依次进链栈元素a,b,c,d,e\n"); Push(s, 'a'); Push(s, 'b'); Push(s, 'c'); Push(s, 'd'); Push(s, 'e'); printf("(4)链栈为%s\n", (StackEmpty(s) ? "空" : "非空")); printf("(5)链栈长度:%d\n", StackLength(s)); printf("(6)从链栈顶到链栈底元素:"); DispStack(s); printf("(7)出链栈序列:"); while(!StackEmpty(s)) { Pop(s, e); printf("%c ", e); } printf("\n"); printf("(8)链栈为%s\n", (StackEmpty(s) ? "空" : "非空")); printf("(9)释放链栈\n"); ClearStack(s); return 0; }
测试结果:
(1)初始化链栈s (2)链栈为空 (3)依次进链栈元素a,b,c,d,e (4)链栈为非空 (5)链栈长度:5 (6)从链栈顶到链栈底元素:e d c b a (7)出链栈序列:e d c b a (8)链栈为空 (9)释放链栈
