Question

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较多少个元素结点

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较多少个元素结点！
（C语言描述）

Answer 1

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（D、（n-1）/2）个元素结点。

一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的。

每个结点的构成：元素（数据元素的映象） +指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

扩展资料：

用户不断申请存储单元和改变链接关系而得到的一种特殊数据结构，将链表的左边称为链头，右边称为链尾。头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。头插法最先得到的是尾结点。

由于链表的长度是随机的，故用一个while循环来控制链表中结点个数。假设每个结点的值都大于O，则循环条件为输入的值大于o。申请存储空间可使用malloc()函数实现，需设立一申请单元指针。

但malloc()函数得到的指针并不是指向结构体的指针，需使用强制类型转换，将其转换成结构体型指针。刚开始时，链表还没建立，是一空链表，head指针为NULL。

Answer 2

n/2吧！以为这个值可以在第一个也可以在最后一个！跟可以在中间一个！两是对称的在前面的话用的次数要少！后面用的次数多！所以一多一少就是个数的平均了！

Answer 3

假如x 在最后一个节点， 就需要查找n 个， 在一般情况下， x所在的节点位置都是等概率的， 为 1 / n , 所以 结果为 n /2

Answer 4

(n+1)/2

Answer 5

这个是算法复杂度问题，好好看看书吧，属于查找问题