线性表的应用4（链表节点的移动）

谁借莪１个温暖的怀抱￠ 2022-07-26 01:55 135阅读 0赞

对单链表，编写算法实现以第一个元素为基准，将小于该元素的节点全部放到前面，大于该节点的元素全部放到后面。时间复杂度要求为O(n)，不能申请新空间。

算法分析：

用两根指针实现的移动，由于是单链表，两根指针分别指向要移动的数据和要移动数据的前一个，如果该元素比首元素大，则不用管，直接向下移动指针即可，如果比首元素节点要小，则把该节点从原处删除，并把该节点插入到head后面，并把指针指回来即可。

代码如下：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct LNode
    {
        ElemType data;
        struct LNode *next;
    } LNode,*LinkList;
    
    LinkList Create()
    {
        LinkList head;
        head=(LinkList)malloc(sizeof(LNode));
        if(head!=NULL)
        {
            head->next=NULL;
            return head;
        }
        else return NULL;
    }
    
    int GetElem(LinkList L,int i,ElemType &e)
    {
        LinkList p;  //LNode *p;
        p=L->next;
        int j=1;
        while(p&&j<i)
        {
            p=p->next;
            ++j;
        }
        if(!p||j>i)
        {
            return 0;
        }
        e=p->data;
        return 1;
    }
    
    int ListInsert(LinkList &L,int i,ElemType e)
    {
        //在带头结点的单链线性表L中第i个位置之前插入元素e
        LinkList p,s; //LNode *p,*s;
        p=L;
        int j=0;
        while(p&&j<i-1)
        {
            p=p->next;
            ++j;
        }
        if(!p||j>i-1)
            return 0;
        s=(LinkList)malloc(sizeof(LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return 1;
    }
    
    int ListDelete(LinkList &L,int i,ElemType &e)
    {//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
        LinkList p,q;
        int j=0;
        while(p->next && j<i-1)
        {
            p=p->next;
            ++j;
        }
        if(!(p->next)||j>i-1) return 0;
        q=p->next;
        p->next=q->next;
        e=q->data;
        free(q);
        return 1;
    }
    
    void Jizhun(LinkList &L)
    {
        LinkList head,p,q;
        head=L;
        int e;
        e=head->next->data;
        //cout<<"e="<<e<<endl;
        p=head->next;
        q=p->next;
        while(q!=NULL)
        {
            if(q->data<e)
            {
                p->next=q->next;
                q->next=head->next;
                head->next=q;
                q=p->next;
            }
            else
            {
                p=p->next;
                q=q->next;
            }
        }
    }
    
    
    void Output(LinkList L)
    {
        LinkList p;
        p=L->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    
    void FreeLink(LinkList &L)
    {
        LinkList p,q;
        p=L;
        q=NULL;
        while(p!=NULL)
        {
            q=p;
            p=p->next;
            free(q);
        }
    }
    
    int main()
    {
        int n,e,flag;
        LNode *Lhead;
        while(scanf("%d",&n)!=EOF)
        {
            Lhead=Create();
            if(Lhead!=NULL)
            {
                for(int i=1;i<=n;i++)
                {
                    scanf("%d",&e);
                    flag=ListInsert(Lhead,i,e);
                    if(flag==0)
                    {
                        cout<<"Insert Fail"<<endl;
                        break;
                    }
                }
                cout<<"The List is:"<<endl;
                Output(Lhead);
                Jizhun(Lhead);
                Output(Lhead);
                FreeLink(Lhead);
            }
            else
            {
                cout<<"Can not do it!\n"<<endl;
            }
        }
        return 0;
    }