已知集合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; } 新闻热点
疑难解答
