2. 考研
  3. 单链表L是一个带有头结点的有序链表，设计一个算法判断L是否为按数值递减的链表。如果L是递减链表，那么就返回1，否则返回0。请回答下列问题： (1)给出算法的主要思想； (2)写出算法的实现函数； (3)总结所用算法的时间和空间复杂度。

单链表L是一个带有头结点的有序链表，设计一个算法判断L是否为按数值递减的链表。如果L是递减链表，那么就返回1，否则返回0。请回答下列问题： (1)给出算法的主要思想； (2)写出算法的实现函数； (3)总结所用算法的时间和空间复杂度。

admin2014-07-18  57
问题 单链表L是一个带有头结点的有序链表，设计一个算法判断L是否为按数值递减的链表。如果L是递减链表，那么就返回1，否则返回0。请回答下列问题：
  (1)给出算法的主要思想；
  (2)写出算法的实现函数；
  (3)总结所用算法的时间和空间复杂度。
选项
答案(1)遍历链表L，将前后两个结点的数值依次作比较，判断链表是否为递减的，如果是就返回1，不是就返回0。 (2)算法的实现过程如下： #include“stdio．h” int increase(LinkList*L) { int min； ／／记录链表中的最小值 LinkList *P，*q；／／辅助指针 P=L->next： if(P) min=P->data；／／因为链表带头结点 q=P->next： while(q!=null){ if(q->data>min) ／／当前元素的值大于其相邻的前一个元素的值，则不为降序 return 0； else{ min=q->data； ／／修改最小值 q=q->next； ／／指针后移 } } return 1： } (3)遍历链表的时间复杂度为O(n)，算法实现过程中使用的辅助空间为常量，空间复杂度为O(1)。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/Iaxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)