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

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

  這道題的常規(guī)做法或者說首先想到直覺的方法M1是先求得鏈表的長(zhǎng)度，即元素總個(gè)數(shù)n，然后問題轉(zhuǎn)化為求順序第n-m+1個(gè)元素。下面給出第2種方法M2：先求得順序第m個(gè)元素，用一指針P指向這個(gè)元素，用另一指針PR指向鏈表的頭部，現(xiàn)在好了，P和PR同時(shí)向右移動(dòng)，直到P為空，則PR就是要求的倒序第m個(gè)元素，如果因m超越界限，則PR為空，表示沒找到，這樣一來，只需一次循環(huán)就夠了。C++代碼描述如下
 1 template<typename T>
 2 struct Node
 3 {  
 4     T  data;    /**////< 數(shù)據(jù)
 5     Node* next;  ///< 指向下一結(jié)點(diǎn)的指針
 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}
  現(xiàn)在分析這2種方法的時(shí)間復(fù)雜度，假設(shè)鏈表元素個(gè)數(shù)為N，所求倒序?yàn)榈贛元素，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) 評(píng)論(11)  編輯 收藏 引用 所屬分類: Algorithm

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

第二個(gè)指針和第一個(gè)指針一起移動(dòng)。

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

這樣算是一次遍歷？  回復(fù)  更多評(píng)論
  
# re: 求單向鏈表倒序第m個(gè)元素 2011-06-25 23:36 | 夢(mèng)提
是一次遍歷，因?yàn)闀r(shí)間上是同步的。@kaka
  回復(fù)  更多評(píng)論
  
# re: 求單向鏈表倒序第m個(gè)元素 2011-06-26 08:47 | 搞笑
這個(gè)也太搞笑了？效率是一樣的，還竟然有：“這樣效率不高”的說法。  回復(fù)  更多評(píng)論
  
# re: 求單向鏈表倒序第m個(gè)元素 2011-06-26 13:54 | temp
是一樣的，兩個(gè)指針分別遍歷。  回復(fù)  更多評(píng)論
  
# re: 求單向鏈表倒序第m個(gè)元素 2011-06-26 15:24 | Arcko
貌似需要遍歷的確實(shí)是一樣的多，不過換個(gè)思路考慮也很好  回復(fù)  更多評(píng)論
  
# re: 求單向鏈表倒序第m個(gè)元素 2011-06-27 10:09 | megadeath
使用遞歸方式（示例代碼，無任何錯(cuò)誤檢查），把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;
}
  回復(fù)  更多評(píng)論
  
# re: 求單向鏈表倒序第m個(gè)元素 2011-07-01 11:06 | 有霧
我也感覺效率一樣的。第二個(gè)里面，同樣要把P移動(dòng)到鏈表尾，這樣才能獲得size。所以不存在O(M),同樣是O(N)啊。@搞笑
  回復(fù)  更多評(píng)論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <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>
            
欧美国产大片|
亚洲黄色免费|
久久久久.com|
欧美日韩一区二区在线视频|
男女精品网站|
伊人久久亚洲影院|
久久精品网址|
另类尿喷潮videofree|
国产精品欧美一区二区三区奶水|
亚洲人久久久|
亚洲肉体裸体xxxx137|
久久久亚洲精品一区二区三区
|
亚洲精品在线观|
中文欧美字幕免费|
欧美午夜不卡|
久久se精品一区精品二区|
日韩一级大片|
欧美大香线蕉线伊人久久国产精品|
欧美国产日韩在线观看|
99成人精品|
好吊成人免视频|
欧美另类专区|
午夜精品久久久久久久99热浪潮
|
最新国产乱人伦偷精品免费网站
|
欧美成人黑人xx视频免费观看|
在线观看视频亚洲|
欧美视频免费在线观看|
欧美中文字幕在线视频|
亚洲美女毛片|
欧美黑人在线观看|
欧美一区二区三区免费在线看|
亚洲精品乱码久久久久久按摩观|
国产日本欧美在线观看|
欧美三级网址|
欧美人与性禽动交情品|
新片速递亚洲合集欧美合集|
亚洲精品免费在线播放|
欧美91视频|
榴莲视频成人在线观看|
久久久精品动漫|
欧美一区二区免费视频|
99视频在线观看一区三区|
在线成人激情视频|
黄色亚洲网站|
亚洲毛片在线|
亚洲日本国产|
亚洲第一精品在线|
91久久综合亚洲鲁鲁五月天|
欧美mv日韩mv亚洲|
亚洲成人资源|
亚洲一区影音先锋|
久久精品亚洲|
欧美精品久久99久久在免费线|
欧美激情免费观看|
欧美视频福利|
在线免费观看一区二区三区|
亚洲精品欧美日韩|
亚洲一区二区三区四区中文|
欧美亚洲尤物久久|
在线色欧美三级视频|
亚洲国产成人久久综合|
99热这里只有精品8|
亚洲欧美日韩成人|
久久久综合免费视频|
亚洲电影免费在线观看|
日韩视频精品在线|
香蕉成人啪国产精品视频综合网|
午夜免费在线观看精品视频|
女女同性精品视频|
国产精品稀缺呦系列在线|
亚洲国产欧美另类丝袜|
亚洲一区三区在线观看|
久久综合图片|
一本色道久久88亚洲综合88|
老巨人导航500精品|
欧美日韩一二区|
亚洲高清自拍|
亚洲视频观看|
亚洲国产精品免费|
久久这里只精品最新地址|
欧美日韩精品一区二区天天拍小说|
国产欧美一区二区白浆黑人|
亚洲午夜三级在线|
99精品欧美一区|
欧美三级乱码|
性欧美video另类hd性玩具|
亚洲性夜色噜噜噜7777|
国产亚洲一级|
久久久久久久97|
欧美一区国产二区|
亚洲精品国产精品久久清纯直播
|
国产精品一区二区你懂的|
亚洲婷婷综合久久一本伊一区|
一区二区三区四区蜜桃|
国产欧美精品一区|
久久频这里精品99香蕉|
玖玖综合伊人|
亚洲图片在线观看|
性欧美videos另类喷潮|
在线精品视频免费观看|
亚洲最新中文字幕|
亚洲一级片在线观看|
国产在线观看91精品一区|
欧美成人三级在线|
欧美色另类天堂2015|
久久蜜桃av一区精品变态类天堂|
欧美激情精品久久久久久|
久久精彩视频|
欧美日韩一区二区在线播放|
久久一二三国产|
国产精品入口|
一本色道久久88综合亚洲精品ⅰ|
激情综合色综合久久|
一区二区精品|
亚洲日韩第九十九页|
久久久久一区二区三区四区|
欧美在现视频|
国产精品久久亚洲7777|
最新国产乱人伦偷精品免费网站|
国内精品久久久久影院薰衣草|
aa亚洲婷婷|
在线视频一区观看|
欧美国产日产韩国视频|
亚洲成色777777女色窝|
亚洲激情视频网站|
久久久久看片|
久久阴道视频|
亚洲第一黄色|
欧美99久久|
欧美激情第五页|
亚洲美女福利视频网站|
免费高清在线一区|
欧美国产成人在线|
亚洲精品在线观看免费|
欧美77777|
99re热这里只有精品免费视频|
亚洲人成啪啪网站|
欧美国产视频在线观看|
日韩午夜电影|
一区电影在线观看|
欧美日韩国产专区|
亚洲少妇自拍|
久久久久国产精品午夜一区|
精品二区久久|
欧美人成在线视频|
亚洲欧美中文日韩在线|
欧美专区在线观看|
亚洲欧洲精品一区二区三区不卡
|
亚洲性视频h|
欧美日韩国产在线播放网站|
亚洲一区二区视频|
麻豆国产精品777777在线|
99成人在线|
激情文学一区|
国产精品久久久久久久浪潮网站
|
亚洲一区图片|
在线播放中文字幕一区|
欧美日韩精品中文字幕|
久久亚洲国产精品日日av夜夜|
亚洲电影在线看|
久久精品国产欧美激情|
99pao成人国产永久免费视频|
国产欧美日本一区二区三区|
欧美日韩999|
你懂的视频欧美|
久久久999精品免费|
99pao成人国产永久免费视频|
亚洲国产精品va|
久久免费午夜影院|
久久精品最新地址|
午夜一区在线|
午夜精品久久久久影视|
夜夜爽99久久国产综合精品女不卡|
红杏aⅴ成人免费视频|
国产无一区二区|
国产精品女主播|
国产精品国产三级国产a|
国产精品久久久久久久免费软件|
欧美性感一类影片在线播放|
欧美日韩国产限制|
欧美三级日韩三级国产三级|
欧美国产一区二区三区激情无套|
久久综合国产精品台湾中文娱乐网|
亚洲视频在线观看三级|
亚洲视频图片小说|
欧美在线一级va免费观看|
欧美自拍偷拍|
久久国内精品自在自线400部|
久久精品国产亚洲精品|
久久手机免费观看|
欧美日韩a区|
国产女人18毛片水18精品|
韩国免费一区|
亚洲欧美清纯在线制服|
亚洲成人自拍视频|
欧美一区二区三区在线观看视频|
久久精品国产999大香线蕉|
欧美国产激情|
欧美福利视频在线观看|
999在线观看精品免费不卡网站|