栈的存储结构和常见操作(c 语言实现)

  1. 云栖社区>
  2. 博客>
  3. 正文

栈的存储结构和常见操作(c 语言实现)

ghost丶桃子 2016-05-19 15:10:32 浏览1222 评论0

摘要: 俗话说得好,线性表(尤其是链表)是一切数据结构和算法的基础,很多复杂甚至是高级的数据结构和算法,细节处,除去数学和计算机程序基础的知识,大量的都在应用线性表。 一、栈 其实本质还是线性表:限定仅在表尾进行插入或删除操作。

俗话说得好,线性表(尤其是链表)是一切数据结构和算法的基础,很多复杂甚至是高级的数据结构和算法,细节处,除去数学和计算机程序基础的知识,大量的都在应用线性表。

一、栈

其实本质还是线性表:限定仅在表尾进行插入或删除操作。 俗称:后进先出 (LIFO=last in first out结构),也可说是先进后出(FILO)。

同样的,栈也分为顺序和链式两大类。其实和线性表大同小异,只不过限制在表尾进行操作的线性表的特殊表现形式。

1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针 top 指示栈顶元素在顺序栈中的位置,附设指针 base 指示栈底的位置。 同样,应该采用可以动态增长存储容量的结构。且注意,如果栈已经空了,再继续出栈操作,则发生元素下溢,如果栈满了,再继续入栈操作,则发生元素上溢。栈底指针 base 初始为空,说明栈不存在,栈顶指针 top 初始指向 base,则说明栈空,元素入栈,则 top++,元素出栈,则 top--,故,栈顶指针指示的位置其实是栈顶元素的下一位(不是栈顶元素的位置)。

复制代码
  1 #ifndef _____ADT__
  2 #define _____ADT__
  3 #include <stdbool.h>
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #define STACK_SIZE 50
  7 #define STACK_INCREMENT 10
  8 
  9 typedef struct{
 10     int stackSize;//栈容量
 11     char *base;//栈底指针
 12     char *top;//栈顶指针
 13 } SqStack;
 14 
 15 //初始化
 16 //本质还是使用动态数组
 17 void initStack(SqStack *s)
 18 {
 19     s->base = (char *)malloc(STACK_SIZE * sizeof(char));
 20     //分配成功
 21     if (s->base != NULL) {
 22         //空栈
 23         s->top = s->base;
 24         s->stackSize = STACK_SIZE;
 25     }
 26     else
 27     {
 28         puts("分配失败!");
 29     }
 30 }
 31 
 32 //判空
 33 bool isEmpty(SqStack s)
 34 {
 35     return s.top == s.base ? true : false;
 36 }
 37 
 38 //判满
 39 bool isFull(SqStack s)
 40 {
 41     return (s.top - s.base) >= STACK_SIZE ? true : false;
 42 }
 43 
 44 //求当前长度
 45 int getLength(SqStack s)
 46 {
 47     int i = 0;
 48     char *q = s.top;
 49     
 50     while (q != s.base) {
 51         q--;
 52         i++;
 53     }
 54     
 55     return i;
 56 }
 57 
 58 //求栈顶元素
 59 char getTop(SqStack s, char topElement)
 60 {
 61     if (isEmpty(s)) {
 62         puts("栈空!");
 63     }
 64     
 65     topElement = *(s.top - 1);
 66     return topElement;
 67 }
 68 
 69 //入栈
 70 void push(SqStack *s, char topElement)
 71 {
 72     char *q = NULL;
 73     
 74     if (isFull(*s)) {
 75         q = (char *)realloc(s->base, STACK_INCREMENT * sizeof(char));
 76         
 77         if (NULL == q) {
 78             exit(0);
 79         }
 80         
 81         s->base = q;
 82         s->stackSize = s->stackSize + STACK_INCREMENT;
 83     }
 84     //进栈
 85     *s->top++ = topElement;
 86 }
 87 
 88 //出栈
 89 void pop(SqStack *s, char *topElement)
 90 {
 91     if (isEmpty(*s)) {
 92         exit(0);
 93     }
 94     
 95     s->top--;
 96     *topElement = *s->top;
 97 }
 98 
 99 //遍历
100 void traversal(SqStack s)
101 {
102     for (int i = 0; i < getLength(s); i++) {
103         printf("栈中元素遍历:%c \n", s.base[i]);
104     }
105 }
106 
107 //清空
108 void cleanStack(SqStack *s)
109 {
110     if (!isEmpty(*s)) {
111         s->top = s->base;
112         puts("栈已经清空!");
113     }
114 }
115 
116 //销毁
117 void destroyStack(SqStack *s)
118 {
119     if (s->base != NULL) {
120         free(s->base);
121         s->base = NULL;
122         s->top = NULL;
123         s->stackSize = 0;
124         puts("栈成功销毁!");
125     }
126 }
127 
128 #endif /* defined(_____ADT__) */
复制代码

 函数: void exit(int status);    所在头文件:stdlib.h

 功 能: 关闭所有文件,终止正在执行的进程。

 exit(1)表示异常退出.这个1是返回给操作系统的。

 exit(x)(x不为0)都表示异常退出

 exit(0)表示正常退出

 exit()的参数会被传递给一些操作系统,包括UNIX,Linux,和MS DOS,以供其他程序使用。

 

 exit()和return的区别:

 按照ANSI C,在最初调用的main()中使用return和exit()的效果相同。 但要注意这里所说的是“最初调用”。如果main()在一个递归程序中,exit()仍然会终止程序;但return将控制权移交给递归的前一级,直到最初的那一级,此时return才会终止程序。

return和exit()的另一个区别在于,即使在除main()之外的函数中调用exit(),它也将终止程序。

 

 _exit()与exit的区别:

 头文件不同:

 exit:#include<stdlib.h>

 _exit:#include<unistd.h>

 _exit()函数:直接使进程停止运行,清除其使用的内存空间,并销毁其在内核中的各种数据结构;

 exit()函数则在这些基础上作了一些包装,在执行退出之前加了若干道工序。比如系统调用之前exit()要检查文件的打开情况,把文件缓冲区中的内容写回文件。

 

复制代码
 1 #include "ADT.h"
 2 
 3 int main(void) {
 4     char temp = '0';
 5     SqStack stack;
 6     initStack(&stack);
 7     
 8     printf("%d\n", getLength(stack));
 9     
10     push(&stack, 'b');
11     push(&stack, 'k');
12     push(&stack, 'y');
13     
14     printf("%d\n", getLength(stack));
15     // 函数使用temp之前必须初始化
16     temp = getTop(stack, temp);
17     printf("%c\n", temp);
18     
19     traversal(stack);
20     
21     pop(&stack, &temp);
22     printf("%d\n", getLength(stack));
23     
24     traversal(stack);
25     
26     cleanStack(&stack);
27     
28     destroyStack(&stack);
29     
30     return 0;
31 }
复制代码

测试结果:

0

3

y

栈中元素遍历:

栈中元素遍历:

栈中元素遍历:

2

栈中元素遍历:

栈中元素遍历:

栈已经清空!

栈成功销毁!

Program ended with exit code: 0 


 

顺序栈的小结:

1)、尽量使用指向结构的指针做函数参数,这样的操作比结构体变量作函数参数效率高,因为无需传递各个成员的值,只需传递一个结构的地址,且函数中的结构体成员并不占据新的内存单元,而与主调函数中的成员共享存储单元。这种方式还可通过修改形参所指成员影响实参所对应的成员值。

2)、栈清空,一定是栈顶指向栈底,不可颠倒,否则析构出错!

3)、再次注意二级指针和一级指针做函数参数的不同

4)、使用一个指针变量之前,必须初始化,不为指针分配内存,即指针没有指向一块合法的内存,那么指针无法使用,强行运行出错,这就是野指针的危害。类似其他类型变量都是如此,(这也是为什么建议声明变量的同时就立即初始化,哪怕是一个不相干的数值),就怕程序写的复杂的话,一时忘记变量是否初始化,导致出错。

5)、为什么顺序栈(包括顺序表)在初始化函数的传入参数里不用二级指针传参?

    个人理解:

  首先清楚函数传参的类型,值传递,引用(c++)传递,和指针传递,且函数修改的是实参的一份拷贝,并不是直接去修改实参。 

    问题是,在之前的链表里,定义结点结构( Node)和指向结点的指针 p,有 struct Node *p;为了给结点分配内存,把这个指针(p本身占据一份内存空间,在栈区操作系统分配,但是 p 的指向是没有初始化的)p 传入初始化函数内,等于是传入的指向结点Node的一个指针 p 的拷贝 _p,而这个拷贝 _p 本身(假设指针变量p自己在内存的地址是0x1111)和拷贝 _p 存储的(指针 p指向的 内存区域)内容是不一样的,此时给 拷贝 _p 使用malloc函数分配内存,看似是修改了 _p ,实际上是把 _p 指向的内存区域改变了, p 本身在内存的地址(0x1111)没有被改变,故函数执行完毕,栈分配的内存被操作系统回收,然后参数返回给主调函数,那份拷贝 _p 还是以前传入的那份拷贝 _p, 高矮胖瘦那是纹丝未动,故不会对实参起到修改的作用,完全类似值传递,在值传递,就是把实参的本身的值传入函数,如果函数内部对其拷贝进行修改,其实传入的参数本身并没有被改变,虽然函数体内,他的值被修改了,但是一旦函数执行完,栈的内存被系统回收,修改就变得徒劳。

 

    顺序栈里,一般是定义的整个表List结构,struct List p;变量p 就是一个实例化的栈结构,注意 p 已经分配了内存(主调函数 main ,操作系统在栈区给p分配),这和主调函数里链表的指针 p 不一样,链表的指针 p 在 main 函数,只是给指针本身分配了内存空间,但是对 其指向的表结点没有分配,需要在初始化函数初始化!故到了顺序栈里,当给函数传入&p(因为开始main 已经给栈结构分配了内存空间,而&p 是栈结构 p 在内存的地址0x1111,也就是栈本身的首地址,也是 base指向的栈的基址),同样是传入一份拷贝 _&p ,且不是给 _&p  malloc 内存,而是给 _&p 指向的内容分配空间—— (&p)->base(表的基地址)分配内存,也就是说,这里堆 p 修改也是没用的,但是对 p 的指向修改,也就是 base,是有用的。而 base 本身就是一个指针,p 其实和 base 值相等,只不过变量的类型不一样,故不需要再传入二级指针。

 

6)、初始化那里,其实写的不好,主调函数里 s 分配了内存,如果没有对这个结构体初始化,就不代表 s 的成员 base 或者 top 等就是有指向的,更别说 NULL 了。很大程度是指向是垃圾值,不确定的内存区域,故这里的判断

 if (s->base != NULL)

在这个前提下,是没有用处的语句。故还是声明变量的同时,最好是初始化,哪怕是0或者 NULL。 

 

2、链栈

其实就是链表的特殊情形,一个链表,带头结点,栈顶在表头,插入和删除(出栈和入栈)都在表头进行,也就是头插法建表和头删除元素的算法。显然,链栈还是插入删除的效率较高,且能共享存储空间。

是栈顶在表头!栈顶指针指向表头结点。栈底是链表的尾部,base 就是尾指针。还有,理论上,链式结构没有满这一说,但是理论上是这样的,也要结合具体的内存,操作系统等环境因素。

复制代码
  1 #ifndef _____ADT__
  2 #define _____ADT__
  3 #include <stdbool.h>
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 
  7 typedef struct Node{
  8     char data;
  9     struct Node *next; //next 指针
 10 } Node, *ListStack;
 11 
 12 //初始化头结点,top 指针指向头结点
 13 void initStack(ListStack *top)
 14 {
 15     //top就是头指针!也就是栈顶指针
 16     *top = (ListStack)malloc(sizeof(Node));
 17     //就一个结点,也就是空栈,其实和链表一样,没啥意思
 18     (*top)->next = NULL;
 19     //内容初始化
 20     (*top)->data = '0';
 21 }
 22 
 23 //判空
 24 bool isEmpty(ListStack top)
 25 {
 26     //栈顶指针的next==NULL 就是空栈,没有满的判断,但是也要悠着点。小心内存受不了。
 27     return top->next == NULL ? true : false;
 28 }
 29 
 30 //入栈
 31 void push(ListStack top, char topElement)
 32 {
 33     ListStack q = NULL;
 34     q = (ListStack)malloc(sizeof(Node));
 35     
 36     if (NULL == q) {
 37         exit(0);
 38     }
 39     //类似头插法建表,进栈
 40     q->next = top->next;
 41     top->next = q;
 42     //赋值
 43     top->data = topElement;
 44     //栈底永远是表尾指针
 45 }
 46 
 47 //出栈
 48 void pop(ListStack top, char *topElement)
 49 {
 50     ListStack p = NULL;
 51     
 52     if (isEmpty(top)) {
 53         exit(0);
 54     }
 55     //栈顶元素出栈,记住,栈顶指针永远是指向栈顶元素的下一位,p 指向栈顶元素
 56     p = top->next;
 57     *topElement = p->data;
 58     //删除这个元素
 59     top->next = p->next;
 60     free(p);
 61 }
 62 
 63 //求当前长度
 64 int getLength(ListStack top)
 65 {
 66     int i = 0;
 67     ListStack q = top->next;
 68     
 69     while (q != NULL) {
 70         i++;
 71         q = q->next;
 72     }
 73     
 74     return i;
 75 }
 76 
 77 //求栈顶元素
 78 char getTop(ListStack top, char topElement)
 79 {
 80     if (isEmpty(top)) {
 81         puts("栈空!");
 82     }
 83     
 84     topElement = top->next->data;
 85     return topElement;
 86 }
 87 
 88 //遍历
 89 void traversal(ListStack top)
 90 {
 91     ListStack p = top->next;
 92     
 93     for (int i = 0; i < getLength(top); i++) {
 94         printf("栈中元素遍历:%c \n", p->data);
 95         p = p->next;
 96     }
 97 }
 98 
 99 //销毁
100 void destroyLinkStack(ListStack *top)
101 {
102     ListStack p = *top;
103     ListStack pn = (*top)->next;
104     
105     while (pn != NULL)
106     {
107         free(p);
108         p = pn;
109         pn = pn->next;
110     }
111     //销毁最后一个
112     free(p);
113     p = NULL;
114     puts("栈成功销毁!");
115 }
116 
117 #endif /* defined(_____ADT__) */
复制代码

main 函数

复制代码
 1 #include "ADT.h"
 2 
 3 int main(void) {
 4     ListStack stack = NULL;
 5     initStack(&stack);
 6     
 7     printf("栈长度 = %d\n", getLength(stack));
 8     
 9     push(stack, 'a');
10     push(stack, 'b');
11     push(stack, 'c');
12     push(stack, 'd');
13     
14     printf("栈长度 = %d\n", getLength(stack));
15     
16     traversal(stack);
17     
18     char temp = '0';
19     printf("栈顶元素 = %c\n", getTop(stack, temp));
20     pop(stack, &temp);
21     
22     printf("栈长度 = %d\n",getLength(stack));
23     
24     traversal(stack);
25     
26     destroyLinkStack(&stack);
27     
28     return 0;
29 }
复制代码

其实链栈和链表是一样的,没什么新鲜的东西。可见,线性表,尤其是链表,是数据结构和算法里的重中之重,后续很多复杂高级的数据结构和算法,都会无数次的用到链表的相关知识和概念。

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4096270.html
【云栖快讯】一站式开发者服务,海量学习资源免费学  详情请点击

网友评论