1 #include 2 #include 3 #include 4 using namespace std; 5 6 template 7 struct genListNode 8 { 9 int utype; 10 union { 11 int ref; 12 Type value; 13 genListNode * hlink; 14 }info; 15 genListNode * tlink; 16 genListNode() 17 { 18 utype = 0; 19 info.ref = 0; 20 tlink = 0; 21 } 22 }; 23 24 #define maxSize 100 25 template 26 class generalized_list 27 { 28 private: 29 genListNode * first; 30 public: 31 generalized_list(); 32 ~generalized_list(); 33 void create_list(); 34 Type get_sum(); 35 private: 36 char list_name[maxSize]; 37 genListNode * list_ptr[maxSize]; 38 int list_num; 39 int search_list_name(char chr); 40 void create_sub_list(genListNode * &ls); 41 void remove_sub_list(genListNode * &ls); 42 }; 43 44 template 45 generalized_list ::generalized_list() 46 { 47 first = new genListNode ; 48 list_num = 0; 49 assert(first != 0); 50 } 51 52 template 53 generalized_list ::~generalized_list() 54 { 55 remove_sub_list(first); 56 list_num = 0; 57 } 58 59 template 60 int generalized_list ::search_list_name(char chr) 61 { 62 for(int i = 0; i < list_num; i++) 63 if(chr == list_name[i]) 64 return i; 65 return -1; 66 } 67 68 template 69 void generalized_list ::create_sub_list(genListNode * &ls) 70 { //新建一个广义表，以这种形式输入："D(B(a,b),C(u,E(x,y,z)),A(#));" 71 char ch; 72 cin >> ch; 73 if(isalpha(ch) && isupper(ch) || ch == '('){ 74 ls = new genListNode ; 75 ls->utype = 2; 76 if(isalpha(ch) && isupper(ch)){ 77 //表名处理 78 int pos; 79 pos = search_list_name(ch); 80 if(pos >= 0){ //该子表已出现过 81 list_ptr[pos]->info.ref++; 82 ls->info.hlink = list_ptr[pos]; 83 cin >> ch; 84 if(ch != '('){ 85 cerr << "输入格式有误！表名之后必须是\'(\'！" << endl; 86 exit(-1); 87 } 88 int flag = 1; 89 while(flag > 0){ //该子表已出现过，把该表的元素读掉 90 cin >> ch; 91 if(ch == '(') 92 flag++; 93 else if(ch == ')') 94 flag--; 95 else 96 ; 97 } 98 }else{ //该子表未出现过 99 //建立子表的附加头结点 100 ls->info.hlink = new genListNode ; 101 ls->info.hlink->utype = 0; 102 ls->info.hlink->info.ref = 1; 103 104 list_name[list_num] = ch; 105 list_ptr[list_num] = ls->info.hlink; 106 list_num++; 107 cin >> ch; 108 if(ch != '('){ 109 cerr << "输入格式有误！表名之后必须是\'(\'！" << endl; 110 exit(-1); 111 } 112 create_sub_list(ls->info.hlink->tlink);//递归建子表 113 } 114 }//表名处理结束 115 create_sub_list(ls);//递归建后续表 116 }else if(ch == ',') 117 create_sub_list(ls->tlink); 118 else if(ch == ')') 119 ls->tlink = NULL; 120 else if(ch == '#'){ 121 ls = NULL; 122 cin >> ch; 123 }else if(ch == ';') 124 return ; 125 else{ 126 cin.putback(ch); 127 Type temp; 128 cin >> temp; 129 ls = new genListNode ; 130 ls->utype = 1; 131 ls->info.value = temp; 132 create_sub_list(ls); 133 } 134 } 135 136 template 137 void generalized_list ::remove_sub_list(genListNode * &ls) 138 { 139 ls->info.ref--; 140 if(ls->info.ref <= 0){ 141 genListNode * p; 142 while(ls->tlink != NULL){ 143 p = ls->tlink; 144 if(p->utype == 2){ 145 remove_sub_list(p->info.hlink); 146 if(p->info.hlink->info.ref <= 0) 147 delete p->info.hlink; 148 } 149 ls->tlink = p->tlink; 150 delete p; 151 }//end while 152 }//end if 153 } 154 155 template 156 void generalized_list ::create_list() 157 { 158 cout << "以下面的形式输入广义表：D(B(a,b),C(u,(x,y,z)),A(#));" << endl; 159 create_sub_list(first->tlink); 160 genListNode *p, *q; 161 p = first; 162 q = first->tlink; 163 first = q->info.hlink; 164 first->utype = 0; 165 first->info.ref = 0; 166 delete p; 167 delete q; 168 } 169 170 template 171 Type generalized_list ::get_sum() 172 { 173 Type sum = 0; 174 genListNode * p; 175 for(int i = 0; i < list_num; i++){ 176 p = list_ptr[i]; 177 for(; p != NULL; p = p->tlink) 178 if(p->utype == 1) 179 sum += p->info.value; 180 } 181 return sum; 182 }
View Code