/* problem ： A single linked list with known leading nodes and increasing order A、B（A、B The number of elements in is respectively m、n） A collection is stored separately . Design algorithm , seek A、B The difference between the set
( Only in A It doesn't appear in B It appears that ), And exist A in , It is required to keep increasing order
*/
// Ideas ： because AB It's all incremental and orderly , use A Every element in is associated with B Compare all the elements in , If it's the same , Delete the element node , In this way, the remaining parts must be orderly after deletion
#include "stdio.h"
#include<stdlib.h>
typedef struct Node{ // Structure
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){ // Parameters ： Linked list A、b,A Element number m,B Element number n
Node *a = A->next;
Node *b;
Node *p = A; //p As a The precursor of , Delete nodes with
int tmp,flag=0; //tmp Storage A The elements of ,flag sign A Did you delete
while(a!=NULL){
flag = 0;
b = B->next; // Every time a And B The comparison of Chinese elements is finished b All back to the first node
tmp = a->data;
while(b!=NULL){
if(tmp==b->data){ // Delete A The median is tmp The node of
p->next = a->next;
free(a);
flag = 1; // Indicates that a deletion has taken place
break; // Delete and you can compare the next number , Reduce the number of comparisons
}
b=b->next; //b Move backward ;
}
// according to A Whether a deletion has occurred , Next a And p There are two ways to move ：1、 A deletion occurred , After deleting a Null pointer , Must let a Do it again p In the subsequent (a=p->next);2、 There was no deletion ：a、p Move backward
// By judgment flag Get the next move
if(flag==1){ // If there is a deletion , that a Is equal to p In the subsequent
a=p->next;
}else{ // If there is no deletion , that a,p All backward ;
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
// Difference set ：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){ // initialization
p->next = NULL;
}
void listCreate(Node *&p,int n){ // Parameters ： Head node , data
Node *q = (Node *)malloc(sizeof(Node));
//**** Head insertion to create （ Insert ） Linked list *********( Last in, first out )
q->data = n;
q->next = p->next;
p->next = q;
//****************
}
void Traversal(Node *&p){ // Traverse
Node *q = p->next;
while (q != NULL)
{
printf("%d ",q->data);
q = q->next;
}
}
