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

admin2015-12-30  41

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

则删除结点后的head为:

要求:
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。

选项

答案算法实现 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); }

解析
转载请注明原文地址:https://kaotiyun.com/show/lKxi777K
0

随机试题
最新回复(0)