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

隨筆-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 春秋十二月 閱讀(2586) 評論(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>
            
亚洲伊人网站|
亚洲高清视频在线|
国产综合色产|
国产伦一区二区三区色一情|
欧美日韩四区|
欧美日韩午夜|
国产精品成人av性教育|
欧美色一级片|
国产精品视频免费一区|
国产精品一区二区在线观看网站
|
欧美成人午夜免费视在线看片
|
欧美一区二区三区视频|
欧美伊人久久久久久久久影院
|
久久精品一区二区|
欧美freesex交免费视频|
亚洲欧洲精品成人久久奇米网|
亚洲精品在线免费|
午夜免费日韩视频|
免费欧美网站|
国产精品分类|
好吊视频一区二区三区四区|
亚洲精品乱码视频|
亚洲欧美一级二级三级|
老鸭窝毛片一区二区三区|
亚洲国产精品免费|
亚洲欧美激情视频在线观看一区二区三区|
欧美制服丝袜|
欧美一区二区日韩一区二区|
国产区欧美区日韩区|
国产一区在线视频|
日韩视频在线一区二区|
欧美在线视屏|
最新国产乱人伦偷精品免费网站
|
欧美国产一区二区|
一本久久综合亚洲鲁鲁|
久久精品国产第一区二区三区|
欧美韩国日本综合|
国产欧美精品在线播放|
亚洲免费观看|
免费观看不卡av|
亚洲欧美日韩国产一区二区|
欧美成人激情在线|
免费观看久久久4p|
国产精品一区二区三区成人|
亚洲人成人99网站|
久久综合五月|
午夜视频久久久|
国产精品国产三级国产普通话99
|
欧美理论电影在线观看|
国产在线视频欧美|
欧美主播一区二区三区|
宅男噜噜噜66一区二区|
欧美黄在线观看|
亚洲日韩第九十九页|
欧美mv日韩mv国产网站|
久久精品99久久香蕉国产色戒|
国产精品制服诱惑|
久久精品夜色噜噜亚洲a∨
|
91久久综合亚洲鲁鲁五月天|
久久在线免费观看视频|
亚洲黄网站在线观看|
欧美xx69|
欧美成人首页|
一区二区电影免费观看|
亚洲精品日日夜夜|
亚洲婷婷综合色高清在线|
欧美精品色综合|
亚洲国产精品成人一区二区|
久久国产主播精品|
亚洲一二区在线|
欧美日一区二区三区在线观看国产免|
亚洲韩日在线|
欧美大片在线观看一区|
欧美一区国产二区|
国产精品亚洲成人|
亚洲欧美日韩在线观看a三区|
亚洲免费成人av|
久久久99免费视频|
激情自拍一区|
欧美成人午夜激情视频|
日韩亚洲欧美综合|
欧美成人精品一区|
亚洲黄色av一区|
久久亚洲免费|
亚洲在线一区二区|
国产精品亚洲综合天堂夜夜|
亚洲精品日韩在线|
久久久久久穴|
欧美一级理论片|
国语自产在线不卡|
久久久久久久久久久久久久一区|
亚洲综合视频网|
国产一区二区三区免费在线观看|
久久久久久久成人|
久久久蜜桃精品|
亚洲激情图片小说视频|
女生裸体视频一区二区三区|
欧美日本精品|
午夜精品亚洲一区二区三区嫩草|
性欧美18～19sex高清播放|
国产偷国产偷亚洲高清97cao|
久久国内精品视频|
美女主播一区|
在线亚洲电影|
亚洲欧美文学|
精品二区久久|
亚洲人成在线影院|
国产美女精品免费电影|
美女精品在线|
欧美日韩18|
亚洲欧美日韩一区二区在线|
亚洲欧美日韩一区二区|
中文欧美在线视频|
国产精品激情电影|
久久综合伊人77777蜜臀|
麻豆国产精品777777在线|
日韩视频一区二区|
最新日韩在线|
欧美大片在线观看一区|
亚洲激情国产|
亚洲精品在线免费|
国产精品video|
久久男人资源视频|
欧美日韩中文精品|
美女精品在线观看|
国产精品v日韩精品|
欧美xx视频|
国产啪精品视频|
久久精品在这里|
国产精品裸体一区二区三区|
免费成人黄色av|
国产精品日韩一区|
亚洲人成艺术|
亚洲第一页中文字幕|
一区二区三区福利|
最新亚洲电影|
欧美在线观看一区|
国产精品99久久99久久久二8|
久久久久久久久久久久久女国产乱|
中文久久乱码一区二区|
亚洲精品日韩在线|
亚洲成色777777女色窝|
欧美性色aⅴ视频一区日韩精品|
欧美日韩国产一区二区三区地区|
99精品欧美一区二区三区
|
亚洲综合三区|
影音先锋欧美精品|
国产精品v欧美精品v日本精品动漫|
亚洲精一区二区三区|
欧美一区二区在线|
久久精品一区二区三区不卡牛牛|
亚洲黄色尤物视频|
亚洲图片激情小说|
欧美精品一区二区三区在线看午夜
|
亚洲午夜久久久久久尤物|
亚洲三级电影全部在线观看高清|
亚洲私拍自拍|
亚洲美女在线一区|
亚洲一区二区三区四区五区午夜
|
久久精品九九|
亚洲日本va午夜在线电影|
欧美激情视频给我|
久久久亚洲国产美女国产盗摄|
午夜精品久久久久久99热|
99re6这里只有精品|
黄色av日韩|
国产亚洲毛片|
亚洲男人第一av网站|
欧美日韩激情网|
91久久在线播放|
亚洲嫩草精品久久|
国产精品剧情在线亚洲|
欧美专区在线播放|
久久久综合免费视频|
亚洲欧洲三级电影|
欧美好吊妞视频|
香蕉成人久久|
久久视频在线看|
日韩午夜电影av|
欧美四级在线|
欧美freesex8一10精品|
日韩视频久久|
欧美不卡高清|
国产真实乱子伦精品视频|
欧美伦理在线观看|
亚洲国产精品悠悠久久琪琪
|
一本色道久久88精品综合|
中文日韩欧美|
久久久人成影片一区二区三区|
另类av一区二区|
欧美喷水视频|
亚洲欧美日韩在线观看a三区|
久久免费视频网|
久久精品国产久精国产思思|
久久国产精品黑丝|
欧美一区观看|
国产精品毛片a∨一区二区三区|国
|
欧美在线地址|
性欧美video另类hd性玩具|
欧美成人综合网站|