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

隨筆-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 春秋十二月 閱讀(2590) 評論(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|
久久久www|
伊人激情综合|
免费日韩av片|
一区二区三区四区国产精品|
亚洲欧美美女|
狠狠色综合色综合网络|
久久婷婷丁香|
亚洲精品一区二区在线观看|
亚洲欧美精品中文字幕在线|
国内精品福利|
欧美成人免费播放|
亚洲午夜精品网|
久久亚洲一区二区|
99ri日韩精品视频|
国产欧美不卡|
欧美成人免费大片|
亚洲一区日本|
美女被久久久|
亚洲欧美电影在线观看|
激情久久久久久久久久久久久久久久
|
日韩亚洲成人av在线|
午夜精品一区二区三区四区|
黄色日韩精品|
欧美天堂亚洲电影院在线播放|
欧美亚洲日本国产|
亚洲黑丝在线|
欧美在线综合|
99天天综合性|
一区二区自拍|
国产精品进线69影院|
久久久夜夜夜|
亚洲欧美久久久久一区二区三区|
欧美国产日韩在线观看|
欧美亚洲综合网|
亚洲肉体裸体xxxx137|
国产欧美日韩三区|
欧美日韩亚洲视频|
久久亚洲一区二区三区四区|
亚洲一区在线观看免费观看电影高清|
欧美激情亚洲自拍|
久久九九精品99国产精品|
亚洲视频网在线直播|
亚洲第一福利视频|
国产精品一区视频网站|
欧美激情综合|
麻豆国产精品va在线观看不卡|
午夜精品视频|
亚洲婷婷综合久久一本伊一区|
欧美成人资源|
玖玖玖国产精品|
久久久国产精品一区|
午夜一区二区三区在线观看|
一区二区三区欧美日韩|
亚洲精品一区在线|
亚洲国产精品一区二区第一页
|
欧美日韩亚洲一区二|
蜜臀久久99精品久久久久久9|
欧美一区二区三区四区夜夜大片|
一区二区黄色|
一本色道久久综合亚洲精品不卡|
亚洲国产欧美日韩精品|
欧美电影在线观看完整版|
久久裸体视频|
久久一区二区三区国产精品|
久久国产欧美精品|
久久精品国产一区二区三|
亚洲欧美伊人|
欧美亚洲系列|
欧美中文在线免费|
久久国产直播|
久久人人97超碰国产公开结果
|
亚洲国内精品|
亚洲国产老妈|
亚洲人成网在线播放|
亚洲精品欧美日韩专区|
亚洲人成小说网站色在线
|
日韩一级不卡|
av成人天堂|
亚洲一区二区在线免费观看|
国产精品99久久久久久宅男|
亚洲午夜精品福利|
先锋影院在线亚洲|
久久精品国产99国产精品澳门|
久久国产精品亚洲77777|
久久久久久9999|
麻豆精品传媒视频|
亚洲高清视频一区|
99国产精品国产精品久久|
一本色道久久综合亚洲精品按摩
|
午夜免费久久久久|
欧美一区二区视频在线|
久久亚洲二区|
亚洲国产精品热久久|
日韩视频在线观看免费|
亚洲一区二区在线视频
|
国产深夜精品福利|
亚洲大胆av|
在线午夜精品|
久久久久国色av免费看影院
|
国产一区二区三区免费在线观看
|
国产一区二区三区在线播放免费观看
|
亚洲一区尤物|
久久久久久亚洲精品不卡4k岛国|
欧美99久久|
一本色道久久精品|
久久精品九九|
欧美体内she精视频在线观看|
国产人成一区二区三区影院|
亚洲国产一区二区三区在线播
|
欧美日韩成人综合天天影院|
国产精品视频一区二区高潮|
一区二区三区在线观看欧美|
av成人天堂|
麻豆精品一区二区综合av|
亚洲美女区一区|
久久久久久久综合狠狠综合|
欧美日韩国产亚洲一区|
国内精品99|
亚洲免费在线精品一区|
欧美99在线视频观看|
亚洲一区二区三区影院|
美女主播视频一区|
国产精品呻吟|
99在线|亚洲一区二区|
久久影视三级福利片|
一区二区高清视频|
欧美aⅴ99久久黑人专区|
国产视频精品免费播放|
一区二区三区成人|
欧美激情视频在线免费观看 欧美视频免费一|
一本久久知道综合久久|
美腿丝袜亚洲色图|
国产婷婷色综合av蜜臀av|
一区二区久久久久|
欧美91视频|
久久久久99|
国产亚洲欧美另类中文
|
久久精品成人|
在线亚洲自拍|
欧美日韩八区|
日韩亚洲国产欧美|
欧美激情精品久久久久|
久久久久久久999精品视频|
国产麻豆精品视频|
亚洲免费人成在线视频观看|
亚洲福利久久|
久久综合色天天久久综合图片|
国产日韩视频一区二区三区|
亚洲欧美国产三级|
在线亚洲成人|
欧美午夜精品一区二区三区|
日韩一级网站|
亚洲电影有码|
欧美大片在线观看|
亚洲国产精品成人综合|
欧美大片在线观看一区|
久久夜色精品一区|
亚洲福利视频一区二区|
欧美电影在线|
免费久久99精品国产自在现线|
在线看视频不卡|
欧美国产第二页|
欧美+日本+国产+在线a∨观看|
亚洲福利视频网|
亚洲国产精品美女|
欧美理论电影在线观看|
夜夜嗨一区二区三区|
99精品欧美|
国产精品久久久久久久久久久久久久
|
亚洲一区综合|
国产婷婷色一区二区三区|
久久午夜影视|
另类尿喷潮videofree|
亚洲激情午夜|
日韩视频亚洲视频|
国产精品尤物福利片在线观看|
欧美伊人久久|
久久嫩草精品久久久精品|
亚洲国产影院|
亚洲最黄网站|
国产日韩欧美在线观看|
另类天堂av|
欧美激情一区二区三区不卡|
一区二区av在线|
亚洲亚洲精品在线观看|
国产一区在线免费观看|
女女同性女同一区二区三区91|
欧美承认网站|
亚洲欧美日韩中文在线制服|
欧美一区影院|
亚洲美女一区|
亚洲欧美国产77777|
在线精品福利|
日韩一二三在线视频播|
国产区精品在线观看|
亚洲大胆人体在线|
欧美在线观看一二区|
久久久国产精品一区二区中文
|