当前位置:   article > 正文

数据结构——线性表——栈_请简述栈和线性表有什么关系

请简述栈和线性表有什么关系

目录

一、栈

1.栈的定义

2.栈的分类

二、栈的顺序存储结构

1.顺序栈的定义

2.顺序栈是四要素

3.顺序栈的基本运算算法

(1)代码部分

(2)结果演示

三、栈的链式存储结构

1.链栈的定义

 2.链栈的四要素

3.链栈的基本运算算法

(1)代码部分

(2)结果演示

四、实例讲解

1.判断一个字符串是否为回文。

2.进制转换

五、总结


一、栈

1.栈的定义

栈是只能从一端存取数据和读取数据且遵循 "先进后出" 或“后进后出”原则的线性存储结构。

2.栈的分类

与线性表存储结构类似,栈也有两种存储结构:顺序存储结构和链式存储结构。

二、栈的顺序存储结构

1.顺序栈的定义

顺序栈:即用顺序存储结构方式设计栈的存储数据,从而实现栈存储结构。

顺序栈通常有一个一维数组data和一个记录栈顶元素位置的变量top组成,底部称为栈底,头部称为栈顶。如图所示:

2.顺序栈是四要素

设顺序栈为st.

(1)栈空:st.top==-1。

(2)栈满条件:st.top==MaxSize-1。

(3)元素x进栈操作:st.top++;将元素x放在st.data[st.top]中。

(4)出栈元素x操作:取出栈元素x=st.data[st.top];st.top--

3.顺序栈的基本运算算法

a:void InitStack()  //初始化顺序栈

b:void DestroyStack()   //销毁顺序栈

c:int Push()  //进栈操作

d:int Pop()    //出栈操作

e:int GetTop()  //取栈顶元素运算

f:int StackEmpty()  //判断栈是否为空

(1)代码部分

  1. #include<stdio.h>
  2. typedef char ElemType;
  3. //顺序栈的声明
  4. #define MaxSize 200 //定义全局变量
  5. typedef struct
  6. {
  7. ElemType data[MaxSize];
  8. int top;
  9. }SequenceStack;
  10. //初始化
  11. void InitStack(SequenceStack &st)
  12. {
  13. st.top=-1; //设计栈顶
  14. }
  15. //销毁
  16. void DestroyStack(SequenceStack st)
  17. {
  18. } //由于顺序栈的内存空间是有系统自由分配的,故系统也会自动释放其空间
  19. //进栈
  20. int Push(SequenceStack &st,ElemType x)
  21. {
  22. if(st.top==MaxSize-1)
  23. return 0; //栈满
  24. else
  25. {
  26. st.top++;
  27. st.data[st.top]=x;
  28. return 1; //成功进栈
  29. }
  30. }
  31. //出栈
  32. int Pop(SequenceStack &st,ElemType &x)
  33. {
  34. if(st.top==-1)
  35. return 0; //栈空
  36. else
  37. {
  38. x=st.data[st.top];
  39. st.top--;
  40. return 1; //成功出栈
  41. }
  42. }
  43. //取栈顶元素运算
  44. int GetTop(SequenceStack st,ElemType &x)
  45. {
  46. if(st.top==-1)
  47. return 0; //栈空
  48. else
  49. {
  50. x=st.data[st.top];
  51. return 1; //成功去栈顶元素
  52. }
  53. }
  54. //判断栈空运算算法
  55. int StackEmpty(SequenceStack st)
  56. {
  57. if(st.top==-1)
  58. return 1; //栈空
  59. else
  60. return 0; //栈不空
  61. }
  62. void main()
  63. {
  64. SequenceStack st;
  65. ElemType e;
  66. printf("初始化栈st\n");
  67. InitStack(st);
  68. printf("栈%s\n",(StackEmpty(st)==1 ?"空" : "不空"));
  69. printf("a进栈\n");
  70. Push(st,'a');
  71. printf("b进栈\n");
  72. Push(st,'b');
  73. printf("c进栈\n");
  74. Push(st,'c');
  75. printf("d进栈\n");
  76. Push(st,'d');
  77. printf("e进栈\n");
  78. Push(st,'e');
  79. printf("f进栈\n");
  80. Push(st,'f');
  81. printf("栈%s\n",(StackEmpty(st)==1 ?"空" : "不空"));
  82. GetTop(st,e);
  83. printf("栈顶元素:%c\n",e);
  84. printf("出栈次序:");
  85. while(!StackEmpty(st))
  86. {
  87. Pop(st,e);
  88. printf("%c",e);
  89. }
  90. printf("\n");
  91. DestroyStack(st);
  92. }

(2)结果演示

三、栈的链式存储结构

1.链栈的定义

采用链式存储结构存储的栈称为链栈。本文采用单链表存储。如图所示:

 2.链栈的四要素

(1)栈空条件:s->next=NULL

(2)栈满条件:不考虑

(3)进制操作:将包含e结点插入到头结点之后

(4)出栈操作:取出头结点之后结点是元素并删除之。

3.链栈的基本运算算法

(1)代码部分

  1. #include <stdio.h>
  2. #include<malloc.h>
  3. typedef char ElemType;
  4. //链栈声明
  5. typedef struct node
  6. {
  7. ElemType data;
  8. struct node *next; //指针域
  9. }LinkStack;
  10. //初始化
  11. void InitStcak(LinkStack *&s)
  12. {
  13. s=NULL; //空栈
  14. }
  15. //销毁
  16. void DestroyStack(LinkStack *&s)
  17. {
  18. LinkStack *pre=s,*p;
  19. if(pre==NULL) //空栈
  20. return ;
  21. p=pre->next;
  22. while(p!=NULL)
  23. {
  24. free(pre); //释放pre结点
  25. pre=p;
  26. p=p->next;
  27. }
  28. free(pre); //释放尾结点
  29. }
  30. //进栈
  31. int Push(LinkStack *&s,ElemType x)
  32. {
  33. LinkStack *p;
  34. p=(LinkStack *)malloc(sizeof(LinkStack));
  35. p->data=x; //插入p结点作为栈顶结点
  36. p->next=s;
  37. s=p;
  38. return 1;
  39. }
  40. //出栈
  41. int Pop(LinkStack *&s,ElemType &x)
  42. {
  43. LinkStack *p;
  44. if(s==NULL) //栈空返回0
  45. return 0;
  46. else //栈不空
  47. {
  48. p=s; //p指向栈顶结点
  49. x=p->data; //取栈顶运算x
  50. s=p->next; //删除结点p
  51. free(p);
  52. return 1;
  53. }
  54. }
  55. //取栈顶元素运算
  56. int GetTop(LinkStack *s,ElemType &x)
  57. {
  58. if(s==NULL)
  59. return 0; //栈空
  60. else
  61. {
  62. x=s->data; //栈不空
  63. return 1;
  64. }
  65. }
  66. //判断栈空
  67. int StackEmpty(LinkStack *s)
  68. {
  69. if(s==NULL)
  70. return 1;
  71. else
  72. return 0;
  73. }
  74. void main()
  75. {
  76. ElemType e;
  77. LinkStack *st;
  78. printf("初始化st\n");
  79. printf("栈%s\n",(StackEmpty(st)==1 ?"空":"不空"));
  80. printf("a进栈\n");
  81. Push(st,'a');
  82. printf("b进栈\n");
  83. Push(st,'b');
  84. printf("c进栈\n");
  85. Push(st,'c');
  86. printf("e进栈\n");
  87. Push(st,'e');
  88. printf("d进栈\n");
  89. Push(st,'d');
  90. printf("f进栈\n");
  91. Push(st,'f');
  92. printf("栈%s\n",(StackEmpty(st)==1 ?"空":"不空"));
  93. GetTop(st,e);
  94. printf("栈顶元素:%c\n",e);
  95. printf("出栈次序:");
  96. while(!StackEmpty(st))
  97. {
  98. Pop(st,e);
  99. printf("%c",e);
  100. }
  101. printf("\n");
  102. DestroyStack(st);
  103. }

(2)结果演示
 

四、实例讲解

1.判断一个字符串是否为回文。

分析:回文是指一个字符串str从前面度和从后面都一样,将字符串str颠倒输出并保持到另一个字符串str2中,如何通过比较字符串str和字符串str2是否一一对应即可判断是否为回文。

由于顺序栈的特点是先进后出,故将字符串str从头到尾的各个字符依次进栈便可得到一个颠倒后是字符串;然后将字符串str从头到尾的各个字符依次与从栈顶到栈底的各个字符比较即可,如果两者都相同,则str是回文,否则不是。

代码详解

  1. int Palindrome(char str[],int strSize)
  2. {
  3. SequenceStack st; //定义一个顺序栈st
  4. InitStack(st);
  5. int i;
  6. char str2;
  7. for(i=0;i<n;i++)
  8. Push(st,str[i]);
  9. i=0;
  10. while(!StackEmpty(st)) //比较字符
  11. {
  12. Pop(st,ch);
  13. if(str2!=str[i++])
  14. {
  15. DestroyStack(st);
  16. return 0;
  17. }
  18. }
  19. DestoryStack(st);
  20. return 1;
  21. }

2.进制转换

本例一十进制转十六进制为例。

分析:采用辗转相除法求余数,并将余数进栈暂存与顺序栈中,最后通过出栈输出十六进制数即可

代码详解:

  1. void tranfroms(int n,char a[])
  2. {
  3. SequenceStack st;
  4. InitStack(st);
  5. char ch;
  6. int i=0;
  7. while(a!=0)
  8. {
  9. ch='0'+n%2;
  10. Push(st,ch);
  11. n/=2;
  12. }
  13. while(!StackEmpty(st))
  14. {
  15. Pop(st,ch);
  16. a[i]=ch;
  17. i++;
  18. }
  19. a[i]='\0';
  20. DestroyStack(st);
  21. }

五、总结

栈是线性表中特殊的存在,具有先进后出、后进先出的特点,可以快速有效的分配存储方式,可以实现很多功能。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/386406
推荐阅读
相关标签
  

闽ICP备14008679号