首页 > 试题广场 >

对于链表中 data 的绝对值相等的结点，仅保留第一次出 现

[问答题]

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

则删除结点后的head 为：

要求：

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

2）使用 C 或 C++语言，给出单链表结点的数据类型定义。

3）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。

4）说明你所设计算法的时间复杂度和空间复杂度。

查看答案及解析
添加回答
推荐
王道论坛头像 王道论坛

41 ． 解答 ：

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) 。

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

编辑于 2016-12-15 18:32:38 回复(0)
changeShen头像 changeShen

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);

}

发表于 2017-08-12 21:48:33 回复(1)
艾晓米Amyfairy头像 艾晓米Amyfairy

41 ． 解答 ：

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) 。

【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。（来自王道论坛）

编辑于 2016-12-15 18:32:38 回复(0)
城市里的养猫者头像 城市里的养猫者

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 *P

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)。

发表于 2016-11-19 17:43:56 回复(0)
橘堇头像 橘堇
使用book数组记录出现的数字
发表于 2020-04-19 17:13:33 回复(0)
icecoldless头像 icecoldless 
#include<iostream>
#include<math.h>
using namespace std;
typedef struct LNode {
	int val;
	LNode *next;
}LNode,*LinkList;

void CreateList_R(LinkList& head) {
	int n;
	cin >> n;
	LinkList r = head;
	for (int i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		cin >> p->val;
		p->next = r->next;
		r->next = p;
		r = p;
	}
}
int main() 
{
	int* tmp = new int[50]{ 0 };
	LinkList head = new LNode;
	head->next = NULL;
	CreateList_R(head);
	LinkList l = head;
	LinkList p = head->next;
	while (p)
	{
		if (!tmp[abs(p->val)])
		{
			tmp[abs(p->val)] = 1;
			cout << abs(p->val)<<" ";
			l = p;
			p = p->next;
		}
		else 
		{
			l->next = p->next;
			LinkList d = p;
			p = p->next;
			delete d;
		}
	}
	system("pause");
	return 0;
}

发表于 2019-10-27 16:32:35 回复(0)
许萌头像 许萌 

	typedef struct node {





	   int        data;





	   struct node   *link;





	}NODE;





	Typedef NODE *PNODE;





	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);





	}

发表于 2017-06-29 16:04:37 回复(0)
提交观点

问题信息

链表
上传者：城市里的养猫者
难度：
7条回答 8225浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号