我是“計算機科學與技術”專業的一名在校大學生，這是我的第一篇博文，用詞不當還請各位看官多多包涵。
這篇博文是關于西北工業大學NOJ資料結構習題中的“求廣義表深度”的思路實作與調試心得，如有錯誤或纰漏歡迎各位大佬指正。
題目如下：
讀題之後，第一反應是與之前做過的一道“表達式括号比對”題目類似，似乎可以用“棧”的方法來解決，但題目明确要求要用廣義表而且老師前兩天也剛剛講過關于廣義表的遞歸運算，是以我決定使用遞歸來将資料存入廣義表，再使用遞歸來計算出該廣義表的深度。
建構廣義表的思路是通過判斷每次輸入的字元來判斷需要新生成什麼樣的節點，再通過上一節點資訊來判斷目前節點應連接配接在表的什麼位置；計算廣義表深度的思路是通過判斷該節點的資訊，計算出後面與下面所有節點深度最大一個，形成遞歸，最終傳回改廣義表的深度。
首先設計出節點的資料類型，“judge”用來判斷此節點類型，1是“Data節點”，0是“Node節點”；“before”是指向上一個節點指針；“next”是指向右側節點的指針；紅框内是union型的資料，為“Data節點”時是存入的資料，為“Node節點”時是指向下面節點的指針。
由此可以将（a，（b，c））轉變為所設計的廣義表：同級的a與bc同行，同級的b與c同行，每個“Node節點”的down所在行的每一節點就是該括号内的所有資料，如下圖：
而我計算深度的方法是不斷将節點右側和下方的深度計算出來，取其中最大的深度，如下圖：
我的實作如下：
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int judge;
struct Node *before;
struct Node *next;
union
{
struct Node *down;
char data;
};
};
void createGeneralNode (struct Node *pre);
void createGeneralList (struct Node *head);
void run ();
int getDepth (struct Node *node);
int main()
{
run ();
return 0;
}
void createGeneralNode (struct Node *pre)
{
char s,ss=0;
struct Node *cur;
if ((s=getchar())==',')
{
ss=s;
s=getchar();
}
if (s>='a'&&s<='z')
{
cur =(struct Node *)malloc (sizeof(struct Node));
if (ss==',')
{
pre->next=cur;
}
else
{
pre->down=cur;
}
cur->before=pre;
cur->data=s;
cur->next=NULL;
cur->judge=1;
createGeneralNode (cur);
}
else
{
if (s=='(')
{
cur =(struct Node *)malloc (sizeof(struct Node));
if (ss==',')
{
pre->next=cur;
}
else
{
pre->down=cur;
}
cur->before=pre;
cur->down=NULL;
cur->next=NULL;
cur->judge=0;
createGeneralNode (cur);
}
else
{
if (s==')')
{
while (pre->judge||pre->next)
{
pre=pre->before;
}
createGeneralNode (pre);
}
}
}
}
void createGeneralList (struct Node *head)
{
head->judge=0;
head->down=NULL;
head->next=NULL;
head->before=NULL;
createGeneralNode(head);
}
void run ()
{
struct Node head;
int depth;
createGeneralList(&head);
depth=getDepth(head.down);
printf ("%d\n%d",depth,depth);
}
int getDepth (struct Node *node)
{
int max=0,depth;
struct Node *p;
for (p=node->next;p;p=p->next)
{
if (p->judge)
{
depth=0;
}
else
{
if (p->down)
{
depth=getDepth(p->down)+1;
}
else
{
depth=1;
}
}
max=depth>max?depth:max;
}
if (node->judge)
{
depth=0;
}
else
{
if (node->down)
{
depth=getDepth(node->down)+1;
}
else
{
depth=1;
}
}
return max=depth>max?depth:max;
}
其函數調用關系如下：
以下是各函數注釋代碼：
void run ()
{
struct Node head;
int depth;
createGeneralList(&head); //建立廣義表并輸入資料
depth=getDepth(head.down); //獲得廣義表深度
printf ("%d\n%d",depth,depth); //輸出
}
void createGeneralList (struct Node *head)
{
head->judge=0; //初始化
head->down=NULL; //初始化
head->next=NULL; //初始化
head->before=NULL; //初始化
createGeneralNode(head); //建立節點
}
void createGeneralNode (struct Node *pre)//輸入值為上一個節點位址
{
char s,ss=0;
struct Node *cur;
if ((s=getchar())==',')//若輸入為","，記錄
{
ss=s;
s=getchar();
}
if (s>='a'&&s<='z')
{
cur =(struct Node *)malloc (sizeof(struct Node));
if (ss==',') //如果與上一個節點同行
{
pre->next=cur;
}
else //如果與上一個節點不同行
{
pre->down=cur;
}
cur->before=pre; //該Date節點指派
cur->data=s;
cur->next=NULL;
cur->judge=1;
createGeneralNode (cur);//遞歸，重新建立節點
}
else
{
if (s=='(')
{
cur =(struct Node *)malloc (sizeof(struct Node));
if (ss==',') //如果與上一個節點同行
{
pre->next=cur;
}
else //如果不同行
{
pre->down=cur;
}
cur->before=pre; //Node節點指派
cur->down=NULL;
cur->next=NULL;
cur->judge=0;
createGeneralNode (cur);//重新建立節點
}
else
{
if (s==')')
{
while (pre->judge||pre->next)//尋找前面第一個右側為空的Node節點
{
pre=pre->before;
}
createGeneralNode (pre);//重新建立節點
}
}
}
}
int getDepth (struct Node *node)
{
int max=0,depth;
struct Node *p;
for (p=node->next;p;p=p->next) //周遊節點右側部分，尋找其中最大深度
{
if (p->judge)
{
depth=0;
}
else
{
if (p->down)
{
depth=getDepth(p->down)+1;
}
else
{
depth=1;
}
}
max=depth>max?depth:max;
}
if (node->judge) //周遊下方節點，尋找其中最大深度
{
depth=0;
}
else
{
if (node->down)
{
depth=getDepth(node->down)+1;
}
else
{
depth=1;
}
}
return max=depth>max?depth:max;//傳回兩側深度較大的值
}
輸入函數我重寫了兩次才完成，都是因為判斷條件不完善導緻無法得到正确的廣義表，下次在設計時需要考慮周全，避免無意義的返工。
測深度的方法想了好久，也參考了老師的方法（其實是沒看懂。。。），主要原因還是對遞歸的了解不夠透徹，無法直接想出所需的遞歸算法。
第一次寫的博文，寫了很長時間，已經快三點了。。。下次我一定盡量在白天寫，希望自己能堅持下來。