Celia_D 2019-12-11 15:17 采纳率: 50%
浏览 1012
已采纳

将两个递增的双向链表合并问题

将两个排好序的双向链表合并成一个,不允许有重复数据,链表1为1 2 3 4 6
链表2为5 6 8 9 10,合并后为1 2 3 4 6 8 9 10缺少了5,麻烦各位看一下是为什么啊?

// shiyan.cpp : 定义控制台应用程序的入口点。
//
/* C program to insetail nodes in doubly 
linked list such that list remains in 
ascending order on printing from left 
to right */
#include "stdafx.h"
#include <iostream>
using namespace std;
#include<stdio.h> 
#include<stdlib.h> 
#include<fstream>

// A linked list node 
struct Node 
{  
    int data; 
    struct Node *prior; 
    struct Node *next; 
}; 
// Function to insetail new node 
void nodeInsetail(struct Node **head, struct Node **tail,int key) 
{ 
    struct Node *p = new Node; 
    p->data = key; 
    p->next = NULL; 
    // If first node to be insetailed in doubly linked list 
    if ((*head) == NULL) 
    { 
        (*head) = p; 
        (*tail) = p; 
        (*head)->prior = NULL; 
        return; 
    } 
    // If node to be insetailed has value less than first node 
    if ((p->data) < ((*head)->data)) 
    { 
        p->prior= NULL; 
        (*head)->prior = p; 
        p->next = (*head); 
        (*head) = p; 
        return; 
    } 
    // If node to be insetailed has value more than last node 
    if ((p->data) > ((*tail)->data)) 
    { 
        p->prior = (*tail); 
        (*tail)->next = p; 
        (*tail) = p; 
        return; 
    } 
    // Find the node before which we need to insert p. 
     struct Node *temp = new Node; 
     temp = (*head)->next; 
     while ((temp->data) < (p->data)) 
        temp = temp->next; 
    // Insert new node before temp 
    (temp->prior)->next = p; 
    p->prior= temp->prior; 
    temp->prior = p; 
    p->next = temp; 
} 

// Function to print nodes in from left to right 
void printList(struct Node *temp) 
{ 
    while (temp != NULL) 
    { 
        printf("%d ", temp->data); 
        temp = temp->next; 
    } 
} 

// Driver program to test above functions 
struct Node *head1=NULL;
struct Node *tail1=NULL;
struct Node *head2=NULL;
struct Node *tail2=NULL;

int _tmain(int argc, _TCHAR* argv[])
{
    int num[10];
    int datalen=0;
    ifstream file("linklist.txt");
    while( ! file.eof() )
    file>>num[datalen++];
    file.close();
    for(int i=0;i<5;i++)
    {
        nodeInsetail(&head1, &tail1,num[i]); 
    }
    printf("Doubly linked list1 is:"); 
    printList(head1);
    printf("\n");
    for(int j=5;j<10;j++)
    {
        nodeInsetail(&head2, &tail2,num[j]); 
    }
    printf("Doubly linked list2 is:"); 
    printList(head2);
    printf("\n");

    Node *phead =head1;//最终返回的头数据节点
    Node *p=head1->next;//p循环的是链表1
    Node *q=head2;//q循环的是链表2
    if(p->data > q->data)
    {
        phead = head2;
        p = head2->next;
        q = head1;
    }
    Node* s=phead;//记录新链表的最后一个节点,方便下一次接上新节点
    while(p!=NULL && q!=NULL)
    {
        if(p->data < q->data)
        {
            s->next = p;
            p->prior=s;
            p = p->next;
            s = s->next;
        }
        else if(p->data = q->data)
        {
            s->next= p;
            p->prior=s;
            p=p->next;
            Node *x=q->next;//备用元素指向
            free(q);
            q=x;
        }
        else if(p->data > q->data)
        {
            s->next = q;
            q->prior=s;
            q = q->next;
            s = s->next;
        }
    }
    if(p == NULL)//链表1先遍历完,说明另一链表还有数据得接过来
    {
        s->next = q;
        q->prior=s;
    }
    if(q == NULL)//链表2先遍历完,因为此时主链表的结构已经发生变化,所以仍需拼接过来
    {
        s->next = p;
        p->prior=s;
    }
    while(phead)
     {
     printf("%d ",phead->data);
     phead=phead->next;
     }
    return 0;
}

图片说明

  • 写回答

1条回答 默认 最新

  • QiQaWgYu 2019-12-11 18:33
    关注
        Node* phead, * p, * q, * s, * t;
        if (head1->data > head2->data) {
            phead = head2;
            q = head1;
        }
        else {
            phead = head1;
            q = head2;
        }
        p = phead;
        s = phead;
        while (p != NULL && q != NULL)
        {
            if (p->data < q->data)
            {
                s = p;
                p = p->next;
            }
            else if (p->data == q->data)
            {
                q = q->next;
                if (q)
                    free(q->prior);
                else
                    break;
            }
            else
            {
                t = q->next;
                p->prior->next = q;
                q->prior = p->prior;
                q->next = p;
                p->prior = q;
                q = t;
            }
        }
        if (p == NULL)
        {
            s->next = q;
            q->prior = s;
        }
        while (phead)
        {
            printf("%d ", phead->data);
            phead = phead->next;
        }
        return 0;
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题