Question

初学者求解一道数据结构[C语言版]的题目

已知线性表中的元素以值递增有序排列,并以单链表做储存结构.试写一高效算法,删除表中大于MINK且小于MAXK的元素(若表中存在这样的元素).同时释放被删除的结点空间,并且分析算法复杂度.注意,MINK,MAXK是给定两个参变量,他们的值可以和表中的元素相同,也可以不同.谢谢!
一个人都没有来?

Answer 1

/***
*
*题目：已知线性表中的元素以值递增有序排列，并以单链表做存储结构。试写一高效的算法，
* 删除表中所有值大于 mink 且小于 maxk 的元素（若表中存在这样的元素）,同时释放
* 被删除节点空间，并分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个
* 参变量，它们的值可以和表中的元素相同，也可以不同）
*
****/

#include <stdio.h>
#include <stdlib.h>
#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;
}