编程知识 cdmana.com

带头结点且递增有序的单链表A、B(A、B中元素个数分别为m、n)分别存储了一个集合。设计算法,求A、B的差集 (仅在A中出现不在B中出现),并存在A中,要求保持递增有序性

/*问题:已知带头结点且递增有序的单链表A、B(A、B中元素个数分别为m、n)分别存储了一个集合。设计算法,求A、B的差集
(仅在A中出现不在B中出现),并存在A中,要求保持递增有序性
*/
// 思路:由于AB都是递增有序的,用A中的每一个元素与B中的全部元素作比较,若是相同,则删除该元素节点,这样删除之后剩下的部分也一定是有序的
#include "stdio.h"
#include<stdlib.h>
typedef struct Node{    //结构体
    int data;
    Node *next;
}Node;
void init(Node *&p);
void listCreate(Node *&p,int n);
void Traversal(Node *&p);

void differentSet(Node *&A,Node *&B,int m,int n){   //参数:链表A、b,A元素个数m,B元素个数n
    Node *a = A->next;
    Node *b;
    Node *p = A;   //p作为a的前驱,删除节点的时候用
    int tmp,flag=0;   //tmp存储A的元素,flag标志A有没有发生删除
    while(a!=NULL){
        flag = 0;       
        b = B->next;    //每次a与B中元素比较完b都回到第一个节点
        tmp = a->data;
        while(b!=NULL){
            if(tmp==b->data){  //删除A中值为tmp的节点
                p->next = a->next;
                free(a);
                flag = 1;   //说明发生了删除
                break;      //删除了就可以比较下一个数了,减少比较次数
            }
            b=b->next;  //b后移;
        }
        //根据A是否发生了删除,接下来a与p有两种移动方式:1、发生删除,删除后a为空指针,要让a重新作为p的后继(a=p->next);2、没有发生删除:a、p后移
        //通过判断flag获取接下来的移动方式
        if(flag==1){    //假如发生了删除,那么a就等于p的后继
            a=p->next;
        }else{     //假如没有发生删除,那么a,p都后移;
            p=a;
            a=a->next;
        }
    }
}

int main(){
    Node *A = (Node *)malloc(sizeof(Node));
    Node *B = (Node *)malloc(sizeof(Node));
    init(A);
    init(B);
    int arr1[]={1,2,3,4,7,8,9};  //7
    int arr2[]={4,5,6,7};    //4
    //差集:12389
    for(int i=6;i>=0;i--){
        listCreate(A,arr1[i]); 
    }
    for(int i=3;i>=0;i--){
        listCreate(B,arr2[i]);
    }
    differentSet(A,B,7,4);
    Traversal(A);
    getchar();
    return 0;
}
void init(Node *&p){    //初始化
    p->next = NULL;
}

void listCreate(Node *&p,int n){      //参数:头节点,数据
    Node *q = (Node *)malloc(sizeof(Node));
    //****头插法建立(插入)链表*********(后进先出)
    q->data = n;
    q->next = p->next;
    p->next = q;
    //****************
}



void Traversal(Node *&p){   //遍历
    Node *q = p->next;
    while (q != NULL)
    {
        printf("%d ",q->data);
        q = q->next;
    }
}

版权声明
本文为[封不烦]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/BreezeFeng/p/13956980.html

Scroll to Top