首页 > 代码库 > 数据结构>>线性表【注意】-->链表求A-B（原A与B都递增，求完的A-B不改变A原来的顺序）

数据结构>>线性表【注意】-->链表求A-B（原A与B都递增，求完的A-B不改变A原来的顺序）

2024-07-17 16:05:35   213人阅读

/*关于链表的题目 * A、B是两个递增有序的单链表，元素个数分别是m和n，求 * 集合A-B，并将结果保存在A中，且仍然保持递增有序。 * converge_ab */#include <iostream.h>using namespace std;typedef struct lnode{    int data;    struct lnode * next;}lnode;int main(){    lnode * create_chain(int num,int interval,int start);    void converge_ab(lnode *A,lnode *B);    lnode * A,*B,*q,*p;    int m=4,n=7;     A=create_chain(4,3,2);        //2 5 8 11     B=create_chain(7,4,1);        //1 5 9 13 17 21 25     p=A;/*      while(p->next != NULL){            cout << p->next->data <<" ";            p=p->next;        }      cout << endl;     q=B;      while(q->next != NULL){            cout << q->next->data <<" ";            q=q->next;        }      cout << endl;    converge_ab(A,B,m,n);      p=A;*/     converge_ab(A,B);     p=A;      while(p->next != NULL){            cout << p->next->data <<" ";            p=p->next;        }}lnode * create_chain(int num,int interval,int start){    lnode * head=(lnode *)malloc(sizeof(lnode)),*p,*q=head;    int i;    for(i=0;i<num;i++){        p=(lnode *)malloc(sizeof(lnode));        p->data=http://www.mamicode.com/start+(i*interval);        p->next=NULL;        q->next=p;        q=q->next;    }    return head;}void converge_ab(lnode *A,lnode *B){    lnode * q=B->next,* r=A,* temp;    while(r->next!=NULL && q!=NULL){        if(r->next->data < q->data){            r=r->next;        }else if(r->next->data =http://www.mamicode.com/= q->data){            temp=r->next;            r->next=temp->next;            free(temp);        }else{            q=q->next;        }    }}
这里之前犯的错误是将后面的写成三个if，而不是else if。它们的区别在于：
 
如果是三个if， 这三个if在条件成立的情况下都会执行，假设第一个if已经执行了，这时r是改变了的，这样一旦改变了的r也符合后面的标准，就会继续执行下面的if
 
如果是if else的话，会选if...else if....else...里面三种情况之一来执行，执行完之后就会退出来，进行下一轮的循环。
 
（使两者等价的做法是将3个if的那种情况中，里面每一个if里面的最后加上continue）


联系
我们