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)插图 工程实践:模块化程序设计(1)插图](https://static.esw.eswlnk.com/2021/06/2021060609250013.png-esw)
📮评论