广义表链表表示的复制删除比较运算的非递归实现(c++)

2018-02-10 20:14:27来源:cnblogs.com作者:Kukucao人点击

分享

广义表链表表示的删除:

从广义表附加头节点开始,逐一分离表头元素,是原子项就直接删除,是子表附加头节点则暂不删除,直接进入子表,再分离表头元素,然后用相同的方法删除,子表删除完成后向上回溯,继续删除上一层子表,如此不断进行直到整个广义表被删除为止

代码(C++)

  1 #include "stdafx.h"  2 #include <iostream>  3 #include <vector>  4 #include<string>  5 using namespace std;  6   7 struct Gen  8 {  9     int utype; 10     union 11     { 12         int ref; 13         struct Gen *hlink; 14         char value; 15     }info; 16     struct Gen *tlink; 17     Gen(int u); 18     Gen(int u, char v); 19 }; 20 Gen::Gen(int u) :utype(u), tlink(nullptr) 21 { 22     if (u == 0) 23         info.ref = 0; 24     else 25         info.hlink = nullptr; 26 } 27  28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr) 29 { 30     info.value = v; 31 } 32  33 Gen * strtogen(); 34  35 int main() 36 { 37     Gen *ptr = strtogen(); //ptr初始化为广义表附加头结点指针 38     bool TF = true; 39     vector<Gen *> stack; 40  41     while (true) 42     { 43         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1)) 44         { 45             if (TF == true) 46             { 47                 stack.push_back(ptr); 48                 if (ptr->utype == 0) 49                 { 50                     if (ptr->tlink == nullptr) 51                     { 52                         stack.pop_back(); 53                         TF = false; 54                         continue; 55                     } 56                     ptr = ptr->tlink;   //拉链,分理出广义表附加头节点的下一待删除节点 57                     stack[stack.size() - 1]->tlink = ptr->tlink; 58                 } 59                 else 60                 { 61                     if (ptr->info.hlink == nullptr) 62                         TF = false; 63                     else 64                     { 65                         ptr = ptr->info.hlink;   //拉链,分离出ptr指向的子表附加头节点在子表中的下一节点 66                         stack[stack.size() - 1]->info.hlink = ptr->tlink; 67                     } 68                 } 69             } 70             else 71             { 72                 if (ptr->utype == 0) 73                 { 74                     delete ptr; //删除附加头节点,至此删除成功,退出 75                     break; 76                 } 77                 else 78                 { 79                     delete ptr;  //删除子表附加头节点,子表删除成功 80                     stack.pop_back(); 81                     ptr = nullptr; 82                 } 83             } 84         } 85         else 86         { 87             if (ptr == nullptr) 88             { 89                 if (stack[stack.size() - 1]->utype == 0) 90                 { 91                     if (stack[stack.size() - 1]->tlink == nullptr) //广义表除附加头节点全部删除完毕 92                     { 93                         TF = false; 94                         ptr = stack[stack.size() - 1]; 95                         stack.pop_back(); 96                     } 97                     else   //广义表附加头节点下一子表附加头节点及子表删除完毕 98                     { 99                         ptr = stack[stack.size() - 1]->tlink;100                         stack[stack.size() - 1]->tlink = ptr->tlink;101                         TF = true;102                     }103                 }104                 else105                 {106                     if (stack[stack.size() - 1]->info.hlink == nullptr)  //子表除附加头节点全部删除完毕107                     {108                         TF = false;109                         ptr = stack[stack.size()-1];110                     }111                     else            //子表附加头节点下一子表附加头节点及子表删除完毕112                     {113                         ptr = stack[stack.size() - 1]->info.hlink;114                         stack[stack.size() - 1]->info.hlink = ptr->tlink;115                         TF = true;116                     }117                 }118             }119             else120             {121                 if (stack[stack.size() - 1]->utype == 0)122                 {123                     if (stack[stack.size() - 1]->tlink == nullptr) //广义表除附加头节点外还剩一个原子项待删除124                     {125                         delete ptr;  //删除之126                         ptr = stack[stack.size() - 1];127                         stack.pop_back();128                         TF = false;129                     }130                     else     //广义表头节点后的原子项待删除,其后还有节点待删除131                     {132                         delete ptr;133                         ptr = stack[stack.size() - 1]->tlink;134                         stack[stack.size() - 1]->tlink = ptr->tlink;135                     }136                 }137                 else138                 {139                     if (stack[stack.size() - 1]->info.hlink == nullptr) //子表除附加头节点外还剩一个原子项待删除140                     {141                         delete ptr;142                         ptr = stack[stack.size() - 1];143                         TF = false;144                     }145                     else   //子表头节点后的原子项待删除,其后还有节点待删除146                     {147                         delete ptr;148                         ptr = stack[stack.size() - 1]->info.hlink;149                         stack[stack.size() - 1]->info.hlink = ptr->tlink;150                     }151                 }152             }153         }154     }155     //运行结束后ptr成为野指针,栈空,删除成功156     cout << "链表形式的广义表删除成功!"<< endl;157     return 0;158 }159 160 Gen * strtogen()161 {162     string glist;163     cout << "请输入广义表的字符串形式" << endl;164     cin >> glist;165 166     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;167     for (auto i = glist.cbegin(); i != glist.cend(); ++i)168     {169         if (*i == '(')170         {171             if (i == glist.cbegin())172             {173                 ptr = new Gen(0);174                 stack.push_back(ptr);175                 TF = true;176             }177             else178             {179                 Gen *temp = new Gen(1);180                 if (ptr->utype == 1)181                 {182                     if (TF == true)183                         ptr->info.hlink = temp;184                     else185                         ptr->tlink = temp;186                 }187                 else188                 {189                     ptr->tlink = temp;190                 }191 192                 stack.push_back(temp);193                 TF = true;194                 ptr = temp;195             }196         }197         else198         {199             if (*i == ')')200             {201                 ptr = stack[stack.size() - 1];202                 stack.pop_back();203                 TF = false;204             }205             else206             {207                 if (*i != ',')208                 {209                     Gen *temp = new Gen(2, *i);210                     if (ptr->utype == 1)211                     {212                         if (TF == true)213                             ptr->info.hlink = temp;214                         else215                             ptr->tlink = temp;216                     }217                     else218                     {219                         ptr->tlink = temp;220                     }221 222                     ptr = temp;223                 }224             }225         }226     }227     cout << "已将字符串形式的广义表转换为链表形式" << endl;228     return ptr;229 }

广义表链表表示的复制:

就是按广度优先遍历的次序逐一复制,为方便复制,目标表指针总比原表遍历指针慢一步,原表遍历完成后复制就结束了

  1 #include "stdafx.h"  2 #include <iostream>  3 #include <vector>  4 #include <string>  5 using namespace std;  6   7 struct Gen  8 {  9     int utype; 10     union 11     { 12         int ref; 13         struct Gen *hlink; 14         char value; 15     }info; 16     struct Gen *tlink; 17     Gen(int u); 18     Gen(int u, char v); 19 }; 20 Gen::Gen(int u) :utype(u), tlink(nullptr) 21 { 22     if (u == 0) 23         info.ref = 0; 24     else 25         info.hlink = nullptr; 26 } 27  28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr) 29 { 30     info.value = v; 31 } 32  33 Gen * strtogen(); 34 void suboutput(Gen *head); 35  36 int main() 37 { 38     vector<Gen *> stack1;//源栈  39     vector<Gen *> stack2;//目标栈 40     Gen *ptr1=strtogen(); //ptr1初始化为源广义表附加头节点指针 41     Gen *ptr2=nullptr; //ptr2为目标广义表拷贝指针 42     bool TF = true; 43  44     while (true)  //循环开始,将源广义表链表表示拷贝为目标广义表链表表示 45     { 46         if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1)) 47         { 48             if (TF == true) 49             { 50                 stack1.push_back(ptr1); 51                 if (ptr1->utype == 0) 52                 { 53                     ptr2 = new Gen(0);           //拷贝广义表附加头节点,完成后ptr1递进 54                     ptr2->info.ref = ptr1->info.ref; 55                     stack2.push_back(ptr2); 56                     ptr1 = ptr1->tlink; 57                 } 58                 else 59                 { 60                     if (ptr2->utype == 1)  //需要把子表附加头节点拷贝至ptr2所指附加头节点后 61                     { 62                         Gen *temp = new Gen(1); 63                         if (ptr2 == stack2[stack2.size() - 1])   //ptr2新进至子表头节点,源广义表子表头节点链接至ptr2所指子表中头节点后 64                             ptr2->info.hlink = temp; 65                         else 66                             ptr2->tlink = temp; 67                         ptr2 = temp; 68                         stack2.push_back(ptr2); 69                         ptr1 = ptr1->info.hlink; 70                     } 71                     else 72                     { 73                         Gen *temp = new Gen(1); //由于ptr2指向目标广义表头节点或原子项,所以直接把待拷贝子表头节点链接于其后 74                         ptr2->tlink = temp; 75                         ptr2 = temp; 76                         stack2.push_back(ptr2); 77                         ptr1 = ptr1->info.hlink; 78                     } 79                 } 80             } 81             else 82             { 83                 if (ptr1->utype == 0) 84                 { 85                     ptr2 = stack2[stack2.size() - 1]; 86                     stack2.pop_back(); 87                     break; //拷贝完毕,退出,ptr2为目标广义表头节点 88                 } 89                 else 90                 { 91                     ptr2 = stack2[stack2.size() - 1]; 92                     stack2.pop_back(); 93                     ptr1 = ptr1->tlink; 94                     TF = true; 95                 } 96             } 97         } 98         else 99         {100             if (ptr1 == nullptr)  //子表拷贝完毕101             {102                 ptr2 = nullptr;103                 ptr1 = stack1[stack1.size() - 1];104                 stack1.pop_back();105                 TF = false;106             }107             else108             {109                 Gen *temp = new Gen(2, ptr1->info.value);  //拷贝原子项110                 if (ptr2->utype == 1 && stack2[stack2.size() - 1] == ptr2)111                     ptr2->info.hlink = temp;   //如果ptr2新进至子表头节点,操作和上述相同112                 else113                     ptr2->tlink = temp;   //操作和上述相同114                 ptr2 = temp;115                 ptr1 = ptr1->tlink;116             }117         }118     }119     cout << "复制完成,复制后的广义表为:";120     suboutput(ptr2);   //输出复制后的广义表121     return 0;122 }123 124 Gen * strtogen()125 {126     string glist;127     cout << "请输入广义表的字符串形式" << endl;128     cin >> glist;129 130     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;131     for (auto i = glist.cbegin(); i != glist.cend(); ++i)132     {133         if (*i == '(')134         {135             if (i == glist.cbegin())136             {137                 ptr = new Gen(0);138                 stack.push_back(ptr);139                 TF = true;140             }141             else142             {143                 Gen *temp = new Gen(1);144                 if (ptr->utype == 1)145                 {146                     if (TF == true)147                         ptr->info.hlink = temp;148                     else149                         ptr->tlink = temp;150                 }151                 else152                 {153                     ptr->tlink = temp;154                 }155 156                 stack.push_back(temp);157                 TF = true;158                 ptr = temp;159             }160         }161         else162         {163             if (*i == ')')164             {165                 ptr = stack[stack.size() - 1];166                 stack.pop_back();167                 TF = false;168             }169             else170             {171                 if (*i != ',')172                 {173                     Gen *temp = new Gen(2, *i);174                     if (ptr->utype == 1)175                     {176                         if (TF == true)177                             ptr->info.hlink = temp;178                         else179                             ptr->tlink = temp;180                     }181                     else182                     {183                         ptr->tlink = temp;184                     }185 186                     ptr = temp;187                 }188             }189         }190     }191     cout << "已将字符串形式的广义表转换为链表形式" << endl;192     return ptr;193 }194 195 void suboutput(Gen *head)196 {197     Gen *ptr = head;198     bool TF = true;199     vector<Gen *> stack;200     while (true)201     {202         if (ptr != nullptr && (ptr->utype == 0 || ptr->utype == 1))  //注意203         {204             if (TF == true)205             {206                 stack.push_back(ptr);207                 cout << "(";208                 if (ptr->utype == 0)   //注意209                 {210                     ptr = ptr->tlink;211                 }212                 else213                 {214                     ptr = ptr->info.hlink;215                 }216             }217             else218             {219                 if (ptr->utype == 0)220                     break;221                 else222                 {223                     ptr = ptr->tlink;224                     TF = true;225                 }226             }227         }228         else229         {230             if (ptr == nullptr)231             {232                 cout << ")";233                 ptr = stack[stack.size() - 1];234                 if (ptr->utype != 0 && ptr->tlink != nullptr)    //注意235                     cout << ",";236                 stack.pop_back();237                 TF = false;238             }239             else240             {241                 cout << ptr->info.value;242                 ptr = ptr->tlink;243                 if (ptr != nullptr)244                     cout << ",";245             }246         }247     }248     cout << endl;249 }

运行结果:

基于广义表链表表示的比较:

两表指针同步动作,按广度优先遍历逐一比较,比较到某一处节点不等则广义表不等,否则会一直比较至遍历完整个广义表,此时两广义表相等

  1 #include "stdafx.h"  2 #include <iostream>  3 #include <vector>  4 #include <string>  5 using namespace std;  6   7 struct Gen  8 {  9     int utype; 10     union 11     { 12         int ref; 13         struct Gen *hlink; 14         char value; 15     }info; 16     struct Gen *tlink; 17     Gen(int u); 18     Gen(int u, char v); 19 }; 20 Gen::Gen(int u) :utype(u), tlink(nullptr) 21 { 22     if (u == 0) 23         info.ref = 0; 24     else 25         info.hlink = nullptr; 26 } 27  28 Gen::Gen(int u, char v) :utype(u), tlink(nullptr) 29 { 30     info.value = v; 31 } 32  33 bool equals(Gen *ptr1, Gen *ptr2); //判断ptr1和ptr2指向的广义表节点是否相等的函数 34 Gen * strtogen(); 35  36 int main() 37 { 38     vector<Gen *> stack1; vector<Gen *> stack2; 39     Gen *ptr1 = strtogen(); //指向广义表1附加头节点 40     Gen *ptr2= strtogen(); //指向广义表2附加头节点 41     //两指针同步动作 42     bool TF = true; 43     int isequals = 1; //=1两广义表相等,否则不等 44     while (true) 45     { 46         if (ptr1 != nullptr && (ptr1->utype == 0 || ptr1->utype == 1)) 47         { 48             if (TF == true) 49             { 50                 if (ptr1->utype == 0) 51                 { 52                     stack1.push_back(ptr1); 53                     stack2.push_back(ptr2); 54                     ptr1 = ptr1->tlink;  //附加头节点不必比较,跳过 55                     ptr2 = ptr2->tlink; 56                 } 57                 else 58                 { 59                     if (equals(ptr1, ptr2) == true)  //比较表1子表头节点或指针和表2对应位置节点或指针 60                     { 61                         stack1.push_back(ptr1); 62                         stack2.push_back(ptr2); 63                         ptr1 = ptr1->info.hlink; 64                         ptr2 = ptr2->info.hlink; 65                     } 66                     else 67                     { 68                         isequals = 0;  //不等,isequals置位,退出 69                         break; 70                     } 71                 } 72             } 73             else 74             { 75                 if (ptr1->utype == 0)  //比较完成,退出 76                     break; 77                 else 78                 { 79                     ptr1 = ptr1->tlink; 80                     ptr2 = ptr2->tlink; 81                     TF = true; 82                 } 83             } 84         } 85         else 86         { 87             if (ptr1 == nullptr) 88             { 89                 if (equals(ptr1, ptr2) == true)  //比较ptr1或其指向节点和ptr2或其指向节点 90                 { 91                     ptr1 = stack1[stack1.size() - 1]; 92                     ptr2 = stack2[stack2.size() - 1]; 93                     stack1.pop_back(); 94                     stack2.pop_back(); 95                     TF = false; 96                 } 97                 else 98                 { 99                     isequals = 0;100                     break;101                 }102             }103             else104             {105                 if (equals(ptr1, ptr2) == true)  //比较ptr1或其指向的原子项和表2对应位置指针ptr2或其指向的节点106                 {107                     ptr1 = ptr1->tlink;108                     ptr2 = ptr2->tlink;109                 }110                 else111                 {112                     isequals = 0;113                     break;114                 }115             }116         }117     }118     if (isequals)119         cout << "两广义表相等";120     else121         cout << "两广义表不等";122     cout << endl;123     return 0;124 }125 126 bool equals(Gen *ptr1, Gen *ptr2)   //ptr1和ptr2所指节点相等返回true否则返回false127 {128     if (ptr1 == nullptr && ptr2 == nullptr)129         return true;130     else131     {132         if (ptr1 != nullptr && ptr2 != nullptr)133         {134             if (ptr1->utype != ptr2->utype)135                 return false;136             else137             {138                 if (ptr1->utype == 1)139                     return true;140                 else141                 {142                     if (ptr1->info.value == ptr2->info.value)143                         return true;144                     else145                         return false;146                 }147             }148         }149         else150         {151             return false;152         }153     }154 }155 156 Gen * strtogen()157 {158     string glist;159     cout << "请输入广义表的字符串形式" << endl;160     cin >> glist;161 162     Gen *ptr = nullptr; vector<Gen *> stack; bool TF;163     for (auto i = glist.cbegin(); i != glist.cend(); ++i)164     {165         if (*i == '(')166         {167             if (i == glist.cbegin())168             {169                 ptr = new Gen(0);170                 stack.push_back(ptr);171                 TF = true;172             }173             else174             {175                 Gen *temp = new Gen(1);176                 if (ptr->utype == 1)177                 {178                     if (TF == true)179                         ptr->info.hlink = temp;180                     else181                         ptr->tlink = temp;182                 }183                 else184                 {185                     ptr->tlink = temp;186                 }187 188                 stack.push_back(temp);189                 TF = true;190                 ptr = temp;191             }192         }193         else194         {195             if (*i == ')')196             {197                 ptr = stack[stack.size() - 1];198                 stack.pop_back();199                 TF = false;200             }201             else202             {203                 if (*i != ',')204                 {205                     Gen *temp = new Gen(2, *i);206                     if (ptr->utype == 1)207                     {208                         if (TF == true)209                             ptr->info.hlink = temp;210                         else211                             ptr->tlink = temp;212                     }213                     else214                     {215                         ptr->tlink = temp;216                     }217 218                     ptr = temp;219                 }220             }221         }222     }223     cout << "已将字符串形式的广义表转换为链表形式" << endl;224     return ptr;225 }

运行结果:

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台