Question

求解一道数据结构的题目，用C语言解，考试用的，急，谢谢。

Answer 1

/***
*
*题目：已知线性表中的元素以值递增有序排列，并以单链表做存储结构。试写一高效的算法，
*
删除表中所有值大于
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;
}