移动链表中的最大值到尾部，链表各元素位置未发生改变

桃扇骨 2022-12-11 13:38 78阅读 0赞

编写函数MoveMaxToTail()，实现查找单链表中值最大的结点，并将其移动到链表尾部，注意其他结点的相对次序不变。要求尽量具有较高的时间效率。（还有另一种方式，采用冒泡排序法，在移动最大值到链表尾部时，链表各元素位置发生改变，详情请参考博主另一篇博客，链接https://blog.csdn.net/qq\_50798384/article/details/108896504）  
1.定义结构体和宏定义类型名

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int DataType; 
    struct Node
    { 
        DataType      data; 
        struct Node*  next;  
    };
    typedef struct Node  *PNode;    
    typedef struct Node  *LinkList;

2.创建头节点，不对头节点进行赋值。代码如下

LinkList SetNullList_Link()
    { 
        LinkList head = (LinkList)malloc(sizeof(struct Node));
        if (head != NULL) head->next = NULL;
        else printf("alloc failure");
        return head;
    }

3.利用尾插法建立一个单向链表。代码如下

void CreateList_Tail(struct Node* head)
    { 
        PNode p = NULL;
        PNode q = head;
        DataType data;
        scanf("%d", &data);
        while (data != -1)
        { 
            p = (struct Node*)malloc(sizeof(struct Node));
            p->data = data;
            p->next = NULL;
            q->next = p;
            q = p;
            scanf("%d", &data);
        }
    }

4.移动链表中的最大值到尾部，链表中其他元素的顺序不表，指针p记录链表中的最大元素，指针q遍历链表，在遍历结束时q=NULL并且pre指向链表中最大元素。元素代码如下

void MoveMaxToTail(head)
    { 
        LinkList pre=head,r=head;
        LinkList q=pre->next;
        while(q!=NULL)
        { 
            if(pre->data<q->data)
            { 
                pre=q;
    
            }
                q=q->next;
        }
         while(r->next!=pre)
            r=r->next;//指针r指向最大元素的上一个元素，便于进行删除操作
        q=head;
        while(q->next!=NULL)
            q=q->next;//使q重新指向链表中的最后一个元素，便于进行插入操作
        if(pre->next==NULL)
                return;//若最后一个元素为最大元素，则直接返回，不需要进行其他操作
        else
        { 
            r->next=pre->next;
         pre->next=NULL;
         q->next=pre;
        }
    }

5.释放有节点，若不释放会占用内存空间，这是一个非常很重要的函数，在以后的链表操作中必不可少，否则你的电脑内存会越来越小，此函数只是作为参考，根据链表的形状和特点自己编写释放函数。代码如下

void DestoryList_Link(LinkList head)
    { 
        PNode  pre = head;
        PNode p = pre->next;
        while (p)
        { 
            free(pre);
            pre = p;
            p = pre->next;
        }
        free(pre);
    }

6.主函数代码如下

int main()
    { 
        LinkList head = NULL;
        head = SetNullList_Link();
        CreateList_Tail(head);
        MoveMaxToTail(head);
        print(head);
        DestoryList_Link(head);
        return 0;
    }