多重表（廣義表）

在深入淺出數據結構系列前面的文章中，我們一直在討論“線性表”，其形式如下：

由a1,a2,a3,……a(n-1)個元素組成的序列，其中每一個元素ai(0<i<n)都是一個“原子”，“原子”的意思就是說元素本身是一個個體，所有元素都是相同的結構。

但是在我們常見的某些應用，比如Excel的表格中，我們發現表并不一定是線性表，Excel中的表就明顯是二維的結構

那么在數據結構中，我們會使用這種廣義上的表嗎？答案是會，我們也會、或者說我們也能使用這樣的非線性表。其實我們早就已經在使用這樣的非線性表、廣義表了，那就是多維數組。不難發現二維數組就可以抽象成Excel當中的表的樣子。那么，廣義表的定義是怎樣的呢？其實很簡單，就是在線性表的基礎上稍加修改，我會用綠色將修改了的部分標識出來：

由a1,a2,a3,……a(n-1)個元素組成的序列，其中每一個元素ai(0<i<n)可能又是一個廣義表。

可能會有人發現一個小小的問題，就是為什么我又將廣義表叫作多重表呢？這其實只是一個理解角度的不同而帶來的不同叫法罷了，多重表這種叫法想表達的主要意思是表中的元素可以是另一個表，而這另一個表中的元素又可以是一個表，相當于“一重又一重”的表，所以叫多重表。這個叫法其實并不是很重要。

講到這兒，多重表的定義和可能的使用場景（想想多維數組可能使用的情況）想必大家都心里有數了，但是這篇博文肯定不能就這么結束了? 其實我們今天真正想討論的，是當多維數組不能滿足或者說不適合我們遇到的情況時，我們該如何用其他途徑實現一個多重表？

為了說明這一點，顯然我們需要先舉一個多維數組不適合、卻又需要使用多重表的例子：

假設我們的程序要存儲一所大學的學生選課情況，然后允許用戶執行兩個操作，一個是查詢某名學生選了哪些課程，另一個是查詢某個課程有哪些學生選擇了。對于這樣的應用場景，顯然需要使用到一個多重表，準確的說是一個二維的多重表，其中一維表示課程，另一維表示學生，就像下面的圖。那么提到二維的多重表，我們腦海中最先浮現的應該就是二維數組了?

（存儲學生選課的抽象的二維多重表，橫向代表學生A,B,C……縱向代表課程1，2，3……，若某一項打勾則表示該學生選了該課程，比如若A1打勾則表示學生A選擇了課程1）

但是，現在情況有了新條件，這一所大學我們知道三個信息：學生人數大約為5000人，學校所有開設的課程大約有1000門，一般來說一個學生選的課程也就10門。

　　那么，根據這三個信息我們會發現，如果我們使用二維數組來存儲學生選課的信息，總共將需要500萬個元素，而平均來說其中只有5萬個元素是“打勾”的，其它495萬個元素都是“空”的，這樣的浪費顯然是巨大的！

　　所以我們現在需要的就是一個“不那么浪費空間”的二維多重表。回顧我們學習線性表的歷史，我們會發現，為了避免使用一維數組帶來的巨大浪費，我們使用了一維的鏈表來替代，那么現在我們在二維數組上遇到了麻煩，是否可以用“二維鏈表”來替代呢？或者換句話說，是否有用鏈表實現的多重表呢？答案是肯定的，實現也是簡單的。其實就是令每個課程作為一個鏈表的表頭，每個學生作為一個鏈表的表頭，除去學生結點和課程結點，其他結點均有一個nextStudent指針和一個nextCourse指針，分別指向下一個學生和下一門課程。我們用一張圖片來展示一下用鏈表實現多重表大致是“長什么樣”的：
　　
　　

不難看出，使用鏈表來實現需要的二維多重表能夠節省下很多的空間（495萬個結點），因為我們“跳過了”不需要的那些結點。那么現在，我們給出實現這個二維多重鏈表的各個結點定義：

struct node
{bool choose;struct node *hNextNode;struct node *vNextNode;struct student *student;struct course * course;
}struct student
{char name[SIZE];struct node *firstNode;
}struct course
{char name[SIZE];struct node *firstNode;
}

有了結點的定義，抽象圖，想來實現二維多重鏈表也不是什么難事了，所以對這個問題的討論就到此為止。

　　

　　稍微回顧一下本文討論的順序就不難發現，其實我們只是將“一維表中浪費空間的解決辦法”擴展到了“二維表中浪費空間的解決辦法”罷了，也可以說將“鏈表替代數組”擴展到了“二維鏈表替代二維數組”的情況，類似的我們還可以繼續擴展到更高的維度，比如上面的例子中，我們除了學生、課程，還可以有“某個學生在某門課程的歷次成績”，這樣一來就出現了第三維度。