创建广义表，判断广义表是否相等

1. //创建广义表 
2. //算法思路: 从字符序列中分离出左部,右部,依次为左部和右部建立存储 
3.  
4. char s[61]; //设字符序列长度不超过60 
5. //eg:  
6. //  (a,b),(c),d,((e,f),g) 
7. //  |    |              | 
8. //  a    i              b 
9. int sever(int a,int b) 
10. {//从Sa->Sb中分离出左部,函数值为左部后面一个字符的下标 
11.  int i,k; 
12.  if(a>b) return 0; //a,b的大小弄错了 
13.  k=0; 
14.  i=a; //i是遍历的指针 
15.  do  
16.  { 
17.   switch(s[i]) 
18.   { 
19.   case '(': k++;break; //k=1 
20.   case ')': k--;       //K=0 .这个时候while可以结束 
21.   } 
22.   i++; 
23.  } while (!((k==0)&&(s[i]==',')||(i>b))); 
24.  
25.  return i; 
26. } 
27. //eg:  
28. //  ((a,b),(c),d,((e,f),g)) 
29. //  |                     | 
30. //  i                     j 
31. void create(node* &p,int i,int j) 
32. {//根据Si~Sj 创建链表,返回表头指针p 
33.  int k; 
34.  node *q; 
35.  if(i>j) 
36.  { 
37.   return NULL;//如果i,j的大小的不对. 
38.  } 
39.  else 
40.  {//生成一个新的节点 
41.   p=new node(); 
42.   if(i==j) 
43.   {//如果i,j指向一个原子节点,生成的节点存放原子值 
44.    p->tag=0; 
45.    p->atom=s[i];   
46.   } 
47.   else 
48.   {//新生成的节点作表头节点 
49.    p->tag=1; 
50.    p->next=NULL; 
51.    //去掉左右括号 
52.    i++; 
53.    j--; 
54.  
55.    //分离出左部和右部 
56.    k=sever(i,j);  //k 左部的下一个字符 
57.  
58.    //递归处理左部 
59.    create(p->head,i,k-1); //p->head为返回的左部建立的链表的头指针 
60.    //递归处理右部 
61.    q=p->head; //q为左部的指针 
62.    while(q!=NULL) 
63.    { 
64.     i=k+1; 
65.     k=sever(q->next,i,k-1); 
66.     q=q->next; 
67.    } 
68.   } 
69.  
70.  } 
71.  
72. } 
73.  
74. //判断两个广义表是否相等 
75. //算法思路:使用递归的方法,设Si是广义表S的第i个元素,Ti是广义表T的第i个元素 
76. int equal(node* s,node* t) 
77. {//s t是两个广义表的表头指针 
78.  int r=0; 
79.  if((s==NULL)&&(t==NULL)) 
80.  {//如果两个广义表都是空的,就相等 
81.   r=1; 
82.  } 
83.  else 
84.  { 
85.   if((s!=NULL)&&(t!=NULL)) 
86.   {//如果两个广义表都不是空的 
87.    if(s->tag == t->tag) 
88.    { 
89.     switch(s->tag) 
90.     { 
91.     case 0: //如果都是原始节点,并且值相等,next相等,就是相等的 
92.      r=((s->atom==t->atom)&&(equal(s->next,t->next)==1)); 
93.      break; 
94.     case 1: //如果是子表,就判断head(它的下一级节点),next(它的同级别节点)是否相同. 
95.      r=(equal(s->head,t->head)==1)&&(equal(s->next,t->next)==1); 
96.     } 
97.    } 
98.   } 
99.  } 
100.  return r; 
101. }