【题目】
41.(15分)用单链表保存m个整数，结点的结构为：
，且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head如下：
则删除结点后的head为：
要习之：
(1)给出算法的基本设计思想。
(2)使用C或C++语言，给出单链表结点的数据类型定义。
(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(4)说明你所设计算法的时间复杂度和空间复杂度。
【答案要点】：
(1)算法的基本设计思想
算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。
因为|data|≤n，故辅助数组q的大小为n+1，各元素的初值均为0。依次扫描链表中的各结点，同时检查q[|data|]的值，如果为0，则保留该结点，并令q[|data|]=1;否则，将该结点从链表中删除。
(2)使用C语言描述的单链表结点的数据类型定义
typedef struct node {
int data：
struct node *link：
} NODE;
typedef NODE*PNODE;
(3)算法实现
void func(PNODE h，int n)
{ PNODE p：h，r;
int*q，m;
q=(int*) malloc(sizeof(int)*(n+1));//申请n+1
//个位置的
//辅助空间
for(int i=0;i<n+1;i++) //数组元素初始值置为0 <n+1;i++) p="" 数组元素初值置0<="">
*(q+i)= 0;
while(p->link!=NULL)
{ m=p->link->data>0 ? p->link->data：-p->link一>data;
if(*(q+m)==0) //判断该结点的data是否已
//出现过
{ *(q+m)=1; //首次出现
p=p->link; //保留
}
else //重复出现
{ r=p->link; //删除
p->link=r->link;
free(r);
}
}
free(q);
}
【(1)、(2)、(3)的评分说明】
①若考生设计的算法满足题目的功能要求且正确，则(1)、(3)根据所实现算法的时间复杂度给分，细则见下表：
②若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，可参照①的标准给分。
③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
④若考生给出的单链表结点的数据类型定义与题目中所给的结点形式不完全相同，酌情给分。
⑤参考答案中只给出了使用C语言的版本，使用C++语言的答案视同使用C语言。
(4)参考答案所给算法的时间复杂度为O(m)，空间复杂度为O(n)。
【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。