请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

猿媛之家

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 8848|回复: 0

一个朋友过来面试引发我要说的一个小话题

[复制链接]

412

主题

474

帖子

1526

积分

金牌会员

Rank: 6Rank: 6

积分
1526
发表于 2015-12-1 21:46:20 | 显示全部楼层 |阅读模式

在很多家公司面试,也包括在携程,大多都会被问到一些算法的问题,其中机票事业部的面试,基本上算是算法问题的重灾区,没办法,有几个领导喜欢用数据结构来考人家,其中包括一些常见数据结构的复杂度以及手写一些算法,比如快排,单链表等等,前几天我一个推荐过来的朋友膝盖就被中了一箭。

题目就不方便具体说了,第一小问就是用非递归来构建一个单链表,我们知道构建单链表可以说是学数据结构的基本功,一说到用链式结构,它跟递归又有了千丝万缕的联系,很多链式的问题,我们用递归就可以轻轻松松的解决,几乎不需要动一下脑子,但是如果用非递归的话,那就稍微比递归要复杂一点了,起码会多考一个引用类型内存分配的问题。

后来QQ上我就用递归和非递归的形式构建单链表回复了他,先给了一个递归的版本,这个没问题,可以消化,然后给了一个非递归的版本,看了之后就扛不住了。

一:递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

class LinkList
    {
        public class LinkNode
        {
            public int data;

            public LinkNode next;
        }

        private LinkNode head;

        public void Add(int data)
        {
            if (head == null)
            {
                head = new LinkNode() { data = data };
            }
            else
            {
                Add(head, data);
            }
        }

        public void Add(LinkNode node, int data)
        {
            if (node.next == null)
            {
                node.next = new LinkNode() { data = data };
                return;
            }

            Add(node.next, data);
        }
    }



二:非递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class LinkList
    {
        public class LinkNode
        {
            public int data;

            public LinkNode next;
        }

        private LinkNode head;

        public void Add(int data)
        {
            LinkNode node = new LinkNode() { data = data };

            if (head == null)
            {
                head = node;
            }
            else
            {
                LinkNode temp = head;

                while (temp.next != null)
                {
                    temp = temp.next;
                }

                temp.next = node;
            }
        }
    }



这个非递归不理解的地方在于临时变量temp,提出的问题就是为什么:“temp.next=node” 之后,head的值发生了改变?我想之所以不能理解,绝逼是对引用类型的内存分配不了解,而这个非递归版本恰恰就是用引用类型这个内存分配技巧来实现 ”非递归构建单链表“。。。为了不让别人踩上这个坑,我还是大概说一下流程,大概是这样的,当我们在new一个引用类型的时候,CLR就要计算实例字段和所有基类上的实例字段的大小,然后再在堆上分配合理的内存块,最后把堆上的内存块的首地址保存在栈上面。

为了方便理解,现在假如LinkList里面有三个结点:instance1 -> instance2 -> instance3,

第一句:

1

LinkNode temp = head;



这个句子不难理解吧,把head的地址赋给temp,那么栈上temp的地址也就是head的地址,head的地址就是指向instacnce1内存块地址。

第二句: 从这句while中可以看到,一直在找instance的next,可以看出之后把instance2的内存地址给了temp,再next之后就把instance3的内存地址给了temp,然后就发现instance3的next为null,然后就跳出循环。

1

2

3

4

while (temp.next != null)
{
     temp = temp.next;
}




第三句:从上一句可以看到,instance3的next已经为null了,这时候就把新构建的结点:LinkNode node = new LinkNode() { data = data };赋

给temp的next指针上来继续构建链表。

1

temp.next = node;



可以看到这时候instance4就构造到了instance3之后,同时temp.next已经是保存instance4的内存地址,这一些操作对head来说都是透明的,它也不管后面怎么操作,当你遍历head的时候会惊奇的发现居然我的链表中多了一个instance4,这个也就是朋友疑惑的地方,如果看到这个内存分配图的话,

也许会豁然开朗,当然这篇博文没什么技术含量,也是自己一时有感而发。


转载自 Huang Xincheng 的博客  
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|猿媛之家    

GMT+8, 2022-1-29 08:35 , Processed in 0.194692 second(s), 27 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表