你所能用到的数据结构(七)

十、装配火车的乐趣

      国庆放假结束了,第一天真是不想来上班啊,接着国庆之前的吧,上一篇写的是利用数组实现堆栈的结构,使用数组的两个致命的弱点是大小必须在使用前指定和效率非常差。那么先前的大牛们就开始思考如何提高效率呢?而在C/C++语言里有一种可以直接操作内存的东西叫做指针并且可以动态指定大小,于是不得不让人思考怎么样利用指针来克服原有的弱点重新实现数据结构。

     在使用指针实现之前,先看看数组为什么能实现堆栈等类似的结构,首先,一个数组可以通过下标来进行遍历,也就是说可以让我们从一个元素寻访到下一个元素或者某一个元素,第二个,数组可以包含元素。那么我们需要用指针也构造出具有这样两个特点的一个结构出来,也就是说,这个结构里面必须包含一个元素另外至少可以允许我们访问到下一个元素,也就是可以练成一个整体。在这种思维的趋势下,我们可以确定的是一个结构要包含元素很简单,只要给他声明一个成员变量就可以了,那么如何使用某一个方法来让其可以在总体上标示自己或者访问到下一个元素呢?我们可以利用指针,所以在创建堆栈之前,我们首先需要做的是需要创建一个这样的结构,一般情况下将这种结构成为节点(Node),节点的意思是“是在运行时存在的物理元素,它表示了一种可计算的资源,它通常至少有一些记忆能力和处理能力。”从这个定义上也可以看出节点的特征。

1 struct Node{
2     char ele;
3        Node* next;    
4 };

     其实你可以把Node想象成为一节火车车厢,里面的元素就是火车里面的负载,指针就是火车车厢连接处的挂钩,通过这个挂钩连接成为一个整体的火车。其实这个小小的struct包含了很多计算机知识,你可以问问自己这个Node*写成Node为什么就不行了?

     好了,有了这个车厢,那么下面就需要利用这个车厢组成火车,使用Node的一个好处就是可以自由装配,虽然在堆栈这个结构中还看不出来的这个好处,但是在后面的结构中这个好处会越来越明显的体现出来。想象着这样一个火车是停在车站里面的,车头前面是一个站台,也就是说这个火车的前面没有路了,这里也有一个细节,对于这个车头,你既可以把它看做一个普通车厢也可以把它看做是一个特殊的车厢,把它看做是一个不能搭载乘客的车厢,它的作用是表明这后面是一个火车,它没有元素,在实现上这样一个节点叫做头节点。我们为了简单起见,采用第一种方式,当然后面我也会特别再描述一下这个问题的。回到火车的问题上来,下面我们要装配这个火车,火车的前面已经没有铁轨了,我们想装配火车只能从或者的尾部开始一节一节的车厢装配上去。装配的办法就是将火车车厢连接的挂钩一个一个连接起来,这样就可以组成一个火车,当要去掉一个车厢也只能从尾部一个一个的去掉车厢,这样就是一个堆栈的结构。

     先看看头文件的组成吧。

 1 class Stack{
 2 public :
 3     Stack();
 4     ~Stack();
 5 
 6     void Push(char ele);
 7     char Pop();
 8     int Top();
 9     char GetValue(int Pos);
10     bool CheckEmpty();
11     int GetCount();
12 
13 private:
14     Node *cur; 
15     int count;
16 };

    大部分和使用数组的实现的差不多,不同的是构造函数之中没有大小了,因为使用指针可以动态的制定大小,还有一个就是成员变量换成了节点,这就好比一节车厢。下面就要思考如何实现了,构造函数就是初始化,构造上面说的一个火车,最开始什么都没有的情况下应该先把火车头先开来放好,然后这个火车头后面什么也没有连接,在程序上也就是指针指向null,你可以理解为火车头后面的挂钩挂着nothing。然后就是push,如果现在要在后面挂一节车厢,那么就是将车厢开来(声明一个新的节点),用后一节车厢的挂钩挂上前面面一节车厢(在程序上实现就是将当前Node结构的指针指向“->"这个新添加的节点,符号"->"我认为是C/C++里最形象的符号,因为看到它就有指向的意思),同时需要标示最后一节车厢的位置,因为不然你就不知道下一节新来的车厢挂哪了。再接下来是Pop,你可以想象是卸载掉一个车厢,因为你首先要让车厢里的乘客下车,所以在卸载之前你得先找个地让乘客下车(声明一个变量保存Node中的元素),然后重新找到卸载后最后一个节点,将挂钩取下(消除这个节点的内存)。最后一个是析构函数,你可以理解为如果我装配好的整列火车都不要了怎么办(当然这个比方不怎么恰当),你需要一个一个的将车厢都卸载掉,让其不要占铁轨资源。使用Node实现的堆栈如下:

 1 Stack::Stack()
 2 {
 3     cur=new Node();
 4     count=0;
 5 }
 6 
 7 Stack::~Stack()
 8 {
 9     Node* tmp=new Node();
10     while(cur->next!=NULL)
11     {
12         tmp=cur;    
13         cur=tmp->next;
14         delete tmp;
15     }
16     delete tmp;
17     delete []stackArray;
18 }
19 
20 bool Stack::CheckEmpty()
21 {
22     return (count==0);
23 }
24 
25 void Stack::Push(char ele)
26 {
27  
28     Node *tmp=new Node();
29     tmp->ele=ele;
30     tmp->next=NULL;
31 
32     if(count==0)
33         cur->ele=ele;
34     else
35     {
36         tmp->next=cur;
37         cur=tmp;
38     }
39     count++;
40 
41 }
42 
43 char Stack::Pop()
44 {
45     if(count==0)
46     {
47         cout<<"stack is empty!"<<endl;
48         return -1;
49     }
50     --count;
51     Node *tmp=cur;
52     char result=cur->ele;
53     if(count!=0)
54     {
55       
56        cur=cur->next;  
57        delete tmp;
58     }
59     else
60     {
61         cur=new Node();
62     }
63     return result;
64 }
65 
66 char Stack::GetValue(int Pos)
67 {      
68     Node *tmp=new Node;
69     tmp=cur;
70     int i=0;
71     while(i<Pos)
72     {
73         tmp=tmp->next;
74         i++;
75     }
76     return tmp->ele;
77 }
78 
79  
80 
81 
82 int Stack::GetCount() 
83 {
84     return count;
85 }

     我们看一下效果,同样还是使用前面的帮助实现交互的函数:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java学习网

学习Java需吃透这些基本概念

学习好比盖房子,打地基好很重要,房了能盖多高关键看地基;学习同样道理,基础知识是以后学习一切技术的必要条件,我们在准备学习一门开发语言时,首先要学习它的基础,不...

25510
来自专栏程序员互动联盟

【编程基础】盖大楼地基要牢固

水之积也不厚,则其负大舟也无力。——庄子 上一篇讲了几个编译编辑器,大家都可以用用,新手掌握几个是没有坏处的。 学编程要从基础学起,就像盖大楼,先把地基打好,...

3719
来自专栏醒者呆

零件组装技术——建造者模式深度解析

建造者模式是最后一个创建型设计模式,也是研究对象的创建。 将一个复杂对象的创建与它的表示分离,使得同样的构建过程可以创建不同的表示。 创建和表示是什么意思...

39110
来自专栏写代码的海盗

脱掉Golang的第一层衣裳 golang入坑系列

海鳖曾欺井内蛙,大鹏张翅绕天涯。强中更有强中手,莫向人前满自夸。 各位看官,现在开始脱衣裳。你不用脱,自个衣裳要穿好了,别脱下来。我们是来学Golang的,不...

2873
来自专栏小詹同学

Leetcode打卡 | No.017 电话号码的字母组合

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1483
来自专栏python3

python3--字典,字典的嵌套,概念:分别赋值

  字典是python中唯一的映射类型,采用键值对(key-value)的形式存储数据。python对key进行哈希函数运算,根据计算的结果决定value的存储...

3263
来自专栏北京马哥教育

让你的Python代码更加pythonic

何为pythonic? pythonic如果翻译成中文的话就是很python。很+名词结构的用法在中国不少,比如:很娘,很国足,很CCTV等等。 我的理解为...

2154
来自专栏web编程技术分享

JavaScript: 零基础轻松学闭包(1)

2015
来自专栏斑斓

编程实践 | Scala亮瞎Java的眼(一)

这是我在11月15日成都OpenParty分享的一个题目,确有标题党的嫌疑。Scala自然不是无所不能,Java也没有这么差劲,我只希望给Java程序员提供另外...

3445
来自专栏一“技”之长

Objective-C关于id引发的一些思考 原

    Objective-C是面向对象语言,但其中又并非全部是对象。在初学这门语言时,我常常从意识上将NS开头的类型与C语言原本的那些类型分割开来,假装他们之...

956

扫码关注云+社区

领取腾讯云代金券