在有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，鏈表仍然保持有序的時(shí)間？答案是錯(cuò)的，你是對(duì)的。本課題主要研究有序單鏈表的插入操作和算法分析。對(duì)數(shù)據(jù)結(jié)構(gòu)的任何操作都不能改變其原始結(jié)構(gòu)特征。因此，在將新節(jié)點(diǎn)插入

在有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，鏈表仍然保持有序的時(shí)間？

答案是錯(cuò)的，你是對(duì)的。本課題主要研究有序單鏈表的插入操作和算法分析。

對(duì)數(shù)據(jù)結(jié)構(gòu)的任何操作都不能改變其原始結(jié)構(gòu)特征。因此，在將新節(jié)點(diǎn)插入有序列表之后，仍然需要保持其順序。插入操作的關(guān)鍵是找到插入位置，主要的時(shí)間也花在找到插入位置上。對(duì)于N個(gè)節(jié)點(diǎn)的單鏈表，有n1個(gè)可能的插入位置，即在第一個(gè)節(jié)點(diǎn)之前和每個(gè)節(jié)點(diǎn)之后。在第一個(gè)節(jié)點(diǎn)前插入并比較一次；在第一個(gè)節(jié)點(diǎn)后插入并比較兩次，在第n個(gè)節(jié)點(diǎn)后插入搜索次數(shù)。如果每個(gè)掩碼上的插入概率相等，即[*]，則在有序單鏈表上查找插入位置的平均比較次數(shù)為：[*

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

要從具有n個(gè)節(jié)點(diǎn)的單鏈表中查找值等于x的節(jié)點(diǎn)，如果搜索成功，比較的平均數(shù)目是（n1）/2個(gè)節(jié)點(diǎn)。

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

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