/***
*
*题目:已知线性表中的元素以值递增有序排列,并以单链表做存储结构。试写一高效的算法,
* 删除表中所有值大于 mink 且小于 maxk 的元素(若表中存在这样的元素),同时释放
* 被删除节点空间,并分析你的算法的时间复杂度(注意:mink 和 maxk 是给定的两个
* 参变量,它们的值可以和表中的元素相同,也可以不同)
*
****/
#include
#include
#include "DynaLinkList.h"
void DelMminMax(LinkList *L, int min, int max)
{
LinkList p = (*L)->next, q = (*L), r;
while (p && p->data <= min)
{
q = p; p = p->next;
}
while ( p && p->data < max)
{
r = p; p = p->next;
q->next = p; free(r);
}
} //算法的时间复杂度为O(n)
int main()
{
LinkList L;
ElemType e, min, max;
InitList(&L);
printf("输入8个元素建立线性表L(元素递增有序):\n");
for (int i=1; i<=8; i++)
{
scanf("%d", &e);
ListInsert(&L, i, e);
}
printf("表L是:\n");
ListTraverse(L, visit);
printf("请输入待删除的元素的区间是(min,max):\n");
scanf("%d%d", &min, &max);
DelMminMax(&L,min,max);
printf("删除(%d,%d)之间的元素后表L是:\n",min,max);
ListTraverse(L, visit);
return 0;
}