數(shù)據(jù)結(jié)構(gòu)教案

第一章緒論§1.1什么是數(shù)據(jù)結(jié)構(gòu)一．?dāng)?shù)據(jù)結(jié)構(gòu)的概念NiklausWirth說(shuō)過(guò)Algorithm+DataStructures=Programs，其中程序設(shè)計(jì):為計(jì)算機(jī)處理問(wèn)題編制一組指令集，算法:處理問(wèn)題的策略，數(shù)據(jù)結(jié)構(gòu):問(wèn)題的數(shù)學(xué)模型。在計(jì)算機(jī)發(fā)展的早期，主要用于數(shù)值計(jì)算，例如：結(jié)構(gòu)靜力分析計(jì)算線性代數(shù)方程組，全球天氣預(yù)報(bào)、環(huán)流模式方程，但是隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和硬、軟件技術(shù)的發(fā)展，非數(shù)值計(jì)算問(wèn)題越來(lái)越多（占90%）例1：學(xué)生信息檢索，計(jì)算機(jī)處理的對(duì)象之間存在一種簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可以歸結(jié)為線性數(shù)據(jù)結(jié)構(gòu)。例2：計(jì)算機(jī)和人對(duì)弈（八皇后問(wèn)題等），為了得到合理的布局，計(jì)算機(jī)要存儲(chǔ)當(dāng)前的布局，從最初的布局開始，每個(gè)布局都會(huì)衍生出許多新的布局，這時(shí)計(jì)算機(jī)所要處理的是一顆對(duì)弈樹，也是一種典型的數(shù)據(jù)結(jié)構(gòu)。例3：教學(xué)計(jì)劃的編排（交通燈），一個(gè)教學(xué)計(jì)劃包含許多課程，課程間有些必須按規(guī)定的先后順序進(jìn)行，有些則沒有次序要求，各個(gè)課程間的次序關(guān)系可用圖來(lái)表示。也是一種典型的數(shù)據(jù)結(jié)構(gòu)由此可見，描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型已不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)，因此說(shuō)，數(shù)據(jù)結(jié)構(gòu)主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間關(guān)系和操作的學(xué)科。二．?dāng)?shù)據(jù)結(jié)構(gòu)的產(chǎn)生和發(fā)展1968年以獨(dú)立的學(xué)科設(shè)立，之后不斷發(fā)展，目前已成為計(jì)算機(jī)專業(yè)的核心課程和許多非計(jì)算機(jī)專業(yè)的選修課程?！?.2有關(guān)概念和術(shù)語(yǔ)一．?dāng)?shù)據(jù)結(jié)構(gòu)的概念1．?dāng)?shù)據(jù):所有能被輸入到計(jì)算機(jī)中，且被計(jì)算機(jī)處理的符號(hào)的集合計(jì)算機(jī)操作的對(duì)象的總稱，是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式2．?dāng)?shù)據(jù)元素:數(shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位，一個(gè)數(shù)據(jù)元素可能包含若干數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)：數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合，例如運(yùn)動(dòng)員（數(shù)據(jù)元素）姓名俱樂部名稱出生日期參加日期職務(wù)業(yè)績(jī)其中出生日期年月日是組合項(xiàng)3．?dāng)?shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集，4．?dāng)?shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，數(shù)據(jù)元素的關(guān)系稱為結(jié)構(gòu)。二．?dāng)?shù)據(jù)結(jié)構(gòu)的表示數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。嚴(yán)格地講，以上定義僅是數(shù)據(jù)的邏輯結(jié)構(gòu)的定義，邏輯結(jié)構(gòu)可以看作是從一個(gè)具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)、集合結(jié)構(gòu)。集合結(jié)構(gòu)：屬于同一集合，別無(wú)其他關(guān)系（常用其他結(jié)構(gòu)表示）線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系樹狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系（a）集合結(jié)構(gòu)（b）線性結(jié)構(gòu)（c）樹型結(jié)構(gòu)（d）圖形結(jié)構(gòu)圖1.4四類基本結(jié)構(gòu)的示意圖數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)─━邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象，他所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，主要有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引和散列存儲(chǔ)數(shù)據(jù)元素的映象方法即關(guān)系的映象方法：（表示<x,y>的方法）順序映象以存儲(chǔ)位置的相鄰表示后繼關(guān)系，y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C，而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息，通常用數(shù)組來(lái)實(shí)現(xiàn)。鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系，需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置，不要求物理位置的相鄰。在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法，當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類型描述之。例如:以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語(yǔ)言中提供的整數(shù)數(shù)組類型，定義長(zhǎng)整數(shù)為:typedefintLong_int[3]；三、數(shù)據(jù)類型數(shù)據(jù)類型：在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明它們所屬的數(shù)據(jù)類型。因?yàn)轭愋兔黠@或隱含地規(guī)定了，在程序執(zhí)行期間，變量或表達(dá)式所有可能取值的范圍，以及在這些之上允許進(jìn)行的操作。數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。四．抽象數(shù)據(jù)類型(AbstractDataType簡(jiǎn)稱ADT)1．定義：是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作，和數(shù)據(jù)類型本質(zhì)相同，抽象指的是數(shù)學(xué)模型的數(shù)學(xué)抽象特性，而且抽象數(shù)據(jù)類型的范圍更廣。ADT有兩個(gè)重要特征:數(shù)據(jù)抽象：用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝：將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。例如抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADTComplex{數(shù)據(jù)對(duì)象：D＝{e1,e2｜e1,e2∈RealSet}數(shù)據(jù)關(guān)系：R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,|e2是復(fù)數(shù)的虛數(shù)部分}基本操作：InitComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex假設(shè):z1和z2是上述定義的復(fù)數(shù)，則Add(z1,z2,z3)操作的結(jié)果將得到z3=z1+z2抽象數(shù)據(jù)類型的描述方法2．抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為基本操作名（參數(shù)表）初始條件：〈初始條件描述〉操作結(jié)果：〈操作結(jié)果描述〉基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。“初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之?！?.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)：抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)預(yù)處理：#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1#defineOVERFLOW-2#include<stdio.h>#include<stdlib.h>typedefintStatus;C語(yǔ)言中的運(yùn)算符（）、[]、->、。！~++--+（正）-(負(fù))*(指針)&sizeof(類型)*/%+-<<>><=<>>=!===&^|&&||=+=-=*=/=%=>>=<<=&=^=|=,(逗號(hào))§1.4算法和算法的衡量一、算法算法是為了解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1．有窮性對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；2．確定性對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；3．可行性算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4．有輸入作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中；5．有輸出它是一組與“輸入”與確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說(shuō)明”方式給出的需求。其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．程序中不含語(yǔ)法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；c．程序?qū)τ诰倪x擇的、典型、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；通常以第c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。2.可讀性算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試；3．健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4．高效率與低存儲(chǔ)量需求通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。兩者都與問(wèn)題的規(guī)模有關(guān)。三、算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:事后統(tǒng)計(jì)法缺點(diǎn)：1。必須執(zhí)行程序2．其它因素掩蓋算法本質(zhì)事前分析估算法和算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問(wèn)題的規(guī)模3．編寫程序的語(yǔ)言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模（通常用整數(shù)量n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n))，稱T(n)為算法的(漸近)時(shí)間復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間，算法的執(zhí)行時(shí)間與原操作執(zhí)行次數(shù)之和成正比從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作，在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則例1for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];}基本操作:乘法操作，時(shí)間復(fù)雜度:O(n3)例2voidselect_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}//select_sort基本操作:比較(數(shù)據(jù)元素)操作，時(shí)間復(fù)雜度:O(n2)四、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度：S(n)=O(g(n))表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。算法的存儲(chǔ)量包括:1．輸入數(shù)據(jù)所占空間;2．程序本身所占空間；3．輔助變量所占空間。若輸入數(shù)據(jù)所占空間只取決與問(wèn)題本身，和算法無(wú)關(guān)，則只需要分析除輸入和程序之外的額外空間。若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為原地工作。若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。學(xué)習(xí)要點(diǎn)：1.熟悉各名詞、術(shù)語(yǔ)的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲(chǔ)結(jié)構(gòu)的性質(zhì)。2.了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。3．理解算法五個(gè)要素的確切含義：①動(dòng)態(tài)有窮性（能執(zhí)行結(jié)束）；②確定性（對(duì)于相同的輸入執(zhí)行相同的路徑）；③有輸入；④有輸出；⑤可行性（用以描述算法的操作都是足夠基本的）。4．掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。

第二章線性表線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集線性結(jié)構(gòu)的基本特征:1．集合中必存在唯一的一個(gè)“第一元素”；2．集合中必存在唯一的一個(gè)“最后元素”；3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。§2.1線性表的邏輯結(jié)構(gòu)一、線性表的類型定義抽象數(shù)據(jù)類型線性表的定義如下：ADTList{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n為線性表的表長(zhǎng);稱n=0時(shí)的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),稱i為ai在線性表中的位序。}二、基本操作：{結(jié)構(gòu)初始化}1．InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。{銷毀結(jié)構(gòu)}2．DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。{引用型操作}3．ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。4．ListLength(L)初始條件：線性表L已存在。操作結(jié)果：返回L中元素個(gè)數(shù)。5．PriorElem(L,cur_e,&pre_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的元素，但不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。6．NextElem(L,cur_e,&next_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的元素，但不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。7．GetElem(L,cur_e,&next_e)初始條件：線性表L已存在，1≤i≤LengthList(L)操作結(jié)果：用e返回L中第i個(gè)元素的值。8．LocateElem(L,e,compare())初始條件：線性表L已存在，compare()是元素判定函數(shù)。操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的元素的位序。若這樣的元素不存在，則返回值為0。9．ListTraverse(L,visit())初始條件：線性表L已存在。操作結(jié)果：依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。{加工型操作}10．ClearList(&L)初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。11．PutElem(L,i,&e)初始條件：線性表L已存在，1≤i≤LengthList(L)操作結(jié)果：L中第i個(gè)元素賦值同e的值。12．ListInsert(&L,i,e)初始條件：線性表L已存在，1≤i≤LengthList(L)+1操作結(jié)果：在L的第i個(gè)元素之前插入新的元素e，L的長(zhǎng)度增1。13．ListDelete(&L,i,&e)初始條件：線性表L已存在且非空，1≤i≤LengthList(L)操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。}ADTList利用上述定義的線性表可以完成其它更復(fù)雜的操作例2-1假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示（即：線性表中的數(shù)據(jù)元素即為集合中的成員），現(xiàn)要求一個(gè)新的集合A＝A∪B。上述問(wèn)題可演繹為，要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。1．從線性表LB中依次取得每個(gè)數(shù)據(jù)元素;GetElem(LB,i)→e2．依值在線性表LA中進(jìn)行查訪;LocateElem(LA,e,equal())3．若不存在，則插入之。ListInsert(LA,n+1,e)voidunion(List&La,ListLb){//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長(zhǎng)度f(wàn)or(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal())ListInsert(La,++La_len1,e);//La中不存在和e相同的數(shù)據(jù)元素，則插入之}}//union例2-2已知一個(gè)非純集合B，試構(gòu)造一個(gè)純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。voidpurge(List&La,ListLb){//已知線性表Lb中的數(shù)據(jù)元素依值非遞減有序排列(Lb是有序表)，//構(gòu)造線性表La，使其只包含Lb中所有值不相同的數(shù)據(jù)元素InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長(zhǎng)度f(wàn)or(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!equal(en,e)){ListInsert(La,++La_len,e);en=e;}//La中不存在和e相同的數(shù)據(jù)元素，則插入之}}//purge例2-3歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列的”線性表LA和LB，求得線性表LC也具有同樣特性設(shè)La=(a1,…,ai,…,an)Lb=(b1,…,bj,…,bm)Lc=(c1,…,ck,…,cm+n)則Ck=k=1,2,…,m+n1．分別從LA和LB中取得當(dāng)前元素ai和bj；2．若ai≤bj，則將ai插入到LC中，否則將bj插入到LC中。voidMergeList(ListLa,ListLb,List&Lc){//已知線性表La和Lb中的元素按值非遞減排列。//歸并La和Lb得到新的線性表Lc，//Lc的元素也按值非遞減排列。InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//merge_list§2.2線性表的順序存儲(chǔ)和基本操作的實(shí)現(xiàn)順序表用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素，線性表的起始地址，稱作線性表的基地址，以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>即：所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc(ai)=Loc(a1)+(I-1)*l，1≤i≤n,l=sizeof(ElemType)順序映像的C語(yǔ)言描述//-----線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)-----#defineLIST_INIT_SIZE80//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量typedefstruct{ElemType*elem;//存儲(chǔ)空間基址intlength;//當(dāng)前長(zhǎng)度intlistsize;//當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)}SqList;//俗稱順序表線性表的基本操作的實(shí)現(xiàn)初始化在順序映像中的實(shí)現(xiàn)StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗L.length=0;//長(zhǎng)度為0L.listsize=LIST_INIT_SIZE;//初始存儲(chǔ)容量returnOK;}//InitList_Sq線性表的建立StatusCreaList_Sq(SqList&L)

{

intlength,i,data;

printf("輸入表的長(zhǎng)度\n");

scanf("%d",&length);

InitList_Sq(L);

printf("輸入表中數(shù)據(jù)\n");for(i=0;i<length;i++){scanf("%d",&data);L.elem[i]=data;}L.length=length;returnOK;}//Crea_Sq3、線性表操作LocateElem(L,e,compare())的實(shí)現(xiàn)：intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序線性表L中查找第1個(gè)值與e滿足compare()的元素的位序。//若找到，則返回其在L中的位序，否則返回0。i=1;//i的初值為第1元素的位序p=L.elem;//p的初值為第1元素的存儲(chǔ)位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq此算法的時(shí)間復(fù)雜度為:O(ListLength(L))4、線性表操作ListInsert(&L,i,e)的實(shí)現(xiàn)：?jiǎn)枺翰迦朐貢r(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)StatusListInsert_Sq(SqList&L,intpos,ElemTypee){//在順序線性表L的第pos個(gè)元素之前插入新的元素e，//pos的合法值為1≤pos≤Listlength_Sq(L)+1if(pos<1||pos>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}q=&(L.elem[pos-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長(zhǎng)增1returnOK;}//ListInsert_Sq性能分析：從I位置插入x，ai到an都要后移，共需移動(dòng)n-I+1個(gè)元素，1≤i≤n+1，平均移動(dòng)次數(shù)：，令，此算法的時(shí)間復(fù)雜度為:O(ListLength(L))5、線性表操作ListDelete(&L,i,&e)的實(shí)現(xiàn)：?jiǎn)枺簞h除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,intpos,ElemType&e){//在順序線性表L中刪除第pos個(gè)元素，并用e返回其值。//pos的合法值為1≤pos≤ListLength_Sq(L)if((pos<1)||(pos>L.length))returnERROR;//刪除位置不合法p=&(L.elem[pos-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被刪除元素之后的元素左移--L.length;//表長(zhǎng)減1returnOK;}//ListDelete_Sq性能分析：刪除第I個(gè)元素，aI+1到an都要前移，共需移動(dòng)n-I個(gè)元素，1≤i≤n，平均移動(dòng)次數(shù)：，令，則此算法的時(shí)間復(fù)雜度為:O(ListLength(L))應(yīng)用舉例例1、線性表的合并StatusMerg_Sq(SqListLa,SqListLb,SqList&Lc)

{

ElemType*pa,*pb,*pc;

ElemType*pa_last,*pb_last;

pa=La.elem;

pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb) *pc++=*pa++;else *pc++=*pb++; }while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;returnOK;}//Merg_Sq例2、將一個(gè)線性表分兩部分，其中前面的比a1小，后面的比a1大//將表分成兩部分,前面的比原來(lái)的第一元素小,后面的比第一個(gè)大

①StatusPart_Sq1(SqList&L)

{

ElemType*p,*p_last,*q,*s;

ElemTypee,et;

p=L.elem;p_last=L.elem+L.length-1;

e=*p;

for(q=p+1;q<=p_last;q++)

if(*q<e)

{

et=*q; for(s=q-1;s>=p;s--)*(s+1)=*s; *p=et; p++; }returnOK;}//Part_Sq②StatusPart_Sq2(SqList&L){inti,j,t;i=0;j=L.length-1;t=*L.elem;while(i<j){while(i<j&&L.elem[j]>=t)j--;L.elem[i]=L.elem[j];while(i<j&&L.elem[i]<=t)i++;L.elem[j]=L.elem[i];}L.elem[i]=t;returnOK;}//Part_Sq§2.3線性表類型的鏈?zhǔn)接诚蠛突静僮鞯膶?shí)現(xiàn)由于線性表的順序存儲(chǔ)是用物理位置上的相鄰實(shí)現(xiàn)了邏輯上的相鄰，因此對(duì)元素插入或移動(dòng)時(shí)，運(yùn)行效率低，但可以隨機(jī)存取任一元素，鏈?zhǔn)酱鎯?chǔ)不需用地址連續(xù)的存儲(chǔ)單元來(lái)實(shí)現(xiàn)，它通過(guò)鏈表來(lái)實(shí)現(xiàn)邏輯上的相鄰，但同時(shí)失去了順序表可隨機(jī)存取的優(yōu)點(diǎn)。一、單鏈表1．定義：用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素，以元素(數(shù)據(jù)元素的映象)+指針(指示后繼元素存儲(chǔ)位置的)=結(jié)點(diǎn)(表示數(shù)據(jù)元素)，以“結(jié)點(diǎn)的序列”表示線性表稱作鏈表，以線性表中第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)地址作為線性表的地址，為線性表的頭指針2．結(jié)點(diǎn)的C語(yǔ)言描述typedefstructLNode{ElemTypedata;//數(shù)據(jù)域structLnode*next;//指針域}LNode,*LinkList;二、單鏈表操作的實(shí)現(xiàn)1．voidCreateList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)scanf(&p->data);//輸入元素值p->next=L->next;L->next=p;//插入到表頭}}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))建立LinkListCreaList1()

{//逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L

LinkListL;

ElemTypex;

LNode*s;

L=(LNode*)malloc(sizeof(LNode));L->next=NULL;scanf("%d",&x);

while(x!=flag)

{

s=(LNode*)malloc(sizeof(LNode));

s->data=x;

s->next=L->next;

L->next=s;

scanf("%d",&x);

}

returnL;}//Crea_LinkListLinkListCreaList2(){//順序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。LinkListL,p,q;ElemTypex;L=(LNode*)malloc(sizeof(LNode));q=L;scanf("%d",&x);while(x!=flag){p=(LNode*)malloc(sizeof(LNode));p->data=x;q->next=p;q=p;scanf("%d",&x);}q->next=NULL;returnL;}//Crea_LinkList2．線性表的操作GetElem(L,i,&e)在鏈表中的實(shí)現(xiàn):基本操作為:使指針p始終指向線性表中第j個(gè)數(shù)據(jù)元素StatusGetElem_L(LinkListL,intpos,ElemType&e){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)線性表中存在第pos個(gè)元素存在時(shí)，則將第pos個(gè)數(shù)據(jù)元素的值賦給e并返回OK，否則返回ERRORp=L->next;j=1;//初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<pos){//順指針向后查找，直到p指向第pos個(gè)元素或p為空p=p->next;++j;}if(!p||j>pos)returnERROR;//第pos個(gè)元素不存在e=p->data;//取第pos個(gè)元素returnOK;}//GetElem_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))3．線性表的操作ListInsert(&L,i,e)在鏈表中的實(shí)現(xiàn):基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針，有序?qū)?lt;ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>StatusListInsert_L(LinkListL,intpos,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈表L中第pos個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素ep=L;j=0;while(p&&j<pos-1){p=p->next;++j;}//尋找第pos-1個(gè)結(jié)點(diǎn)if(!p||j>pos-1)returnERROR;//pos小于1或者大于表長(zhǎng)s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)s->data=e;s->next=p->next;//插入L中p->next=s;returnOK;}//LinstInsert_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))StatusListInsert_L(LinkListL,intpos,ElemTypee){//在沒有頭結(jié)點(diǎn)的單鏈表L中第pos個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素es=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)s->data=e;if(pos==1){s->next=L;L=s;}else{j=0;p=L;while(p&&j<pos-1){p=p->next;++j;}//尋找第pos-1個(gè)結(jié)點(diǎn)if(!p||j>pos-1)returnERROR;//pos小于1或者大于表長(zhǎng)s->next=p->next;//插入L中p->next=s;}returnOK;}//LinstInsert_L4．線性表的操作ListDelete(&L,i,&e)在鏈表中的實(shí)現(xiàn):基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針，有序?qū)?lt;ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>StatusListDelete_L(LinkListL,intpos,ElemType&e){//在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第pos個(gè)元素，并由e返回其值p=L;j=0;while(p->next&&j<pos-1){//尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前趨p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))StatusListDelete_L(LinkListL,intpos,ElemType&e){//在沒有頭結(jié)點(diǎn)的單鏈表L中，刪除第pos個(gè)元素，并由e返回其值if(pos==1)L=L->next;else{p=L;j=0;while(p->next&&j<pos-1){//尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前趨p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);}returnOK;}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))5.求表的長(zhǎng)度：intListLeng_L(LinkListL){LNode*p=L->next;intj=0;while(p!=NULL){p=p->next;j++;}returnj;}//Leng_LinkList6．查找LNode*LocaElem(LinkListL,ElemTypee){LNode*p=L->next;while(p!=NULL&&p->data!=e) p=p->next;returnp;}//Loca_LinkList應(yīng)用舉例例1．逆置：voidreverse(LinkList&L)（中科院93年試題）

{

LNode*p,*q;

p=L->next;L->next=NULL;while(p){q=p;p=p->next;q->next=L->next;L->next=q;}}例2：兩個(gè)鏈表的合并voidMerg_LinkList(LinkListLa,LinkListLb,LinkList&Lc){LinkListpa,pb,pc;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa&&pb)if(pa->data<=pb->data){ pc->next=pa; pc=pa; pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pa:pb;free(Lb);}//Merg_LinkList例3已知單鏈表L，寫一算法，刪除其重復(fù)結(jié)點(diǎn)(北京工業(yè)大學(xué)96年試題)StatusPur_LinkList(LinkList&L){LNode*p,*q,*r;p=L->next;if(p==NULL)returnERROR;while(p->next){q=p;while(q->next)if(q->next->data==p->data) { r=q->next; q->next=r->next; free(r); }else q=q->next;p=p->next;}returnOK;}//Pur_LinkList例4：逆向合并(中國(guó)科技大學(xué)97年研究生入學(xué)試題）voidRev_MergList(LinkListA,LinkListB,LinkList&C){LinkListq,pa,pb,pc,pre;pa=A->next;pb=B->next;pre=NULL;while(pa&&pb){if(pa->data<pb->data){ pc=pa; q=pa->next; pa->next=pre; pa=q;}else{pc=pb;q=pb->next;pb->next=pre;pb=q;}pre=pc;}while(pa){q=pa->next;pa->next=pc;pc=pa;pa=q;}while(pb){q=pb->next;pb->next=pc;pc=pb;pb=q;}A->next=pc;C=A;}//Rev_MergList例5StatusDeleteBetween(LinkList&L,ElemTypemink,ElemTypemaxk){LNode*p,*q;p=L;while(p->next->data<mink)p=p->next;if(p->next){q=p->next;while(q->data<maxk)q=q->next;p->next=q;}returnOK;}6、判斷La是否包含在Lb中(清華大學(xué)94年研究生入學(xué)試題）intInclude(LinkListLa,LinkListLb){LinkListpa,pb;pa=La->next;pb=Lb->next;if(pa==NULL)returnTRUE;while(pb&&pa->data>=pb->data)if(pa->data==pb->data) returnInclude(pa,pb);else pb=pb->next;returnFALSE;}用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問(wèn)題：1．單鏈表的表長(zhǎng)是一個(gè)隱含的值；2．在單鏈表的最后一個(gè)元素最后插入元素時(shí)，需遍歷整個(gè)鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念強(qiáng)化。改進(jìn)鏈表的設(shè)置：1．增加“表長(zhǎng)”、“表尾指針”和“當(dāng)前位置的指針”三個(gè)數(shù)據(jù)域；2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”*四、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型typedefstructLNode{//結(jié)點(diǎn)類型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//鏈表類型Linkhead,tail;//指向頭結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)intlen;//指示鏈表長(zhǎng)度Linkcurrent;//指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)的指針，//初始位置指向頭結(jié)點(diǎn)}LinkList.StatusMakeNode(Link&p,ElemTypee);//分配由p指向的值為e的結(jié)點(diǎn)，并返回OK；若分配失敗，則返回ERRORvoidFreeNode(Link&p);//釋放p所指結(jié)點(diǎn)鏈表的基本操作:{結(jié)構(gòu)初始化和銷毀結(jié)構(gòu)}StatusInitList(LinkList&L);//構(gòu)造一個(gè)空的線性鏈表L，//頭指針、尾指針和當(dāng)前指針均指向頭結(jié)點(diǎn)，表長(zhǎng)為零StatusDestroyList(LinkList&L);//銷毀線性鏈表L，L不再存在{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//求表長(zhǎng)StatusPrior(LinkListL);//改變當(dāng)前指針指向其前驅(qū)StatusNext(LinkListL);//改變當(dāng)前指針指向其后繼ElemTypeGetCurElem(LinkListL);//返回當(dāng)前指針?biāo)笖?shù)據(jù)元素StatusLocatePos(LinkListL,inti);//改變當(dāng)前指針指向第i個(gè)結(jié)點(diǎn)StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//若存在與e滿足函數(shù)compare()判定關(guān)系的元素，則移動(dòng)當(dāng)前指針指向第1個(gè)滿足條件的元素，并返回OK;否則返回ERRORStatusListTraverse(LinkListL,Status(*visit)());//依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit(){加工型操作}StatusClearList(LinkList&L);//重置為空表StatusSetCurElem(LinkList&L,ElemTypee);//更新當(dāng)前指針?biāo)笖?shù)據(jù)元素StatusAppend(LinkList&L,Links);//一串結(jié)點(diǎn)鏈接在最后一個(gè)結(jié)點(diǎn)之后StatusInsAfter(LinkList&L,ElemTypee);//將元素e插入在當(dāng)前指針之后StatusDelAfter(LinkList&L,ElemType&e);//刪除當(dāng)前指針之后的結(jié)點(diǎn){這里定義的大部分算法都將結(jié)點(diǎn)和指針的概念封裝在算法中}StatusInsAfter(LinkList&L,ElemTypee){//若當(dāng)前指針在鏈表中，則將數(shù)據(jù)元素e插入在線性鏈表L中，當(dāng)前指針?biāo)附Y(jié)點(diǎn)之后,并返回OK;否則返回ERROR。if(!L.current)returnERROR;if(!MakeNode(s,e))returnERROR;s->next=L.current->next;L.current->next=s;RreturnOK;}//InsAfterStatusDelAfter(LinkList&L,ElemType&e){//若當(dāng)前指針及其后繼在鏈表中，則刪除線性鏈表L中當(dāng)前指針?biāo)附Y(jié)點(diǎn)之后的結(jié)點(diǎn)，并返回OK;否則返回ERROR。if(!(L.current&&L.current->next))returnERROR;q=L.current->next;L.current->next=q->next;e=q->data;FreeNode(q);returnOK;}//DelAfter{利用上述定義的線性鏈表可以完成線性表的其它操作}例1:StatusListInsert_L(LinkListL,inti,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈線性表L的第i個(gè)元素之前插入元素eif(!LocatePos(L,i-1))returnERROR;//i值不合法if(InsAfter(L,e))returnOK;//插入在第i-1個(gè)結(jié)點(diǎn)之后elsereturnERROR;}//ListInsert_L例2:voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lcint(*compare)(ElemType,ElemType))){//已知單鏈線性表La和Lb的元素按值非遞減排列，歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列if(!InitList(Lc))returnERROR;//存儲(chǔ)空間分配失敗LocatePos(La,0);LocatePos(Lb,0);//當(dāng)前指針指向頭結(jié)點(diǎn)if(DelAfter(La,e))a=e;elsea=MAXC;//MAXC為常量最大值if(DelFirst(Lb,e))b=e;elseb=MAXC;//a和b為兩表中當(dāng)前比較元素while(!(a=MAXC&&b=MAXC)){//La或Lb非空if((*compare)(a,b)<=0){//a≤bInsAfter(Lc,a);if(DelAfter(La,e1)a=e1;elsea=MAXC;}else{//a＞bInsAfter(Lc,s);if(DelAfter(Lb,e)b=e1;elseb=MAXC;}}DestroyList(La);DestroyList(Lb);//銷毀鏈表La和LbreturnOK;}//MergeList_L四、其它形式的鏈表1．循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表（將在多項(xiàng)式中詳細(xì)說(shuō)明）通常在實(shí)際的操作中，保留尾結(jié)點(diǎn)的地址，這樣合并時(shí)比較容易p=r1->next;r1->next=r2->next->next;r2->next=p;例如：猴子選大王（復(fù)旦大學(xué)97年研究生入學(xué)試題）voidSeleKing(){LinkListL,p,q;inti,n,m;printf("inputmonkeynum\n");scanf("%d",&n);L=(LNode*)malloc(sizeof(LNode));L->data=1;p=L;i=2;while(i<=n){q=(LNode*)malloc(sizeof(LNode));q->data=i;i++;p->next=q;p=q;}p->next=L;i=0;p=q;printf("inputm\n");scanf("%d",&m);while(p!=p->next){p=p->next;i++;if(i%m==0) q->next=p->next;else q=p;}printf("king=%d",p->data);}//Seleking2.雙向鏈表（1）//-----線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)-----typedefstructDuLNode{ElemTypedata;//數(shù)據(jù)域structDuLNode*prior;//指向前驅(qū)的指針域structDuLNode*next;//指向后繼的指針域}DuLNode,*DuLinkList;（2）.基本操作：建立：DuLinkListCreaList_Du(){DuLinkListhead,p,q;ElemTypex,flag=32767;head=(DuLNode*)malloc(sizeof(DuLNode));head->prior=NULL;head->next=NULL;q=head;scanf("%d",&x);while(x!=flag){p=(DuLNode*)malloc(sizeof(DuLNode));p->data=x;p->next=NULL;q->next=p;p->prior=q;q=p;scanf("%d",&x);}returnhead;}//Crea_DuLinkList得到某個(gè)元素的值或地址DuLinkListGetElem_Du(DuLinkListL,inti){intj=0;DuLinkListp;p=L;while(p&&j<i){p=p->next;j++;}if(!p||j>i)returnNULL;elsereturnp;}//Get_DuLinkLIst插入某個(gè)元素：StatusListInsert_Du(DuLinkList&L,inti,ElemTypee){DuLinkListp,s;p=GetElem_Du(L,i-1);if(p==NULL){ printf("noi-1node\n"); returnERROR;}else{ if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) exit(OVERFLOW); s->data=e; if(p->next!=NULL) { s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; } else { s->prior=p; s->next=p->next; p->next=s; } returnOK;}}//Inse_DuLinkList刪除某個(gè)元素：StatusListDelete_Du(DuLinkList&L,inti,ElemType&e){DuLinkListp;if(!(p=GetElem_Du(L,i)))returnERROR;e=p->data;if(p->next==NULL) p->prior->next=p->next; else { p->prior->next=p->next; p->next->prior=p->prior; }free(p);returnOK;}//Dele_DuLinkListStatusPrin_DuLinkList(DuLinkListL){DuLinkListp;p=L->next;while(p){printf("%4d",p->data);p=p->next;}returnOK;}3。靜態(tài)鏈表//靜態(tài)鏈表

（1）基本操作#include"common.h"

#defineMAXSIZE20

typedefcharElemType;

typedefstructSNode{

ElemTypedata;

intcur;

}SNode,SLinkList[MAXSIZE];

初始化：StatusInit_SLinkList(SLinkList&S)

{

inti;

for(i=0;i<MAXSIZE-1;i++)S[i].cur=i+1;S[MAXSIZE-1].cur=0;returnOK;}分配單元：intMalloc_SLinkList(SLinkList&S){inti;i=S[0].cur;if(S[0].cur)S[0].cur=S[i].cur;returni;}釋放單元StatusFree_SLinkList(SLinkList&S,intk){S[k].cur=S[0].cur;S[0].cur=k;returnOK;}//Free_SLinkLIst輸出：StatusPrin_SLinkList(SLinkListS,inti){intt=s[i].cur;while(t!=0){ printf("%4c",S[t].data); t=S[t].cur;}returnOK;}（2）應(yīng)用舉例例1求(A-B)U(B-A)voidDiff(SLinkList&Space,int&S){inti,j,k,r,m,n,p;charc;Init_SLinkList(Space);S=Malloc_SLinkList(Space);r=S;printf("inputaelemnum\n");scanf("%d",&m);getchar();for(j=1;j<=m;++j){i=Malloc_SLinkList(Space);scanf("%c",&Space[i].data);Space[r].cur=i;r=i;}Space[r].cur=0;printf("inputbelemnum\n");scanf("%d",&n);getchar();for(j=1;j<=n;j++){scanf("%c",&c);p=S;k=Space[S].cur;while(k!=Space[r].cur&&Space[k].data!=c){ p=k; k=Space[k].cur; }if(k==Space[r].cur){ i=Malloc_SLinkList(Space); Space[i].data=c; Space[i].cur=Space[r].cur; Space[r].cur=i; }else { Space[p].cur=Space[k].cur; Free_SLinkList(Space,k); if(k==r)r=p; }}}//Diff例2插入排序voidList_InseSort(SLinkLists,int&p){inti,j,q;ElemTypee;s[0].data=32767;s[0].cur=1;printf("%c",&e);s[1].data=e;s[1].cur=0;i=2;scanf("%c",&e);while(e!='\0'){s[i].data=e;p=s[0].cur;q=0;while(e>s[p].data&&s[p].cur!=0){ q=p; p=s[p].cur; }s[i].cur=p;s[q].cur=i;scanf("%c",&e);i++;}p=s[0].cur;}§2.4一元多項(xiàng)式的表示一元多項(xiàng)式的表示在計(jì)算機(jī)中，可以用一個(gè)線性表來(lái)表示：P=(p0,p1,…，pn)但是對(duì)于形如S(x)=1+3x10000–2x20000的多項(xiàng)式，上述表示也就不恰當(dāng)了。一般情況下的一元多項(xiàng)式可寫成Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指數(shù)為ei的項(xiàng)的非零系數(shù)，0≤e1<e2<┄<em=n它可以用其數(shù)據(jù)元素為(系數(shù)項(xiàng)，指數(shù)項(xiàng))的線性表來(lái)表示（（p1,e1）,(p2,e2),┄,(pm,em)）例如：線性表（(7,3),(-2,12),(-8,999)）表示多項(xiàng)式P999(x)=7x3-2x12-8x999抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：ADTPolynomial{數(shù)據(jù)對(duì)象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0}{TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,且ai-1中的指數(shù)值＜ai中的指數(shù)值，i=2,...,n}基本操作：CreatPolyn(&P,m)操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式P。DestroyPolyn(&P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。PrintPolyn(&P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式P。AddPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：Pa=Pa＋Pb，并銷毀一元多項(xiàng)式Pb。SubtractPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相減運(yùn)算，即：Pa=Pa－Pb，并銷毀一元多項(xiàng)式Pb。MultiplyPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相乘運(yùn)算，即：Pa=Pa×Pb，并銷毀一元多項(xiàng)式Pb。PolynLength(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的項(xiàng)數(shù)。}ADTPolynomial如此定義的多項(xiàng)式可以看成是一個(gè)有序表(對(duì)其數(shù)據(jù)元素中的指數(shù)項(xiàng)而言),則多項(xiàng)式定義中的各個(gè)操作均可利用有序表的操作來(lái)完成。二、基本操作的實(shí)現(xiàn)//多項(xiàng)式

#include"common.h"

#defineflag32767

typedefstructPolyNode{

floa