2015-d-二-1

/**
    算法思想：如果有序有两种情况1.递增2.递减,注意有相邻相等情况
    从前之后两两比较相邻节点差值
**/
#include <stdio.h>
#include <stdlib.h>
//链表结构体
typedef struct lNode
{
    int data;
    struct LNode *next;
}LNode;


// 返回值0：无序 1：有序
// init 、flag 0：两个值相等 1：递增 -1：递减
int isOrder(LNode *l)
{
    LNode *p,*q;
    int flag,init;//init为第一个结点标记 flag为循环中标记
    p=l;//p指向开始结点
    q=p->next;//q指向p的下一个结点

    while(p->data==q->data&&q->next!=NULL)//恰好两个比较的值相等
    {
        p=p->next;
        q=p->next;
    }
    if(p->data>q->data) init=-1;//递减
    else if (p->data<q->data) init=1;//递增
    else {
        init=0;//从头至尾都相等
        return 1;
    }
    while(q)
    {
        if(p->data>q->data) flag=-1;//递减
        else if (p->data<q->data) flag=1;//递增
        else flag=0;//说明此时链表中元素均相等
        if(flag+init==0) return 0;//无序
        p=p->next;
        q=q->next;
    }
    return 1;
}

//链表建立,测试数据
LNode* create()
{
    LNode *c,*s,*r;

    s=(LNode*)malloc(sizeof(LNode));
    s->next=NULL;
    s->data=6;

    r=s;
    c=s;

    s=(LNode*)malloc(sizeof(LNode));
    s->next=NULL;
    s->data=6;
    r->next=s;
    r=r->next;

    s=(LNode*)malloc(sizeof(LNode));
    s->next=NULL;
    s->data=5;
    r->next=s;
    r=r->next;

    s=(LNode*)malloc(sizeof(LNode));
    s->next=NULL;
    s->data=4;
    r->next=s;
    r=r->next;

    s=(LNode*)malloc(sizeof(LNode));
    s->next=NULL;
    s->data=1;
    r->next=s;
    r=r->next;

    s=(LNode*)malloc(sizeof(LNode));
    s->next=NULL;
    s->data=1;
    r->next=s;
    r=r->next;

    return c;
}


int main()
{
    LNode *l = create();;
    printf("%d",isOrder(l));
}