线性表的应用3（单链表的基本实现和逆置）

墨蓝 2022-07-26 01:29 55阅读 0赞

设计算法实现带头节点单链表的逆置。

算法分析：整个过程中用到两根新引入的指针

建立起一个拥有n个元素的单链表以后，首先用一根指针指向头结点，即把它记录下来，然后把头结点摘下来，并把其L->next指针域置空，然后再借助于另外一根指针，把原链表中的节点依次插入头结点的后面（每一次都是直接插到头结点后面哟~），即完成了链表中元素的就地逆置。

代码实现：

#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 Nizhi(LinkList &L)
    {
        LinkList p,q;
        p=L->next;
        L->next=NULL;
        while(p)
        {
            q=p;
            p=p->next;
            q->next=L->next;
            L->next=q;
        }
    }
    
    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;
                    }
                }
                Output(Lhead);
                Nizhi(Lhead);
                Output(Lhead);
                FreeLink(Lhead);
            }
            else
            {
                cout<<"Can not do it!\n"<<endl;
            }
        }
        return 0;
    }