1 /*//////////////////////////////////  2             BY WEI  3             2014-10-27  4 //////////////////////////////////*/  5 #include <iostream>  6 #include <fstream>  7 #include <string>  8 #include <iomanip>  9 using namespace std; 10 typedef int ElemTp; 11 typedef struct OL 12 { 13     int i,j; 14     ElemTp v; 15     struct OL *right, *down; 16 }*OLink,OLNode; 17  18 OLink CreatOL(int m,int n) 19 { 20     OLink head=new OLNode; 21     head->i=m,head->j=n; 22     OLink q=head; 23     for(int i=0; i<m; i++) 24     { 25         OLink p=new OLNode; 26         p->right=p; 27         p->j=-1; 28         p->i=i; 29         q->down=p; 30         q=p; 31     } 32     q->down=head; 33     q=head; 34     for(int i=0; i<n; i++) 35     { 36         OLink p=new OLNode; 37         p->down=p; 38         p->j=i; 39         p->i=-1; 40         q->right=p; 41         q=p; 42     } 43     q->right=head; 44     q=head->right; 45     return head; 46 } 47 void DeleteOL(OLink head,int i,int j) 48 { 49     if(i<0||j<0||i>head->i-1||j>head->j-1) 50         return ; 51     OLink q,p; 52     p=head->right; 53     while(p!=head&&p->j!=j) 54         p=p->right; 55     q=p->down; 56     OLink q_down=p; 57     while(q!=p&&q->i!=i) 58     { 59         q=q->down; 60         q_down=q_down->down; 61     } 62     if(q==p) 63         return; 64     p=head->down; 65     while(p!=head&&p->i!=i) 66         p=p->down; 67     q=p->right; 68     OLink q_right=p; 69     while(q!=p&&q->j!=j) 70     { 71         q=q->right; 72         q_right=q_right->right; 73     } 74     if(q==p) 75         return ; 76     OLink temp=q_down->down; 77     q_down->down=q_down->down->down; 78     q_right->right=q_right->right->right; 79     delete temp; 80 } 81  82 bool InsertOL(OLink head,int i,int j,int value) 83 { 84     if(value=http://www.mamicode.com/=0) 85     { 86         DeleteOL(head,i,j); 87         return true; 88     } 89     DeleteOL(head,i,j); 90     int m=head->i,n=head->j; 91     if(i<0||j<0||i>m-1||j>n-1) 92         return false; 93     OLink p=head->right; 94     while(p->j!=j) 95         p=p->right; 96     OLink q=p->down; 97     OLink s=p; 98     while(q!=p&&q->i<i) 99     {100         q=q->down;101         s=s->down;102     }103     q=s;104     OLink temp=new OLNode;105     temp->i=i,temp->j=j,temp->v=value;106     OLink tt=q->down;107     q->down=temp;108     temp->down=tt;109     p=head->down;110     while(p->i!=i)111         p=p->down;112     q=p->right;113     s=p;114     while(q!=p&&q->j<j)115     {116         q=q->right;117         s=s->right;118     }119     q=s;120     tt=q->right;121     q->right=temp;122     temp->right=tt;123     return true;124 }125 void DisplayOL(OLink head)126 {127     OLink p=head->down;128     while(p!=head)129     {130         OLink q=p->right;131         while(q!=p)132         {133             cout<<setw(3)<<q->i<<" "<<setw(3)<<q->j<<" "<<setw(4)<<q->v<<endl;134             q=q->right;135         }136         p=p->down;137     }138 }139 void Show(OLink head)140 {141     OLink p=head->down;142     int i=0;143     while(i<head->i)144     {145         int j=0;146         OLink q=p->right;147         while(j<head->j)148         {149             if(q->j==j)150             {151                 cout<<setw(3)<<q->v<<" ";152                 q=q->right;153             }154             else155                 cout<<"  0 ";156             j++;157         }158         p=p->down;159         i++;160         cout<<endl;161     }162 }163 OLink Read_Text(void)164 {165     string path;166     cout<<"please input path:";167     cin>>path;168     ifstream in(path);169     if(!in)170     {171         cout<<"Can not open file"<<endl;172         return NULL;173     }174     int m,n;175     in>>m>>n;176     OLink head=CreatOL(m,n);177     int i,j,value;178     while(in>>i>>j>>value)179     {180         InsertOL(head,i,j,value);181     }182     return head;183 }184 185 void DeleteOL(OLink head)186 {187     OLink p=head->down;188     while(p!=head)189     {190         OLink q=p->right;191         while(q!=p)192         {193             OLink t=q->right;194             delete q;195             q=t;196         }197         OLink t=p->down;198         delete p;199         p=t;200     }201     p=head->right;202     while(p!=head)203     {204         OLink t=p->right;205         delete p;206         p=t;207     }208     delete head;209 }210 OLink Locate(OLink head,int i,int j)211 {212     if(i<0||j<0||i>head->i-1||j>head->j-1)213         return NULL;214     OLink p=head->down;215     for(int k=0; k!=i; k++)216     {217         p=p->down;218     }219     OLink q=p->right;220     while(q!=p)221     {222         if(q->j==j)223             break;224         q=q->right;225     }226     if(q->i==i&&q->j==j)227         return q;228     return NULL;229 }230 void TransformOL(OLink head)231 {232     int m=head->i,n=head->j;233     if(m>n)234     {235         OLink p=head;236         while(p->right!=head)237         {238             p=p->right;239         }240         for(int i=1; i<=m-n; i++)241         {242             OLink q=new OLNode;243             q->j=n-1+i;244             q->i=-1;245             q->down=q;246             p->right=q;247             q->right=head;248             p=q;249         }250     }251     else252     {253         if(n>m)254         {255             OLink p=head;256             while(p->down!=head)257             {258                 p=p->down;259             }260             for(int i=1; i<=n-m; i++)261             {262                 OLink q=new OLNode;263                 q->i=m-1+i;264                 q->j=-1;265                 q->right=q;266                 p->down=q;267                 q->down=head;268                 p=q;269             }270         }271     }272     int mm=max(m,n);273     head->i=mm,head->j=mm;274     OLink p=head->down;275     for(int i=0; i<mm; i++)276         for(int j=0; j<i; j++)277         {278             OLink a=Locate(head,i,j);279             OLink b=Locate(head,j,i);280             ElemTp aa;281             if(!a)282                 aa=0;283             else284                 aa=a->v;285             ElemTp bb;286             if(!b)287                 bb=0;288             else289                 bb=b->v;290             InsertOL(head,i,j,bb);291             InsertOL(head,j,i,aa);292         }293     if(n>m)294     {295         p=head;296         for(int i=0; i<n; i++)297             p=p->right;298         OLink ttt=p;299         p=p->right;300         ttt->right=head;301         for(int i=0; i<m-n; i++)302         {303             OLink t=p->down;304             while(t->down!=p)305             {306                 OLink tp=t->down;307                 delete t;308                 t=tp;309             }310             t=p->right;311             delete p;312             p=t;313         }314     }315     else316     {317         if(m>n)318         {319             p=head;320             for(int i=0; i<m; i++)321                 p=p->down;322             OLink ttt=p;323             p=p->down;324             ttt->down=head;325             for(int i=0; i<n-m; i++)326             {327                 OLink t=p->right;328                 while(t!=p)329                 {330                     OLink tp=t->right;331                     delete t;332                     t=tp;333                 }334                 t=p->down;335                 delete p;336                 p=t;337             }338         }339     }340     head->i=n,head->j=m;341 }342 int main(int a[],char *arg)343 {344     OLink head=Read_Text();345     Show(head);346     cout<<"Transform"<<endl;347     TransformOL(head);348     Show(head);349     DeleteOL(head);350     return 0;351 }