Question

从一个具有n个节点的单链表中查找其值等于x的节点，在查找成功的情况下，平均需要比较几个结点，说下原因。

Answer 1

从一个具有n个节点的单链表中查找其值等于x的节点，在查找成功的情况下，平均需要比较(n+1)/2个节点。

由于单链表只能进行单向顺序查找，以从第一个节点开始查找为例，查找第m个节点需要比较的节点数f(m)=m，查找成功的最好情况是第一次就查找成功，只用比较1个节点，最坏情况则是最后才查找成功，需要比较n个节点。

所以一共有n种情况，平均下来需要比较的节点为(1+2+3+...+(n-1)+n)/n=(n+1)/2。

扩展资料

单链表中的数据是以结点来表示的，每个结点是由一个元素和一个指针构成，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

由于结点中的指针只存放了下一个结点的地址，因此只能从每个结点找到其对应下个结点，因此查找时只能从当前结点找到对应的下个节点，也就是只能顺序进行查找。

参考资料来源：百度百科-单链表

Answer 2

n个节点，单链表。
如果x等于第一个元素的值。则要比较1次
x等于第二个元素的值，则要比较2次
…
最不巧：x值刚好等于第n个元素，则要比较x次

所以总次数是1+2+3+……+n-1+n=(n+1)*n/2

所以平均需要：(n+1)/2次。

顺序数组可以用折半查找，需要 log2…为低…N 次

Answer 3

查找成功的情况下，x在1~n各节点的可能一样，平均需要比较的节点数为
(1+2+..+n)/n=(n+1)/2

Answer 4

什么意思？写代码加注释？