136国产福利精品导航网址应用,99国产精品视频免费观看,亚洲欧美日韩精品

求單向鏈表倒序第m個(gè)元素

原題為某游戲公司試題，大意如下：對(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++代碼描述如下

template<typename T>
2

struct Node
3

{
4

T data; /**////< 數(shù)據(jù)
5

Node* next; ///< 指向下一結(jié)點(diǎn)的指針
6

} ;
7

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 春秋十二月閱讀(2573) 評(píng)論(11) 編輯收藏引用所屬分類: Algorithm

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 關(guān)于分圓域的一般結(jié)論一個(gè)歐拉數(shù)整除問題的兩種證法有限域上的特征與指數(shù)和之?dāng)U展二元二次型的相似變換、正定性與正交分解關(guān)于群的一些結(jié)論及應(yīng)用不定方程的代數(shù)數(shù)論解法關(guān)于橢圓曲線的驗(yàn)證計(jì)算不可約多項(xiàng)式判別算法的改正論證有限域上平方根的求解求解離散對(duì)數(shù)問題的Terr算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

常用鏈接

留言簿(79)

隨筆分類(161)

隨筆檔案(162)

文章分類(30)

關(guān)注的開源項(xiàng)目

最新隨筆

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜