C数据结构-链表习题解析

Dear 丶 2021-12-20 00:07 179阅读 0赞

**（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据**

> **\[题目分析\]**
> 
> **合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后**

void merge(List *L1,List *L2,List *&L3) //尾插法合并链表，链表顺序
    {
        List *p = L1->next;
        List *q = L2->next;
        List *pr = L3;
        L3 = L1;  //将L1的头结点赋给L3
        L3->next = NULL;
        free(L2);   //释放L2的头结点
        pr = L3;   //pr指向L3
        while(p&&q)
        {
            if(p->data<q->data)
            {
                pr->next = p;
                p = p->next;
                pr = pr->next;
            }
            else if(p->data>q->data)
            {
                pr->next = q;
                q = q->next;
                pr = pr->next;
            }
            else
            {
                pr->next = p;
                p = p->next;
                pr = pr->next;
                q = q->next;
            }
        }
        p->next = p?p:q;
    }

**（2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据**

> **\[题目分析\]**
> 
> **合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的表头结点之后，如果两个表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素依次摘取，链接在Lc表的表头结点之后**

void merge01(List *L1,List *L2,List *&L3) //头插法合并链表，逆序
    {
        List *p = L1->next;
        List *q = L2->next;
        List *pr;
        L3 = L1;
        L3->next = NULL;
        pr = L3;
        while(p&&q)
        {
            if(p->data<q->data)
            {
                pr = p;
                p = p->next;
                pr->next = L3->next;
                L3->next = pr;
            }
            else
            {
                pr = q;
                q = q->next;
                pr->next = L3->next;
                L3->next = pr;
            }
        }
        while(p)
        {
            pr = p;
            p = p->next;
            pr->next = L3->next;
            L3->next = pr;
        }
        while(q)
        {
            pr = q;
            q = q->next;
            pr->next = L3->next;
            L3->next = pr;
        }
    }

void merge01book(List* &L1,List* &L2,List* &L3)
    {
        //合并链表L1和L2，合并后的新表用L3指向
        List *p = L1->next;
        List *q = L2->next;
        //p,q分别为L1，L2的工作指针，初始化为链表的首元结点
        List *pr,*px;
        L3 = L1;
        pr = L3;
        L3->next = NULL;
        while(p||q)
        {
            //只要有一个非空表，用px指向待摘取的元素
            if(!p)
            //L1表为空，用px指向q，q指针后移
            {
                px = q;
                q = q->next;
            }
            else if(!q)
            //L2表为空，用px指向p，p指针后移
            {
                px = p;
                p = p->next;
            }
            else if(p->data<=q->data)
            //取较小者（包括相等）L1中的元素，用px指向p，p指针后移
            {
                px = p;
                p = p->next;
            }
            else
            //取较小者L2中元素，用px指向q，q指针后移
            {
                px = q;
                q = q->next;
            }
            //将L3的指针域赋给px的指针域
            px->next = L3->next;
            //L3指向px（头插法）
            L3->next = px;
        }
        delete L2;
    }

**（3）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中**

> **\[题目分析\]**
> 
> **只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针Lc指向。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，如果两个表中相等的元素时，摘取La表中的元素，删除Lb表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。当链表La和Lb有一个到达表尾结点，为空时，依次删除另一个非空表中的所有元素**

void merge02(List* &L1,List* &L2,List* &L3)
    //将L1和L2相等的节点放入L3中，并删除此时L2的节点，L1大于L2时，L2后移并删除原节点，L1小于L2，L2后移并删除原节点
    {
        List *p = L1->next;
        List *q = L2->next;
        //p和q分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
        List *pr,*px;
        L3 = L1;
        pr = L3;
        //用L1的头结点作为L3的头结点
        L3->next = NULL;
        while(p&&q)
        {
            if(p->data == q->data)      //交集并入结果表中。
            {
                pr->next = p;
                pr = p;
                p = p->next;
                px = q->next;
                delete q;
                q = px;
            }
            else if(p->data>q->data)
            {
                px = q->next;
                delete q;
                q = px;
            }
            else
            {
                px = p->next;
                delete p;
                p = px;
            }
        }
        while(p)        //释放结点空间
        {
            px = p->next;
            delete p;
            p = px;
        }
        while(q)        //释放结点空间
        {
            px = q->next;
            delete q;
            q = px;
        }
        delete L2;      //释放L2的头结点
    }

**（4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数**

> **\[题目分析\]**
> 
> **求两个集合A和B的差集是指在A中删除A和B中共有的元素，即删除链表中的相应结点,所以要保存待删除结点的前驱，使用指针pre指向前驱结点。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，如果La表中的元素小于Lb表中的元素，pre置为La表的工作指针pa删除Lb表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。当链表La和Lb有一个为空时，依次删除另一个非空表中的所有元素**

void Difference(List* &L1,List* &L2,int &n)
    //差集的结果存储于单链表L1中，n是结果集合中元素个数，调用时为L1长度
    //删除L1中与L2相等的节点
    {
        List *p = L1->next;
        List *q = L2->next;
        //p和q分别是链表L1和L2的工作指针,初始化为相应链表的第一个结点
        List *px = L1,*pr;  //px为L1中p所指结点的前驱结点的指针
        while(p)
        {
            p = p->next;
            n++;
        }
        p = L1->next;
        while(p&&q)
        {
            if(p->data == q->data)
            {
                pr = p->next;
                px->next = pr;
                delete p;
                p = pr;
                n--;
            }
            else if(p->data<q->data)
            {
                px = p;
                p = p->next;
            }
            else
            {
                q = q->next;
            }
        }
    }

**（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点**）

> **\[题目分析\]**
> 
> **B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，将小于0的结点插入B表,大于等于0的结点插入C表**

void DisCompose(List *&L1,List* &L2,List* &L3)
    {
        List *p = L1->next; //p为L1的工作节点
        List *q,*pr,*pb;
        L2 = L1;            //L2指向L1的头节点
        L2->next = NULL;    //头结点指针域置空
        L3 = (List *)malloc(sizeof(List));  //为L3头结点申请堆空间
        L3->next = NULL;    //头结点指针域置空
        while(p)
        {
            pb = p->next;   //pb保存p后继的地址
            if(p->data<0)   //使用头插法将元素插入到L2中
            {
                p->next = L2->next;
                L2->next = p;
            }
            else
            {
                p->next = L3->next;
                L3->next = p;
            }
            p = pb;
        }
    }

**（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点**

> **\[题目分析\]**
> 
> **假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则设其下一个元素为最大值，反复进行比较，直到遍历完该链表**

void Max(List *L1,int &n)
    {
        List *p = L1->next;
        int max = p->data;
        List *q = p->next;
        while(q)
        {
            if(p->data<q->data)
            {
                max = q->data;
                p = q;
                q = q->next;
            }
            else
            {
                p = q;
                q = q->next;
            }
        }
        n = max;
    }

**（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间**

> **\[题目分析\]**
> 
> **从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部**

void inverse(List *&L1)
    //算法思想:创建L2指针，使其指向L1头结点，将L1每个节点用头插法插入到L2中，最后将L2的地址赋给L1
    {
        List *p = L1->next;
        List *L2 = L1,*pr;
        L2->next = NULL;
        while(p)
        {
            pr = p;
            p = p->next;
            pr->next = L2->next;
            L2->next = pr;
        }
        L1 = L2;
    }

## 完整测试代码 ##

#include <stdio.h>
    #include <stdlib.h>
    #define OK 1
    #define ERROR 0
    typedef int ElemType;
    typedef int Status;
    typedef struct list List;
    struct list
    {
        ElemType data;
        List* next;
    };
    Status CreateList(List *&L,int n);
    Status ListPrintf(List *L);
    void merge(List *L1,List *L2,List *&L3);
    void merge01(List *L1,List *L2,List *&L3);
    void merge02(List* &L1,List* &L2,List* &L3);
    void mergebook(List* &L1,List* &L2,List* &L3);
    void merge01book(List* &L1,List* &L2,List* &L3);
    void Difference(List* &L1,List* &L2,int &n);
    void Difference(List* &La,List* &Lb,int &n);
    void DisCompose(List *&L1,List* &L2,List *&L3);
    void Max(List *L1,int &n);
    void inverse(List *&L1);
    int main()
    {
        List *L1,*L2,*L3,*L4;
        int n1,n2,n=0;
        printf("请输入链表L1的长度:\n");
        scanf("%d",&n1);
        CreateList(L1,n1);
        ListPrintf(L1);
    //    printf("请输入链表L2的长度:\n");
    //    scanf("%d",&n2);
    //    CreateList(L2,n2);
    //    ListPrintf(L2);
    
    //    printf("合并后递增有序:\n");
    //    mergebook(L1,L2,L3);
    //    ListPrintf(L3);
    
    //    printf("合并后递减有序:\n");
    //    merge01book(L1,L2,L4);
    //    ListPrintf(L4);
    
    //    printf("L1和L2的交集为:\n");
    //    merge02(L1,L2,L3);
    //    ListPrintf(L3);
    
    //    printf("L1和L2的差集为:\n");
    //    Difference(L1,L2,n);
    //    ListPrintf(L1);
    //    printf("长度为:%d\n",n);
    
    //    DisCompose(L1,L2,L3);
    //    printf("L2为:\n");
    //    ListPrintf(L2);
    //    printf("L3为:\n");
    //    ListPrintf(L3);
    
    //    Max(L1,n);
    //    printf("链表L1中最大的值为:%d\n",n);
    
        inverse(L1);
        ListPrintf(L1);
    }
    Status CreateList(List *&L,int n)       //创建链表，返回链表的地址-----尾插法创建链表，链表是顺序插入的
    {
        List *end,*node;
        L = (List*)malloc(sizeof(List));    //创建头结点，并申请堆空间
        L->next = NULL;                     //头结点指针域置空
        end = L;                            //使尾结点指向头结点
        printf("请输入链表中的数据:\n");
        for(int i=0; i<n; i++)
        {
            node = (List *)malloc(sizeof(List));     //创建子节点，并申请堆空间
            scanf("%d",&node->data);
            node->next = NULL;                       //新建子节点的指针域置空
            end->next = node;                        //尾结点的指针域指向新建子节点(让上一个节点指针域保存下一个节点的地址)
            end = node;                              //尾结点指向新建子节点
        }
    }
    //将两个递增的有序链表合并成一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据
    void merge(List *L1,List *L2,List *&L3) //尾插法合并链表，链表顺序
    {
        List *p = L1->next;
        List *q = L2->next;
        List *pr = L3;
        L3 = L1;  //将L1的头结点赋给L3
        L3->next = NULL;
        free(L2);   //释放L2的头结点
        pr = L3;   //pr指向L3
        while(p&&q)
        {
            if(p->data<q->data)
            {
                pr->next = p;
                p = p->next;
                pr = pr->next;
            }
            else if(p->data>q->data)
            {
                pr->next = q;
                q = q->next;
                pr = pr->next;
            }
            else
            {
                pr->next = p;
                p = p->next;
                pr = pr->next;
                q = q->next;
            }
        }
        if(p)
        {
            pr->next = p;
        }
        if(q)
        {
            pr->next = q;
        }
    
    }
    void mergebook(List* &L1,List* &L2,List* &L3)
    {
        //合并链表L1和L2，合并后的新表用L3指向
        List *p = L1->next;
        List *q = L2->next;
        //p,q分别为L1，L2的工作指针，初始化为链表的首元结点
        List *pr,*pb;
        L3 = L1;    //将L1的头结点作为L3的头结点
        pr = L3;
        while(p&&q)
        {
            if(p->data<q->data)
                //取L1，L2中较小的元素插入到L3中，pr指针后移
            {
                pr->next = p;
                pr = p;
                p = p->next;
            }
            else if(p->data<q->data)
            {
                pr->next = q;
                pr = q;
                q = q->next;
            }
            else
                //当L1，L2中元素值相等，将p插入到L3中，删除q所指L2中的节点
            {
                pr->next = p;
                pr = p;
                p = p->next;
                pb = q->next;
                delete q;
                q = pb;
            }
        }
        pr->next = p?p:q;
        //插入p，q剩余段到L3中
        delete L2;
        //释放L2的头结点
    }
    //将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据
    void merge01(List *L1,List *L2,List *&L3) //头插法合并链表，逆序
    {
        List *p = L1->next;
        List *q = L2->next;
        List *pr;
        L3 = L1;
        L3->next = NULL;
        pr = L3;
        while(p&&q)
        {
            if(p->data<q->data)
            {
                pr = p;
                p = p->next;
                pr->next = L3->next;
                L3->next = pr;
            }
            else
            {
                pr = q;
                q = q->next;
                pr->next = L3->next;
                L3->next = pr;
            }
        }
        while(p)
        {
            pr = p;
            p = p->next;
            pr->next = L3->next;
            L3->next = pr;
        }
        while(q)
        {
            pr = q;
            q = q->next;
            pr->next = L3->next;
            L3->next = pr;
        }
    }
    void merge01book(List* &L1,List* &L2,List* &L3)
    {
        //合并链表L1和L2，合并后的新表用L3指向
        List *p = L1->next;
        List *q = L2->next;
        //p,q分别为L1，L2的工作指针，初始化为链表的首元结点
        List *pr,*px;
        L3 = L1;
        pr = L3;
        L3->next = NULL;
        while(p||q)
        {
            //只要有一个非空表，用px指向待摘取的元素
            if(!p)
            //L1表为空，用px指向q，q指针后移
            {
                px = q;
                q = q->next;
            }
            else if(!q)
            //L2表为空，用px指向p，p指针后移
            {
                px = p;
                p = p->next;
            }
            else if(p->data<=q->data)
            //取较小者（包括相等）L1中的元素，用px指向p，p指针后移
            {
                px = p;
                p = p->next;
            }
            else
            //取较小者L2中元素，用px指向q，q指针后移
            {
                px = q;
                q = q->next;
            }
            //将L3的指针域赋给px的指针域
            px->next = L3->next;
            //L3指向px（头插法）
            L3->next = px;
        }
        delete L2;
    }
    //已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A和B的交集，并存放在A链表中
    void merge02(List* &L1,List* &L2,List* &L3)
    //将L1和L2相等的节点放入L3中，并删除此时L2的节点，L1大于L2时，L2后移并删除原节点，L1小于L2，L2后移并删除原节点
    {
        List *p = L1->next;
        List *q = L2->next;
        //p和q分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
        List *pr,*px;
        L3 = L1;
        pr = L3;
        //用L1的头结点作为L3的头结点
        L3->next = NULL;
        while(p&&q)
        {
            if(p->data == q->data)      //交集并入结果表中。
            {
                pr->next = p;
                pr = p;
                p = p->next;
                px = q->next;
                delete q;
                q = px;
            }
            else if(p->data>q->data)
            {
                px = q->next;
                delete q;
                q = px;
            }
            else
            {
                px = p->next;
                delete p;
                p = px;
            }
        }
        while(p)        //释放结点空间
        {
            px = p->next;
            delete p;
            p = px;
        }
        while(q)        //释放结点空间
        {
            px = q->next;
            delete q;
            q = px;
        }
        delete L2;      //释放L2的头结点
    }
    //已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），
    //并以同样的形式存储，同时返回该集合的元素个数
    void Difference(List* &L1,List* &L2,int &n)
    //差集的结果存储于单链表L1中，n是结果集合中元素个数，调用时为L1长度
    //删除L1中与L2相等的节点
    {
        List *p = L1->next;
        List *q = L2->next;
        //p和q分别是链表L1和L2的工作指针,初始化为相应链表的第一个结点
        List *px = L1,*pr;  //px为L1中p所指结点的前驱结点的指针
        while(p)
        {
            p = p->next;
            n++;
        }
        p = L1->next;
        while(p&&q)
        {
            if(p->data == q->data)
            {
                pr = p->next;
                px->next = pr;
                delete p;
                p = pr;
                n--;
            }
            else if(p->data<q->data)
            {
                px = p;
                p = p->next;
            }
            else
            {
                q = q->next;
            }
        }
    }
    //设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C,其中B表的节点为A表中值小于0的节点，而C表的节点为A表中值大于0的节点
    //(链表A中的元素为非0整数，要求B,C表利用A表中的节点)
    void DisCompose(List *&L1,List* &L2,List* &L3)
    {
        List *p = L1->next; //p为L1的工作节点
        List *q,*pr,*pb;
        L2 = L1;            //L2指向L1的头节点
        L2->next = NULL;    //头结点指针域置空
        L3 = (List *)malloc(sizeof(List));  //为L3头结点申请堆空间
        L3->next = NULL;    //头结点指针域置空
        while(p)
        {
            pb = p->next;   //pb保存p后继的地址
            if(p->data<0)   //使用头插法将元素插入到L2中
            {
                p->next = L2->next;
                L2->next = p;
            }
            else
            {
                p->next = L3->next;
                L3->next = p;
            }
            p = pb;
        }
    }
    //设计一个算法，通过一趟遍历在单链表中确定值最大的结点
    void Max(List *L1,int &n)
    {
        List *p = L1->next;
        int max = p->data;
        List *q = p->next;
        while(q)
        {
            if(p->data<q->data)
            {
                max = q->data;
                p = q;
                q = q->next;
            }
            else
            {
                p = q;
                q = q->next;
            }
        }
        n = max;
    }
    //设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间
    void inverse(List *&L1)
    //算法思想:创建L2指针，使其指向L1头结点，将L1每个节点用头插法插入到L2中，最后将L2的地址赋给L1
    {
        List *p = L1->next;
        List *L2 = L1,*pr;
        L2->next = NULL;
        while(p)
        {
            pr = p;
            p = p->next;
            pr->next = L2->next;
            L2->next = pr;
        }
        L1 = L2;
    }
    Status ListPrintf(List *L)
    {
        List* p = L->next;
        while(p)
        {
            printf("%d\t",p->data);
            p = p->next;
        }
        printf("\n");
        return OK;
    }