设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C, 其中B表的结点为A表中值＜0的结点, 而C表的结点为A表中值≥0的结点(链表A中的元素为整数, 要求B、C表利用A表的结点)

淩亂°似流年 2022-10-15 00:45 67阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    short InitHeadNode(struct Node* &, struct Node* &);
    short RearInsert(struct Node* &, struct Node* &, short);
    short GetListLength(struct Node* &);
    void Classify(struct Node* &, struct Node* &, struct Node* &);
    void Traversal(struct Node* &);
    /* 链表结点定义 */
    struct Node
    {
        short data;
        struct Node *next;
    };
    int main()
    {
        struct Node *head1;
        struct Node *rear1;
        struct Node *head2;
        struct Node *rear2;
        struct Node *head3;
        struct Node *rear3;
        /* 初始化1#链表的头结点 */
        if(InitHeadNode(head1, rear1) == -1)
        {
            /* 头结点申请失败, 程序直接结束 */
            exit(0);
        }
        short temp;
        /* 向链表中插入数据结点 */
        while(1)
        {
            while(scanf("%hd", &temp) != 1)
            {
                while(getchar() != '\n') ;
                printf("请输入合法数据.\n");
            }
            if(temp == -1)
            {
                break;
            }
            if(RearInsert(head1, rear1, temp) == -1)
            {
                /* 申请结点失败 */
                exit(0);
            }
        }
        /* 初始化2#链表的头结点 */
        if(InitHeadNode(head2, rear2) == -1)
        {
            /* 头结点申请失败, 程序直接结束 */
            exit(0);
        }
        /* 初始化3#链表的头结点 */
        if(InitHeadNode(head3, rear3) == -1)
        {
            /* 头结点申请失败, 程序直接结束 */
            exit(0);
        }
        /* 至此, 三个链表均已初始化 */
        Classify(head1, head2, head3);
        Traversal(head2);
        Traversal(head3);
        /* */
        return 0;
    }
    /* 核心算法 */
    void Classify(struct Node* &head1, struct Node* &head2, struct Node* &head3)
    {
        struct Node *p1 = head1 -> next;
        struct Node *p2 = head2;
        struct Node *p3 = head3;
        while(p1 != NULL)
        {
            if(p1 -> data < 0)
            {
                p2 -> next = p1;
                head1 -> next = p1 -> next;
                p1 -> next = NULL;
                p2 = p1;
                p1 = head1 -> next;
            }
            else
            {
                p3 -> next = p1;
                head1 -> next = p1 -> next;
                p1 -> next = NULL;
                p3 = p1;
                p1 = head1 -> next;
            }
        }
    }
    /* 遍历单链表并输出 */
    void Traversal(struct Node* &head)
    {
        struct Node *p = head -> next;
        while(p != NULL)
        {
            printf("%4hd", p -> data);
            p = p -> next;
        }
        putchar('\n');
    }
    /* 获取表长 */
    short GetListLength(struct Node* &head)
    {
        struct Node *p = head -> next;
        short length = 0;
        while(p != NULL)
        {
            length ++;
            p = p -> next;
        }
        return length;
    }
    /* 尾插法 */
    short RearInsert(struct Node* &head, struct Node* &rear, short value)
    {
        struct Node *p = (struct Node*)malloc(sizeof(struct Node));
        if(p != NULL)
        {
            /* 结点申请成功 */
            rear -> next = p;
            p -> next = NULL;
            p -> data = value;
            rear = p;
            return 1;
        }
        else
        {
            /* 结点申请失败 */
            return -1;
        }
    }
    /* 初始化头结点 */
    short InitHeadNode(struct Node* &head, struct Node* &rear)
    {
        struct Node *p = (struct Node*)malloc(sizeof(struct Node));
        if(p != NULL)
        {
            /* 头结点申请成功 */
            head = p;
            head -> data = 0;
            head -> next = NULL;
            rear = head;
            return 1;
        }
        else
        {
            /* 头结点申请失败 */
            return -1;
        }
    }

![20210522212721153.png][]

![20210522212758934.png][]

![20210522212842940.png][]

![20210522212922169.png][]

[20210522212721153.png]: /images/20221014/c0761029612d477ab2b77d285475a702.png
[20210522212758934.png]: /images/20221014/41fd1edb31f740bfbba26ceeafd9f0ab.png
[20210522212842940.png]: /images/20221014/97050d6a987e45a8b5736c2ae4d9c809.png
[20210522212922169.png]: /images/20221014/d7a3850da4e14914bc928beedbccc783.png