Question

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

Answer 1

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

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

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

扩展资料：

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

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

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