判断单链表是否有序

lixiangrong
2024-01-29 / 0 评论 / 12 阅读 / 正在检测是否收录...

判断单链表是否有序

#include <stdio.h>
#include <stdlib.h>

typedef int dataType;
typedef struct linkNode
{
    dataType data;
    struct linkNode *next;
}node,*linkList;

// 1.初始化不带头结点的单链表
void init(linkList *list)
{
    *list = NULL; // 表示链表指针指向空处
}

// 2.根据用户输入构造单链表
void scanInsert(linkList *head)
{
    node *p,*q;
    dataType x;
    printf("请输入(以9999作为结束标识)...\n");
    scanf("%d",&x);
    while (x!=9999)
    {
        q = (node*) malloc(sizeof(node));
        q->data = x;
        q->next = NULL;
        if(!*head) // 创建第一个结点时
        {
            *head = q;
            p = *head;
        }
        else
        {
            p->next = q;
            p = p->next;
        }
        scanf("%d",&x);
    }
}

// 3.8.5 判断单链表是否有序
int isOrder(linkList head)
{
    node *p = head;
    if(!p || !p->next) // 链表为空或只有一个节点时默认有序
        return 1;
    while (p->next) // 先找到第一个严格有序的
    {
        if(p->data == p->next->data)
            p = p->next;
        else break;
    }
    if(!p->next || !p->next->next) // 链表只剩一个或两个节点时默认有序
        return 1;
    if(p->data < p->next->data) // 链表增序
    {
        while (p->next)
        {
            if(p->data > p->next->data)
                return 0;
            p = p->next;
        }
    }
    else // 链表降序
    {
        while (p->next)
        {
            if(p->data < p->next->data)
                return 0;
            p = p->next;
        }
    }
    return 1;
}

int main()
{
    linkList list;
    init(&list);
    scanInsert(&list);
    if(isOrder(list))
        printf("链表有序!");
    else
        printf("链表无序!");
    return 0;
}
0

评论 (0)

取消