C語言程序設(shè)計課件第13章

第13章Ｃ語言的綜合應(yīng)用[Return]本章學(xué)習(xí)目標(biāo)理解數(shù)據(jù)結(jié)構(gòu)與算法的基本概念及其在C語言程序設(shè)計中的重要地位。掌握利用C語言實現(xiàn)在順序表和鏈表兩種最基本的數(shù)據(jù)結(jié)構(gòu)上的插入、刪除等常見操作的方法。能夠綜合應(yīng)用所學(xué)的C語言的基本語法知識、基本程序設(shè)計方法以及數(shù)據(jù)結(jié)構(gòu)和算法的基本知識，為解決實際應(yīng)用問題進(jìn)行C程序設(shè)計。13.1數(shù)據(jù)結(jié)構(gòu)與算法的概念

13.2順序表的插入與刪除

13.3鏈表的插入與刪除13.4繪制圖形實例（略）

13.5綜合應(yīng)用案例分析（略）

13.1數(shù)據(jù)結(jié)構(gòu)與算法的概念

早在1976年，瑞士著名科學(xué)家尼克來·沃思（Niklauswirth）就提出了這樣一個公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序從前面章節(jié)的學(xué)習(xí)我們已經(jīng)了解到，一個程序基本包括兩個方面的內(nèi)容：對數(shù)據(jù)的描述和對操作的描述。對數(shù)據(jù)的描述即是構(gòu)造一個合理的數(shù)據(jù)結(jié)構(gòu)；對操作的描述即是算法的實現(xiàn)。所以說，程序設(shè)計其實就是為求解問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計一個好的算法。13.1.1數(shù)據(jù)結(jié)構(gòu)1．什么是數(shù)據(jù)結(jié)構(gòu)？

一般來說，計算機處理的問題可以分為兩類：數(shù)值問題和非數(shù)值問題。對數(shù)值問題的求解一般是分析問題后將各個量之間的關(guān)系抽象成一定的數(shù)學(xué)模型。

對于非數(shù)值問題的求解往往無法用數(shù)學(xué)方程來描述，而需要用到下面介紹的線性結(jié)構(gòu)、樹結(jié)構(gòu)或圖結(jié)構(gòu)進(jìn)行描述。（1）線性結(jié)構(gòu)

表13-1是某學(xué)校的學(xué)生檔案表，要利用計算機進(jìn)行學(xué)生檔案管理，一般要實現(xiàn)如下功能：瀏覽、查詢、插入、刪除、修改、統(tǒng)計等。【例13-2】學(xué)生檔案管理。

要解決這個問題，只用若干個簡單變量顯然是難以描述清楚這么多的數(shù)據(jù)，數(shù)據(jù)之間的關(guān)系也不能用方程式表示。分析表格后發(fā)現(xiàn)，如果把每一行看成一個記錄并稱作一個結(jié)點，則表中每個結(jié)點有且只有一個前驅(qū)結(jié)點（第一個結(jié)點除外），有且只有一個后繼結(jié)點（最后一個結(jié)點除外）。結(jié)點與結(jié)點之間的關(guān)系是一種簡單的一對一聯(lián)系，即線性關(guān)系。我們把具有這種特點的數(shù)據(jù)結(jié)構(gòu)叫做線性結(jié)構(gòu)。

線性結(jié)構(gòu)的結(jié)點之間按順序排列，如圖13-1所示。讀者不難發(fā)現(xiàn)：表中結(jié)點是按學(xué)號從小到大排列的，并且學(xué)號是標(biāo)識結(jié)點唯一性（區(qū)分不同結(jié)點）的數(shù)據(jù)項，即關(guān)鍵項，也稱關(guān)鍵字。

12345圖13-1線性結(jié)構(gòu)示意圖線性結(jié)構(gòu)具有如下特點：存在唯一的“第一個”結(jié)點。存在唯一的“最后一個”結(jié)點。除第一個結(jié)點外，每一個結(jié)點都只有一個前驅(qū)結(jié)點。除最后一個結(jié)點外，每一個結(jié)點都只有一個后繼結(jié)點。（2）樹結(jié)構(gòu)

【例13-3】某企業(yè)的人事組織關(guān)系。…企業(yè)銷售部生產(chǎn)部后勤部員工2員工n員工1…員工2員工n員工1……圖13-2某企業(yè)的人事組織關(guān)系

圖13-2是某企業(yè)的人事組織關(guān)系圖，它清晰地描述這個企業(yè)有幾個部門，每個部門有幾個員工。它像一棵倒掛的樹，頂部的樹根結(jié)點沒有前驅(qū)結(jié)點，其他結(jié)點有且只有一個前驅(qū)結(jié)點，每個結(jié)點可以有多個后繼結(jié)點（葉子結(jié)點可看作有0個后繼結(jié)點）。這種結(jié)構(gòu)的特點是結(jié)點之間具有一對多的聯(lián)系，即層次關(guān)系。我們把具有這種特點的數(shù)據(jù)結(jié)構(gòu)叫做樹結(jié)構(gòu)。圖13-3樹結(jié)構(gòu)示意圖ABCDEFGHI

像家族的家譜、學(xué)校里的教師學(xué)生關(guān)系等都具有這種層次關(guān)系，描述這種層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)都可采用樹結(jié)構(gòu)。樹結(jié)構(gòu)的示意圖如圖13-3所示。A為樹根，稱作根結(jié)點；D、E、F、G、H、I為葉子結(jié)點；B和C為分支結(jié)點。A下面有三棵子樹，B、C、D分別為這三棵子樹的根結(jié)點。A是B、C、D的雙親結(jié)點，B是E、F的雙親結(jié)點；B、C、D是A的孩子結(jié)點，E、F是B的孩子結(jié)點。樹結(jié)構(gòu)具有如下特點：存在唯一的根結(jié)點，根結(jié)點沒有前驅(qū)結(jié)點。除根結(jié)點外，每一個結(jié)點都只有一個前驅(qū)結(jié)點。每一個結(jié)點都可以有0個或多個后繼結(jié)點。

顯然，樹結(jié)構(gòu)是一種非線性結(jié)構(gòu)。而線性結(jié)構(gòu)可以看作樹結(jié)構(gòu)的一種特例：每個結(jié)點都只有一個后繼結(jié)點的樹。（3）圖結(jié)構(gòu)

【例13-4】求解城市之間最小造價的通訊網(wǎng)絡(luò)問題。已知任意兩個城市之間建設(shè)通訊線路的費用，要求選定若干通訊線路建成一個通訊網(wǎng)絡(luò)，使得各個城市之間都能直接或間接相通，而造價最低。如圖13-4所示。364城市E城市C城市D城市B城市市A城市B城市D城市C城市Ea)通訊線路費用網(wǎng)絡(luò)圖b)最小造價通訊網(wǎng)絡(luò)圖圖13-4用圖描述求解最小造價通訊網(wǎng)絡(luò)問題

圖中圓圈表示一個城市結(jié)點，連線表示兩個城市之間的通訊線路，連線邊上的數(shù)值表示費用。圖中每個結(jié)點可以有任意多個前驅(qū)結(jié)點和后繼結(jié)點。這種結(jié)構(gòu)的特點是結(jié)點之間具有多對多的聯(lián)系，即網(wǎng)絡(luò)關(guān)系。我們把具有這種特點的數(shù)據(jù)結(jié)構(gòu)叫做叫圖結(jié)構(gòu)。

圖結(jié)構(gòu)在日常生活中的應(yīng)用非常廣泛，常見的交通圖、電路圖、結(jié)構(gòu)圖、流程圖等，都具有這種圖結(jié)構(gòu)。圖結(jié)構(gòu)的示意圖如圖13-5所示。圖13-5圖結(jié)構(gòu)示意圖ABCDEF

圖結(jié)構(gòu)的特點是：任何結(jié)點可以有若干個前驅(qū)結(jié)點，也可以有若干個后繼結(jié)點。圖是一種復(fù)雜的非線性結(jié)構(gòu)，樹結(jié)構(gòu)和線性結(jié)構(gòu)都可以看作圖結(jié)構(gòu)的特例。實際應(yīng)用問題中所有的元素之間的邏輯關(guān)系都可以歸為線性關(guān)系、層次關(guān)系或網(wǎng)絡(luò)關(guān)系，解決問題采用的數(shù)據(jù)結(jié)構(gòu)都可以由這三種關(guān)系相對應(yīng)的線性結(jié)構(gòu)、樹結(jié)構(gòu)或圖結(jié)構(gòu)派生出來。

“數(shù)據(jù)結(jié)構(gòu)”就是研究在程序設(shè)計中，如何對非數(shù)值計算的應(yīng)用問題進(jìn)行分析，抽象出各種數(shù)據(jù)之間的邏輯關(guān)系，然后如何將數(shù)據(jù)及其關(guān)系進(jìn)行存儲，并實現(xiàn)各種操作的一門學(xué)科。2．?dāng)?shù)據(jù)結(jié)構(gòu)的常用術(shù)語

數(shù)據(jù)：各種事物在計算機中的符號表示。數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計算機中作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)項：數(shù)據(jù)的不可分割、含有獨立意義的最小單位。數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)聯(lián)方式。常見的有四種：集合結(jié)構(gòu)（有限個數(shù)據(jù)元素隨意組合在一起構(gòu)成的一個集合）、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)：數(shù)據(jù)在計算機中的存放方式，又叫存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲實現(xiàn)。通常有順序、鏈接、索引、散列等存儲形式。數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)的組織形式，包括兩個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。但通常所說的數(shù)據(jù)結(jié)構(gòu)一般是指數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)類型：對數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)以及允許施加的操作的一種描述。13.1.2算法

算法是解決問題的方法或步驟。算法在程序設(shè)計中有著舉足輕重的地位，程序就是算法在計算機中的實現(xiàn)。（1）算法的特性

輸入：一個算法有零個或多個輸入；輸出：一個算法有一個或多個輸出。有窮性：一個算法必須由有限步組成，即算法必須可以終止，不能進(jìn)入死循環(huán)。確定性：算法執(zhí)行的每一步都必須有確定的含義，不能有二義性?？尚行裕核惴ǖ拿恳徊蕉急仨毷乔袑嵖尚械模丛瓌t上可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。算法具有以下特性：【例13-5】歐幾里德算法。給定兩個正整數(shù)p和q，如何求出p和q的最大公約數(shù)g？

著名的幾何學(xué)家歐幾里德設(shè)計了一個巧妙的求解方法，用自然語言描述如下：

第一步：輸入p和q。

第二步：如果p小于q,則交換p和q。

第三步：令r是p除以q的余數(shù)。

第四步：如果r等于0，則令g=q和輸出g并終止程序；否則令p=q、q=r，并轉(zhuǎn)向第三步。

這個算法有兩個輸入：p和q；有一個輸出：g；算法是可行的：由若干個基本操作如交換兩個數(shù)、相除求余數(shù)、比較大小、判斷相等、控制轉(zhuǎn)向等組成；算法是有窮的：交替執(zhí)行第三步和第四步，r總小于q，第四步轉(zhuǎn)第三步后p和q不斷減少，若干步后一定終止；算法是確定的：每一步都有明確的操作。（2）算法的描述

描述算法的工具有很多，常用的有自然語言、傳統(tǒng)流程圖、N-S圖、偽代碼等。在前面第1章的1.5.1節(jié)已簡單介紹過自然語言和傳統(tǒng)流程圖描述方法，下面著重介紹比傳統(tǒng)流程圖更加適合于描述結(jié)構(gòu)化程序設(shè)計算法的N-S圖。

N-S圖是一種符合結(jié)構(gòu)化原則的圖形算法描述工具。在N-S圖中，去掉了傳統(tǒng)流程圖中容易引起麻煩的流程線，每一種基本結(jié)構(gòu)都可以用一個框描述，一個框內(nèi)可以包含其他從屬的框，全部算法都寫在一個矩形框內(nèi)。所以N-S圖也稱盒圖。

下面介紹三種基本結(jié)構(gòu)的N-S圖。順序結(jié)構(gòu)：圖13-6是順序結(jié)構(gòu)的N-S圖，圖中的模塊S1、S2、S3是按順序執(zhí)行的。S1S2S3圖13-6順序結(jié)構(gòu)的N-S圖選擇結(jié)構(gòu)：圖13-7是兩個分支的選擇結(jié)構(gòu)的N-S圖，當(dāng)條件滿足時執(zhí)行模塊S1，當(dāng)條件不滿足時執(zhí)行模塊S2。圖13-8是多個分支的選擇結(jié)構(gòu)的N-S圖，根據(jù)條件的取值情況分別執(zhí)行相應(yīng)的模塊。滿足條件不滿足S1S2圖13-7選擇結(jié)構(gòu)的N-S圖情況1情況2情況n……S1S2Sn條件圖13-8多路分支選擇結(jié)構(gòu)的N-S圖循環(huán)結(jié)構(gòu)：圖13-9是當(dāng)型循環(huán)結(jié)構(gòu)的N-S圖，當(dāng)條件滿足時反復(fù)執(zhí)行模塊S，否則跳出循環(huán)。圖13-10是直到型循環(huán)結(jié)構(gòu)，首先執(zhí)行模塊S，然后判斷條件，若條件不滿足，則繼續(xù)執(zhí)行循環(huán)體（模塊S），直到條件滿足時跳出循環(huán)。WHILE條件S圖13-9順序結(jié)構(gòu)的N-S圖UNTIL條件S圖13-10順序結(jié)構(gòu)的N-S圖

以上三種基本結(jié)構(gòu)中的模塊S、S1、S2、或S3又可以是這三種基本結(jié)構(gòu)的任意組合。【例13-6】歐幾里德算法的N-S圖描述。用N-S圖描述【例13-5】中的歐幾里德算法如圖13-11所示。輸入p和q是否P<q交換p和q令r是p除以q的余數(shù)當(dāng)r不為0令g=q并輸出g,結(jié)束令p=q、q=r，并令r是p除以q的余數(shù)圖13-11歐幾里德算法的N-S圖（3）算法的評價

解決同一個問題，往往會有許多不同的算法。對算法進(jìn)行評價，目的是從解決同一問題的不同算法中選擇出較為合適的一種。一般從以下幾個方面評價一個算法：正確性：這是設(shè)計和評價一個算法的首要條件。一個正確的算法是指在合理的數(shù)據(jù)輸入下，能夠在有限的運行時間內(nèi)得出正確的結(jié)果。可讀性：是指一個算法供人們閱讀的容易程度?？勺x性好有助于理解和交流，便于維護(hù)與擴(kuò)展。健壯性：對非法輸入數(shù)據(jù)，算法也能適當(dāng)做出反應(yīng)或處理，而不導(dǎo)致錯誤結(jié)果。時間效率和空間效率：時間效率是指算法的執(zhí)行時間，時間短則效率高；空間效率是指算法執(zhí)行過程中占用存儲空間的大小，存儲需要越小，空間效率越高。時間效率和空間效率都與問題的規(guī)模有關(guān)。（4）算法的時間效率分析

一個算法的運行時間與機器本身的速度有關(guān)。但是一個算法所需要執(zhí)行的簡單操作的次數(shù)是與機器無關(guān)的。算法的簡單操作次數(shù)乘以機器執(zhí)行一次簡單操作所需時間即為算法運行時間。所以，我們只討論不依賴于機器的影響運行時間的另一個重要的因素——算法中進(jìn)行簡單操作的次數(shù)。

通常把算法中包含簡單操作次數(shù)的多少叫做算法的時間復(fù)雜度。一般地，一個算法的時間復(fù)雜度與問題的規(guī)模n（n一般指算法要處理的對象的個數(shù)）有關(guān)，可表示為n的一個函數(shù)T(n)。分析方法：重點分析算法中的循環(huán)語句，找出簡單操作次數(shù)與n的關(guān)系。

【例13-7】分析下面算法的時間復(fù)雜度。intlargest(int*array,intn){intx,i;for(i=0;i<n;i++)scanf(“d%”,&array[i]);/*重復(fù)執(zhí)行n次*/x=array[0];for(i=1;i<n;i++)if(array[i]>x)x=array[i];/*重復(fù)執(zhí)行n-1次*/returnx;}分析：重點考察兩個for循環(huán)語句。第一個for語句循環(huán)體中的基本輸入數(shù)據(jù)操作被重復(fù)執(zhí)行n次，第二個for語句循環(huán)體的比較大小操作被重復(fù)執(zhí)行n-1次，由于兩個for語句在同一層上，所以整個算法的時間復(fù)雜度可看作兩者相加，表示為： T(n)=n+n-1+KK為一個常數(shù)上式可以簡化為T(n)=C*n，C為常數(shù)。即該算法的時間復(fù)雜度隨規(guī)模n線性增長，記作O(n)?！纠?3-8】分析下面算法的時間復(fù)雜度。sum=0;for(i=1;i<=n;i++)/*外層循環(huán)n次*/for(j=1;j<=n;j++)/*內(nèi)層循環(huán)n次*/sum++;分析：本例中重復(fù)執(zhí)行的基本操作是sum的累加，以及循環(huán)變量i和j的累加，這是雙層的嵌套循環(huán)，基本操作的次數(shù)約為兩個for語句循環(huán)操作次數(shù)的相乘，即T(n)=C*n2，記作O（n2）。該算法的運行時間隨規(guī)模n成二次增長率。13.2順序表的插入與刪除13.2.1什么是順序表

從前面介紹我們知道，數(shù)據(jù)結(jié)構(gòu)分線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)又可以分為線性表、棧、隊列等。線性表是線性結(jié)構(gòu)中最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。

線性表可定義為：一個線性表是n個具有相同屬性的數(shù)據(jù)元素的有限序列。

表示為：（a1,a2,…,ai,ai+1,…，an）。

元素個數(shù)叫線性表長度，用n表示。n=0,表示線性表為空表，a1為表頭元素，an為表尾元素。例如：以下都是線性表的例子。例13-2中按學(xué)號排列的學(xué)生檔案表；L1=(25,38,49,50,60);L2=(‘a(chǎn)’,’b’,’c’,…,’z’);L3=(“BASIC”,”PASCAL”,”FORTRAN”,”COBOL”,”VC++”,”JAVA”);等等。

線性表只描述了數(shù)據(jù)之間具有線性的邏輯關(guān)系，要在計算機上實現(xiàn)對數(shù)據(jù)進(jìn)行操作處理還必須按一定的方式存儲數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系。每一種數(shù)據(jù)結(jié)構(gòu)都可以有多種存儲方式，常用的有順序存儲和鏈接存儲。順序表就是線性表的順序存儲結(jié)構(gòu)。具體可定義為：順序表就是用一組地址連續(xù)的存儲單元依次存放線性表的元素。

順序表是利用數(shù)組來實現(xiàn)。順序表的結(jié)構(gòu)示意圖如圖13-12所示。a1a2aiai+1…an……Loc(a1)Loc(ai)Loc(ai+1)圖13-12線性表的順序存儲結(jié)構(gòu)地址連續(xù)的一塊存儲空間地址數(shù)組的存放空間順序表具有如下特點：表中相鄰的元素ai,ai+1對應(yīng)存儲地址Loc(ai)和Loc(ai+1)也相鄰。即邏輯結(jié)構(gòu)上相鄰的元素在物理位置上也相鄰。表中任何元素的存儲位置可由公式唯一確定：Loc(ai)=Loc(a1)+(i-1)*b(1<=i<=n)

（b為一個元素占用的存儲單元個數(shù)）可隨機訪問表中任一元素。13.2.2順序表的插入和刪除

在數(shù)據(jù)結(jié)構(gòu)上的基本操作有初始化、插入、刪除、查找、定位等。限于篇幅這里只介紹最常用到的初始化、插入、刪除和遍歷操作。（1）順序表的數(shù)據(jù)類型描述

#defineDATATYPEint/*定義順序表中的數(shù)據(jù)元素類型*/#defineMAXSIZE100/*定義順序表的最大容量*/typedefstruct/*自定義類型*/{DATATYPEdatas[MAXSIZE];/*聲明存放線性表的數(shù)組*/

intsize;/*用于存放當(dāng)前順序表中的元素個數(shù)*/}LIST;想一想：順序表的結(jié)構(gòu)類型與9.3節(jié)介紹的結(jié)構(gòu)數(shù)組有何區(qū)別？（2）順序表的初始化

初始化順序表就是將它設(shè)置為一個空表，即將長度域size置0。voidinitlist(LIST*a){a->size=0;}（3）順序表的插入

插入操作是指在長度為n的線性表中第i（1<=i<=n）個元素之前插入一個元素x，使長度從n變?yōu)閚+1。算法的自然語言描述如下：①檢查表是否已滿，若是，則停止插入。②從插入位置i起，把它和后面所有位置上的元素均后移一位置。③把新元素寫入到空出的第i個位置上。④線性表長度增1。算法的實現(xiàn)如下：intinsert(LIST*a,DATATYPEx,inti)/*將新元素x插入在順序表a的第i（1<=i<=n）個元素的前面*/{intk;if(i<1||(i>a->size+1)||(a->size==MAXSIZE))/*若線性表滿或i超出范圍則停止插入并返回0*/{printf(“positionisoutofrangeorlistisfull!”);return0;}else{

for(k=a->size;k>=i;k--)a->datas[k]=a->datas[k-1];a->datas[i-1]=x;a->size++;return1;}}算法的時間復(fù)雜度分析：這個算法中，運行時間主要花在為空出插入位置所需的移動元素的次數(shù)。假定新元素插入的位置為下標(biāo)i，則元素的移動次數(shù)為n-i次（n為線性表的長度a.size）。在任意位置插入的幾率相同的條件下，平均需要移動n/2次，即移動線性表中一半的元素。時間復(fù)雜度為O(n)。（4）順序表的刪除

在順序表上刪除第i個元素的操作與插入操作一樣需要移動大量元素，需要將ai+1,ai+2,…，an按次序向前移動一個位置，并將表長度減1。

算法的實現(xiàn)如下：intdelete(LIST*a,inti)/*在順序表a中刪除第i個元素*/{intk;if(i<1||(i>a->size)||(a->size==0))/*若線性表空或i超出范圍則停止刪除并返回0*/{printf(“positionisofrangeorlistisempty!”);return0;}else{for(k=i;k<a->size;k++)a->datas[k-1]=a->datas[k];a->size--;return1;}}算法的時間復(fù)雜度分析：這個算法中，運行時間主要花在刪除元素后需要將刪除位置后的所有元素向前移動一個位置。在任意位置刪除的幾率相同的條件下，平均需要移動n/2次，即移動線性表中一半的元素。時間復(fù)雜度為O(n)。（5）順序表的遍歷

遍歷一個線性表就是從線性表的第一個元素起，按順序依次訪問或輸出每一個元素。voidtraverse(LIST*a){inti;for(i=0;i<a->size;i++)printf(“%d”,a->datas[i]);printf(“\n”);}【例13-9】從鍵盤輸入10個整數(shù)建立一個具有10個整數(shù)的線性表；從鍵盤上輸入另一個值，插入到指定位置上；將指定位置的值刪除；輸出插入前、插入后和刪除后的線性表?！舅悸穼?dǎo)航】首先定義一個順序表結(jié)構(gòu)變量，調(diào)用initlist()函數(shù)初始化該線性表，再循環(huán)調(diào)用insert()函數(shù)將從鍵盤輸入的數(shù)據(jù)按順序存放到順序表中，為了使表中元素的位置與輸入的順序一致，每次都是從尾部插入。然后再從鍵盤輸入另一個值，再調(diào)用insert()函數(shù)將其插入到指定位置。采用模塊化程序設(shè)計方法，將宏定義、順序表結(jié)構(gòu)類型定義以及各函數(shù)原型聲明組織成一個源文件:f13_1.c*/，將initlist()、insert()、delete()和traverse()幾個功能函數(shù)組織成另一個源文件：f13_2.c，將主控函數(shù)組織成文件f13_3。程序代碼如下：/*exam13_9*//*f13_1.c*/#defineDATATYPEint/*定義順序表中的數(shù)據(jù)元素類型*/#defineMAXSIZE100/*定義順序表的最大容量為100*/typedefstruct/*自定義類型*/{DATATYPEdatas[MAXSIZE];/*聲明存放線性表的數(shù)組*/intsize;/*聲明一個整形變量存放順序表元素個數(shù)*/}LIST;

voidinitlist(LIST*a);intinsert(LIST*a,DATATYPEx,inti);intdelete(LIST*a,inti)voidtraverse(LIST*a);（續(xù)）/*f13_2.c*/#include<c:\output\f13_1.c>/*將定義LIST類型的文件做包含預(yù)處理，注意寫出完整路徑*/voidinitlist(LIST*a)/*初始化函數(shù)*/{a->size=0;}intinsert(LIST*a,DATATYPEx,inti)/*插入函數(shù)*/{intk;if(i<1||(i>a->size+1)||(a->size==MAXSIZE)){printf(“positionisoutofrangeorlistisfull”);return0;}else{for(k=a->size;k>=i;k--)a->datas[k]=a->datas[k-1];a->datas[i-1]=x;a->size++;return1;}}（續(xù)）intdelete(LIST*a,inti)/*刪除函數(shù)*/{intk;if(i<1||(i>a->size)||(a->size==0)){printf(“positonisoutofrangeorlistisempty”);return0;}else{for(k=i;k<a->size;k++)a->datas[k-1]=a->datas[k];a->size--;return1;}}voidtraverse(LIST*a)/*遍歷函數(shù)*/{inti;for(i=0;i<a->size;i++)printf("%d,",a->datas[i]);printf("\n");}（續(xù)）/*f13_3.c*/#include<stdio.h>#include<c:\output\f13_2.c>intmain(void){inti,k;DATATYPEitem,x;LISTa,*p=&a;initlist(p);printf(“Pleaseinput10numbers:\n”);for(i=0;i<10;i++){scanf(“%d”,&x);insert(p,x,i+1);}printf(“Theoriginallist:\n”);traverse(p);printf(“enteranewnumber:\n”);scanf(“%d”,&item);printf(“enterthepositionforthenewnumber:\n”);（續(xù)）scanf(“%d”,&k);insert(p,item,k);printf(“Thelistafterinsert:\n”);traverse(p);printf(“enterthepositionfordelete:\n”);scanf(“%d”,&k);delete(p,k);printf(“Thelistafterdelete:\n”);traverse(p);printf(“\n”);return0;}[演示]想一想：如果順序表中元素的數(shù)據(jù)類型是結(jié)構(gòu)類型，此情況下該如何修改上面的插入、刪除和遍歷函數(shù)？請試著擴(kuò)充例11-1中的各個功能函數(shù)。

13.3鏈表的插入與刪除13.3.1什么是鏈表

從上一節(jié)的介紹中，我們知道，順序表具有方便隨機讀取任一元素，物理關(guān)系與邏輯關(guān)系一致等優(yōu)點，但同時又有如下缺點：插入、刪除需要移動大量元素，效率低（O(n)）；存儲分配需預(yù)先進(jìn)行，不靈活或容易造成浪費。

例如，建立通訊錄時，我們必須預(yù)定總記錄個數(shù)，假定為100，若某個用戶需要建立聯(lián)絡(luò)信息人不超過30個，則其余70個預(yù)留的空間就是浪費。若某個用戶需要建立聯(lián)絡(luò)信息的人數(shù)超過100個，則造成插入溢出，即第100個后的記錄無法插入。因此，通常還采用另一種動態(tài)分配存儲空間的數(shù)據(jù)組織方式——鏈表。

鏈表就是線性表的鏈接存儲結(jié)構(gòu)，用一組任意的存儲單元來存放線性表的數(shù)據(jù)元素，這些存儲單元可以是連續(xù)的，也可以是不連續(xù)的。鏈表可以是單向的，也可以是雙向的，這里我們只討論單向鏈表。單向鏈表，簡稱單鏈表，每個結(jié)點由兩部分組成，一部分存放數(shù)據(jù)元素的值，另一部分存放其后繼結(jié)點的地址（也叫指針），如圖13-13所示。datanext圖13-13單鏈表的結(jié)點結(jié)構(gòu)

其中data叫數(shù)據(jù)域，用來存放數(shù)據(jù)元素的值，next叫指針域，用來存放其后繼結(jié)點的地址。由（a1,a2,…，an）n個元素組成的單鏈表如圖13-2所示：a1

a2

ai

ai+1

an^……h(huán)ead圖13-14單鏈表示意圖

單鏈表中除第一個結(jié)點外的每個結(jié)點的存儲地址都保存在其前驅(qū)結(jié)點的指針域中，終端結(jié)點無后繼結(jié)點，所以指針域為空值，用NULL（或^）表示。每個單鏈表必須有一個頭指針，指向表中第一個結(jié)點（地址）。一旦知道了頭指針，就可以訪問鏈表的第一個結(jié)點，然后通過每個結(jié)點的指針域，訪問其后繼結(jié)點，直到指針域等于NULL即可遍訪所有結(jié)點。所以單鏈表可以用頭指針來表示。當(dāng)頭指針head=NULL時表示單鏈表為空表。13.3.2單鏈表的建立、插入與刪除

（1）單鏈表結(jié)點類型的描述

用C語言描述單鏈表的結(jié)點結(jié)構(gòu)類型如下：#defineDATATYPEchar/*定義鏈表中的數(shù)據(jù)元素為字符型*/typedefstructnode

/*定義鏈表結(jié)點的結(jié)構(gòu)類型*/{DATATYPEdata;

structnode*next;

/*指向下一個結(jié)點的指針*/}LINKNODE;

/*結(jié)點的結(jié)構(gòu)類型名*/（2）建立單鏈表

建立單鏈表就是動態(tài)地為每一個結(jié)點開辟一個存儲空間，并且把它們鏈接成一個單鏈表。建立鏈表有兩種方法：頭插入法和尾插入法。頭插入法

頭插入法是將新結(jié)點插入到表頭位置，每次插入需要修改兩個指針：把頭指針head指向的第一個結(jié)點地址賦給新結(jié)點的next域，把新結(jié)點的地址賦給頭指針head，如圖13-15所示。這種方法比較簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。圖13-15從表頭插入結(jié)點…an

a2

a1^headpnew·LINKNODE*create_front(void){LINKNODE*head,*p;head=NULL;/*初始化單鏈表*/charch;while((ch=getchar())!=’$’)/*輸入字符$則結(jié)束*/{p=malloc(sizeof(LINKNODE));/*申請新結(jié)點存儲空間*/p->data=ch;

/*賦值給新結(jié)點的數(shù)據(jù)域*/p->next=head;/*讓新結(jié)點的指針域指向原來的頭結(jié)點*/head=t;/*讓頭指針指向新結(jié)點*/}returnhead;/*將新的頭結(jié)點通過函數(shù)名返回去*/}尾插入法

為了使生成的鏈表元素順序與輸入數(shù)據(jù)時的次序一致，可采用尾插入法。尾插入法是將新結(jié)點插在鏈表的尾部，插入第一個結(jié)點時，要把新結(jié)點地址賦給頭指針head，以后每次插入只需修改一個指針：把新結(jié)點地址賦給最后一個結(jié)點的next域，為此每次插入后需要使用一個指針記錄（指向）當(dāng)前鏈表的最后一個結(jié)點，如圖13-16所示。a)圖13-16在表尾插入一個結(jié)點a)插入新結(jié)點前b)插入新結(jié)點后p…a1

a2

an^lastheadnew^last…a1

a2

an

headnew^b)LINKNODE*create_rear_1(void){LINKNODE*head,*p,*last;intn=0;charch;/*記錄當(dāng)前結(jié)點為第幾個結(jié)點*/head=NULL;/*初始化單鏈表*/p=last=(LINKNODE*)malloc(sizeof(LINKNODE));/*開辟一個新單元*/while((ch=getchar())!=’$’)/*輸入字符$則結(jié)束*/{n=n+1;

/*結(jié)點數(shù)增１*/p=malloc(sizeof(LINKNODE));/*申請新結(jié)點存儲空間*/p->data=ch;if(n==1)head=p;/*若是第一個結(jié)點則讓頭指針指向它*/elselast->next=p;last=p;}last->next=NULL;

/*將最后一個結(jié)點的指針域置NULL*/returnhead;

/*返回單鏈表的頭指針*/}建立帶頭結(jié)點的單鏈表

從上面尾插入法建立單鏈表的討論中，我們發(fā)現(xiàn)當(dāng)鏈表為空表而又是插入第一個元素時，情況比較特殊。為了使鏈表上有些操作實現(xiàn)起來比較簡單、清晰，通常在鏈表的第一個結(jié)點之前增設(shè)一個類型相同的結(jié)點，稱為頭結(jié)點。帶頭結(jié)點的鏈表有兩個特點：一是表中所有元素結(jié)點的地址均存放在前驅(qū)結(jié)點的指針域中；其次，無論鏈表是否為空，頭指針都指向頭結(jié)點。如圖13-17所示：頭結(jié)點…

a1

an^heada2

頭結(jié)點^head圖13-17帶頭結(jié)點的單鏈表a)非空鏈表b)空鏈表

增加了頭結(jié)點后，不用另行考慮第一個元素結(jié)點的插入情況，對所有元素結(jié)點處理可以一致化，從而使插入等操作更加簡便。例如上面尾插入建立單鏈表算法，在引入頭結(jié)點后算法可修改如下：LINKNODE*create_rear_2(void){LINKNODE*head,*p,*last;charch;head=NULL;p=(LINKNODE*)malloc(sizeof(LINKNODE));head=p;last=p;p->next=NULL;while((ch=getchar())!=’$’)/*輸入字符$則結(jié)束*/{p=malloc(sizeof(LINKNODE));/*申請新結(jié)點存儲空間*/p->data=ch;last->next=p;last=p;p->next=NULL;

/*將最后一個結(jié)點的指針域置NULL*/}returnhead;

/*返回單鏈表的頭指針*/}

※注意：帶頭結(jié)點的單鏈表的判斷空表的條件是head->next==NULL，而沒有頭結(jié)點的單鏈表的判斷空表的條件是head==NULL。（3）單鏈表的插入操作

單鏈表的插入有頭插入、尾插入和有序插入（或稱保序插入），有序插入是指鏈表已經(jīng)按某個成員項（比如通訊錄鏈表中的number）的值由小到大排好順序，現(xiàn)要求把一個新的結(jié)點插入到適當(dāng)?shù)奈恢?，使得插入后新鏈表仍然有序，頭插入指將新結(jié)點總是插入在表頭，尾插入指將新結(jié)點總是插入在表尾。下面我們討論保序插入。

首先，要找到插入位置，假設(shè)在ｐ指向的結(jié)點之前插入，ｑ為指向ｐ的前驅(qū)結(jié)點的指針，ｔ為待插入的新結(jié)點，則需要調(diào)整兩個指針：若ｐ為第一個結(jié)點，要把p賦給ｔ－＞next，把ｔ賦給頭指針head；若p為表尾，要把ｔ賦給q－＞next，把NULL賦給t－＞next；若p既非表頭也非表尾，則要把p賦給ｔ－＞next，同時把ｔ賦給q－＞next。插入過程如圖13-18所示。圖13-18插入結(jié)點的示意圖data

pdata插入位置data

data……插入位置的前驅(qū)q新結(jié)點ｔLINKNODE*insert(LINKNODE*head,LINKNODE*t){LINKNODE*p,*q;p=head;/*使p指向第一個結(jié)點*/if(head==NULL)/*若鏈表為空表*/{head=t;t－>next=NULL;}/*使新結(jié)點t作為頭結(jié)點*/else{while((t->data>p->data)&&(p->next!=NULL)){q=p;/*使q指向剛比較過的結(jié)點*/p=p->next;}/*使p指向下一個結(jié)點*/if(t->data<=p->data)/*若找到插入位置p*/{if(p==head)head=t;/*若p為第一個結(jié)點，使head指向t*/elseq->next=t;/*若p在鏈表中間，將t插到q之后*/t->next=p;}else{p->next=t;t->next=NULL;}}returnhead;/*返回新的頭指針*/}（4）單鏈表的刪除操作

從單鏈表中刪除一個結(jié)點，只需把它從鏈表中分離出來，即撤銷原來的鏈接關(guān)系，然后釋放這個結(jié)點所占用的內(nèi)存空間即可。刪除過程如圖13-19所示：data待刪除結(jié)點data

data……pq釋放該結(jié)點待刪除結(jié)點的前驅(qū)圖13-19刪除結(jié)點的示意圖/*刪除頭指針為head的單鏈表中數(shù)據(jù)域等于指定值的結(jié)點*/LINKNODE*delete(LINKNODE*head,DATATYPEx){LINKNODE*p,*q;if(h