首页 > 试题广场 >

题目来源于王道论坛 用单链表保存m个整数,结

[问答题]
题目来源于王道论坛

用单链表保存m个整数,结点的结构为:[data][link],且|data|nn为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head如下:

则删除结点后的head为:

要求:

1)给出算法的基本设计思想。

2)使用CC++语言,给出单链表结点的数据类型定义。

3)根据设计思想,采用CC++语言描述算法,关键之处给出注释。

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
 *(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);
}

【评分说明】若考生设计的算法满足题目的功能要求且正确,则酌情给分。

4)参考答案所给算法的时间复杂度为O(m),空间复杂度为O(n)

【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致,可给分。

发表于 2018-06-16 11:34:35 回复(1)
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
 *(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);
}
发表于 2019-09-02 20:13:48 回复(0)