C语言高手帮忙 已知线形表中的元素以值递增有序排列，并以单链表作存储结构。试编写一个高效算法，

Question

删除该表所有值大于MIN且小于MAX的元素（若表中存在这样的元素），同时释放被删除节点的存储空间。
要完整地程序，不要伪代码！
正确加分哦！~

Answer 1

/*
C语言高手帮忙 已知线形表中的元素以值递增有序排列，并以单链表作存储结构。试编写一个高效算法，
删除该表所有值大于MIN且小于MAX的元素（若表中存在这样的元素），同时释放被删除节点的存储空间。
*/
#include <iostream>
#include <vector>
using namespace std;

//结点
struct Node
{
int data;
Node *pNext;
};

//构造一个链表的函数
Node *CreateList()
{
Node *pHead = new Node();
pHead->data = 1;
pHead->pNext = NULL;

Node *pWork = pHead;
for ( int i = 2 ; i <= 10 ; i++ )
{
pWork->pNext = new Node();
pWork = pWork->pNext;
pWork->data = i;
pWork->pNext = NULL;
}

return pHead;
}

//销毁一个链表的函数
void DestroyMyList(Node* &pHead)
{
while ( NULL != pHead )
{
Node *pWork = pHead->pNext;
delete pHead;
pHead = pWork;
}
pHead = NULL;
}

//输出一个链表
void OutPutList( Node* &pHead )
{
Node *pWork = pHead;
while ( NULL != pWork )
{
cout<<pWork->data<<"->";
pWork = pWork->pNext;
}
cout<<"NULL"<<endl;
}

//删除min与max之间的数据
void DeleteBetweenMinAndMax( Node* &pHead,int min,int max )
{
//定义一个可变长度的数组,来保存所有指向每个LIST结点的指针
vector<Node * > PointerArrToEveryNode;
Node *pWork = pHead;
while ( pWork != NULL )
{
//将每个结点的指针添加到数组中
PointerArrToEveryNode.push_back(pWork);
pWork = pWork->pNext;
}
//此时PointerArrToEveryNode数组中指针就是指向每个LIST结点的指针,下面查找min及max的位置并删除内容
for ( int i = 0 ; i < PointerArrToEveryNode.size() ; i++ )
{
if ( PointerArrToEveryNode[i]->data > min && PointerArrToEveryNode[i]->data < max )
{
delete PointerArrToEveryNode[i];//删除数据空间
PointerArrToEveryNode.erase(PointerArrToEveryNode.begin() + i);//在指针数组中删除元素
i--;//删除了一个元素后数组中的个数减少了,应该在i--处继续循环
}
}
//删除某些符合要求的结点后,链表的链可能断了,根据ointerArrToEveryNode数组中指针重建链
if ( PointerArrToEveryNode.size() > 0 )
{
for ( int i = 0 ; i < PointerArrToEveryNode.size() - 1 ; i++ )
{
PointerArrToEveryNode[i]->pNext = PointerArrToEveryNode[i+1];
}
//重新给头结点赋值
pHead = PointerArrToEveryNode[0];
//重新给尾结点赋值pNext指针
PointerArrToEveryNode[PointerArrToEveryNode.size()-1]->pNext = NULL;
}
else
{
//元素被删完了
pHead = NULL;
}
}

int main(void)
{
//测试函数是否正常
//先创建一个链表
Node *pHead = CreateList();
//输出删除前的内容
OutPutList(pHead);

//执行删除5和7之间的数据
DeleteBetweenMinAndMax(pHead,3,8);
//再输出删除后的内容
OutPutList(pHead);

//执行删除9和22之间的数据
DeleteBetweenMinAndMax(pHead,9,22);
//再输出删除后的内容
OutPutList(pHead);

//执行删除0和4之间的数据
DeleteBetweenMinAndMax(pHead,0,4);
//再输出删除后的内容
OutPutList(pHead);

//执行删除8和15之间的数据
DeleteBetweenMinAndMax(pHead,8,15);
//再输出删除后的内容
OutPutList(pHead);

//执行删除0和20之间的数据
DeleteBetweenMinAndMax(pHead,0,20);
//再输出删除后的内容
OutPutList(pHead);

//结束前销毁链表
DestroyMyList(pHead);

cin.get();
return 0;
}