青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆-163  評論-223  文章-30  trackbacks-0
   原題為某游戲公司試題，大意如下：  對于一個單向鏈表，試寫出找到它的倒序第m個元素(m >= 1)的函數，注意變量命名、注釋、時間復雜度、空間復雜度。注：要求寫出可編譯并可以運行通過的程序代碼。

  這道題的常規做法或者說首先想到直覺的方法M1是先求得鏈表的長度，即元素總個數n，然后問題轉化為求順序第n-m+1個元素。下面給出第2種方法M2：先求得順序第m個元素，用一指針P指向這個元素，用另一指針PR指向鏈表的頭部，現在好了，P和PR同時向右移動，直到P為空，則PR就是要求的倒序第m個元素，如果因m超越界限，則PR為空，表示沒找到，這樣一來，只需一次循環就夠了。C++代碼描述如下
 1 template<typename T>
 2 struct Node
 3 {  
 4     T  data;    /**////< 數據
 5     Node* next;  ///< 指向下一結點的指針
 6 } ;
 7 
 8 template<typename T>
 9 Node<T>* ReverseFind(Node<T>* head, size_t m)
10{
11    size_t  n = 0;
12    Node<T> *p, *pR = NULL;
13    for (p = head;p;p = p->next)
14    {
15        if (++n == m)
16        {
17            pR = head;
18            continue;
19        }
20        if (pR)
21        {
22            pR = pR->next;
23        }
24    }
25    return pR;
26}
  現在分析這2種方法的時間復雜度，假設鏈表元素個數為N，所求倒序為第M元素，N>=M，則M1方法為0(N)+0(N-M)=0(2N-M)，M2方法為O(M)+O(N-M)=0(N)，因此M2快于M1。
posted on 2011-06-24 11:40 春秋十二月 閱讀(2595) 評論(11)  編輯 收藏 引用 所屬分類: Algorithm

評論:
# re: 求單向鏈表倒序第m個元素 2011-06-24 12:30 | coreBugZJ
贊一個  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-06-24 16:45 | paw
額，，考研數據結構題。。。  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-06-24 23:57 | 魚吃貓
頂一個~  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素[未登錄] 2011-06-25 12:06 | 英雄哪里出來
不錯，贊一個~~  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素[未登錄] 2011-06-25 13:39 | kaka
第一個指針從頭移動到m，和第二個指針一起再移動到尾部。

第二個指針和第一個指針一起移動。

只不過將一個指針大于一次遍歷的操作分解成兩個指針操作。

這樣算是一次遍歷？  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-06-25 23:36 | 夢提
是一次遍歷，因為時間上是同步的。@kaka
  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-06-26 08:47 | 搞笑
這個也太搞笑了？效率是一樣的，還竟然有：“這樣效率不高”的說法。  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-06-26 13:54 | temp
是一樣的，兩個指針分別遍歷。  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-06-26 15:24 | Arcko
貌似需要遍歷的確實是一樣的多，不過換個思路考慮也很好  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-06-27 10:09 | megadeath
使用遞歸方式（示例代碼，無任何錯誤檢查），把for語句也消隱掉。

static int nOrder = 0;
template <typename ITERATOR, typename UINT>
void F(ITERATOR begin, ITERATOR end, UINT M)
{
ITERATOR it = begin;
if (begin != end)
F(++begin, end, M);

if (++nOrder == ++M)
cout << *it << endl;
}
  回復  更多評論
  
# re: 求單向鏈表倒序第m個元素 2011-07-01 11:06 | 有霧
我也感覺效率一樣的。第二個里面，同樣要把P移動到鏈表尾，這樣才能獲得size。所以不存在O(M),同樣是O(N)啊。@搞笑
  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
亚洲日本va午夜在线影院|
欧美激情一区二区三区蜜桃视频|
亚洲经典在线看|
另类av一区二区|
亚洲黑丝一区二区|
欧美激情视频一区二区三区免费|
老牛影视一区二区三区|
亚洲精品久久久久久久久久久久久
|
中文国产成人精品|
国产精品私拍pans大尺度在线|
欧美在线999|
久久女同精品一区二区|
亚洲精品久久久蜜桃|
日韩一级在线|
国产日韩精品一区二区浪潮av|
久久久99国产精品免费|
久久综合给合|
在线一区二区三区做爰视频网站
|
能在线观看的日韩av|
欧美精品成人在线|
性一交一乱一区二区洋洋av|
欧美尤物巨大精品爽|
亚洲精品一区二区三区婷婷月|
99re成人精品视频|
国产一区二区三区黄视频|
亚洲国产成人av在线|
国产精品一区二区三区免费观看|
久久午夜精品|
欧美日韩一区二区在线观看|
久久久亚洲精品一区二区三区|
免费亚洲一区|
翔田千里一区二区|
久热综合在线亚洲精品|
亚洲欧美日本另类|
欧美激情精品久久久久久变态|
亚洲欧美日韩在线高清直播|
毛片一区二区|
久久久久久久91|
欧美色欧美亚洲另类七区|
蜜桃av噜噜一区|
国产精品毛片一区二区三区|
欧美激情亚洲精品|
国内精品**久久毛片app|
亚洲免费观看|
91久久精品国产91性色tv|
性视频1819p久久|
中文日韩电影网站|
欧美韩国在线|
免费成人高清视频|
国产日韩欧美高清|
亚洲在线国产日韩欧美|
亚洲精品一区在线观看|
久久久亚洲欧洲日产国码αv
|
国产在线精品自拍|
亚洲一级黄色|
亚洲一级高清|
欧美三区在线|
日韩亚洲成人av在线|
亚洲精品乱码久久久久久|
久久一区二区三区av|
久久av一区二区三区|
国产精品实拍|
亚洲视频免费观看|
亚洲欧美日本精品|
欧美午夜精品电影|
一本一本a久久|
一区二区三区蜜桃网|
欧美日韩高清一区|
一本色道久久综合亚洲精品不卡
|
香蕉免费一区二区三区在线观看|
欧美视频在线观看免费|
99精品欧美一区二区三区|
一区二区欧美在线|
欧美视频中文一区二区三区在线观看
|
麻豆国产精品777777在线|
国产精品一页|
香蕉视频成人在线观看|
欧美亚洲自偷自偷|
国产午夜精品一区二区三区欧美|
亚洲综合久久久久|
久久国产精品久久国产精品|
国产亚洲欧美日韩日本|
久久精品国产亚洲a|
免费观看一区|
亚洲精选视频在线|
欧美性猛交视频|
亚洲欧美视频一区|
麻豆精品在线视频|
99在线精品观看|
国产精品福利在线|
久久精品国产久精国产思思|
欧美激情第3页|
亚洲一线二线三线久久久|
国产区精品视频|
久久婷婷国产麻豆91天堂|
亚洲电影免费观看高清完整版在线观看
|
91久久精品一区二区别|
在线亚洲国产精品网站|
国产一级一区二区|
欧美精品18+|
亚洲欧美日韩精品综合在线观看|
久久手机免费观看|
一区二区三区欧美在线|
国产婷婷色一区二区三区在线|
久久综合网络一区二区|
一本色道久久88亚洲综合88|
欧美一区二区三区四区视频|
亚洲国产一区二区a毛片|
国产精品免费一区二区三区在线观看
|
性伦欧美刺激片在线观看|
免费在线日韩av|
亚洲欧美福利一区二区|
在线欧美视频|
国产精品一级久久久|
欧美成人精品影院|
欧美一区二区精品|
一本高清dvd不卡在线观看|
玖玖玖免费嫩草在线影院一区|
一区二区三区**美女毛片|
黑人极品videos精品欧美裸|
国产精品av久久久久久麻豆网|
久久天天躁狠狠躁夜夜爽蜜月|
亚洲午夜伦理|
最新亚洲一区|
欧美国产日韩视频|
久久精品青青大伊人av|
亚洲一区二区三区中文字幕|
亚洲欧洲日本国产|
在线播放不卡|
国产一区二区三区av电影|
国产精品嫩草99av在线|
欧美日韩国产天堂|
欧美福利影院|
欧美成人国产一区二区|
久久综合色天天久久综合图片|
性色一区二区|
午夜一级在线看亚洲|
亚洲欧美国产精品va在线观看
|
欧美电影美腿模特1979在线看
|
99riav久久精品riav|
亚洲高清不卡一区|
国产一区二区三区在线免费观看
|
国产精品美女主播|
国产精品久久久久久久久动漫
|
欧美在线欧美在线|
午夜在线播放视频欧美|
亚洲欧美在线免费|
亚洲色图综合久久|
亚洲一区二区黄色|
午夜在线精品偷拍|
午夜伦欧美伦电影理论片|
亚洲欧美在线网|
欧美影院午夜播放|
久久国产精品久久精品国产|
欧美在线视屏|
久久久久久久综合日本|
久久综合色综合88|
欧美激情一区二区三区成人|
欧美精品激情在线|
欧美视频一区二区三区…|
国产精品视频区|
国产手机视频一区二区|
在线观看日韩专区|
亚洲美女视频在线观看|
一区二区三区视频在线播放|
亚洲综合色自拍一区|
午夜日韩福利|
久久综合伊人|
亚洲国产日韩精品|
亚洲一区二区影院|
久久精品夜夜夜夜久久|
欧美激情国产精品|
国产精品一区二区久久|
在线观看国产成人av片|
亚洲少妇最新在线视频|
久久精品国产99精品国产亚洲性色|
麻豆成人在线观看|
一区二区黄色|
久久久久久久久久久一区|
欧美极品在线视频|
国产私拍一区|
一区二区日韩精品|
久久人人97超碰国产公开结果|
亚洲第一福利社区|
先锋影音网一区二区|
欧美福利网址|
国产一区二区精品久久91|
日韩西西人体444www|
男女激情久久|
国产精品久久久久久久7电影|
一区二区在线观看视频在线观看|
亚洲日本国产|
久久久久久久一区二区|
亚洲裸体视频|
久久久蜜臀国产一区二区|
国产精品成人一区二区艾草|
亚洲第一福利视频|
性高湖久久久久久久久|
亚洲狠狠丁香婷婷综合久久久|
午夜精品国产更新|