问答题
单链表L是一个带有头结点的有序链表,设计一个算法判断L是否为按数值递减的链表。如果l是递减链表,那么就返回1,否则返回0。请回答下列问题:
问答题
给出算法的主要思想;
【正确答案】遍历链表L,将前后两个结点的数值依次作比较,判断链表是否为递减的,如果是就返回1,不是就返回0。
【答案解析】
问答题
写出算法的实现函数;
【正确答案】算法的实现过程如下:
#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;
}
【答案解析】
问答题
总结所用算法的时间和空间复杂度。
【正确答案】遍历链表的时间复杂度为O(n),算法实现过程中使用的辅助空间为常量,空间复杂度为O(1)。
【答案解析】