面試-常考的數(shù)據(jù)結(jié)構(gòu)題(已修改)
2025-06-19 22:51 本頁面
【正文】 面試——?？嫉臄?shù)據(jù)結(jié)構(gòu)題 為了能進微軟江西的暑假實訓(xùn)班,猛補了一下數(shù)據(jù)結(jié)構(gòu)的知識，現(xiàn)在總結(jié)一下?？嫉臄?shù)據(jù)結(jié)構(gòu)的知識吧。 知識點：1鏈表 2二叉樹 3排序 4查找：判斷一個鏈表是否存在環(huán)，例如下面這個鏈表就存在一個環(huán)：例如N1N2N3N4N5N2就是一個有環(huán)的鏈表，環(huán)的開始結(jié)點是N5這里有一個比較簡單的解法。設(shè)置兩個指針p1，p2。每次循環(huán)p1向前走一步，p2向前走兩步。直到p2碰到NULL指針或者兩個指針相等結(jié)束循環(huán)。如果兩個指針相等則說明存在環(huán)。 struct link { int data。 link* next。}。bool IsLoop(link* head){ link* p1=head, *p2 = head。 if (head ==NULL || headnext ==NULL) { return false。 } do{ p1= p1next。 p2 = p2nextnext。 } while(p2 amp。amp。 p2next amp。amp。 p1!=p2)。 if(p1 == p2) return true。 else return false。}2,鏈表反轉(zhuǎn) 單向鏈表的反轉(zhuǎn)是一個經(jīng)常被問到的一個面試題，也是一個非?；A(chǔ)的問題。比如一個鏈表是這樣的： 12345 通過反轉(zhuǎn)后成為54321。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當(dāng)前指針指向的下一個元素，然后將當(dāng)前節(jié)點元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。源代碼如下： struct linka { int data。 linka* next。}。void reverse(linka*amp。 head){ if(head ==NULL) return。 linka*pre, *cur, *ne。 pre=head。 cur=head
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1