判断带表头的单链表是否有序递增

题目

设计一个算法判定带表头结点的单链表是否有序递增，并讨论算法的时间复杂度。

部分代码

判断是否有序递增

Status order(HeaderList *h, int n){
	int flag=-1;  //判定标志
	Node *p = h->head->link,*q=p->link;
	while(p->link!=NULL){  //判断单链表结束
		if(p->element>=q->element){  //判断是否有序递增
			flag=-1;
			break;
		}
		else flag=1;
		p=q;
		q=q->link;
	}
	if(flag==-1){
		printf("No");
	}
	else printf("Yes");
	return OK;
}

完整程序

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
#define ERROR 0
#define OK 1

typedef struct Node {
	ElemType element;
	struct Node * link;
}Node;

typedef struct {
	struct Node* head;
	int n;
}HeaderList;

Status Init(HeaderList *h);
Status Output(HeaderList *h);
Status order(HeaderList *h, int mSize);
Status Insert(HeaderList *h, int i, ElemType x);
// Status Delete(SeqList *L,int i);
// void Destory(SeqList *L);


// 单链表的初始化
Status Init(HeaderList *h) {
    h->head=(Node*)malloc(sizeof(Node));
    if(!h->head){
        return ERROR;
    }
	h->head->link = NULL;
	h->n = 0;
	return OK;
}



Status order(HeaderList *h, int n){
	int flag=-1;  //判定标志
	Node *p = h->head->link,*q=p->link;
	while(p->link!=NULL){  //判断单链表结束
		if(p->element>=q->element){  //判断是否有序递增
			flag=-1;
			break;
		}
		else flag=1;
		p=q;
		q=q->link;
	}
	if(flag==-1){
		printf("No");
	}
	else printf("Yes");
	return OK;
}



Status Insert(HeaderList *h, int i, ElemType x) {
	Node *p, *q;
	int j;
	if (i<-1 || i>h->n - 1)
		return ERROR;
	p = h->head;
	for (j = 0; j <= i; j++) {
		p = p->link;
	}
	q = (Node*)malloc(sizeof(Node));
	q->element = x;
	q->link = p->link;
	p->link = q;
	h->n++;
	return OK;
}


// 单链表的输出
Status Output(HeaderList *h) {
	Node *p;
	if (!h->n)
		return ERROR;
	p = h->head->link;
	while (p) {
		printf("%d ",p->element);
		p = p->link;
	}
	return OK;
}



int main()
{
	int i, x, nn;
	HeaderList list;
	scanf("%d", &nn);
	printf("\n");
	Init(&list);
	for (i = 0; i < nn; i++) {
		scanf("%d", &x);
		Insert(&list, i - 1, x);
	}
	Output(&list);
	printf("\n");
	order(&list,nn);
	return 0;
}

判断带表头的单链表是否有序递增

题目

部分代码

判断是否有序递增

完整程序

实验结果

是有序递增

不是有序递增