【练习】c++单向链表求交集

Bertha 。 2023-01-13 09:29 96阅读 0赞

思路：先递增排序再二路归并

![在这里插入图片描述][20210417110703104.png]  
代码：

//直接插入排序
    void sort(node*& L) { 
        node* p = L->next->next;
      
        node* q;
        L->next->next = NULL;//构建只含一个数据结点的有序表
        node* pre = L;
        while (p != NULL) { 
            pre = L;//注意每次最外面的while中都要初始化pre
            q = p->next;//q保存当前p结点的后继结点
            while (pre->next != NULL && pre->next->data < p->data)
                pre = pre->next;
            p->next = pre->next;//当pre->next->data>p->d%ata 在pre后面插入p结点 因为p的数据更小 按递增排序
            pre->next = p;
            p = q;//p指向原来的后继结点
        }
    }
    
    void jiao(node* a, node* b, node*& c) { 
        
        node* pa = a->next, * pb = b->next;
        node* s, * r;
        c = new node;
     // c->next = NULL;
        r = c;
        while (pa != NULL && pb != NULL) { 
           
            if (pa->data == pb->data) { 
                s = new node;
                s->data = pa->data;
                s->next = c->next;
                c->next = s;
                pa = pa->next;
                pb = pb->next;
            }
            else if (pb->data < pa->data) { 
                pb = pb->next;
            }
            else { 
                pa = pa->next;
                
            }
        }
    
    }
    
    int main()
    { 
        srand(0);
        node* begin=new node;
        begin->next = NULL;
        node* m = new node;
    
        m->data = rand() % 15;
        //cout << m->data;
          m->next= begin->next;
          begin->next = m;
        node* n = new node;
        n->data = rand() % 7;
      n->next= begin->next;
      begin->next = n;
        node* nn = new node;
    
        nn->data = rand() % 20;
        nn->next = begin->next;
        begin->next = nn;
        node* jj = new node;
        jj->data = 10;
        jj->next = begin->next;
        begin->next = jj;
       
      sort(begin);
    
      node* copy_m = begin;
      cout << "第一个链表：";
      while (copy_m->next) { 
    
          cout << copy_m->next->data << ",";
          copy_m = copy_m->next;
      }
      node* begin2 = new node;
      begin2->next = NULL;
      node* m2 = new node;
    
      m2->data = rand() % 15;
      //cout << m->data;
      m2->next = begin2->next;
      begin2->next = m2;
      node* n2 = new node;
      n2->data = 5;
      n2->next = begin2->next;
      begin2->next = n2;
      node* nn2 = new node;
    
      nn2->data = 8;
      nn2->next = begin2->next;
      begin2->next = nn2;
      node* jj2 = new node;
      jj2->data = 10;
      jj2->next = begin2->next;
      begin2->next = jj2;
      node* copy_m2 = begin2;
      sort(begin2);
      cout << "第二个链表：";
      while (copy_m2->next) { 
    
          cout << copy_m2->next->data << ",";
          copy_m2 = copy_m2->next;
      }
      cout << endl;
      cout << "交集：";
      node* c = new node;
      c->next = NULL;
      jiao(begin, begin2, c);
      while (c != NULL) { 
          cout << c->next->data<<"->";
          c = c->next;
      }
    
    }

[20210417110703104.png]: /images/20221022/cc394825435d406eac8e0b66f9f8a938.png