博客

数据结构算法题

1. 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。

int MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递增链表,用原有的空间，不能有重复的数据
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){
        if(pa->data<pb->data){//比较较小的节点插入Lc中
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else if(pa->data>pb->data){
                pc->next=pb;
                pc=pb;
                pb=pb->next;
        }
        else{//有相同节点时选择其中一个链入Lc中，另一个则释放掉
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    pc->next=pa?pa:pb;
    return OK;
}

2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

int Union(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递减的链表,用原有的空间，可有重复的数据（用头插法，完成逆序）
    LinkList pa,pb,p;
    pa=La->next;
    pb=Lb->next;
    Lc=La;
    Lc->next=NULL;
    while(pa||pb){
        if(!pa){
            p=pb;
            pb=pb->next;
        }
        else if(!pb){
            p=pa;
            pa=pa->next;
        }
        else if(pa->data<=pb->data){
            p=pa;
            pa=pa->next;
        }
        else{
            p=pb;
            pb=pb->next;
        }
        p->next=Lc->next;
        Lc->next=p;//插入
    }
}

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

int Mix(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表求交集,用原有La的空间
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){//有一个表结束，就可以全部结束了
        if(pa->data==pb->data){
            pc->next=pa;//相交并入表
            pc=pa;
            pa=pa->next;
            u=pb->next;//释放空间
            free(pb);
            pb=u;
        }
        else if(pa->data<pb->data){//较小节点前移，等待比较
                u=pa->next;
                free(pa);
                pa=u;
        }
        else {
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    while(pa){
        u=pa->next;
        free(pa);
        pa=u;
    }
    while(pb){
        u=pb->next;
        free(pb);
        pb=u;
    }
    pc->next=NULL;//结尾标志
    free(Lb);
    return OK;
}

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

int Difference(LinkList &La,LinkList &Lb,int &n){//两个递增链表求A-B的差集,用原有La的空间
    LinkList pa,pb,pre;//从La表中修改将不是差集中的删除
    pa=La->next;
    pb=Lb->next;
    pre=La;//用pre作pa的头节点
    while(pa&&pb){
        if(pa->data<pb->data){
            pre=pa;
            pa=pa->next;
            n++;//计数
        }
        else if(pa->data>pb->data){
            pb=pb->next;
        }
        else {
            pre->next=pa->next;//删除不是差集中的结点
            free(pa);
            pa=pre->next;
        }
    }
    return OK;
}

5.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。

int Divide(LinkList &La,LinkList &Lb,LinkList &Lc){//将La分成两个分别大于零和小于零的Lb和Lc
    LinkList p,pc,pb;
    p=La->next;
    Lb=La;
    pb=Lb;
    Lc=(LinkList)malloc(sizeof(Lnode));
    pc=Lc;
    while(p){
        if(p->data>0){
            pb->next=p;
            pb=p;
            p=p->next;
        }
        else if(p->data<0){
            pc->next=p;
            pc=p;
            p=p->next;
        }
    }
    pb->next=NULL;//结束标记
    pc->next=NULL;
    return OK;
}

全部代码：

#include <iostream>
#define OK 1
#define ERROR 0
#include <stdio.h>
#include<stdlib.h>
#include<malloc.h>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode *next;
}Lnode,*LinkList;
int Initlist_L(LinkList &L);//建立一个空表，并将表头返回
int Create(LinkList &L);//将空表传入，为表中输入元素，在返回表头
int MergeList(LinkList &La,LinkList &Lb,LinkList &Lc);//两个递增链表合并为一个递增链表,用原有的空间，不能有重复的数据
int Union(LinkList &La,LinkList &Lb,LinkList &Lc);//两个递增链表合并为一个递减的链表,用原有的空间，可有重复的数据
int Mix(LinkList &La,LinkList &Lb,LinkList &Lc);//两个递增链表求交集,用原有La的空间
int Difference(LinkList &La,LinkList &Lb,int &n);//两个递增链表求A-B的差集,用原有La的空间
int Divide(LinkList &La,LinkList &Lb,LinkList &Lc);//将La分成两个分别大于零和小于零的Lb和Lc
int OperateMenu();//建立菜单，提示操作代码
void printfs(LinkList L);//将线性表L中的元素依次打印
int main(){
    LinkList La=NULL;
    LinkList Lb=NULL;
    LinkList Lc=NULL;
    int i=1,n=0;
    while(i){
    switch(OperateMenu()){
        case 1:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            MergeList(La,Lb,Lc);
            printf("合并完的链表为：");
            printfs(Lc);
            break;
        case 2:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            Union(La,Lb,Lc);
            printf("合并完的链表为：");
            printfs(Lc);
            break;
        case 3:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            Mix(La,Lb,Lc);
            printf("合并完的链表为：");
            printfs(Lc);
            break;
        case 4:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            Difference(La,Lb,n);
            printf("合并完长度%d的链表为：",n);
            printfs(La);
            break;
        case 5:
            printf("La:");
            Create(La);
            Divide(La,Lb,Lc);
            printf("大于零链表为：");
            printfs(Lb);
            printf("小于零链表为：");
            printfs(Lc);
            break;
        case 0:
           i=0;
           break;
    }
    }
}

int Initlist_L(LinkList &L){//建立一个空表，并将表头返回
    L=(LinkList)malloc(sizeof(Lnode));
    L->data=0;
    L->next=NULL;
    return OK;
}
int Create(LinkList &L){//将空表传入，为表中输入元素，在返回表头
    Initlist_L(L);//先建立一个带头节点的链表
    LinkList p,s;
    int e;
    p=L;
    scanf("%d",&e);
    while(e!=0)
    {
        s = (LinkList)malloc(sizeof(Lnode));
        s->data=e;
        p->next=s;
        p=s;//插入到表尾
        L->data++;
        scanf("%d",&e);
    }
    p->next=NULL;
    return OK;
}

int OperateMenu(){//建立菜单，提示操作代码
    int num;
    printf("                             *-----------------------------------------------------------------*\n");
    printf("                                               1.两个递增链表合并为一个递增链表\n");
    printf("                                               2.两个递增链表合并为一个逆序链表\n");
    printf("                                               3.两个递增链表合并两个链表的交集\n");
    printf("                                               4.两个递增链表合并为一个A-B的差集\n");
    printf("                                               5.将一个链表分成以零为界限的两个表\n");
    printf("                                               0.结束\n");
    printf("                             *-----------------------------------------------------------------*\n");
    scanf("%d",&num);
    for(int i=0;;i++){
        if(num<0||num>5){printf("选择错误！");return -1;}
        else if(num==1){return num;break;}
        else if(num==2){return num;break;}
        else if(num==3){return num;break;}
        else if(num==4){return num;break;}
        else if(num==5){return num;break;}
    }
}
int MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递增链表,用原有的空间，不能有重复的数据
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){
        if(pa->data<pb->data){//比较较小的节点插入Lc中
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else if(pa->data>pb->data){
                pc->next=pb;
                pc=pb;
                pb=pb->next;
        }
        else{//有相同节点时选择其中一个链入Lc中，另一个则释放掉
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    pc->next=pa?pa:pb;
    return OK;
}
int Union(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递减的链表,用原有的空间，可有重复的数据（用头插法，完成逆序）
    LinkList pa,pb,p;
    pa=La->next;
    pb=Lb->next;
    Lc=La;
    Lc->next=NULL;
    while(pa||pb){
        if(!pa){
            p=pb;
            pb=pb->next;
        }
        else if(!pb){
            p=pa;
            pa=pa->next;
        }
        else if(pa->data<=pb->data){
            p=pa;
            pa=pa->next;
        }
        else{
            p=pb;
            pb=pb->next;
        }
        p->next=Lc->next;
        Lc->next=p;//插入
    }
}
int Mix(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表求交集,用原有La的空间
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){//有一个表结束，就可以全部结束了
        if(pa->data==pb->data){
            pc->next=pa;//相交并入表
            pc=pa;
            pa=pa->next;
            u=pb->next;//释放空间
            free(pb);
            pb=u;
        }
        else if(pa->data<pb->data){//较小节点前移，等待比较
                u=pa->next;
                free(pa);
                pa=u;
        }
        else {
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    while(pa){
        u=pa->next;
        free(pa);
        pa=u;
    }
    while(pb){
        u=pb->next;
        free(pb);
        pb=u;
    }
    pc->next=NULL;//结尾标志
    free(Lb);
    return OK;
}
int Difference(LinkList &La,LinkList &Lb,int &n){//两个递增链表求A-B的差集,用原有La的空间
    LinkList pa,pb,pre;//从La表中修改将不是差集中的删除
    pa=La->next;
    pb=Lb->next;
    pre=La;//用pre作pa的头节点
    while(pa&&pb){
        if(pa->data<pb->data){
            pre=pa;
            pa=pa->next;
            n++;//计数
        }
        else if(pa->data>pb->data){
            pb=pb->next;
        }
        else {
            pre->next=pa->next;//删除不是差集中的结点
            free(pa);
            pa=pre->next;
        }
    }
    return OK;
}
int Divide(LinkList &La,LinkList &Lb,LinkList &Lc){//将La分成两个分别大于零和小于零的Lb和Lc
    LinkList p,pc,pb;
    p=La->next;
    Lb=La;
    pb=Lb;
    Lc=(LinkList)malloc(sizeof(Lnode));
    pc=Lc;
    while(p){
        if(p->data>0){
            pb->next=p;
            pb=p;
            p=p->next;
        }
        else if(p->data<0){
            pc->next=p;
            pc=p;
            p=p->next;
        }
    }
    pb->next=NULL;//结束标记
    pc->next=NULL;
    return OK;
}
void printfs(LinkList L){//将线性表L中的元素依次打印
    LinkList p=L->next;
    if(p!=NULL){
    for(int j=0;;j++){
        printf("%d ",p->data);
        p=p->next;
        if(p==NULL)break;
    }
    }
    else printf("该链表为空！\n");
    printf("\n");
}