当前位置:首页>维修大全>综合>

在有n个结点的有序单链表中插入一个新结点 链表仍然保持有序的时间(在单链表中删除值相同的多余结点)

在有n个结点的有序单链表中插入一个新结点 链表仍然保持有序的时间(在单链表中删除值相同的多余结点)

更新时间:2024-06-25 17:11:16

在有n个结点的有序单链表中插入一个新结点 链表仍然保持有序的时间

答案错了,你是对的 本题主要考核有序单链表上的插入操作及算法分析。

对数据结构的任何操作都不能改变其原有的结构特性。因此,在有序单链表中插入一个新结点后,仍然要保持它的有序性。插入操作的关键是查找插入位置,主要时间也是花在插入位置的查找上。n个结点的单链表,有,n+1个可能插入的位置,即第一个结点之前和每一个结点之后。在第一个结点之前插入,需比较一次;在第一个结点之后插入需比较两次;……;在第,n个结点之后插入需查找次。如果在每一个位罩上作插入的概率相等,即[*]则在有序单链表上查找插入位置的平均比较次数为: [*]

更多栏目