设为首页 加入收藏

TOP

链栈的基本操作(C语言)
2019-01-04 16:09:02 】 浏览:74
Tags:基本操作 语言

  栈的链式储存结构称为链栈。链栈的节点类型与链式线性表的节点类型

定义相同,不同的是它是仅在表头进行操作的单链表。链栈通常用不带头节

点的单链表来实现,栈顶指针就是链表的头指针 ,如图所示:

  

  代码如下:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define OK 1
  5 #define ERROR 0
  6 typedef int SElemType;
  7 //栈的链式储存结构
  8 typedef struct SNode {
  9     SElemType data; //数据域
 10     struct SNode *next; //指针域
 11 
 12 }SNODE, *PSNODE;
 13 //栈顶节点
 14 typedef struct
 15 {

		    
 
			
n> 16 PSNODE top; //栈顶指针 17 int count; //栈的长度 18 19 }LinkStack; 20 21 //初始化栈顶节点 22 int Init_LS(LinkStack *s) { 23 s->top = (PSNODE)malloc(sizeof(SNODE)); 24 if (!s->top) 25 return ERROR; 26 27 s->top = NULL; 28 s->count = 0; 29 return OK; 30 } 31 //判断栈是否为空 32 int Is_Empty(LinkStack *s) { 33 if (s->top == NULL) 34 { 35 printf("栈为空\n"); 36 return OK; 37 } 38 39 else { 40 printf("栈不为空\n"); 41 return ERROR; 42 } 43 } 44 //遍历栈 45 int Traverse_LS(LinkStack *s) { 46 int i; 47 if (Is_Empty(s) == OK) return ERROR; 48 PSNODE p = s->top; 49 for(i=s->count;i>0;i--) 50 { 51 52 printf("%d ", p->data); 53 p = p->next; 54 } 55 printf("\n"); 56 return OK; 57 } 58 //链栈元素入栈 59 int Push_LS(LinkStack *s, SElemType e) { 60 61 PSNODE p = (PSNODE)malloc(sizeof(SNODE)); 62 if (!p) return ERROR; 63 p->data = e; 64 p->next = s->top; //新结点指向栈顶指针指向的地址 65 s->top = p; //更新栈顶指针 66 s->count++; // 节点增加1 67 68 return OK; 69 70 } 71 // 获取栈顶元素 72 int GetTop(LinkStack *s, SElemType *e) { 73 if (Is_Empty(s) == OK) return ERROR; 74 *e = s->top->data; 75 return OK; 76 } 77 //链栈元素出栈 78 int Pop_LS(LinkStack *s, SElemType *e) { 79 if (Is_Empty(s) == OK) return ERROR; 80 81 PSNODE temp = s->top; 82 *e = temp->data; 83 s->top = temp->next; 84 s->count--; 85 free(temp); 86 return OK; 87 } 88 //销毁栈 89 int Destroy_LS(LinkStack *s) { 90 PSNODE p,q=NULL; 91 if(Is_Empty(s)==OK) return ERROR; 92 p = s->top; 93 for (int i = s->count; i > 0; i--) 94 { 95 q = p->next; 96 free(p); 97 p = q; 98 } 99 s->count = 0; 100 return OK; 101 } 102 103 int main() { 104 LinkStack s,*ps; 105 SElemType a, *e; 106 e = (SElemType*)malloc(sizeof(SElemType)); 107 ps = &s; 108 Init_LS(ps); 109 int n; 110 Is_Empty(ps); 111 printf("请输入入栈元素的个数:"); 112 scanf("%d", &n); 113 for(int i=0;i<n;i++) 114 { 115 scanf("%d", &a); 116 Push_LS(ps, a); 117 } 118 Traverse_LS(ps); 119 Pop_LS(ps, e); 120 printf("弹出的元素为%d\n", *e); 121 Traverse_LS(ps); 122 GetTop(ps, e); 123 printf("栈顶元素为%d\n", *e); 124 if(Destroy_LS(ps)==OK) printf("栈销毁成功!"); 125 126 return 0; 127 }

  我写的这个链栈的代码 稍微修改了一点 --把栈顶指针与count 组成一个结构体

count用来储存链栈的长度。如果链栈的长度很长而且经常需要返回长度 一个一个

算的话显得特别费时间;而使用count要方便的多 。

  如果我们要把两个链栈合并,必然需要其中一个的栈底地址

而且如果这个链栈很大,我们要从栈顶开始寻找栈底地址 很麻烦吧

但是我们在LinkStack  中增加一个 PSNODE bottom指针,在入栈函数中

根据count来给bottom赋值。这样栈底地址就有了。

  所以,数据结构的一些细节上的东西不是一成不变的,而是可以根据具体

的问题修改。


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇搞懂C语言函数指针 下一篇Visual Studio提示“无法启动IIS ..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }