從一個具有n個節(jié)點(diǎn)的單鏈表中查找其值等于x的節(jié)點(diǎn)，在查找成功的情況下，平均需要比較幾個結(jié)點(diǎn)，說下原因？要從包含n個節(jié)點(diǎn)的單鏈表中找到值等于x的節(jié)點(diǎn)，我們需要在搜索成功時(shí)平均比較（n1）/2個節(jié)點(diǎn)。由于

從一個具有n個節(jié)點(diǎn)的單鏈表中查找其值等于x的節(jié)點(diǎn)，在查找成功的情況下，平均需要比較幾個結(jié)點(diǎn)，說下原因？

要從包含n個節(jié)點(diǎn)的單鏈表中找到值等于x的節(jié)點(diǎn)，我們需要在搜索成功時(shí)平均比較（n1）/2個節(jié)點(diǎn)。

由于單鏈表只能執(zhí)行單向順序搜索，因此以從第一個節(jié)點(diǎn)開始的搜索為例，需要比較的節(jié)點(diǎn)數(shù)f（m）=m才能找到第m個節(jié)點(diǎn)。搜索成功的最佳情況是第一次搜索成功，只比較一個節(jié)點(diǎn)，最壞情況是最后一次搜索成功，需要比較n個節(jié)點(diǎn)。

總共有n個案例，要比較的平均節(jié)點(diǎn)是（1，2，3。。。（n-1）n）/n=（n 1）/2。