欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

链栈的基本操作(C语言)

程序员文章站 2022-03-24 12:43:48
栈的链式储存结构称为链栈。链栈的节点类型与链式线性表的节点类型 定义相同,不同的是它是仅在表头进行操作的单链表。链栈通常用不带头节 点的单链表来实现,栈顶指针就是链表的头指针 ,如图所示: 代码如下: 我写的这个链栈的代码 稍微修改了一点 --把栈顶指针与count 组成一个结构体 count用来储 ......

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

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

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

  链栈的基本操作(C语言)

  代码如下:

  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 {
 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赋值。这样栈底地址就有了。

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

的问题修改。