• <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>
            

    
            

            




            







												


        




            
	
		
		
            

隨筆-161 
評(píng)論-223 
文章-30 
trackbacks-0

            
	

            

            
	
					


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

              這道題的常規(guī)做法或者說(shuō)首先想到直覺(jué)的方法M1是先求得鏈表的長(zhǎng)度，即元素總個(gè)數(shù)n，然后問(wè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為空，表示沒(méi)找到，這樣一來(lái)，只需一次循環(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 春秋十二月 閱讀(2555) 評(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 | 魚(yú)吃貓
            
				
            頂一個(gè)~  回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	
		
            
			
            
			# re: 求單向鏈表倒序第m個(gè)元素[未登錄](méi)
				2011-06-25 12:06 | 英雄哪里出來(lái)
            
				
            不錯(cuò)，贊一個(gè)~~  回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	
		
            
			
            
			# re: 求單向鏈表倒序第m個(gè)元素[未登錄](méi)
				2011-06-25 13:39 | kaka
            
				
            第一個(gè)指針從頭移動(dòng)到m，和第二個(gè)指針一起再移動(dòng)到尾部。

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

            只不過(guò)將一個(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è)也太搞笑了？效率是一樣的，還竟然有：“這樣效率不高”的說(shuō)法。  回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	
		
            
			
            
			# re: 求單向鏈表倒序第m個(gè)元素
				2011-06-26 13:54 | temp
            
				
            是一樣的，兩個(gè)指針?lè)謩e遍歷。  回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	
		
            
			
            
			# re: 求單向鏈表倒序第m個(gè)元素
				2011-06-26 15:24 | Arcko
            
				
            貌似需要遍歷的確實(shí)是一樣的多，不過(guò)換個(gè)思路考慮也很好  回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	
		
            
			
            
			# re: 求單向鏈表倒序第m個(gè)元素
				2011-06-27 10:09 | megadeath
            
				
            使用遞歸方式（示例代碼，無(wú)任何錯(cuò)誤檢查），把for語(yǔ)句也消隱掉。

            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 | 有霧
            
				
            我也感覺(jué)效率一樣的。第二個(gè)里面，同樣要把P移動(dòng)到鏈表尾，這樣才能獲得size。所以不存在O(M),同樣是O(N)啊。@搞笑

              回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	








            






            

				

            






    
    







            
	   
	



色偷偷88888欧美精品久久久|
久久99热这里只有精品国产
|
人妻丰满AV无码久久不卡
|
久久国产成人|
久久精品桃花综合|
色综合久久无码中文字幕|
国产巨作麻豆欧美亚洲综合久久
|
国产精品青草久久久久福利99|
亚洲v国产v天堂a无码久久|
亚洲国产精品无码久久一线|
国产精品美女久久久久|
人妻中文久久久久|
国产精品久久久久…|
久久这里有精品|
国产高潮国产高潮久久久91
|
久久综合鬼色88久久精品综合自在自线噜噜
|
性做久久久久久久久久久|
996久久国产精品线观看|
亚洲欧美国产精品专区久久|
996久久国产精品线观看|
亚洲αv久久久噜噜噜噜噜|
性欧美大战久久久久久久|
99久久99久久精品国产|
久久久久女人精品毛片|
亚洲国产日韩欧美久久|
久久国产三级无码一区二区|
国产成年无码久久久久毛片|
伊人久久综合精品无码AV专区|
日日狠狠久久偷偷色综合0|
久久99精品久久久久久9蜜桃|
久久精品国产亚洲av高清漫画|
中文字幕人妻色偷偷久久|
无码任你躁久久久久久老妇App|
国产精品永久久久久久久久久|
久久国产精品国产自线拍免费|
久久99精品国产自在现线小黄鸭|
久久人人爽人人爽人人片AV麻烦|
99久久精品免费看国产一区二区三区
|
99久久无码一区人妻a黑|
精品蜜臀久久久久99网站|
久久精品国产亚洲AV嫖农村妇女|