算法设计题2、(3)

【题目】

已知两个链表A和链表B分别表示两个集合,其元素递增排列。请设计一个算法用于求出A和B的交集,并存放到A链表中。

【思路分析】

1、定义两个指针a、b分别指向链表A和链表B的首元结点 和一个int类型的i变量用于记录要插入结点的位置
2、当a指向结点的data小于b指向的结点的data，a向后移动一个结点并且删除之前指向的结点
3、当a指针指向的data大于b指向的结点的data，b向后移动一个结点
4、当a指向的结点data等于b指向的结点data，就让a、b指针都向后移动一个结点并且将i++
5、如果a先指向NULL就直接退出循环,如果b先指向NULL就将a->next = NULL

【代码实现】

/**
  * 求链表A和链表B的交集 并存放在链表A中
  * @param A 链表A其元素递增
  * @param B 链表B其元素递增
  * @return
  */
Status JiaoSet(LinkList &A,LinkList B){
    int i=1;
    LNode* a = A->next;
    LNode* b = B->next;
    while (a && b){
        if (a->data.no < b->data.no){
            a = a->next;
            ListDelete(A,i);
        }else if (a->data.no > b->data.no) b=b->next;
        if(a && a->data.no == b->data.no){
            if (b->next == NULL){
                a->next = NULL;
                break;
            }else{
                a = a->next;
                b = b->next;
            }
            i++;
        }
    }
    return OK;
}
/**
 * 按照位置删除结点
 * @param L 链表
 * @param i 要删除结点的位置
 * @return
 */
Status ListDelete(LinkList &L,int i){
    LinkList p = L;
    int j = 0;
    while (p && j<i-1){
        p = p->next;
        j++;
    }
    if(!p || j>i-1){
        return ERROR;
    }
    LNode *q = p->next;
    p->next = q->next;
    delete q;
    return OK;
}

【头文件及主方法】

#include <iostream>
#include <string>
#define OK 1
#define ERROR 0
using namespace std;
typedef int Status;

struct ElemType{
    int no;
    string name;
};

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

/*初始化*/
Status InitList(LinkList &L){
    L = new LNode;
    L->next = NULL;
    return OK;
}
/*尾插法*/
 void CreateList_R(LinkList &L, int n){
     L = new LNode;
     L->next = NULL;//建立带头结点的空链表
     LNode *r = L;
    for (int i = 0; i < n; ++i) {
        LNode* p = new LNode;
        cout<<"输入学号和姓名以添加结点,用空格分隔"<<endl;
        cin>>p->data.no>>p->data.name;
        p->next = NULL;
        r->next = p;
        r = p;
    }
 }

int main(){
    LNode *L1;
    LNode *L2;
    InitList(L1);
    InitList(L2);
    CreateList_R(L1,5);
    cout<<"第二条链表"<<endl;
    CreateList_R(L2,3);
    JiaoSet(L1,L2);
    Show(L1);
}

算法设计题2、（4）

【题目】

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B的差集（即仅有在A中出现而不在B中出现的元素构成的集合）,并以同样的形式存储,同时返回该集合的元素个数。

【思路分析】

1、定义两个指针a、b分别指向链表A和链表B的首元结点 和一个int类型的i变量用于记录要插入结点的位置
2、当a指向结点的data小于b指向的结点的data，a向后移动一个结点并且i++
3、当a指针指向的data大于b指向的结点的data，b向后移动一个结点
4、当a指向的结点data等于b指向的结点data，就让a、b指针都向后移动一个结点并且删除a指针之前指向的结点
5、a或b指针只要有一个指向NULL就退出循环

【代码实现】

/**
 * 求链表A和链表B的差集（A中出现而不在B中出现）
 * @param A 链表A 其元素递增
 * @param B 链表B 其元素递增
 * @return 返回差集的链表的长度
 */
Status ChaSet(LinkList &A,LinkList B){
    int i=1;
    LNode* a = A->next;
    LNode* b = B->next;
    while (a && b){
        if (a->data.no < b->data.no){
            a = a->next;
            i++;
        }else if (a->data.no > b->data.no) b=b->next;
        if (b == NULL || a == NULL) break;
        if(a->data.no == b->data.no){
            a = a->next;
            b = b->next;
            ListDelete(A,i); //ListDelete()函数实现在上一题代码中
        }
    }
    return Length(A);
}

//求链表中元素的个数
int Length(LinkList L){
    int count = 0;
    LNode* p = L->next;
    if (!p)
        return 0;
    while (p){
        count++;
        p = p->next;
    }
    return count;
}

【头文件及主方法】

#include <iostream>
#include <string>
#define OK 1
#define ERROR 0
using namespace std;
typedef int Status;

struct ElemType{
    int no;
    string name;
};

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

int main(){
    LNode *L1;
    LNode *L2;
    InitList(L1);
    InitList(L2);
    CreateList_R(L1,5);
    cout<<"第二条链表"<<endl;
    CreateList_R(L2,3);
    int length = ChaSet(L1,L2);
    Show(L1);
    cout<<endl<<"差集长度："<<length;
}

求并集

【题目】

已知两个链表A和链表B分别表示两个集合,其元素递增排列。请设计一个算法用于求出A和B的交集,并存放到A链表中。

【代码实现】

/**
  * 求A和B链表的并集 并存放在A中
  * @param A 链表A 其元素递增排序
  * @param B 链表B 其元素递增排序
  */
 Status UnionSet(LinkList &A,LinkList B){
     int i=1;
     LNode* a = A->next;
     LNode* b = B->next;
     while (a && b){
         if (a->data.no >= b->data.no){
             ElemType e = {b->data.no,b->data.name};
             InsertByLocation(A,i,e);
             i++;
             b = b->next;
         }
         else if (b->data.no > a->data.no) {
             a = a->next;
             i++;
         }
     }
     return OK;
 }

/**
 * 根据位置插入结点
 * @param i 插入结点的位置
 * @param e 要插入的结点
 */
Status InsertByLocation(LinkList &L,int i,ElemType e){
    LinkList p = L;
    int j = 0;
    while (p && j<i-1){
        p = p->next;
        j++;
    }
    if (!p || j>i-1)
        return ERROR;
    /*插入结点*/
    LNode* s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}