【文章內容簡介】 pMNode = new numST。 pMNodenum = 12。 pMNodenext = NULL。 insert(pMHead, pMNode)。 // 調用 insert函數將結點 pMNode插入鏈表 print(pMHead)。 // 調用 print函數，輸出鏈表內容 // 與 new 對應，用 delete 釋放空間 …… } // 主函數結束 程序設計基礎 第 11章 鏈表 定義兩個 numST 型結構指針 *pMHead， *pMNode，并初始化 pMHead 和 pMNode 為 NULL。 分配 3 個 numST 結構的內存空間，用于構造鏈表 （ 1） pMHead = new numST。 （ 2） pMHeadnext = new numST。 （ 3） pMHeadnextnext = new numST。 先看主函數 pMHead 這 3 個 numST 結構的內存空間如上圖所示。 pMHeadnext pMHeadnextnext 程序設計基礎 第 11章 鏈表 下面用賦值語句往這 3 個空間中放 num 數據。最后的一個結點為隊尾，在其指針域存放 NULL。 （ 4） pMHeadnum=5。 （ 5） pMHeadnextnum=10。 （ 6） pMHeadnextnextnum=15。 （ 7） pMHeadnextnextnext=NULL。 做了這 4條之后形成了一條鏈表如下： 5 pMHead 10 15 NULL 該鏈表的頭結點由 pMHead 所指向。 程序設計基礎 第 11章 鏈表 構造一個結點 pMNode，在 pMNode 結點的數據域放 12，再插入鏈表 （ 1） pMNode = new numST。 （ 2） pMNodenum = 12。 （ 3） pMNodenext = NULL。 調用 insert 函數來插入 pMNode 結點。 語句為 insert(pMHead, pMNode)。 意思是以將 pMNode 插入到以 pMHead 為隊頭的鏈表中。但這里在調用時，用 pMHead作為實參，傳遞的是引用，而非傳值。所以在函數體內對pHead的修改，就等價于對 pMHead的操作。 程序設計基礎 第 11章 鏈表 這里要講傳值和傳引用的區(qū)別 （ 1）如果是傳值調用 主程序中的調用語句為 insert(pMHead, pMNode)。 被調用函數為 void insert( munST *pHead, numST*pNode)。 pMHead pMNode 實際參數 形式參數 pNode pHead 程序設計基礎 第 11章 鏈表 當著實際參數 pMHead 賦給了形式參數 pHead之后， pHead 就指向了已經存在了的鏈表，見下圖。 5 10 15 NULL pHead 這時原來的主函數中的頭指針 pMHead 就不再起作用了，而是子函數中的 pHead 起作用。假如現在 pNode 中的結點數據為 4 小于 5，應該將 pNode 插入到 pHead 所指向的結點前，如下圖 pMHead 程序設計基礎 第 11章 鏈表 5 pMHead 10 15 NULL pHead 被調用函數無法改變主函數的 pMHead。雖然在子函數內 pHead 被修改，指向了含有四個結點的鏈表頭，但當函數返回后，主函數中的 pMHead 仍然指向鏈表后面的三個結點，新插入的結點并沒有包含進去。所以要想將新的插入到最前面的結點包含進去，就必須用傳址或傳引用。 4 pHead 程序設計基礎 第 11章 鏈表 （ 2）如果是傳引用調用 主程序中的調用語句為 insert(pMHead, pMNode)。 被調用函數為 void insert(munST *amp。pHead, numST *pNode)。 先看 numST *amp。pHead 是說聲明 pHead 為 numST 結構指針的引用，即 pHead 是“指向 numST 結構的指針”的引用。 程序設計基礎 第 11章 鏈表 主程序中的實參為鏈表頭指針 pMHead 的引用，傳給被調用函數的 pHead，在子函數中對 pHead 的操作就等價于對 pMHead 的操作。 pMHead (pHead) *pMHead 程序設計基礎 第 11章 鏈表 在主函數中 pMHead為頭指針，在被調用的子函數中 pHead 為頭指針。 pHead 和 pMHead 是同一個單元，只不過分別叫不同的名罷了。當然在子函數中無論插入什么結點都會讓 pHead 指向鏈表的頭。自然返回到主函數后， pMHead也會是指向同一鏈表的頭。 從這個例子中讀者可以領會到傳引用調用與傳值調用的區(qū)別。 這樣在子函數做插入結點的過程中，頭指針的改變也能反映到主函數中來。調用 print 函數，從 pMHead 開始輸出整個鏈表的內容。 程序設計基礎 第 11章 鏈表 下面我們來研究 insert 函數 前提是主程序已將兩個實參傳給了 insert 函數的兩個形參，這時 pHead 是 pMHead 的引用，指向鏈表頭， pNode 所指向的就是待插入的一個結點。事先定義兩個結構指針 q 和 r。 程序設計基礎 第 11章 鏈表 第一種情況： pHead==NULL 說明主程序傳過來的頭指針為空，即鏈表為空，一個結點都不存在。這時待插入的 pNode 結點就是鏈表中的第一個結點。只要執(zhí)行如下兩條語句即可 pHead = pNode。 // 將表頭指針指向 p結點 return。 // 返回主程序 在主程序中必然頭指針 pMHead 指向 pMNode 結點。 程序設計基礎 第 11章 鏈表 第二種情況： pNode 結點的 num 值小于等于鏈表頭結點的 num 值，即 pNodenum = pHeadnum 這時要將 pNode 結點插入到頭結點的前面，要執(zhí)行如下三條語句 pNodenext=pHead。 // 在 pNode 結點的指針域 // 賦以頭結點的地址值 pHead=pNode。 // 將頭結點指針 pHead // 指向 pNode 結點 return。 // 返回主程序 程序設計基礎 第 11章 鏈表 這種情況如下圖（演示） 5 pHead 10 4 15 NULL pNode NULL 程序設計基礎 第 11章 鏈表 第三種情況： 前兩種情況，無論遇到哪一種，都會返回主程序。只要不返回就是這第三種情況，即 pNode 結點的 num 大于等于頭指針所指向的結點的 num 值。這時肯定地說 pNode 結點要插入到頭結點之后，究竟要插到哪里需要找到應該插入的位置。我們設指針 r 和指針 q，分別指向相鄰的兩個結點， r 在前 q 在后。 程序設計基礎 第 11章 鏈表 當著滿足 rnum pNodenum = qnum 時， pNode 就插在 r 與 q 之間。（演示） 5 pHead 10 12 pNode 15 NULL NULL q r 程序設計基礎 第 11章 鏈表 一開始讓 r=pHead，讓 q=pHeadnext (1) 當指針 q 為空指針時，說明原鏈表中只有一個結點，即 r 指向的結點，這時只要將 pNode 結點接在 r 之后即可。執(zhí)行 rnext=pNode。 pNodenext=q。 程序設計基礎 第 11章 鏈表 (2) 如果 q!=NULL，說明起碼有兩個結點在鏈表中，接著要判 pNode 結點的 num 值是否大于 q 結點的 num 值。如果是大，則說明 pNode 應插在 q 之后而不是之前，這時讓 r 和 q 指針同時后移一步，即 r=q。 q=qnext。 程序設計基礎 第 11章 鏈表 執(zhí)行 (2) 在 q!=NULL 的情況下，如果 pNodenum = qnum 說明這時找到了正確的插入位置，退出 while 循環(huán)，將 pNode 結點插入到 r 后， q 前即可。使用的語句為 在下面我們畫出該算法的結構框圖 rnext=pNode。 pNodenext=q。 程序設計基礎 第 11章 鏈表 pH e ad== N U L L T F T F p N ode nu m =pHea d nu m 第 2 種情況： p N ode 結點中的數據小于頭結點中的數據。將 p N ode 結點插入到表頭前，然后返回主函數。即 p N ode nex t = pH e ad。 pH e ad=p N ode 。 r e t u r n 。 第 3 種情況： p N ode 結點中的數據大于等于頭結點中的數據。定義兩個指針 r 和 q ，讓 r 指向表頭，讓 q 指向相鄰的下一個結點，即 r= pH e ad。 q= pH e ad nex t 。 進入循環(huán)查找 該 插入的位置。 第 1 種情況：鏈表為空。讓鏈表 頭 pH e ad指向p N ode 結點，之后返回主函數。即 pH e ad= p N ode 。 r e t u r n 。 T F p N ode nu m q nu m w