学步园

已知非空线性链表第1个链结点的指针为list，在算法的设计中需要用到4个LinkList指针，q 用来记录域值最大的那个链结点，s 用来记录域值最大的那个链结点的直接前驱结点，p用来遍历整个链表，r 用来记录在遍历过程中当前正在比较的链结点的直接前驱结点。在算法设计中需要分两步，第一步是要找到最大值结点，第二步是要将最大值结点移动至链表的末尾（如果最大值结点不是末尾结点）。

在将最大值结点移动到末尾结点的算法中，需要考虑最大值结点是否是链表的第1个结点，因为最大值是否是链表第1个链结点对最大值结点移动到末尾的过程有影响。链表定义如下：

typedef struct node {
    char data[100];
    struct node *link;
}LNode, *LinkList;

算法设计如下：

/*将非空线性链表中数据域值最大的那个链结点移至链表的末尾
q用来指向最大值结点的地址，最开始假定第一个结点为域最大值结点，p用来遍历链表，
r用来在遍历过程中所比较值域链结点的直接前驱结点，s用来记录最大值域节点的直接前驱结点*/
void removeElemToEnd( LinkList *list ){
    LinkList q = *list, p = ( *list )->link, r = *list, s;
    while( p != NULL ){     //寻找最大值结点及其前驱结点
        if(strcmp( p->data, q->data ) > 0){     //如果新的链结点大于之前记录的域最大结点,则更新s, q的值
            s = r;
            q = p;
        }
        r = p;          //如果新的链结点不大于之前记录的域最大结点，则跳到下一个链结点
        p = p->link;
    }

    if( q != r ){      //如果最大值结点不是链表的末尾结点
        if( q == *list ){     //如果最大值结点是链表的第一个结点
            *list = ( *list )->link;
        }
        else{                //如果最大值结点不是链表的第一个结点
            s->link = q->link;
        }

        r->link = q;   //将最大值结点移动至末尾，并将新的末尾结点的指针域置空
        q->link = NULL;
    }
}