线性表的应用5（单链表实现二进制的加法）

╰半夏微凉° 2022-07-26 04:04 176阅读 0赞

建立一个带头节点的线性链表，用以存放输入的二进制数，链表中每个节点的data域存放一个二进制位。并在此链表上实现对二进制数的加1运算。

算法分析：

约定：以输入一个非0,1的数字作为一个二进制数的结束标志

由于是单链表，即只能通过一个方向进行遍历，但是为了模拟加法操作，即必须要在表尾进行加1操作并要准确的考虑进位，所以我们利用链表的逆置，即先逆置，再加1，再逆置，即可方便的实现二进制数的加1操作。

代码实现：

#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 Add_1(LinkList &L)
    {
        LinkList p,q;
        p=L->next;
        int idx=1; //表示从低位来的进位
        while(p!=NULL) //四种情况中只有两种会改变data和进位的值，则要进行特殊考虑
        {
            if(p->data==1 && idx==1) //1+1=0进1;
            {
                p->data=0;
                idx=1;
            }
            else if(p->data==0 && idx==1) //0+1=1原位变为1,进位变为0;
            {
                p->data=1;
                idx=0;
            }
            p=p->next;
        }
        p=L;
        if(idx==1)  //如果还有进位，则要增加链表的节点
        {
            q=(LinkList)malloc(sizeof(LNode));
            q->data=1;
            q->next=NULL;
            while(p->next!=NULL)
            {
                p=p->next;
            }
            p->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 i,e,flag;
        LNode *Lhead;
        Lhead=Create();
        if(Lhead!=NULL)
        {
            i=1;
            while(1)
            {
                scanf("%d",&e);
                if(e==0||e==1)
                {
                    flag=ListInsert(Lhead,i++,e);
                    if(flag==0)
                    {
                        cout<<"Insert Fail"<<endl;
                        break;
                    }
                }
                else
                {
                    cout<<"Input Over!"<<endl;
                    break;
                }
            }
            cout<<"The List is:"<<endl;
            Output(Lhead);
    
            Nizhi(Lhead);
            cout<<"Nizhi_1:"<<endl;
            Output(Lhead);
    
            Add_1(Lhead);
            cout<<"Add_1:"<<endl;
            Output(Lhead);
    
            Nizhi(Lhead);
            cout<<"The result is:"<<endl;
            Output(Lhead);
    
            FreeLink(Lhead);
        }
        else
        {
            cout<<"Can not do it!\n"<<endl;
        }
        return 0;
    }