C语言链表练习1

时间:2022-09-09 19:56:38

题目描述

新建两个链表,一个无序,一个降序。然后将无序的链表插入到降序的链表中,并使原来降序的链表仍然保持降序。输入的整形以空格隔开


#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(SNODE)

typedef struct node
{
    int num;
    struct node *next;
}SNODE;

//打印函数
void print(SNODE* head)
{
    head=head->next;
    while(head!=NULL)
    {
        printf("%d ",head->num);
        head=head->next;
    }

    putchar('\n');
}//print

//创建降序链表
void creatLinkDown(int n,SNODE *head)
{
    SNODE *p,*q=head;;
    p=(SNODE*)malloc(LEN);
    p->num=n;
    if(head->next==NULL)//表空
    {
        p->next=NULL;
        head->next=p;
    }
    else
    {
        while(q->next!=NULL)//找到第一个比待插入节点num值小的节点,插入其前面
        {
            if(q->next->num < p->num)
            {
                p->next=q->next;
                q->next=p;
                break;
            }
            q=q->next;
        }

        if(q->next==NULL)//没有比待插入节点num小的节点则插入表尾
        {
            p->next=NULL;
            q->next=p;
        }
    }
}//creatLinkDown

//创建无序链表
void creatLink(int n,SNODE *head)
{
    SNODE *p,*q=head;
    while(q->next!=NULL) q=q->next;

    p=(SNODE *)malloc(LEN);
    p->next=NULL;
    p->num=n;

    q->next=p;
}//creatLink

//插入链表
void combine(SNODE *headDown,SNODE *head)
{
    SNODE *p=head,*q=headDown;
    while(p->next!=NULL)//当前链表不空
    {   
        q=headDown;
        while(q->next!=NULL)//从要插入的链表中找到比当前节点num小的节点,插入其前面
        {
            if(q->next->num < p->next->num)
            {
                p=p->next;
                head->next=p->next;
                p->next=q->next;
                q->next=p;
                break;
            }
            q=q->next;
        }

        if(q->next==NULL)//没有找到比当前节点num小的节点,插入尾部
        {
            p=p->next;
            head->next=p->next;
            p->next=NULL;
            q->next=p;
        }
        
        p=head;
    }
}//combine

int main()
{
    SNODE *heada,*headb;
    heada=(SNODE*)malloc(LEN);//无序链表头节点
    heada->next=NULL;
    heada->num=-1;

    headb=(SNODE*)malloc(LEN);//降序链表头节点
    headb->next=NULL;
    headb->num=-1;
    int n;
    char ch;

    while(1)//创建无序链表
    {
        scanf("%d",&n);//读入整形
        creatLink(n,heada);//加入无序链表
        ch=getchar();//吃掉空格
        if(ch=='\n') break;
    }

    while(1)//创建有序链表
    {
        scanf("%d",&n);
        creatLinkDown(n,headb);
        ch=getchar();
        if(ch=='\n') break;
    }

    print(heada);//打印无序链表
    print(headb);//打印降序链表
    combine(headb,heada);//插入链表
    print(headb);//打印插入后的表

    return 0;
}//main