【数据结构】链表实现的高进度加减乘

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】链表实现的高进度加减乘，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
<pre class="cpp" name="code">#include "number.h"
#include <cstring>
#include "Lstack.h"
void number::del()
{   moveToStart();
    int  t = zs_len;
    for(int i = 0;i<zs_len;i++)
    {
        if(getValue()=='0')
        {   head = head->next;
            t--;
            print();
        }
        if(getValue()!='0')
        {break;}
    }
   // print();
    moveToStart();
    if(getValue()=='.') {insert('0');t++;}
    zs_len = t;
//    print();
    //cout<<zs_len<<endl;
    //cout<<zs_len;
    if(zs_len+1==length()) return;
    moveToStart();
    for(int i =0;i<zs_len+1;i++) next();
    //cout<<"##\n";
    LStack<char> sta;
    while (curr->next != NULL){
    		sta.push(remove());
    	}
    while ((sta.length()!=0)&&(sta.topValue() == '0'))
        {sta.pop();}
    xs_len = sta.length();
    while(!sta.isEmpty())
        insert(sta.pop());

   // cout<<zs_len<<" "<<xs_len<<endl;
}

void number::input()
{
    char *p;
    p = new char[1000];
    cin>>p;
    int len = strlen(p);
    bool have_dot = false ;
    for(int i = 0; i<len; i++)
    {
        if(p[i]=='.'){zs_len = i;have_dot =true;}
        append(p[i]);
    }
   // cout<<(tail->next==NULL)<<endl;
    if(have_dot)
        xs_len = length()-zs_len-1;
    else{
        xs_len = 0;
        zs_len = length();
        append('.');
    }
    //del0();
    //print();
}
number::number(const number& num)
{
    clear();
    zs_len = num.zs_len;
    xs_len = num.xs_len;
    Link<char> *tmp = num.head->next;
    while(tmp !=NULL)
    {
        append(tmp->element);
        tmp=tmp->next;
    }
}
number& number::operator=(const number& num)
{
    clear();
    zs_len = num.zs_len;
    xs_len = num.xs_len;
    Link<char> *tmp = num.head->next;
    while(tmp !=NULL)
    {
        append(tmp->element);
        tmp=tmp->next;
    }
    return *this;
}
number number::operator+(number& num)
{

    number result;
    int max_xs = xs_len>num.xs_len?xs_len:num.xs_len;
    //int max_zs = zs_len>num.zs_len?zs_len:num.zs_len;
    moveToStart();
    num.moveToStart();
    LStack<char> sta0;
    for(int i=0;i<zs_len+1;i++)
        next();
    for(int i=0;i<num.zs_len+1;i++)
        num.next();
    int carry = 0;
    {
    LStack<char> sta1;
    LStack<char> sta2;
    for(int i=0;i<max_xs;i++)
    {
        if(curr!=tail){
            sta1.push(getValue());//cout<<getValue();
            next();}
        else
            sta1.push('0');

        if(num.curr!=num.tail){
            sta2.push(num.getValue());//cout<<num.getValue();
            num.next();//cout<<(num.curr==NULL)<<endl;
            }
        else
            sta2.push('0');
    }
    while(!(sta1.isEmpty()||sta2.isEmpty()))
    {
        int t =sta1.pop()+sta2.pop()-'0'-'0'+carry;
        carry = t/10;
        sta0.push(t%10+'0');
    }
    }
    LStack<char> sta;
    {
    LStack<char> sta1;
    LStack<char> sta2;
    moveToStart();num.moveToStart();
    for(int i=0;i<zs_len;i++)
    {
        char ch =getValue();
        sta1.push(ch);
        next();
    }
    for(int i=0;i<num.zs_len;i++)
    {
        sta2.push(num.getValue());
        num.next();
    }
    while(!(sta1.isEmpty()||sta2.isEmpty()))
    {
        int t =sta1.pop()+sta2.pop()-'0'-'0'+carry;
        carry = t/10;
        sta.push(t%10+'0');
    }
    while(!sta1.isEmpty())
    {
        int t =sta1.pop()-'0'+carry;
        carry =t/10;
        sta.push(t%10+'0');
    }
    while(!sta2.isEmpty())
    {
        int t =sta2.pop()-'0'+carry;
        carry =t/10;
        sta.push(t%10+'0');
    }
    if(carry!=0) sta.push(carry+'0');
    }

    while(!sta.isEmpty())
        result.append(sta.pop());
    result.append('.');
    while(!sta0.isEmpty())
        result.append(sta0.pop());
       // result.del();
    return result;
}
number number::operator-(number& num)
{
    number result;
    moveToStart();num.moveToStart();
    if(zs_len<num.zs_len)
    {
        result = num - *this;
        result.moveToStart();
        result.insert('-');
        return result;
    }
    if(zs_len==num.zs_len)
    {
        int check =0;
        int i = 0;
        for(i=0;i<length()&&i<num.length();++i)
        {
            if(getValue()>num.getValue())
                break;
            if(getValue()<num.getValue())
            {
                check = 1;
                break;
            }
            next();num.next();
        }
        if((i==length())&&(i!=num.length())) check = 1;
        if(check)
        {
            result = num - *this;
            result.moveToStart();
            result.insert('-');
            return result;
        }
    }

    int max_xs = xs_len>num.xs_len?xs_len:num.xs_len;
    //int max_zs = zs_len>num.zs_len?zs_len:num.zs_len;
    moveToStart();
    num.moveToStart();
    int carry = 0;
    LStack<char> sta0;
    {
    for(int i=0;i<zs_len+1;i++)
        next();
    for(int i=0;i<num.zs_len+1;i++)
        num.next();
    LStack<char> sta1;
    LStack<char> sta2;
    for(int i=0;i<max_xs;i++)
    {
        if(curr!=tail){
            sta1.push(getValue());//cout<<getValue();
            next();}
        else
            sta1.push('0');

        if(num.curr!=num.tail){
            sta2.push(num.getValue());//cout<<num.getValue();
            num.next();//cout<<(num.curr==NULL)<<endl;
            }
        else
            sta2.push('0');
    }
    while(!(sta1.isEmpty()||sta2.isEmpty()))
    {
        int t =sta1.pop()-sta2.pop()+carry;
        if(t<0)
        {
            t+=10;
            carry = -1;
            sta0.push(t+'0');
        }
        else
        {
            carry = 0;
            sta0.push(t+'0');
        }
    }
    }
    LStack<char> sta;
    {
    LStack<char> sta1;
    LStack<char> sta2;
    moveToStart();num.moveToStart();
    for(int i=0;i<zs_len;i++)
    {
        char ch =getValue();
        sta1.push(ch);
        next();
    }
    for(int i=0;i<num.zs_len;i++)
    {
        sta2.push(num.getValue());
        num.next();
    }
    while(!(sta1.isEmpty()||sta2.isEmpty()))
    {
        int t =sta1.pop()-sta2.pop()+carry;
        if(t<0)
        {
            t+=10;
            carry = -1;
            sta.push(t+'0');
        }
        else
        {
            carry = 0;
            sta.push(t+'0');
        }
    }
    while(!sta1.isEmpty())
    {
        int t =sta1.pop()-'0'+carry;
        if(t<0)
        {
            t+=10;
            carry = -1;
            sta.push(t+'0');
        }
        else
        {
            carry = 0;
            sta.push(t+'0');
        }
    }
    while(!sta2.isEmpty())
    {
        int t =sta2.pop()-'0'+carry;
        if(t<10)
        {
            t+=10;
            carry = -1;
            sta.push(t+'0');
        }
        else
        {
            carry = 0;
            sta.push(t+'0');
        }
    }
    }
    while(!sta.isEmpty())
        result.append(sta.pop());
    result.append('.');
    while(!sta0.isEmpty())
        result.append(sta0.pop());
    result.del();
    return result;
}


number number::operator*(number& num)
{
    number result;
    reverse();
    num.reverse();
   // num.print();
    int i;                           // 先全部插入零
    for (i = 0; i < (zs_len+xs_len+num.zs_len+num.xs_len); i++){
        result.insert('0');
    }
   // cout<<"###"<<endl;
    Link<char> *cur = result.head->next;
    num.moveToStart();
    while (num.curr->next != NULL){  // 每一位进行相乘
    if (num.curr->next->element == '.') { num.next(); continue; }
        int carry = 0;
        result.curr = cur;
        moveToStart();
        while (curr->next != NULL){
            if (curr->next->element == '.') { next(); continue; }
            int t = result.curr->element - '0';
            t += (getValue() - '0') * (num.getValue() - '0') + carry;
            carry = t / 10;
            result.curr->element = t % 10 + '0';
            result.next();
            next();
        }
        while (result.curr != NULL){
            int t = result.curr->element - '0' + carry;
            carry = t / 10;
            result.curr->element = t % 10 + '0';
            result.curr = result.curr->next;
        }
        num.next();
        cur = cur->next;
    }
    result.moveToPos(xs_len + num.xs_len);    // 添上小数点
    result.insert('.');
  //  result.print();
    result.reverse();
  //  result.print();
    reverse();
    num.reverse();
  //  cout<<"###"<<endl;
    result.del0();
  // result.print();
  //  cout<<"###"<<endl;
    return result;
}

number number::chengfang(int n)
{
    number result = *this;

    while(n>1)
    {
       // cout<<n<<endl;
        result = result * (*this);
        n--;
        //result.print();
       // cout<<n<<endl;
    }
    //result.del();
    return result;

}

void number::del0()
{
    reverse();
    int i = 0;
    moveToStart();
    while (getValue() == '0') remove();
    while (getValue() != '.'){
        next();
        i++;
    }
    xs_len = i;
    moveToStart();
    LStack<char> st;
    while (curr->next != NULL){
        st.push(remove());
    }
    while (st.topValue() == '0') st.pop();
    if (st.topValue() == '.') st.push('0');
    while (st.length() > 0) insert(st.pop());
    zs_len = length() - 1 - i;
    reverse();
}


void number::display()
{
    curr = head;
    while(curr->next!=tail)
    {
        cout<<curr->next->element;
        curr = curr->next;
    }
    if(tail->element!='.')
        cout<<tail->element;
    cout<<endl;
}

#include <iostream>#include "number.h"#include "Llist.h"using namespace std;int main(){ number A,B,C;int n; cout<<"===================================================\n" <<"= calculator =\n" <<"===================================================\n"; cout<<"\n\nInput two positive number A and B,we will give you A+B,A-B,A*B.\n\n\nA :";A.input(); cout<<"B: ";B.input(); cout<<"A+B: ";(A+B).display(); cout<<"A-B: ";(A-B).display(); cout<<"A*B: ";(A*B).display(); cout<<"===================================================\n\n\n"; cout<<"Input a positive number C and a integer n,we will give C^n.\nC: ";C.input(); cout<<"n: ";cin>>n; cout<<"C^n: ";C.chengfang(n).display(); return 0;} 
 

以下是链表存储的数字number.h.
 

#ifndef NUMBER_H_INCLUDED#define NUMBER_H_INCLUDED#include "Llist.h"#include "Lstack.h"
 

class number :public Llist<char>{ private: int zs_len; int xs_len; void del(); void del0(); public:
 

 void input(); void display(); number(){zs_len=xs_len=0;} number& operator=(const number& num); number(const number& num); number operator+(number& num); number operator-(number& num); number operator*(number& num); number chengfang(int n);};
 

#endif // NUMBER_H_INCLUDED
 

#ifndef LLIST_H_INCLUDED
#define LLIST_H_INCLUDED

#include<iostream>
using namespace std;

template <typename E>
class Link
{
    private:
    static Link<E>* freelist;
    public:
    E element;
    Link* next;

    Link(const E elem,Link *n=NULL)
    {
        element = elem;
        next = n;
    }
    Link(Link *n=NULL)
    {
        next = n;
    }

};
////////////////////////////////////////////////////////////////////////////////////////
template <typename E>
class Llist
{
private://

    int cnt;
    void initial()
    {
        curr=head=tail=new Link<E>;
        cnt=0;
    }
    void removeall()
    {
        while(head!=tail)
        {
            curr = head;
            head = head->next;
            delete curr;
        }
    }
public:
    Link<E>* head;
    Link<E>* tail;
    Link<E>* curr;
	Llist(int size = 0){initial();}

	~Llist(){removeall(); }
    void print()
    {
        curr = head;
        while(curr!=tail)
        {
            cout<<curr->next->element;
            curr = curr->next;
        }
        cout<<endl;
    }
	void clear()
	{//reinitialize the list
        removeall();initial();
	}
	void insert(const E& it)
	{
        curr->next = new Link<E>(it,curr->next);//具体实现要看Link这个类里面的语法
        if (tail==curr) tail = curr->next;
        cnt++;
	}


	void append(const E& it)
	{
        tail=tail->next=new Link<E> (it,NULL);
        cnt++;
	}
    E remove()
    {
        E it =curr->next->element;
        Link<E> *temp =curr->next;
        if (tail ==curr->next) tail= curr;
        curr->next=temp->next;
        delete temp;
        cnt--;
        return it ;
	}
	void moveToStart(){curr =head;}
	void moveToEnd(){curr=tail;	}
	void prev()
	{
        if (curr==head) return;
        Link<E>* temp =head;
        while(temp->next!=curr)
            temp = temp ->next;
        curr=temp;
	}

    void reverse()//create a new list and move every element from the second element from the orginal list to new head->next
    {
        Link<E>* tmp = head->next;
        Link<E> *ptr,*r;
        Link<E>* t = tail;
        r = t->next = new Link<E>(tmp->element);
        tmp = tmp->next;
        while (tmp!=tail->next){
            ptr = new Link<E>(tmp->element,t->next);
            //cout<<ptr->element;
            t->next = ptr;
            delete head;
            head = head->next;
            tmp =tmp->next;
          //  cout<<"##\n";
        }
        head = tail;
        tail = r;
    }

	void next(){curr=curr->next;}
	int length()const{ return cnt;}
	int currPos()const
	{
        Link <E> *temp=head;
        int i;
        for(i=0;curr!=temp;i++)
        {
            temp=temp->next;
        }
        return i;
	}
	void moveToPos(int pos)
	{
        curr=head;
        for(int i =0;i<pos;i++)
            curr=curr->next;
	}
	const E& getValue()const
	{
        return curr->next->element;
	}
    E maxValue()
    {
        curr = head ->next;
        E max = curr->element;
        while(curr!=NULL)
        {
            if(curr->element>max) max = curr->element;
            curr = curr->next;
        }
        return max;
    }
};


#endif // LLIST_H_INCLUDED



 

#ifndef LSTACK_H_INCLUDED
#define LSTACK_H_INCLUDED
//template <typename E>
//class Link
//{
//  public:
//  E element;
//  Link<E> *next;
//  Link(E it,Link<E>* n = NULL)
//  {
//      element = it;
//      next = n;
//  }
//};

template <typename E>
class LStack
{   template <typename U>
    struct Link
    {
        E element;
        Link<U> *next;
        Link(U it,Link<U>* n = NULL)
        {
            element = it;
            next = n;
        }
    };
    private:
    Link<E> *top;
    int size;

    public:
    LStack(){top=NULL;size = 0;}
    ~LStack()
    {
        delete top;
    }
    //reclaim all the space used by the stack element
    void clear()
    {
        while(top!=NULL)
        {
            Link<E> *tmp =top;
            top = top->next;
            delete tmp;
        }
        size = 0;
    }
    //push an element on the top of the stack
    void push(const E &it)
    {
        top = new Link<E>(it,top);
        size++;
    }
    //remove the top element of the stack and return it
    E pop()
    {
        E it = top->element;
        Link<E> *temp = top;
        top= top->next;
        delete temp;
        size--;
        return it;
    }
    //get the top value
    const E& topValue() const
    {
        return top->element;
    }
    //return the number of the elements in the stack
    int length() const
    {
        return size;
    }
    bool isEmpty()
    {
        return (size==0);
    }

};

#endif // LSTACK_H_INCLUDED

 

 

 

 
 
 
 
 


   

 原文链接：https://www.f2er.com/datastructure/382864.html

      

      
                 
              

            

          

          
          
          

            

              




            

          


          

            

              

                  
    
猜你在找的数据结构相关文章



                                    
【数据结构】键树

                                
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...

                                
                                
                            



                                    
【数据结构】绪论

                                
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...

                                
                                
                            



                                    
【数据结构】证明法

                                
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...

                                
                                
                            



                                    
数据结构与算法系列之目录

                                
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...

                                
                                
                            



                                    
【数据结构】数组

                                
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...

                                
                                
                            







                                    
[操作系统]操作系统中断机制

                                
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...

                                
                                
                            



                                    
[日常] 浏览器前进后退与数据结构的思想

                                
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...

                                
                                
                            



                                    
[算法] 开放寻址法解决哈希冲突方式

                                
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...

                                
                                
                            



                                    
二叉树的基本概念介绍与代码实现（多图+代码）

                                
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...

                                
                                
                            



                                    
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)

                                
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...

                                
                                
                            







            

          

        

        
        
        
        

          
          

            

              

                
                
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全

                

              

            

          

          
         
          

            

              
 



              

            

          

          
          
          
          

            

              

                
                
              

            

          

          


          
          

            

              

                
                
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test