已知集合A和B的元素分別用不含頭結點的單鏈表存儲，函數difference()用于求解集合A與B的差集，并將結果保存在集合A的單鏈表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成計算后A={10,20,30}。題意簡單說就是鏈表差集簡單操作。
[cpp] view plain copy
#include <iostream> using namespace std; struct node { int elem; node* next; }; void insert(node **rootp,int value) { node *newNode=new node; if (newNode==NULL) { cout<<" memory error /n"; } newNode->elem=value; newNode->next=*rootp; (*rootp)=newNode; } void PRintList(node *root) { if (root==NULL) { cout<<"empty list /n"; return ; } while (root) { cout<<root->elem<<" "; root=root->next; } cout<<endl; } void difference(node** LA , node* LB) { node *pa , *pb , *pre , *q; pre = NULL; pa=*LA; while(pa) { pb = LB; while(pb && pa->elem!=pb->elem)//在pb鏈表中找 pb = pb->next; if(pb) //如果找到了 則pb!=NULL { if(!pre) *LA = pa->next; //如果是第一個元素，直接移動*LA指向 else pre->next= pa->next; //如果不是第一個元素，改變pre指向，實現刪除pa的效果 q = pa; pa = pa->next; free(q); } else { pre=pa; //pa指向元素在LB中不存在，則pre指pa前一個位置，pa后移 pa = pa->next; } } } int main() { int a[]={5,7,9,10,12,4}; int b[]={4,5,6,7,9}; node *LA=NULL,*LB=NULL; for (int i=0;i<6;i++) { insert(&LA,a[i]); } for (int i=0;i<5;i++) { insert(&LB,b[i]); } difference(&LA,LB); PrintList(LA); return 0; } 新聞熱點
疑難解答
