随笔 - 89  文章 - 118  trackbacks - 0
<2008年2月>
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

刚刚有人考了我一道题,逆序输出单链表:
我是这样答的(下面的代码为伪代码,不能通过编译):

void printSList(slist *pList)
{
    assert(pList);
    
if (pList == NULL)
        
return;

    string str;
    
while (pList)
    {
        str 
= string(*pList) + str;
        pList 
= pList->next;
    }

    printf(
"%s", str.c_str());
}

后来他让我想一想还有没有更为简单的方法了,当时允许我上网,我用了几分钟到网上找了一下,没有找到更好的办法,如果先把链表逆序,再顺序输出时间复杂度更高。

我走出大楼以后,忽然想到,是递归呀,对是递归:

void printSList(slist *pList)
{
    assert(pList);
    
if (pList == NULL)
        
return;
    
    
if (pList->next == NULL)
        printf(
"%s"*pList);
    
else
    {
        printSList(pList
->next);
        printf(
"%s"*pList);
    }
}

哎,人生中机会就是一瞬之间,错过不知道下一次又是什么时候。但只要做了就会收获,会一次比一次做的好。吃饭去了...


posted on 2008-02-29 11:43 胡满超 阅读(10328) 评论(19)  编辑 收藏 引用

FeedBack:
# re: 单链表逆序输出 2008-02-29 12:47 raof01
先逆序再输出比递归高效。
N个节点,递归就存在N次函数调用,而先逆序再输出就2次调用(分两个函数写的话)——当然不包括调用其他函数。其他函数如print()调用次数是固定的。假设N巨大,还有可能出现栈问题,而先做逆序仅仅是指针的赋值循环。  回复  更多评论
  
# re: 单链表逆序输出 2008-02-29 13:00 胡满超
@raof01
“先逆序再输出”是最直观的想法,我的第一段代码是另外一种思路。“先逆序再输出”的时间复杂度是O(N*2),但会破坏原链表本身的结构。三种解决办法各有优缺点,让我选,我会选择我的第一段代码,这种实现最为清晰易懂。  回复  更多评论
  
# re: 单链表逆序输出 2008-02-29 13:04 hyou
lol那个链尾==null时不该打印呀 否则岂不末尾打印两次?
哈无论如何 都是慢慢进步咯 学习了  回复  更多评论
  
# re: 单链表逆序输出 2008-02-29 13:27 魔域私服
学习了````  回复  更多评论
  
# re: 单链表逆序输出[未登录] 2008-02-29 14:40 santa
如果你是去面dev的话你这个回答人家会不满意的,如果数据量大,递归绝对挂掉。递归的效率会很低,因为要设计到许多系统栈操作,比起逆序要低效许多许多。  回复  更多评论
  
# re: 单链表逆序输出 2008-02-29 17:08 浪迹天涯
面试时 切记使用傻傻的方法
我觉得递归 可能是最先想到的
第一张方法也很巧妙 已经回答的很好了  回复  更多评论
  
# re: 单链表逆序输出 2008-02-29 18:01 humanchao
@浪迹天涯
谢谢您的鼓励!  回复  更多评论
  
# re: 单链表逆序输出 2008-02-29 18:27 comiunknown
先把这个单项链表按顺序把每个节点的值压到一个堆栈里面,读完后,然后从堆栈中把值依次读出来,算法复杂度只有O(n)。感觉这个题是考堆栈。  回复  更多评论
  
# re: 单链表逆序输出 2008-03-01 10:00 winsty
递归的效率很低的...  回复  更多评论
  
# re: 单链表逆序输出[未登录] 2008-04-18 23:43 christanxw
递归绝对是失败的做法。  回复  更多评论
  
# re: 单链表逆序输出 2008-09-26 17:50 oracle3
分配一个数组,把指针放到数组中,然后for倒着打印,应该最简单  回复  更多评论
  
# re: 单链表逆序输出 2010-10-16 17:14 QQ124045670
递归那个方法我还没学到,所以我使用了分配一个数组,把指针放到数组中,然后for倒着打印
Status display(LinkList &L)
{
printf("\n---------------------------显示单链线性表----------------------\n");
LinkList p;
int n[100];
int j=100;
p=L->next; //打印的时候应该从头结点的下一个结点开始打印,否则会出现乱码
printf("\n单链表为:\t");
if(p!=NULL)
{
for(;p!=NULL;--j)
{
n[j-1]=p->date; //j-1是因为100要存放头结点的位置
p=p->next;
}
for(;j<100;j++)
{
printf("%d",n[j]);
}
}
free(p);
return 1;
}//display  回复  更多评论
  
# re: 单链表逆序输出 2011-09-18 21:47 wmj
@comiunknown
我也这么想的  回复  更多评论
  
# re: 单链表逆序输出 2012-07-02 09:33 
业绩依据绝对不是建立在一种想象当中,是必须从客观数据当中体现业绩的一种常态依据的,尽管这样的依据多少反映了一些现实,但是其实更多的反映的是事实上面业绩的依据。  回复  更多评论
  
# re: 单链表逆序输出 2012-07-02 09:34 
业绩依据证明有效的方式一定是取决于业绩依据的新的概念,这个新的概念其实是对于产品的定义,或者说产品的定义领导了一种思维变化的过程,这个其实是存在的一种业绩依据的表现  回复  更多评论
  
# re: 单链表逆序输出 2012-07-02 09:35 
实际上业绩依据的两种表现在市场表现容量的方式在于对于人得市场反映程度的高低,而在产品概念上面是取决于经济常识的需要  回复  更多评论
  
# re: 单链表逆序输出 2012-07-02 09:37 
业绩依据的两个方面,就 市场方面具体体现其实就是实质的专柜,店面的位置面积,形象的一个代表,而业绩依据的产品方面其实就是概念,定义,理论,原理上面的  回复  更多评论
  
# re: 单链表逆序输出 2012-07-02 09:39 
作为对于业绩依据的形成应该作为一种每年的规划出来的事实来 看待,而这样的规划一定是建立在两种要素上面,也就是市场要素与产品要素  回复  更多评论
  
# re: 单链表逆序输出 2012-07-02 09:40 
规划业绩的效果是长期的事情,也是必须重视起来的事情,这个与业绩数据没有什么关系  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理