C++合并有序链表,C\C++交流,技术交流,鱼C论坛

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

C++合并有序链表

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

输入样例：
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;
            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;
   for(i=0;i<m;i++)
   {
            cin >> a;
      }
   LinkList la(a,m);

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

   //Todo:用与la相同方式创建单链表lb
   cin >> n;
   int * b = new int;
   for(i=0;i<n;i++)
   {
            cin >> b;
      }
   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里的代码，别的代码题目给的尽量不动{:5_100:}

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

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

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;
            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;
   for(i=0;i<m;i++)
   {
         cin >> a;
   }
   LinkList la(a,m);

   //Todo:用与la相同方式创建单链表lb
   cin >> n;
   int b;
   for(i=0;i<n;i++)
   {
         cin >> b;
   }
   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;
}

页: [1]

鱼C论坛's Archiver

C++合并有序链表