影響空間規(guī)模的幾種數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

正文
            所謂數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，就是數(shù)據(jù)的元素與元素之間在計(jì)算機(jī)中的一種表示，它的目的是為了解決空間規(guī)模問(wèn)題，或者是通過(guò)空間規(guī)模問(wèn)題從而間接地解決時(shí)間規(guī)模問(wèn)題。我們知道，隨著輸入的數(shù)據(jù)量越來(lái)越大，在有限的內(nèi)存里，不能把這些數(shù)據(jù)完全的存下來(lái)，這就對(duì)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和設(shè)計(jì)存儲(chǔ)的算法提出了更高的要求。

       本文將介紹幾種存儲(chǔ)結(jié)構(gòu)，分別為鏈?zhǔn)浇Y(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖結(jié)構(gòu)以及矩陣結(jié)構(gòu)。

第一節(jié) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

       所謂鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，一般就是用一個(gè)頭指針指向鏈表的第一個(gè)節(jié)點(diǎn)，如果你要增加新的存儲(chǔ)元素時(shí)，只需在已有節(jié)點(diǎn)的后面插入新結(jié)點(diǎn)即可。

       鏈表通常有單鏈表、雙鏈表、循環(huán)鏈表。在這，我只介紹單鏈表，雙鏈表和循環(huán)鏈表只是單鏈表的拓展罷了。下圖就是一個(gè)簡(jiǎn)單的單鏈表圖示。

單鏈表的類型描述如下代碼：
  1. typedef char DataType;  /***假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符***/  
  2. typedef struct node{    /***結(jié)點(diǎn)類型定義***/  
  3.     DataType data;      /***結(jié)點(diǎn)的數(shù)據(jù)域***/  
  4.     struct node *next;  /***結(jié)點(diǎn)的指針域***/  
  5.     }ListNode;  
  6.     typedef ListNode *LinkList;  
  7.     ListNode *p;  
  8.     LinkList head;  
  9. 附注：   
  10.     ① LinkList和ListNode *是不同名字的同一個(gè)指針類型（命名的不同是為了概念上更明確）  
  11.     ② LinkList類型的指針變量head表示它是單鏈表的頭指針  
  12.     ③ ListNode *類型的指針變量p表示它是指向某一節(jié)點(diǎn)的指針  

下面我們來(lái)看單鏈表的操作：創(chuàng)建節(jié)點(diǎn)、增加節(jié)點(diǎn)、刪除節(jié)點(diǎn)、查詢、修改。

1.創(chuàng)建節(jié)點(diǎn)：聲明一個(gè)節(jié)點(diǎn)并為其申請(qǐng)一段內(nèi)存空間，此節(jié)點(diǎn)有數(shù)據(jù)域和指針域。
  1. node = (struct List *)malloc(sizeof(struct List));  

2.增加節(jié)點(diǎn)：插入節(jié)點(diǎn)，分為頭插入、尾插入和非頭尾插入。
    ①. 在表頭插入節(jié)點(diǎn)，如圖

插入頭節(jié)點(diǎn)的代碼如下：
  1. if(p == head)   /***其中p為鏈表中的某一節(jié)點(diǎn)***/  
  2. {  
  3.     struct list *s = NULL;  
  4.     s = (struct list *)malloc(sizeof(struct list)); /***申請(qǐng)空間***/  
  5.     s->DataNumber = data;    /***為節(jié)點(diǎn)s的數(shù)據(jù)域賦值***/  
  6.   
  7.     /***將節(jié)點(diǎn)s插入表頭***/  
  8.     s->next = p;  
  9.     head = s;  
  10. }  

  ②. 在表尾插入節(jié)點(diǎn)，如圖

插入尾節(jié)點(diǎn)的代碼如下：
  1. if(p->next == NULL)  /***其中p為鏈表中的某一節(jié)點(diǎn)***/  
  2. {  
  3.     struct list *s = NULL;  
  4.     s = (struct list *)malloc(sizeof(struct list)); /***申請(qǐng)空間***/  
  5.     s->DataNumber = data;    /***為節(jié)點(diǎn)s的數(shù)據(jù)域賦值***/  
  6.       
  7.     /***將節(jié)點(diǎn)s插入表尾***/  
  8.     p->next = s;  
  9.     s->next = NULL;  
  10. }  

  ③. 在表中插入非頭尾節(jié)點(diǎn)，如圖

插入非頭尾節(jié)點(diǎn)的代碼如下：
  1. struct list *s = NULL;  
  2. s = (struct list *)malloc(sizeof(struct list)); /***申請(qǐng)空間***/  
  3. s->DataNumber = data;    /***為節(jié)點(diǎn)s的數(shù)據(jù)域賦值***/  
  4.   
  5. /***將節(jié)點(diǎn)s插入表中***/  
  6. s->next = p; /***其中p為鏈表中的某一節(jié)點(diǎn)***/  
  7. q->next = s; /***其中q為鏈表中p節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)***/  

3.刪除節(jié)點(diǎn)：分為刪除頭結(jié)點(diǎn)，刪除尾節(jié)點(diǎn)，刪除頭尾節(jié)點(diǎn)。

①. 刪除表頭結(jié)點(diǎn)，如圖

刪除頭結(jié)點(diǎn)的代碼如下：
  1. if(p == head)   /***p指向鏈表中的某一節(jié)點(diǎn)***/  
  2. {  
  3.     head = p->next;  
  4. }  

②. 刪除表尾節(jié)點(diǎn)，如圖

附注說(shuō)明：上圖中刪完尾節(jié)點(diǎn)之后，新鏈表的尾節(jié)點(diǎn)下標(biāo)應(yīng)為n-1。不過(guò)由于作圖時(shí)只做了尾節(jié)點(diǎn)，故用圖中的n2節(jié)點(diǎn)代替。

刪除尾節(jié)點(diǎn)的代碼如下：

  1. if(p->next == NULL)  /***p指向鏈表中的某一節(jié)點(diǎn)***/  
  2. {  
  3.     q->next = NULL;  /***q指向鏈表中的p節(jié)點(diǎn)的前一節(jié)點(diǎn)**/  
  4. }  

③. 刪除非頭尾節(jié)點(diǎn)，如圖

刪除非頭尾節(jié)點(diǎn)的代碼如下：

  1. q->next = p->next;    /***p指向鏈表中的某一節(jié)點(diǎn)，q指向鏈表中的p節(jié)點(diǎn)的前一節(jié)點(diǎn)***/  

4.查詢節(jié)點(diǎn)：在鏈表中找到你想要找的那個(gè)節(jié)點(diǎn)。此操作是根據(jù)數(shù)據(jù)域的內(nèi)容來(lái)完成的。查詢只能從表頭開(kāi)始，當(dāng)要找的節(jié)點(diǎn)的數(shù)據(jù)域內(nèi)容與當(dāng)前不相符時(shí)，只需讓當(dāng)前節(jié)點(diǎn)指向下一結(jié)點(diǎn)即可，如此這樣，直到找到那個(gè)節(jié)點(diǎn)。

附注：此操作就不在這用圖和代碼說(shuō)明了。


5.修改節(jié)點(diǎn)：修改某個(gè)節(jié)點(diǎn)數(shù)據(jù)域的內(nèi)容。首先查詢到這個(gè)節(jié)點(diǎn)，然后對(duì)這個(gè)節(jié)點(diǎn)數(shù)據(jù)域的內(nèi)容進(jìn)行修改。
附注：同上


       ok，鏈表的幾種操作介紹完了，接下來(lái)我們來(lái)總結(jié)一下鏈表的幾個(gè)特點(diǎn)。

       鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：
              1.易插入，易刪除。不用移動(dòng)節(jié)點(diǎn)，只需改變節(jié)點(diǎn)中指針的指向。
              2.查詢速度慢：每進(jìn)行一次查詢，都要從表頭開(kāi)始，速度慢，效率低。

擴(kuò)展閱讀
鏈表：http://public.whut.edu.cn/comptsci/web/data/512.htm


第二節(jié) 樹(shù)形存儲(chǔ)結(jié)構(gòu)

       所謂樹(shù)形存儲(chǔ)結(jié)構(gòu)，就是數(shù)據(jù)元素與元素之間存在著一對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu)。在樹(shù)形存儲(chǔ)結(jié)構(gòu)中，樹(shù)的根節(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余的每個(gè)節(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)，除葉子結(jié)點(diǎn)沒(méi)有后續(xù)節(jié)點(diǎn)外，其他節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)可以有一個(gè)或者多個(gè)。

如下圖就是一棵簡(jiǎn)單的樹(shù)形結(jié)構(gòu)：

       說(shuō)到樹(shù)形結(jié)構(gòu)，我們最先想到的就是二叉樹(shù)。我們常常利用二叉樹(shù)這種結(jié)構(gòu)來(lái)解決一些算法方面的問(wèn)題，比如堆排序、二分檢索等。所以在樹(shù)形結(jié)構(gòu)這節(jié)我只重點(diǎn)詳解二叉樹(shù)結(jié)構(gòu)。那么二叉樹(shù)到底是怎樣的呢？如下圖就是一顆簡(jiǎn)單的二叉樹(shù)：

附注：有關(guān)樹(shù)的概念以及一些性質(zhì)在此不做解釋，有意者請(qǐng)到百科一覽。


二叉樹(shù)的類型描述如下：

  1. typedef struct tree  
  2. {  
  3.     char data;  
  4.     struct tree * lchild, * rchild; /***左右孩子指針***/  
  5. }tree;  

二叉樹(shù)的操作：創(chuàng)建節(jié)二叉樹(shù)，創(chuàng)建節(jié)點(diǎn)，遍歷二叉樹(shù)，求二叉樹(shù)的深度。

1.創(chuàng)建二叉樹(shù)：聲明一棵樹(shù)并為其申請(qǐng)存儲(chǔ)空間。

  1. struct tree * T = NULL;  
  2. T = (struct tree *)malloc(sizeof(struct tree));  

2.創(chuàng)建節(jié)點(diǎn)：除根節(jié)點(diǎn)之外，二叉樹(shù)的節(jié)點(diǎn)有左右節(jié)點(diǎn)之分。

創(chuàng)建節(jié)點(diǎn)的代碼如下：

  1. struct tree * createTree()  
  2. {  
  3.     char NodeData;  
  4.     scanf(" %c", &NodeData);  
  5.     if(NodeData == '#')  
  6.         return NULL;  
  7.     else  
  8.     {  
  9.         struct tree * T = NULL;  
  10.         T = (struct tree *)malloc(sizeof(struct tree));  
  11.         T->data = NodeData;  
  12.         T->lchild = createTree();  
  13.         T->rchild = createTree();  
  14.         return T;  
  15.     }  
  16. }  

3.遍歷二叉樹(shù)：分為先序遍歷、中序遍歷、后續(xù)遍歷。

    ①.先序遍歷：若二叉樹(shù)非空，則依次執(zhí)行如下操作：
                    (1) 訪問(wèn)根結(jié)點(diǎn)；
                    (2) 遍歷左子樹(shù)；
                    (3) 遍歷右子樹(shù)。

如圖：

先序遍歷的代碼如下：

  1. void PreTravser(struct tree * T)  
  2. {  
  3.     if(T == NULL)  
  4.         return;  
  5.     else  
  6.     {  
  7.         printf("%c",T->data);  
  8.         PreTravser(T->lchild);  
  9.         PreTravser(T->rchild);  
  10.     }  
  11. }  

②.中序遍歷：若二叉樹(shù)非空，則依次執(zhí)行如下操作：
                 (1)遍歷左子樹(shù)；
                 (2)訪問(wèn)根結(jié)點(diǎn)；
                 (3)遍歷右子樹(shù)。
如圖：

中序遍歷的代碼如下：

  1. void MidTravser(struct tree * T)  
  2. {  
  3.     if(!T)  
  4.     {  
  5.         return;  
  6.     }  
  7.     else  
  8.     {  
  9.         MidTravser(T->lchild);  
  10.         printf("%c",T->data);  
  11.         MidTravser(T->rchild);  
  12.     }  
  13. }  

③.后續(xù)遍歷：若二叉樹(shù)非空，則依次執(zhí)行如下操作：
                 (1)遍歷左子樹(shù)；
                 (2)遍歷右子樹(shù)；
                 (3)訪問(wèn)根結(jié)點(diǎn)。
如圖：

后續(xù)遍歷的代碼如下：
  1. void PostTravser(struct tree * T)  
  2. {  
  3.     if(!T)  
  4.         return;  
  5.     else  
  6.     {  
  7.         PostTravser(T->lchild);  
  8.         PostTravser(T->rchild);  
  9.         printf("%c->",T->data);  
  10.     }  
  11. }  

4.求二叉樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)層次的最大值，也稱高度。
二叉樹(shù)的深度表示如下圖：

求二叉樹(shù)深度的代碼如下：
  1. int treeDeepth(struct tree * T)  
  2. {  
  3.     int i, j;  
  4.     if(!T)  
  5.         return 0;  
  6.     else  
  7.     {  
  8.         if(T->lchild)  
  9.             i = treeDeepth(T->lchild);  
  10.         else  
  11.             i = 0;  
  12.           
  13.         if(T->rchild)  
  14.             j = treeDeepth(T->rchild);  
  15.         else  
  16.             j = 0;  
  17.     }  
  18.     return i > j? i+1:j+1;   
  19. }  

好了，二叉樹(shù)的幾種操作介紹完了。

拓展閱讀
二叉樹(shù)：http://student.zjzk.cn/course_ware/data_structure/web/DOWNLOAD/%CA%FD%BE%DD%BD%E1%B9%B9%D3%EB%CB%E3%B7%A82.htm
赫夫曼編碼：http://blog.csdn.net/fengchaokobe/article/details/6969217

第三節(jié) 圖型存儲(chǔ)結(jié)構(gòu)
       所謂圖形結(jié)構(gòu)，就是數(shù)據(jù)元素與元素之間的關(guān)系是任意的，任意兩個(gè)元素之間均可相關(guān)，即每個(gè)節(jié)點(diǎn)可能有多個(gè)前驅(qū)結(jié)點(diǎn)和多個(gè)后繼結(jié)點(diǎn)，因此圖形結(jié)構(gòu)的存儲(chǔ)一般是采用鏈接的方式。圖分為有向圖和無(wú)向圖兩種結(jié)構(gòu)，如下圖


       通過(guò)圖，我們可以判斷兩個(gè)點(diǎn)之間是不是具有連通性；通過(guò)圖，我們還可以計(jì)算兩個(gè)點(diǎn)之間的最小距離是多少；通過(guò)圖，我們還可以根據(jù)不同的要求，尋找不同的合適路徑。

1.圖的結(jié)構(gòu)有好幾種，在實(shí)際應(yīng)用中需根據(jù)具體的情況選擇合適的結(jié)點(diǎn)結(jié)構(gòu)和表結(jié)構(gòu)。常用的有數(shù)組結(jié)構(gòu)、鄰接表。
   ①.數(shù)組結(jié)構(gòu)
   數(shù)組結(jié)構(gòu)的類型描述如下：
  1. typedef char VertexType;    /***頂點(diǎn)類型***/  
  2. typedef int EdgeType;   /***邊權(quán)值類型***/  
  3. #define maxvex 100  /***頂點(diǎn)的最大個(gè)數(shù)***/   
  4.   
  5. typedef struct  
  6. {  
  7.     VertexType vexs[maxvex];    /***頂點(diǎn)個(gè)數(shù)***/  
  8.     EdgeType arc[maxvex][maxvex];   /***兩頂點(diǎn)構(gòu)成邊的權(quán)值***/  
  9. }Mgraph;  
附注：當(dāng)前圖為無(wú)向圖時(shí)，圖中某兩個(gè)頂點(diǎn)VA和VB構(gòu)成一條邊時(shí)，其權(quán)值可表示為EdgeType arc[VA][VB]；當(dāng)前圖為有向圖時(shí)，圖中某兩個(gè)頂點(diǎn)VA和VB構(gòu)成一條邊時(shí)，并且是由VA指向VB，其權(quán)值可表示為EdgeType arc[VA][VB]，如果是由VB指向VA，其權(quán)值可表示為EdgeType arc[VB][VA]。

   ②.鄰接表
   鄰接表的類型描述如下：
  1. typedef char VertexType;   // 頂點(diǎn)類型   
  2. typedef int EdgeType;     //邊權(quán)值類型   
  3.   
  4. typedef struct EdgeNode  //邊表節(jié)點(diǎn)   
  5. {  
  6.    int adjvex;              //鄰接點(diǎn)域，存儲(chǔ)該頂點(diǎn)對(duì)應(yīng)的下標(biāo)   
  7.    EdgeType weight;         //用于存儲(chǔ)權(quán)值   
  8.    struct EdgeNode *next;   //鏈域,指向下一個(gè)鄰接點(diǎn)   
  9. }EdgeNode;  
  10.   
  11. typedef struct VertexNode   //頂點(diǎn)表節(jié)點(diǎn)   
  12. {  
  13.    VertexType data;       //頂點(diǎn)域，存儲(chǔ)頂點(diǎn)信息   
  14.    EdgeNode * firstedge;  //邊表頭指針   
  15. }VertexNode,AdjList[MAXVEX];  
  16.   
  17. typedef struct  
  18. {  
  19.     AdjList adjList;  
  20.     int numVertexes,numEdges;   //圖當(dāng)前頂點(diǎn)數(shù)和邊數(shù)   
  21. }GraphAdjList;  

2.圖的遍歷：從圖中的某一節(jié)點(diǎn)出發(fā)訪問(wèn)圖中的其余節(jié)點(diǎn)，且使每一節(jié)點(diǎn)僅被訪問(wèn)一次。圖的遍歷算法是求解圖的連通性問(wèn)題、拓?fù)渑判蚝颓舐窂降人惴ǖ幕A(chǔ)。圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷，且它們對(duì)無(wú)向圖和有向圖均適用。

   ①. 深度優(yōu)先遍歷
   定義說(shuō)明：假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò)。在G中任選一頂點(diǎn)V為初始出發(fā)點(diǎn)，則深度優(yōu)先遍歷可定義如下：首先訪問(wèn)出發(fā)點(diǎn)V，并將其標(biāo)記為已訪問(wèn)過(guò)；然后依次從V出發(fā)搜索v的每個(gè)鄰接點(diǎn)W。若W未曾訪問(wèn)過(guò)，則以W為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)V有路徑相通的頂點(diǎn)(亦稱為從源點(diǎn)可達(dá)的頂點(diǎn))均已被訪問(wèn)為止。若此時(shí)圖中仍有未訪問(wèn)的頂點(diǎn)，則另選一個(gè)尚未訪問(wèn)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)均已被訪問(wèn)為止。

深度遍歷過(guò)程如下圖：


②. 廣度優(yōu)先遍歷
   定義說(shuō)明：假設(shè)從圖中某頂點(diǎn)V出發(fā)，在訪問(wèn)了V之后一次訪問(wèn)V的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中還有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。換句話說(shuō)，廣度優(yōu)先遍歷圖的過(guò)程是以V為起點(diǎn)，由近至遠(yuǎn)，依次訪問(wèn)和V有路徑相同且路徑長(zhǎng)度為1,2，...的頂點(diǎn)。

廣度遍歷過(guò)程如下圖：


擴(kuò)展閱讀
最小生成樹(shù)：Prim算法，Kruskal算法
最短路徑：Dijkstra算法，F(xiàn)loyd算法

第四節(jié) 結(jié)束語(yǔ)
       想想，寫寫，畫畫......
原文地址：http://blog.csdn.net/fengchaokobe/article/details/7416547
作者：csh624366188 發(fā)表于2012-4-9 22:54:15 原文鏈接
閱讀：126 評(píng)論：2 查看評(píng)論