编程知识 cdmana.com

A and B (the number of elements in a and B are m and N respectively) with the leading node and increasing order store a set respectively. The algorithm is designed to find the difference set of a and B (only in a, not in B), and exist in a, which requires

/* 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;
    }
}

版权声明
本文为[Can't be bothered]所创,转载请带上原文链接,感谢

Scroll to Top