[已解决]C++合并有序链表

旋转小代码 · 发表于 2020-9-23 16:25:58

问题描述：将两个非递减有序单链表合并成一个非递减有序单链表；

输入样例：
5
1 3 5 7 9
6
2 3 4 6 8 10

输出样例：
1 2 3 3 4 5 6 7 8 9 10
以下是我的代码，只有部分是自己写的，剩下是原题目，错误大致在于 Merge(LinkList &A, LinkList &B) 里。

#include <iostream> 
using namespace std; 
struct Node 
{ 
        int data; 
    
        Node *next; 
}; 
class LinkList 
{ 
public: 
    
        LinkList(int a[],int n);//尾插法在单链表中插入n个数据
        
        ~LinkList(); 
        
        void PrintList();
           
        Node * GetFirst(){return first;}

private: 
    
        Node *first; 
}; 

LinkList::LinkList(int a[],int n)
{ 
        first = new Node; //附设头结点

        Node *rear = first;
        
        int i;
        for(i=0;i<n;i++)
        {
                Node *s = new Node;
                s->data = a[i];
                rear->next = s;
                rear = s;
        }        
        rear->next = NULL;
} 

void LinkList::PrintList() 
{ 
        
        Node *p=first->next; 
        
        while(p) 
                
        { 
                
                cout<<p->data<<" "; 
        
                p=p->next; 
                
        } 
} 


LinkList::~LinkList() 
{ 
    
        Node *p=first,*s; 
    
        while(!p) 
                
        { 
        
                s=p; 
        
                p=p->next; 
        
                delete s; 
                
        } 
} 

void Merge(LinkList &A, LinkList &B)
{
        //Todo:将A和B两个非递减有序单链表合并，结果放到A链表中
        
        Node *p = A.GetFirst() ->next;
        Node *q = B.GetFirst() ->next;
        Node *s, *t;
        s = q;
        t = p;
        
//while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
        while(q->next!= nullptr)
        {
                for(int count = 0; count<m; count++)
                {
                        if(s->data >= p->data && s->next < p->next)
                        {
                                q = q->next ;
                                s->next =p->next ;
                                p->next =s;
                                s = q;
                        }
                        else
                        {
                                p = p->next;
                        }
                }
                
        }

}
int main()
{ 
        int m,i,x; 
    
        cin >> m;
        int a[m];
        for(i=0;i<m;i++)
        {
                cin >> a[i];
          }
        LinkList la(a,m);

        //Todo:用与la相同方式创建单链表lb
        cin >> n;
        int b[n];
        for(i=0;i<n;i++)
        {
                cin >> b[i];
          }
        LinkList lb(b,n);

        
            
        Merge(la,lb);

        la.PrintList();

        return 0; 
}

最佳答案

月排行榜 / 总排行榜

xieglt

2020-9-23 16:25:59

本帖最后由 xieglt 于 2020-9-23 17:29 编辑

#include <iostream> 
using namespace std; 

struct Node 
{ 
        int data; 
        struct Node *next; 
                
                bool operator > (const struct Node  & e)
                {
                        return (data > e.data) ? true : false;
                }

                bool operator < (const struct Node  & e)
                {
                        return (data < e.data) ? true : false;
                }
}; 

class LinkList 
{ 
public: 
    
        LinkList(int a[],int n);//尾插法在单链表中插入n个数据
        
        ~LinkList(); 
        
        void PrintList();
           
        Node * GetFirst(){return first->next;}
                
                void Clean()
                {
                        first->next = NULL;
                }

                void SetList(Node * p)
                {
                        first->next = p;
                }

private: 
    
        Node *first; 
}; 

LinkList::LinkList(int a[],int n)
{ 
        first = new Node; //附设头结点

        Node *rear = first;
        
        int i;
        for(i=0;i<n;i++)
        {
                Node *s = new Node;
                s->data = a[i];
                rear->next = s;
                rear = s;
        }        
        rear->next = NULL;
} 

void LinkList::PrintList() 
{ 
        
        Node *p=first->next; 
        
        while(p) 
                
        { 
                
                cout<<p->data<<" "; 
        
                p=p->next; 
                
        } 
} 


LinkList::~LinkList() 
{ 
    
        Node *p=first,*s; 
                
                //!p 循环条件逻辑错误,
        while(p != NULL) 
                
        { 
        
                s=p; 
        
                p=p->next; 
        
                delete s; 
                
        } 
} 

Node * MergeList(Node* l1,Node * l2)
{
        if(l1 == NULL)
        {
                return l2;
        }
        
        if(l2 == NULL)
        {
                return l1;
        }
        
        Node * lpHead = (* l1 < * l2) ? l1 : l2;
        Node * lpBig = (* l1 < * l2) ? l2 : l1;
        
        Node * lpSmall = lpHead;
        
        while(lpSmall != NULL)
        {
                if(lpSmall->next == NULL)
                {
                        lpSmall->next = lpBig;
                        break;
                }
                
                if(*(lpSmall->next) < * lpBig)
                {
                        lpSmall = lpSmall->next;
                }
                else
                {
                        Node * lpNode = lpSmall->next;
                        lpSmall->next = lpBig;
                        
                        lpSmall = lpBig;
                        lpBig = lpNode;
                }
        }        
        return lpHead;
}

void Merge(LinkList &A, LinkList &B)
{
        
        Node *p = A.GetFirst();
        Node *q = B.GetFirst();
        Node *s, *t;
        s = q;
        t = p;

        A.SetList(MergeList(p,q));
        //将两个链表合并后，要把后一个链表清空，否则释放内存释放两次
        B.Clean();
        
        //while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
/*        while(q->next!= nullptr)
        {
                for(int count = 0; count<m; count++)
                {
                        if(s->data >= p->data && s->next < p->next)
                        {
                                q = q->next ;
                                s->next =p->next ;
                                p->next =s;
                                s = q;
                        }
                        else
                        {
                                p = p->next;
                        }
                }
                
    }
*/
}

int main()
{ 
        int m,n,i,x; 
    
        cin >> m;
                //动态数组不能这么定义，得用new生成
                //int a[m]
        int * a = new int[m];
        for(i=0;i<m;i++)
        {
                cin >> a[i];
        }
        LinkList la(a,m);
                delete[] a;

        //Todo:用与la相同方式创建单链表lb
        cin >> n;
        int * b = new int[n];
        for(i=0;i<n;i++)
        {
                cin >> b[i];
          }
        LinkList lb(b,n);
                delete [] b;

        
            
        Merge(la,lb);

        la.PrintList();

        return 0; 
}

跳转到最佳答案楼层

xieglt · 发表于 2020-9-23 16:25:59

这个最佳答案由 xieglt 给出，感谢 xieglt 的回答。

单击隐藏图章

本帖最后由 xieglt 于 2020-9-23 17:29 编辑

#include <iostream> 
using namespace std; 

struct Node 
{ 
        int data; 
        struct Node *next; 
                
                bool operator > (const struct Node  & e)
                {
                        return (data > e.data) ? true : false;
                }

                bool operator < (const struct Node  & e)
                {
                        return (data < e.data) ? true : false;
                }
}; 

class LinkList 
{ 
public: 
    
        LinkList(int a[],int n);//尾插法在单链表中插入n个数据
        
        ~LinkList(); 
        
        void PrintList();
           
        Node * GetFirst(){return first->next;}
                
                void Clean()
                {
                        first->next = NULL;
                }

                void SetList(Node * p)
                {
                        first->next = p;
                }

private: 
    
        Node *first; 
}; 

LinkList::LinkList(int a[],int n)
{ 
        first = new Node; //附设头结点

        Node *rear = first;
        
        int i;
        for(i=0;i<n;i++)
        {
                Node *s = new Node;
                s->data = a[i];
                rear->next = s;
                rear = s;
        }        
        rear->next = NULL;
} 

void LinkList::PrintList() 
{ 
        
        Node *p=first->next; 
        
        while(p) 
                
        { 
                
                cout<<p->data<<" "; 
        
                p=p->next; 
                
        } 
} 


LinkList::~LinkList() 
{ 
    
        Node *p=first,*s; 
                
                //!p 循环条件逻辑错误,
        while(p != NULL) 
                
        { 
        
                s=p; 
        
                p=p->next; 
        
                delete s; 
                
        } 
} 

Node * MergeList(Node* l1,Node * l2)
{
        if(l1 == NULL)
        {
                return l2;
        }
        
        if(l2 == NULL)
        {
                return l1;
        }
        
        Node * lpHead = (* l1 < * l2) ? l1 : l2;
        Node * lpBig = (* l1 < * l2) ? l2 : l1;
        
        Node * lpSmall = lpHead;
        
        while(lpSmall != NULL)
        {
                if(lpSmall->next == NULL)
                {
                        lpSmall->next = lpBig;
                        break;
                }
                
                if(*(lpSmall->next) < * lpBig)
                {
                        lpSmall = lpSmall->next;
                }
                else
                {
                        Node * lpNode = lpSmall->next;
                        lpSmall->next = lpBig;
                        
                        lpSmall = lpBig;
                        lpBig = lpNode;
                }
        }        
        return lpHead;
}

void Merge(LinkList &A, LinkList &B)
{
        
        Node *p = A.GetFirst();
        Node *q = B.GetFirst();
        Node *s, *t;
        s = q;
        t = p;

        A.SetList(MergeList(p,q));
        //将两个链表合并后，要把后一个链表清空，否则释放内存释放两次
        B.Clean();
        
        //while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
/*        while(q->next!= nullptr)
        {
                for(int count = 0; count<m; count++)
                {
                        if(s->data >= p->data && s->next < p->next)
                        {
                                q = q->next ;
                                s->next =p->next ;
                                p->next =s;
                                s = q;
                        }
                        else
                        {
                                p = p->next;
                        }
                }
                
    }
*/
}

int main()
{ 
        int m,n,i,x; 
    
        cin >> m;
                //动态数组不能这么定义，得用new生成
                //int a[m]
        int * a = new int[m];
        for(i=0;i<m;i++)
        {
                cin >> a[i];
        }
        LinkList la(a,m);
                delete[] a;

        //Todo:用与la相同方式创建单链表lb
        cin >> n;
        int * b = new int[n];
        for(i=0;i<n;i++)
        {
                cin >> b[i];
          }
        LinkList lb(b,n);
                delete [] b;

        
            
        Merge(la,lb);

        la.PrintList();

        return 0; 
}

旋转小代码 · 发表于 2020-9-23 18:28:27

xieglt 发表于 2020-9-23 17:28

能不能只改while里的代码，别的代码题目给的尽量不动

fury可 · 发表于 2020-9-23 21:30:36

你这s 和 t 有什么定义的必要么而且还把s 和 p混用

fury可 · 发表于 2020-9-24 14:22:01

#include <iostream> 
using namespace std; 
struct Node 
{ 
        int data; 
    
        Node *next; 
}; 
class LinkList 
{ 
public: 
    
        LinkList(int a[],int n);//尾插法在单链表中插入n个数据
        
        ~LinkList(); 
        
        void PrintList();
           
        Node * GetFirst(){return first;}

private: 
    
        Node *first; 
}; 

LinkList::LinkList(int a[],int n)
{ 
        first = new Node; //附设头结点

        Node *rear = first;
        
        int i;
        for(i=0;i<n;i++)
        {
                Node *s = new Node;
                s->data = a[i];
                rear->next = s;
                rear = s;
        }        
        rear->next = nullptr;
} 

void LinkList::PrintList() 
{ 
        
        Node *p=first->next; 
        
        while(p) 
                
        { 
                
                cout<<p->data<<" "; 
        
                p=p->next; 
                
        } 
} 


LinkList::~LinkList() 
{ 
    
        Node *p=first,*s; 
    
        while(p) 
                
        { 
        
                s=p; 
        
                p=p->next; 
        
                delete s; 
                
        } 
} 

void Merge(LinkList &A, LinkList &B, int m,int n)
{
        //Todo:将A和B两个非递减有序单链表合并，结果放到A链表中
        
        Node *p = A.GetFirst() ->next;
        Node *q = B.GetFirst() ->next;
        Node *s, *t, *j;
        t = A.GetFirst()->next;
        s = B.GetFirst()->next;
        
//while里的m 和n 是主函数的变量，不知道怎么访问，或者有别的方法？求指教=_=      
        while(p)
        {
                if(p->data<q->data&&p)
                {
                    t = p;
                    p = p->next;
                }
                else
                {
                    t->next = s;
                    while((q->data<=p->data)&&q)
                    {
                        s = q;
                        q = q->next;
                    }
                    s->next = p;
                    s = q;
                }
        }
        if(q)
        {
            t->next = q;
        }

}
int main()
{ 
        int m,n,i,x; 
    
        cin >> m;
        int a[m];
        for(i=0;i<m;i++)
        {
            cin >> a[i];
        }
        LinkList la(a,m);

        //Todo:用与la相同方式创建单链表lb
        cin >> n;
        int b[n];
        for(i=0;i<n;i++)
        {
            cin >> b[i];
        }
        LinkList lb(b,n);

        cout<< "Merge"<<endl;
            
        Merge(la,lb,m,n);

        la.PrintList();

        return 0; 
}

孟婆汤 · 发表于 2020-9-25 11:06:25

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node
{
        Node* pNext;
        int data;
}Node, *pNode;

typedef struct Link
{
        int cur_len;
        pNode pHeader;
}Link, *PLink;


PLink InitLink()
{
        pNode pHeader = (pNode)malloc(sizeof(Node));
        memset(pHeader, 0, sizeof(Node));
        pHeader->data = 0;
        pHeader->pNext = NULL;

        PLink plinkNode = (PLink)malloc(sizeof(Link));
        memset(plinkNode, 0, sizeof(Link));
        plinkNode->cur_len = 0;
        plinkNode->pHeader = pHeader;

        return plinkNode;
}

bool AddNode(PLink plinkNode, int data)
{
        pNode pHeader = plinkNode->pHeader;
        if (pHeader == NULL)
        {
                printf("无效链表\n");
                return false;
        }
        pNode pTempNode = (pNode)malloc(sizeof(Node));
        memset(pTempNode, 0, sizeof(Node));
        pTempNode->data = data;
        pTempNode->pNext = NULL;

        pNode pCurNode = pHeader;
        while (pCurNode->pNext != NULL)
        {
                pCurNode = pCurNode->pNext;
        }
        pCurNode->pNext = pTempNode;
        plinkNode->cur_len++;
        return true;
}

bool InsertSortData(PLink plinkNode, int data)
{
        pNode pHeader = plinkNode->pHeader;
        if (pHeader == NULL)
        {
                printf("无效链表\n");
                return -1;
        }

        pNode pCurNode = pHeader;
        int flag = 0;
        while (pCurNode->pNext != NULL)
        {
                if (pCurNode->pNext->data >= data)
                {
                        pNode pTempNode = (pNode)malloc(sizeof(Node));
                        pTempNode->data = data;
                        pTempNode->pNext = pCurNode->pNext;
                        pCurNode->pNext = pTempNode;
                        flag = 1;
                        plinkNode->cur_len++;
                        break;
                }
                else
                {
                        pCurNode = pCurNode->pNext;
                }
        }
        // 最后一个
        if (flag == 0)
        {
                pNode pTempNode = (pNode)malloc(sizeof(Node));
                pTempNode->data = data;
                pTempNode->pNext = pCurNode->pNext;
                pCurNode->pNext = pTempNode;
                plinkNode->cur_len++;
        }
}

void MergeLink(PLink plinkNode1, PLink plinkNode2)
{
        // 将 Plink2 中的元素，插入 Plink1中

        pNode pHeader1 = plinkNode1->pHeader;
        pNode pHeader2 = plinkNode2->pHeader;


        pNode pCurNode1 = pHeader1->pNext;
        pNode pCurNode2 = pHeader2->pNext;


        /*
        5
        1 3 5 7 9
        6
        2 3 4 6 8 10
        */
        for (int i = 0; i < plinkNode2->cur_len; i++)
        {
                InsertSortData(plinkNode1, pCurNode2->data);
                pHeader2->pNext = pCurNode2->pNext;
                free(pCurNode2);
                pCurNode2 = pHeader2->pNext;
        }
        free(pHeader2);
        free(plinkNode2);

}

int main()
{
        PLink plinkNode1 = InitLink();
        PLink plinkNode2 = InitLink();
        for (int i = 1; i < 10; i+=2)
        {
                AddNode(plinkNode1, i);
        }
        for (int i = 2; i < 11; i+=2)
        {
                AddNode(plinkNode2, i);
        }

        MergeLink(plinkNode1, plinkNode2);


        system("pause");
        return 0;        
}

账号		自动登录	找回密码
密码			立即注册