`
tubaluer
  • 浏览: 1435539 次
文章分类
社区版块
存档分类
最新评论
  • sblig: c / c++ 是不一样的都会输出 100
    j = j++

重学数据结构003——栈的基本操作及实现(链式存储)

 
阅读更多

1.栈的概念

展示只允许在其一端进行插入语删除操作的表。从定义上来说,栈其实也是线性表,因此栈也具备大多数线性表所具备的基本操作。但是,从定义上可知,栈在进行插入、删除操作时,只能在一端进行操作,这一端成为栈顶(top)。

栈最核心的操作主要是:进栈(Push)、出栈(Pop)、返回栈顶元素(Top)。 此外,栈还判断栈是否为空、创见栈、清空栈等操作。

既然是线性表,那么栈从实现方式来说主要有两种:顺序存储实现(数组)、链式存储实现(链表)。下面是链式存储实现方式下,站的数据结构定义:

  1. typedefstructNode*PtrToNode;
  2. typedefPtrToNodeStack;
  3. typedefstructNode
  4. {
  5. intElement;
  6. PtrToNodeNext;
  7. };

站的基本操作如下:

  1. //判断栈是否为空
  2. intIsEmpty(StackS);
  3. //创见栈
  4. StackCreateStack();
  5. //销毁栈
  6. voidDisposeStack(StackS);
  7. //清空栈
  8. voidMakeEmpty(StackS);
  9. //进栈
  10. voidPush(intX,StackS);
  11. //返回栈顶元素
  12. intTop(StackS);
  13. //出栈
  14. voidPop(StackS);

下面是一个完整的关于栈的基本操作的例子:

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedefstructNode*PtrToNode;
  4. typedefPtrToNodeStack;
  5. typedefstructNode
  6. {
  7. intElement;
  8. PtrToNodeNext;
  9. };
  10. intIsEmpty(StackS);
  11. StackCreateStack();
  12. voidDisposeStack(StackS);
  13. voidMakeEmpty(StackS);
  14. voidPush(intX,StackS);
  15. intTop(StackS);
  16. voidPop(StackS);
  17. //判断栈是否为空
  18. intIsEmpty(StackS)
  19. {
  20. returnS->Next==NULL;
  21. }
  22. //创建链栈
  23. StackCreateStack()
  24. {
  25. StackS=malloc(sizeof(structNode));
  26. if(S==NULL)
  27. {
  28. printf("Noenoughmemory!");
  29. returnNULL;
  30. }
  31. S->Next=NULL;
  32. MakeEmpty(S);
  33. returnS;
  34. }
  35. voidMakeEmpty(StackS)
  36. {
  37. if(S==NULL)
  38. {
  39. printf("UseCreateStackFirst!");
  40. }
  41. else
  42. {
  43. while(!IsEmpty(S))
  44. {
  45. Pop(S);
  46. }
  47. }
  48. }
  49. voidPush(intX,StackS)
  50. {
  51. PtrToNodeTmp;
  52. Tmp=malloc(sizeof(structNode));
  53. if(Tmp!=NULL)
  54. {
  55. Tmp->Element=X;
  56. Tmp->Next=S->Next;
  57. S->Next=Tmp;
  58. }
  59. else
  60. {
  61. printf("Outofspace!");
  62. }
  63. }
  64. voidPop(StackS)
  65. {
  66. if(IsEmpty(S))
  67. {
  68. printf("TheStackisEmpty!");
  69. }
  70. else
  71. {
  72. PtrToNodeTmp=S->Next;
  73. S->Next=Tmp->Next;
  74. free(Tmp);
  75. }
  76. }
  77. intTop(StackS)
  78. {
  79. if(IsEmpty(S))
  80. {
  81. printf("Thestackisempty!");
  82. return0;
  83. }
  84. else
  85. {
  86. returnS->Next->Element;
  87. }
  88. }
  89. intmain(void)
  90. {
  91. StackS=CreateStack();
  92. inti;
  93. for(i=0;i<5;i++)
  94. {
  95. Push(i,S);
  96. }
  97. while(!IsEmpty(S))
  98. {
  99. printf("%d\n",Top(S));
  100. Pop(S);
  101. }
  102. return0;
  103. }

分享到:
评论

相关推荐

    《数据结构》——栈的操作

    用C++实现的栈操作,涉及顺序存储和链式存储。顺序存储的栈操作用类SeqStack实现,链式表存储的栈操作用LinkStack实现。main函数中做了部分测试。可根据需要继续扩充此程序。SeqStack和LinkStack可直接复制到其他...

    数据结构实验——单链表

    实验二 单链表实验 一、实验目的 1、掌握用Visual C++6.0上机调试单链表的基本方法 2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 ...[基本要求]用链式存储结构实现存储

    《数据结构》——线性表的操作

    用C++语言实现了对线性表的操作,有对线性表的顺序存储和链式存储,可根据需要适当扩充。本程序有三个类:SeqList、LinkList、Function。前面两个类实现了相同的功能(线性表中的常用功能),一个是顺序存储,一个是...

    《数据结构》——队列的操作

    用C++实现的。顺序存储和链式存储都封装成了类。里面的注释写了些提示,希望能有所帮助。

    数据结构 主要是栈 含有课件 练习

    1. 栈的基本概念 2. 栈的顺序存储表示表示和实现 (1)顺序栈动态分配存储空间方法 和对栈操作设计 (2)顺序栈静态分配存储空间方法 和对栈...3. 栈的链式存储结构——链栈 顺序栈静态分配存储空间方法 和对栈操作设计

    数据结构-第二章(5)-链式存储结构(csdn)————程序.pdf

    数据结构-第二章(5)-链式存储结构(csdn)————程序

    数据结构入门——队列的实现.rar

    队列是一种先进先出的数据结构:即插入在表的一端(队尾)进行,删除在表的另一端(队头)进行 与线性表相似,队列也有顺序储存和链式储存两种储存方法;实现方法和代码在此文档中,详细说明见本人博客

    《数据结构——用C语言描述》+课后题答案

    《数据结构——用C语言描述》+课后题答案包括顺序存储链式存储结构等 栈和队列推荐

    基本的数据结构知识——队列

    用不同的存储结构构成了队列。 即用线性存储结构和链式存储结构构成。

    数据结构——线性表(选择题).docx

    简单,线性表的链式存储原理,02702004 [单选题] A、必须是连续的 B、一定是不连续的 C、部分地址必须是连续的 D、连续与否均可以(正确答案) 数据结构——线性表(选择题)全文共11页,当前为第1页。 数据结构——...

    链式栈各种基本运算算法的实现

    成员函数是实现栈最基本的操作——push()向栈中加入元素,pop()移出栈顶元素,top()得到栈顶元素,empty()判断栈是否为空。 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748213

    数据结构实验——二叉树的存储与遍历

    (1)采用链式存储结构建立二叉树,并按先序输入二叉树的结点序列。建立时按先序输入的结点序列为:a b c # # # d e # f # # g # # (2)二叉树的建立采用递归方式实现,先序遍历、中序遍历、后序遍历均采用非递归方式...

    数据结构-二叉树的创建与遍历(链式存储结构)

    数据结构——二叉树的创建与遍历(链式存储结构)

    数据结构-线性表的链式存储

    数据结构——线性表的链式存储。 一篇文章带你快速了解!

    C++数据结构队列——离散事件模拟(银行处理系统)

    (1) 熟练掌握队列的两种存储方式。 (2) 掌握队列的基本操作及应用。 (3) 利用链式存储线性表和队列实现银行业务模拟程序。

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar

    3.5.4 字符数据在内存中的存储形式及使用方法 41 3.5.5 字符串常量 41 3.5.6 符号常量 42 3.6 变量赋初值 42 3.7 各类数值型数据之间的混合运算 43 3.8 算术运算符和算术表达式 44 3.8.1 C运算符简介 44 3.8.2 算术...

    数据结构——用C描述

    数据结构——用C描述答案 习题解答(唐策善版)(其他版本在上面) 第一章 绪论(参考答案) 1.3 (1) O(n) (2) (2) O(n) (3) (3) O(n) (4) (4) O(n1/2) (5) (5) 执行程序段的过程中,x,y值变化如下: 循环次数 x y 0...

    软件工程之专题九:数据结构知识

    数据结构上的基本操作: ◆插入操作 ◆删除操作 ◆更新操作 ◆查找操作 ◆排序操作 数据结构是指数据对象及相互关系和构造方法,一个数据结构B形式上可以用一个二元组表示为B=(A,R)。其中,A是数据结构中的数据...

    数据结构实验——二叉排序树查找

    实验内容:建立有n个元素的二叉排序树,并在其上进行查找。...实验说明:(1)建立n个元素的二叉树,以链式结构存储,数据元素为整型。(2)在该二叉树上查找某数据,若查找成功则输出成功信息,若查找失败,则插入该数据。

    数据结构算法——Visual C++ 6.0程序集PPT

    侯识忠 等编著 共10章 第一章 顺序存储结构的表、堆栈和队列 第二章链式存储结构的表,堆栈和队列 第三章 数组、串和广义表 第四章 递归 .....

Global site tag (gtag.js) - Google Analytics