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

admin2015-12-30  42

问题 用单链表保存m个整数,结点的结构为:[dlata][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->fink free(r); }

解析
转载请注明原文地址:https://jikaoti.com/ti/xkfjFFFM
0

相关试题推荐
随机试题
最新回复(0)