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

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

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

计算机408

学硕统考专业

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