发表文章

[最新] 数据结构习题——5单链表的删除

qq41858784 27天前 0

time_limit

3000MS

memory_limit

10000KB

description

已知A,B和C为三个非递减有序的线性表,均以单链表作为存储结构。现要求对A表作如下操作:删去那些既在B表中出现又在C表中出现的元素。试对单链表编写实现上述操作的算法,并释放A表中的无用结点空间。

input

第一行输入3个正整数m,n,p(m,n,p<=100),用空格分开,表示三个线性表中的元素个数,其后3行依次输入A,B,C表中的元素。

output

输出实现上述操作后的A表。

sample_input

8 5 6

1 2 3 4 5 6 6 7

2 3 5 9 12
2 4 5 6 12 13

sample_output

1 3 4 6 6 7

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct Node{
    ElemType data;
    struct Node *next;
}LNode,*PLNode;

typedef struct Linklist{
    PLNode head;
}Linklist,*PLinklist;

PLinklist Initlist(int n)
{
    int i;
    PLNode p,q;
    PLinklist plist;

    plist=(PLinklist)malloc(sizeof(Linklist));
	q=plist->head=(PLNode)malloc(sizeof(LNode));
    for(i=0;i<n;i++){
        p=(PLNode)malloc(sizeof(LNode));
        scanf("%d",&p->data);
        q->next=p;
        q=q->next;
    }
    q->next=NULL;
    return plist;
}

ElemType get_list(PLNode p)
{
    return p->data;
}

PLNode locate_list(PLinklist plist,ElemType x)
{
    PLNode p;
    p=plist->head->next;
    while(p!=NULL&&p->data!=x){
        p=p->next;
    }
    return p;
}

void delete_list(PLinklist plist,PLNode p)
{
    PLNode q;
    q=plist->head;
    while(q->next!=p){
        q=q->next;
    }
    q->next=p->next;
    //free(p);
}

void show_list(PLinklist plist)
{
    int i=0;
    PLNode p;
    p=plist->head->next;
    while(p){
        if(0!=i)printf(" ");
        printf("%d",p->data);
        p=p->next;
        i++;
    }
    printf("\n");
}
int main()
{
    PLNode pa,pb,pc,location;
    PLinklist la,lb,lc;
    ElemType x;
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);

    la=Initlist(a);
    lb=Initlist(b);
    lc=Initlist(c);

    //下面时b和c的交集
    pb=lb->head->next;
    while(pb){
        PLNode t=pb->next;
		x=get_list(pb);
        location=locate_list(lc,x);
        if(NULL==location){
            delete_list(lb,pb);
            pb=t;
        }
        else
            pb=pb->next;
    }

    //下面是差集:
    pa=la->head->next;
    while(pa){
    	PLNode t=pa->next;
        x=get_list(pa);
        location=locate_list(lb,x);
        if(NULL!=location){
            delete_list(la,pa);
            pa=t;
        }
        else
            pa=pa->next;
    }

	show_list(la);
    //printf("Hello world!\n");
    return 0;
}

 

相关推荐
最新评论 (0)
返回
发表文章
qq41858784
文章数
10
评论数
0
注册排名
1370858