c - 在循环链表中查找最大值和最小值时出错

Question

我需要找到循环链表中的最大数和最小数，并且我应该将最小数移动到列表的开头(在head之前)，将最大数移动到列表的末尾(在minimum之前)

为什么我的代码在输出中出现错误？

注意:不允许使用双向链表，只能使用循环链表。

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  int num;
  struct node *next;
} NODE;

void init(NODE **h)
{
  (*h) = (NODE*)malloc(sizeof(NODE));
  (*h)->next = *h;
}

NODE* add(NODE* h,NODE* p,int x)
{
  int i;
  NODE *temp;
  temp = (NODE*)malloc(sizeof(NODE));
  temp->num = x;
  temp->next = h;
  if(h->next == h)
  {
    h->next = temp;
    return h;
  }
  else
  {
    temp = p->next;
    p = temp;
    return h;
  }
  return h;
}

NODE* fin(NODE *h,NODE *p)
{
  NODE* ptr,*pmin,*pmax,*temp,*temp2,*mnprev,*mxprev;
  // temp: minimum
  // temp2: maximum
  // pmin: holds the minimum
  // pmax: holds the maximum
  // ptr: o(n) search
  // mnprev: holds the previous node of the minimum
  // mxprev: hold the previous node of the maximum
  mnprev = mxprev = pmin = pmax = h;
  ptr = h->next;
  int mini, maxi;
  mini = h->num;
  maxi = h->num;
  do
  {
    if(ptr->num < mini)
    {
      mini = ptr->num;
      pmin = ptr;
      mnprev->next = pmin;
    }
    if(ptr->num > maxi)
    {
      maxi = ptr->num;
      pmax = ptr;
      mxprev->next = pmax;
    }

    ptr = ptr->next;
  } while(ptr != h);
  temp = pmin;
  temp2 = pmax;
  mnprev->next = pmin->next;
  mxprev->next = pmax->next;
  free(pmin);
  free(pmax);

  temp->next = h;
  temp2->next = temp;

  ptr = temp;
  do {
    printf("%d ",ptr->num);
    ptr = ptr->next;
  } while(ptr != h);

}

int main()
{
  int i,x;
  NODE *lis,*p;
  init(&lis);
  p = lis;
for(i=0;i<7;i++)
  {
    scanf("%d",&x);
add(lis,p,x);
    }
      fin(lis,p);

}

Answer 1

重写你的代码

• 函数 init 删除，因为它将创建未使用的节点。
• 改为此后最大值和最小值之间的节点 只需替换该值就足够了。

像这样

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int num;
    struct node *next;
} NODE;

NODE* add(NODE **head, NODE **tail, int x){
    NODE *temp;
    temp = (NODE*)malloc(sizeof(NODE));
    temp->num = x;
    if(*head == NULL){
        temp->next = temp;
        *tail = *head = temp;
    } else {
        temp->next = *head;
        (*tail)->next = temp;
        *tail = temp;
    }
    return *head;
}

void print(NODE *p){
    NODE *top =p;
    do{
        printf("%d ", p->num);
        p=p->next;
    }while(p != top);
    printf("\n");
}

void drop(NODE *head, NODE *tail){
    NODE *p = head;

    tail->next = NULL;
    while(p){
        NODE *temp = p;
        p = p->next;
        free(temp);
    }
}

void minmax(NODE *head, NODE *tail){
    NODE *p, *maxp, *minp;
    int temp;

    maxp = minp = p = head;
    do{
        if(maxp->num < p->num){
            maxp = p;
        }
        if(minp->num > p->num){
            minp = p;
        }
        p = p->next;
    }while(p != head);
    temp = maxp->num; maxp->num = tail->num; tail->num = temp;
    if(tail == minp)//exchanged minp
        minp = maxp;//fixed
    temp = minp->num; minp->num = head->num; head->num = temp;
}

int main(void){
    int i, x;
    NODE *head, *tail;

    tail = head = NULL;
    for(i=0;i<7;i++){
        printf("%d>", i+1);
        scanf("%d", &x);
        add(&head, &tail, x);
    }
    //print(head);
    minmax(head, tail);
    print(head);
    drop(head, tail);

    return 0;
}