6-2 线性表元素的区间删除 (20 分)
时间: 2023-04-19 14:00:39 浏览: 122
题目描述
给定一个线性表 L,以及两个元素 min 和 max,删除所有值在 [min,max] 之间(包括 min 和 max)的元素。
函数接口定义:
List Delete( List L, ElementType minD, ElementType maxD );
其中 List 结构定义如下:
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
函数 Delete 应该返回被删除后的链表的头指针。
裁判测试程序样例:
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */
List Delete( List L, ElementType minD, ElementType maxD );
int main()
{
List L;
ElementType minD, maxD;
L = Read();
scanf("%d %d", &minD, &maxD);
L = Delete(L, minD, maxD);
Print(L);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例:
10
8 10 9 7 5 6 1 3 2 4
5 9
输出样例:
8 10 7 1 3 2 4
题目分析
本题需要删除线性表中指定区间的元素,可以使用双指针法来实现。定义两个指针 p 和 q,初始时 p 指向头结点,q 指向 p 的下一个结点。然后遍历整个链表,如果 q 指向的结点的值在指定区间内,则将 p 的 Next 指针指向 q 的下一个结点,同时释放 q 指向的结点。否则,p 和 q 同时向后移动一个结点。最后返回头结点即可。
需要注意的是,如果头结点的值在指定区间内,则需要特殊处理,即将头结点释放,并将头指针指向第二个结点。
参考代码