当前位置: 首页 > 工具软件 > Tada > 使用案例 >

对于链表中tada的绝对值相等的点,仅保留第一次出现的结点而删除其余绝对值相等的点...

荀金鹏
2023-12-01

算法的核心思想是用空间换时间,使用辅助数组记录链表中已出现的数值  从而只需对链表进行一趟扫描

typedef struct node {
  int data;
  struct node* next;
 }NODE;
  typedef NODE*  PNODE;


void   func (PNODE h, int n){                              //链表中的|data| <= n
  PNODE p = h,  r ;                           //其中p为工作指针   r为保存删除的结点,以供free掉   
  int *q;
  q = (int*) malloc(sizeof(int) * (n+1));       //申请n+1个辅助空间
   for(int i=0;i<n+1;i++)
    q[i] = 0;

  while(p->next!=NULL){
    int temp;
    temp = p->data >0 ? p->next->data: -(p->next->data);
    if( q[temp] == 0){
        q[temp] = 1;
        p=p->next;        //  移动p指针
    }
    else{ 
      r = p->next;   //使得p是r的前驱节点
      p->next = r->next;   // 对p->next重新赋值既删除了q结点, 又使while循环可以 
 循环下去 
      free(r);
    }
  
  }
  
  free(q);
} 
   

 

转载于:https://www.cnblogs.com/zhuxuan1997/p/10679082.html

 类似资料: