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

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

admin2015-12-30  51
问题 用单链表保存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://kaotiyun.com/show/TIRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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