listの追加削除と並べ替えのマージ

  
  
  
  

   
   
   
   
#include<iostream> 
   
   
   
   
using namespace std; 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
struct listnode 
   
   
   
   
{ 
   
   
   
   
    type data; 
   
   
   
   
    listnode<type> * next; 
   
   
   
   
}; 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
class list 
   
   
   
   
{ 
   
   
   
   
public: 
   
   
   
   
    list(); 
   
   
   
   
    ~list(); 
   
   
   
   
    void insertend(type); //  
   
   
   
   
    bool insert(type,int); //  
   
   
   
   
    void delnode(int i);  //  
   
   
   
   
    int find(type T);   //  
   
   
   
   
    void uni(list<type>);//  
   
   
   
   
    void sort();         //  
   
   
   
   
    void empty();   //  
   
   
   
   
    bool print();  //  
   
   
   
   
    void merge(list<type>);//  
   
   
   
   
    int getlen();  //  
   
   
   
   
private: 
   
   
   
   
    listnode<type>* find_for_sort(int); 
   
   
   
   
    listnode<type> *first,*last; 
   
   
   
   
    int length; 
   
   
   
   
}; 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
listnode<type>* list<type>::find_for_sort(int t) 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *p=first->next; 
   
   
   
   
    int i=1; 
   
   
   
   
    while(p&&i!=t) 
   
   
   
   
    { 
   
   
   
   
        p=p->next; 
   
   
   
   
        i++; 
   
   
   
   
    } 
   
   
   
   
    return p; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
void list<type>::sort() 
   
   
   
   
{ 
   
   
   
   
    int m; 
   
   
   
   
    for(int i=1;i<=length;i++) 
   
   
   
   
    { 
   
   
   
   
        type t=find_for_sort(i)->data; 
   
   
   
   
        m=i; 
   
   
   
   
        for(int j=i+1;j<=length;j++) 
   
   
   
   
        { 
   
   
   
   
            if(find_for_sort(j)->data<t) 
   
   
   
   
            { 
   
   
   
   
                t=find_for_sort(j)->data; 
   
   
   
   
                m=j; 
   
   
   
   
            } 
   
   
   
   
        } 
   
   
   
   
        delnode(m); 
   
   
   
   
        insert(t,1); 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
void list<type>::uni(list<type> o) 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *p=o.first->next; 
   
   
   
   
    while(p) 
   
   
   
   
    { 
   
   
   
   
        if(!find(p->data)) insertend(p->data); 
   
   
   
   
        p=p->next; 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
void list<type>::merge(list<type> o) 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *t; 
   
   
   
   
    listnode<type> *pa=this->first->next; 
   
   
   
   
    listnode<type> *pb=o.first->next; 
   
   
   
   
    while(pa&&pb) 
   
   
   
   
    { 
   
   
   
   
        if(pa->data>pb->data) 
   
   
   
   
        { 
   
   
   
   
            t=pa; 
   
   
   
   
            pa=pa->next; 
   
   
   
   
        } 
   
   
   
   
        else 
   
   
   
   
        { 
   
   
   
   
            t->next=pb; 
   
   
   
   
            t=pb; 
   
   
   
   
            pb=pb->next; 
   
   
   
   
            t->next=pa; 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
    if(pa==0) t->next=pb; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
int list<type>::getlen() 
   
   
   
   
{ 
   
   
   
   
    return length; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
void list<type>::empty() 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *p1,*p2; 
   
   
   
   
 
   
   
   
   
    p1=first->next; 
   
   
   
   
    first->next=NULL; 
   
   
   
   
    while(p1!=NULL) 
   
   
   
   
    { 
   
   
   
   
        p2=p1; 
   
   
   
   
        p1=p1->next; 
   
   
   
   
        delete p2; 
   
   
   
   
    } 
   
   
   
   
    length=0; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
void list<type>::insertend(type t) 
   
   
   
   
{ 
   
   
   
   
 
   
   
   
   
    listnode<type> *p; 
   
   
   
   
    p=new listnode<type>; 
   
   
   
   
    p->data=t; 
   
   
   
   
    p->next=NULL; 
   
   
   
   
    last->next=p; 
   
   
   
   
    last=p; 
   
   
   
   
    length++; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
bool list<type>::insert(type t,int i) 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *p; 
   
   
   
   
    p=first; 
   
   
   
   
 
   
   
   
   
    int k=1; 
   
   
   
   
    while(p!=NULL&&k<i) 
   
   
   
   
    { 
   
   
   
   
        p=p->next; 
   
   
   
   
        k++; 
   
   
   
   
    } 
   
   
   
   
    if(p==NULL&&k!=i) 
   
   
   
   
        return false; 
   
   
   
   
    else 
   
   
   
   
    { 
   
   
   
   
        listnode<type> *tp; 
   
   
   
   
        tp=new listnode<type>; 
   
   
   
   
        tp->data=t; 
   
   
   
   
        tp->next=p->next; 
   
   
   
   
        p->next=tp; 
   
   
   
   
        length++; 
   
   
   
   
        if(i==length) last=tp; 
   
   
   
   
        return true; 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
void list<type>::delnode(int i) 
   
   
   
   
{ 
   
   
   
   
    int k=0; 
   
   
   
   
    listnode<type> *p,*t=0; 
   
   
   
   
    p=first; 
   
   
   
   
    while(p!=NULL&&k!=i) 
   
   
   
   
    { 
   
   
   
   
        t=p; 
   
   
   
   
        p=p->next; 
   
   
   
   
        k++; 
   
   
   
   
    } 
   
   
   
   
    t->next=p->next; 
   
   
   
   
    length--; 
   
   
   
   
    delete p; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
bool list<type>::print() 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *p=first->next; 
   
   
   
   
    if(length==0) 
   
   
   
   
        return false; 
   
   
   
   
    else 
   
   
   
   
    { 
   
   
   
   
        cout<<" "<<length<<" : "<<endl; 
   
   
   
   
        while(p) 
   
   
   
   
        { 
   
   
   
   
            cout<<p->data<<" "; 
   
   
   
   
            p=p->next; 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
    cout<<endl; 
   
   
   
   
    return true; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
int list<type>::find(type T) 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *p=first->next; 
   
   
   
   
    int i=1; 
   
   
   
   
    while(p&&p->data!=T) 
   
   
   
   
    { 
   
   
   
   
        p=p->next; 
   
   
   
   
        i++; 
   
   
   
   
    } 
   
   
   
   
    if(p) 
   
   
   
   
        return i; 
   
   
   
   
    else 
   
   
   
   
        return 0; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
list<type>::~list() 
   
   
   
   
{ 
   
   
   
   
    delete first,last; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
template<class type> 
   
   
   
   
list<type>::list() 
   
   
   
   
{ 
   
   
   
   
    listnode<type> *node=new listnode<type>; 
   
   
   
   
    node->next=NULL; 
   
   
   
   
    first=last=node; 
   
   
   
   
    length=0; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
int main() 
   
   
   
   
{ 
   
   
   
   
    list<int> s1,s2; 
   
   
   
   
    s1.insert(10,1); 
   
   
   
   
    s1.insert(7,2); 
   
   
   
   
    s1.insert(3,3); 
   
   
   
   
    s1.insert(4,4); 
   
   
   
   
    s2.insert(2,1); 
   
   
   
   
    s2.insert(4,2); 
   
   
   
   
    s2.insert(6,3); 
   
   
   
   
    s2.insert(8,4);// 4 type 8 
   
   
   
   
    //s1.sort(); 
   
   
   
   
    //s1.print(); 
   
   
   
   
    //s2.sort(); 
   
   
   
   
    //s2.print(); 
   
   
   
   
    //s1.merge(s2); // sort merge  
   
   
   
   
    s1.uni(s2);//  
   
   
   
   
    s1.print(); 
   
   
   
   
    return 0; 
   
   
   
   
}