6-1 集合合并-(链表) (30 分)

先分别输入两个链表La,Lb的结点数据(0 结束链表输入,输入数据没有排序要求),Lb中出现的新元素插入依次到La的后面,然后输入删除结点的位置(指La,Lb合并后的链表中欲删除的结点)

函数接口定义:

 Status ListLength(LinkList L);
 void Union(LinkList *La,LinkList Lb);
 Status GetElem(LinkList L,int i,ElemType *e);
 Status ListEmpty(LinkList L);
 Status LocateElem(LinkList L,ElemType e,Status compare(ElemType a,ElemType b));  //compare是一个函数指针变量形参 
 Status equal(ElemType a,ElemType b);
 Status ListInsert(LinkList *L,Status i,Status e);
 Status ListDelete(LinkList *L,Status i,Status *e);  //删除位置不对,输出:Position Error
 void input(LinkList *L,char *str);

裁判测试程序样例:

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

//Status 为函数的类型,其值是函数结果状态代码,如OK等
typedef int Status;

// ElemType为数据元素类型,根据实际情况而定,这里假设为int
typedef int ElemType;
struct LNode               /* 结点定义 */
 {
   ElemType data;
   struct LNode *next;
 };
 typedef struct LNode* LinkList; /* 表的头指针类型 */
 /*相关函数定义*/
 Status ListLength(LinkList L);
 void Union(LinkList *La,LinkList Lb);
 Status GetElem(LinkList L,int i,ElemType *e);
 Status ListEmpty(LinkList L);
 Status LocateElem(LinkList L,ElemType e,Status compare(ElemType a,ElemType b));  //compare是一个函数指针变量形参 
 Status equal(ElemType a,ElemType b);
 Status ListInsert(LinkList *L,Status i,Status e);
 Status ListDelete(LinkList *L,Status i,Status *e); //如果删除位置不存在,输出"Position Error\n"
 void input(LinkList *L);
 void output(LinkList *L);

 int main(void)
{
    LinkList La = NULL,Lb = NULL;
    Status i;
    ElemType *e;
    input(&La);input(&Lb);
    scanf("%d",&i);    

    Union(&La,Lb);output(&La);
    ListDelete(&La,i,e);output(&La);
    return 0;
}
void output(LinkList *L)
{
    LinkList fp = *L;
    if(fp==NULL)
    {
        printf("No Chain!");
    }
    else
        while(fp){
            printf("%d ",fp->data);
            fp = fp->next;
        }
    printf("\n");
}
/* 请在这里填写答案 */

输入样例1:

先分别输入La,Lb链表(0结束输入),然后输入欲在合并后链表中删除的结点位置

1 2 3 0
4 5 6 0
4

输出样例1:

先输出合并后的链表,再输出在合并链表中删除结点后的链表

1 2 3 4 5 6 
1 2 3 5 6 

输入样例2:

先分别输入La,Lb链表(0结束输入),然后输入欲在合并后链表中删除的结点位置

1 2 3 0
3 4 5 6 0
8

输出样例2:

先输出合并后的链表,再输出在合并链表中删除结点后的链表

1 2 3 4 5 6 
Position Error
1 2 3 4 5 6 

我的解答

Status ListLength(LinkList L) {
    LinkList p ;
    int len = 0;
    for (p = L; p != NULL; p = p->next)
        len++;
    return len;
}
void Union(LinkList* La, LinkList Lb) {
    int i;
    ElemType e;
    int La_len;
    int Lb_len;
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);
    for (i = 1; i <= Lb_len; i++)
    {
        GetElem(Lb, i, &e);//取位置为i的元素赋值给e 
        if (!LocateElem(*La, e, equal))//判断La中 是否含有e 
            ListInsert(La, ++La_len, e);//将e插入到尾端 
    }
}
Status GetElem(LinkList L, int i, ElemType* e) {
    LinkList p;
    int t = 0;
    for (p = L; p != NULL; p = p->next)
    {
        t++;
        if (t == i)
        {
            *e = p->data;
            return OK;
        }
        if (t > i)
            break;
    }
    return ERROR;
}
Status ListEmpty(LinkList L) {
    if (L == NULL)
        return TRUE;
    else
        return FALSE;
}
Status LocateElem(LinkList L, ElemType e, Status compare(ElemType a, ElemType b))//compare是一个函数指针变量形参 
{
    LinkList s;
    s = L;
    if (s == NULL)
        return ERROR;//如果为NULL则无法定位序号
    for (; s != NULL; s = s->next)
    {
        if (compare(s->data, e))
            return OK;
    }
    return ERROR;
}
Status equal(ElemType a, ElemType b) {
    if (a == b)
        return TRUE;
    else
        return FALSE;
}
Status ListInsert(LinkList* L, Status i, Status e) {//将p2接到p1后面
    LinkList head = *L;
    LinkList tail = *L;//初始化p1,p1指向L
    tail = (struct LNode*)malloc(sizeof(struct LNode));
    tail->data = e;
    tail->next = NULL;//初始化设置为NULL
    if (*L == NULL)
    {
        *L = tail;//L没有 则直接插入并返回OK
        return OK;
    }
    while (head->next != NULL && head != NULL)
    {
        head = head->next;
    }
    head->next = tail;//拼接
    return OK;
}
Status ListDelete(LinkList* L, Status i, Status* e) {//删除位置不对,输出:Position Error
    LinkList head = *L;
    LinkList tail = *L;//初始化p1,p1指向L
    int flag = 1;
    if (i == 1 && head != NULL)
    {
        *L = (*L)->next;//如果位置为1 则直接向前移动一个
        return OK;
    }
    for (; head != NULL; head = head->next)
    {
        if (flag >= i)
            break;
        tail = head;
        flag++;
    }
    if(head==NULL)
        printf("Position Error\n");
    else {
        tail->next = head->next;
        free(head);//移动后 释放节点
    }

}
void input(LinkList* L) {
    int num;
    LinkList p1, p2=NULL;
    scanf("%d", &num);
    while (num != 0)
    {
        p1 = (struct LNode*)malloc(sizeof(struct LNode));
        p1->data = num;
        p1->next = NULL;//初始化为NULL
        if (*L == NULL)
            *L = p1;//将申请好的地址传入L 进行链接
        else
            p2->next = p1;
        p2 = p1;
        scanf("%d", &num);
    }
}

运行截图

工程实践:模块化程序设计(1)插图