已知非空线性链表第1个链结点指针为list,链结点构造为
struct node{
datatype data;
node *link;
};
请写一算法,将该链表中数据域值最大的那个点移到链表的最后面。(假设链表中数据域值最大的链结点惟一)(注意:要求先写出算法的解题思路,然后再写出算法)
用循环不断比较每个节点的值,如果找到最大值,则记录这个值及其节点,循环结束把尾结点的值和最大值节点的值互换即可,代码如下:
#include <stdio.h>
#include <stdlib.h>
typedef int datatype ;
struct node{
datatype data;
node * link;
};
int main(void){
node * list,* tmp,*pre=NULL;
int i=0;
//创建测试链表节点的测试数据
while(i<5){
printf("请输入链表第%d个节点的值:",i+1);
tmp = (node*)malloc(sizeof(node));
if(pre!=NULL){
pre->link = tmp;
}
if(i==0){
list = tmp;
}
scanf("%d",&tmp->data);
tmp->link = NULL;
pre = tmp;
i++;
}
//打印移动前,链表各节点的值
printf("移动最大值前链表各节点的值为:\n");
tmp = list;
while(tmp!=NULL){
printf("%d ",tmp->data,tmp->link);
tmp = tmp->link;
}
printf("\n");
tmp = list;
int max=tmp->data; //把链表节点最大值赋值为链表节点第一个值
node* maxList=tmp,tmp2; //最大值节点也赋值为链表第一个节点
// printf("0\n");
//i=0;
while(tmp!=NULL){
//printf("0,tmp->data=%d,tmp->link=%p\n",tmp->data,tmp->link);
//如果链表节点当前最大值小于当前节点的值,则把最大值赋值为当前节点的值,最大值节点也赋值为当前节点
if(max<tmp->data){
// printf("tmp->data=%d,max=%d\n",tmp->data,max);
max = tmp->data;
maxList = tmp;
}
// i++;
// printf("i=%d\n",i);
pre = tmp; //记录当前节点,以便循环结束记录到链表节点的尾结点
tmp = tmp->link;
}
// printf("1-1,maxList=%p,pre=%p\n",maxList,pre);
maxList->data = pre->data; //把最大值节点的值赋值为尾结点的值
pre->data = max; //把尾结点的值赋值为最大值节点的值,实现把最大值移到节点的最后面的目的
//打印移动后的结果
printf("移动最大值后链表各节点的值为:\n");
tmp = list;
while(tmp!=NULL){
printf("%d ",tmp->data);
tmp = tmp->link;
}
printf("\n");
return 0;
}