#include?
#include?
#include?
const?int?N?=?1e5+10;//?最長的整數長度
char?A[N]?B[N];
//循環鏈表結點
struct?node
{
????int?data;???????????//?數值域
????int?len;???????????//?長度
????node*?pre;????//?前驅
????node*?next;??//?后繼
};

typedef?node*?List;

void?Type_char（List?*L?char?*s）;//!字符串轉換為鏈表
List?add（List?A?List?B）;//!計算A+B
List?sub（List?A?List?B）;//!計算A-B
void?print（List?a）;//!輸出a鏈表
void?Init（）;//!初始化操作包括輸入
void?menu（）;//!菜單
int?main（）
{
????menu（）;
????return?0;
}
/*測試數據
（1）-23456789;?-76543211;?輸出?-1000000
（2）-99999999;?1000000000000;?輸出?999900000001
（3）100010001;?-100010001;?輸出?0
（4）100010001;?-100010000;?輸出?1
（5）-999999999999;?-999999999999;?輸出?-1999999999998
（6）1000099999999;?1;?輸出?1000100000000
*/





//?將字符串字轉換成鏈表
//!頭部是符號位
void?Type_char（List?*L?char?*s）
{
????List?p?q;
????（*L）?=?（List）malloc（sizeof（node））;
????（*L）->pre?=?NULL;
????（*L）->next?=?NULL;
????（*L）->data?=?‘+‘;???????????//?默認符號位為‘+‘
????p?=?（*L）;
????int?len?=?strlen（s）sum?=?1Size?=?0End?=?0;
????if（s[0]?==?‘-‘）
????{
????????（*L）->data?=?‘-‘;
????????End?=?1;????//?如果是符號“，“則從字符串第二個字符位置開始
????}
????for?（int?i?=?len-1;?i?>=?End;?--i）
????{
????????if（sum?%?5）
????????{
????????????q?=?（List）malloc（sizeof（node））;
????????????q->data?=?s[i]?-?‘0‘;?????????//?字符轉換為整數
????????????q->pre?=?p;
????????????p->next?=?q;
????????????p?=?q;
????????????Size++;
????????}
????????sum++;
????}

????//?循環連接
????p->next?=?（*L）;
????（*L）->pre?=?p;
????（*L）->len?=?Size;????????????????????//?記錄鏈表的長度-1?————?不帶符號位的長度
}

//?加法
List?add（List?A?List?B）
{
????int?len1?=?A->len;
????int?len2?=?B->len;
????List?a?b;????????//?a為較長的整數鏈表，?b為較短的整數鏈表
????if（len1?>?len2）
????{
????????a?=?A;
????????b?=?B;
????}
????else
????{
????????a?=?B;
????????b?=?A;
????}
????len1?=?a->len;??????????//?較長鏈表長度
????len2?=?b->len;??????????//?較短鏈表長度

????int?sum?=?0;
????int?temp?=?0;?????????????//?保存進位值
????while?（sum?!=?len1）
????{
????????a?=?a->next;
????????b?=?b->next;

????????if?（sum?>=?len2）?a->data?=?a->data?+?temp;//已經超過較短鏈表長度，所以不需要加b->data
????????else?a->data?=?a->data?+?b->data?+?temp;
????????temp?=?0;
????????if?（a->data?>=?10）?a->data?-=?10?temp?=?1;//超過10表示有進位值
????????sum++;
????}
????if?（temp）
????{
????????//?如果最后一位還有進位則創建一個新的結點放到隊頭
????????List?p?=?（List）malloc（sizeof（node））;
????????p->data?=?temp;
????????p->next?=?a->next;
????????a->next->pre?=?p;
????????p->pre?=?a;
????????a->next?=?p;
????????a?=?p;
????????len1++;
????}
????a?=?a->next;???????//?回到符號位
????a->len?=?len1;??????//?注意頭部長度要變化
????return?a;
}

//?減法
List?sub（List?A?List?B）
{
????int?len1?=?A->len;
????int?len2?=?B->len;
????List?a?b;????????//?a為較長的整數鏈表，?b為較短的整數鏈表
????if（len1?>?len2）
????{
????????a?=?A;
????????b?=?B;
????}
????else?if（len1?????{
????????a?=?B;
????????b?=?A;
????}
????else
????{
????????List?tmp1?=?A?tm