數(shù)據(jù)結構教案

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

#defineFALSE0

#defineOK1

#defineERROR0

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

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

{

intlength,i,data;

printf("輸入表的長度\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())的實現(xiàn)：intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序線性表L中查找第1個值與e滿足compare()的元素的位序。//若找到，則返回其在L中的位序，否則返回0。i=1;//i的初值為第1元素的位序p=L.elem;//p的初值為第1元素的存儲位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq此算法的時間復雜度為:O(ListLength(L))4、線性表操作ListInsert(&L,i,e)的實現(xiàn)：問：插入元素時，線性表的邏輯結構發(fā)生什么變化？(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)StatusListInsert_Sq(SqList&L,intpos,ElemTypee){//在順序線性表L的第pos個元素之前插入新的元素e，//pos的合法值為1≤pos≤Listlength_Sq(L)+1if(pos<1||pos>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){//當前存儲空間已滿，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲分配失敗L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存儲容量}q=&(L.elem[pos-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長增1returnOK;}//ListInsert_Sq性能分析：從I位置插入x，ai到an都要后移，共需移動n-I+1個元素，1≤i≤n+1，平均移動次數(shù)：，令，此算法的時間復雜度為:O(ListLength(L))5、線性表操作ListDelete(&L,i,&e)的實現(xiàn)：問：刪除元素時，線性表的邏輯結構發(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個元素，并用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;//表長減1returnOK;}//ListDelete_Sq性能分析：刪除第I個元素，aI+1到an都要前移，共需移動n-I個元素，1≤i≤n，平均移動次數(shù)：，令，則此算法的時間復雜度為:O(ListLength(L))應用舉例例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、將一個線性表分兩部分，其中前面的比a1小，后面的比a1大//將表分成兩部分,前面的比原來的第一元素小,后面的比第一個大

①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線性表類型的鏈式映象和基本操作的實現(xiàn)由于線性表的順序存儲是用物理位置上的相鄰實現(xiàn)了邏輯上的相鄰，因此對元素插入或移動時，運行效率低，但可以隨機存取任一元素，鏈式存儲不需用地址連續(xù)的存儲單元來實現(xiàn)，它通過鏈表來實現(xiàn)邏輯上的相鄰，但同時失去了順序表可隨機存取的優(yōu)點。一、單鏈表1．定義：用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素，以元素(數(shù)據(jù)元素的映象)+指針(指示后繼元素存儲位置的)=結點(表示數(shù)據(jù)元素)，以“結點的序列”表示線性表稱作鏈表，以線性表中第一個數(shù)據(jù)元素a1的存儲地址作為線性表的地址，為線性表的頭指針2．結點的C語言描述typedefstructLNode{ElemTypedata;//數(shù)據(jù)域structLnode*next;//指針域}LNode,*LinkList;二、單鏈表操作的實現(xiàn)1．voidCreateList_L(LinkList&L,intn){//逆位序輸入n個元素的值，建立帶表頭結點的單鏈線性表L。L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個帶頭結點的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新結點scanf(&p->data);//輸入元素值p->next=L->next;L->next=p;//插入到表頭}}//CreateList_L算法的時間復雜度為:O(Listlength(L))建立LinkListCreaList1()

{//逆位序輸入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個元素的值，建立帶表頭結點的單鏈線性表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)在鏈表中的實現(xiàn):基本操作為:使指針p始終指向線性表中第j個數(shù)據(jù)元素StatusGetElem_L(LinkListL,intpos,ElemType&e){//L為帶頭結點的單鏈表的頭指針。當線性表中存在第pos個元素存在時，則將第pos個數(shù)據(jù)元素的值賦給e并返回OK，否則返回ERRORp=L->next;j=1;//初始化，p指向第一個結點，j為計數(shù)器while(p&&j<pos){//順指針向后查找，直到p指向第pos個元素或p為空p=p->next;++j;}if(!p||j>pos)returnERROR;//第pos個元素不存在e=p->data;//取第pos個元素returnOK;}//GetElem_L算法的時間復雜度為:O(ListLength(L))3．線性表的操作ListInsert(&L,i,e)在鏈表中的實現(xiàn):基本操作為:找到線性表中第i-1個結點，修改其指向后繼的指針，有序對<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>StatusListInsert_L(LinkListL,intpos,ElemTypee){//在帶頭結點的單鏈表L中第pos個數(shù)據(jù)元素之前插入數(shù)據(jù)元素ep=L;j=0;while(p&&j<pos-1){p=p->next;++j;}//尋找第pos-1個結點if(!p||j>pos-1)returnERROR;//pos小于1或者大于表長s=(LinkList)malloc(sizeof(LNode));//生成新結點s->data=e;s->next=p->next;//插入L中p->next=s;returnOK;}//LinstInsert_L算法的時間復雜度為:O(ListLength(L))StatusListInsert_L(LinkListL,intpos,ElemTypee){//在沒有頭結點的單鏈表L中第pos個數(shù)據(jù)元素之前插入數(shù)據(jù)元素es=(LinkList)malloc(sizeof(LNode));//生成新結點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個結點if(!p||j>pos-1)returnERROR;//pos小于1或者大于表長s->next=p->next;//插入L中p->next=s;}returnOK;}//LinstInsert_L4．線性表的操作ListDelete(&L,i,&e)在鏈表中的實現(xiàn):基本操作為:找到線性表中第i-1個結點，修改其指向后繼的指針，有序對<ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>StatusListDelete_L(LinkListL,intpos,ElemType&e){//在帶頭結點的單鏈表L中，刪除第pos個元素，并由e返回其值p=L;j=0;while(p->next&&j<pos-1){//尋找第pos個結點，并令p指向其前趨p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結點e=q->data;free(q);returnOK;}//ListDelete_L算法的時間復雜度為:O(ListLength(L))StatusListDelete_L(LinkListL,intpos,ElemType&e){//在沒有頭結點的單鏈表L中，刪除第pos個元素，并由e返回其值if(pos==1)L=L->next;else{p=L;j=0;while(p->next&&j<pos-1){//尋找第pos個結點，并令p指向其前趨p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結點e=q->data;free(q);}returnOK;}//ListDelete_L算法的時間復雜度為:O(ListLength(L))5.求表的長度：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應用舉例例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：兩個鏈表的合并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，寫一算法，刪除其重復結點(北京工業(yè)大學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：逆向合并(中國科技大學97年研究生入學試題）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中(清華大學94年研究生入學試題）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;}用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的問題：1．單鏈表的表長是一個隱含的值；2．在單鏈表的最后一個元素最后插入元素時，需遍歷整個鏈表；3．在鏈表中，元素的“位序”概念淡化，結點的“位置”概念強化。改進鏈表的設置：1．增加“表長”、“表尾指針”和“當前位置的指針”三個數(shù)據(jù)域；2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”*四、一個帶頭結點的線性鏈表類型typedefstructLNode{//結點類型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//鏈表類型Linkhead,tail;//指向頭結點和最后一個結點intlen;//指示鏈表長度Linkcurrent;//指向當前訪問的結點的指針，//初始位置指向頭結點}LinkList.StatusMakeNode(Link&p,ElemTypee);//分配由p指向的值為e的結點，并返回OK；若分配失敗，則返回ERRORvoidFreeNode(Link&p);//釋放p所指結點鏈表的基本操作:{結構初始化和銷毀結構}StatusInitList(LinkList&L);//構造一個空的線性鏈表L，//頭指針、尾指針和當前指針均指向頭結點，表長為零StatusDestroyList(LinkList&L);//銷毀線性鏈表L，L不再存在{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//求表長StatusPrior(LinkListL);//改變當前指針指向其前驅StatusNext(LinkListL);//改變當前指針指向其后繼ElemTypeGetCurElem(LinkListL);//返回當前指針所指數(shù)據(jù)元素StatusLocatePos(LinkListL,inti);//改變當前指針指向第i個結點StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//若存在與e滿足函數(shù)compare()判定關系的元素，則移動當前指針指向第1個滿足條件的元素，并返回OK;否則返回ERRORStatusListTraverse(LinkListL,Status(*visit)());//依次對L的每個元素調用函數(shù)visit(){加工型操作}StatusClearList(LinkList&L);//重置為空表StatusSetCurElem(LinkList&L,ElemTypee);//更新當前指針所指數(shù)據(jù)元素StatusAppend(LinkList&L,Links);//一串結點鏈接在最后一個結點之后StatusInsAfter(LinkList&L,ElemTypee);//將元素e插入在當前指針之后StatusDelAfter(LinkList&L,ElemType&e);//刪除當前指針之后的結點{這里定義的大部分算法都將結點和指針的概念封裝在算法中}StatusInsAfter(LinkList&L,ElemTypee){//若當前指針在鏈表中，則將數(shù)據(jù)元素e插入在線性鏈表L中，當前指針所指結點之后,并返回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){//若當前指針及其后繼在鏈表中，則刪除線性鏈表L中當前指針所指結點之后的結點，并返回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){//在帶頭結點的單鏈線性表L的第i個元素之前插入元素eif(!LocatePos(L,i-1))returnERROR;//i值不合法if(InsAfter(L,e))returnOK;//插入在第i-1個結點之后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;//存儲空間分配失敗LocatePos(La,0);LocatePos(Lb,0);//當前指針指向頭結點if(DelAfter(La,e))a=e;elsea=MAXC;//MAXC為常量最大值if(DelFirst(Lb,e))b=e;elseb=MAXC;//a和b為兩表中當前比較元素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)鏈表最后一個結點的指針域的指針又指回第一個結點的鏈表（將在多項式中詳細說明）通常在實際的操作中，保留尾結點的地址，這樣合并時比較容易p=r1->next;r1->next=r2->next->next;r2->next=p;例如：猴子選大王（復旦大學97年研究生入學試題）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）//-----線性表的雙向鏈表存儲結構-----typedefstructDuLNode{ElemTypedata;//數(shù)據(jù)域structDuLNode*prior;//指向前驅的指針域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得到某個元素的值或地址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插入某個元素：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刪除某個元素：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）應用舉例例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一元多項式的表示一元多項式的表示在計算機中，可以用一個線性表來表示：P=(p0,p1,…，pn)但是對于形如S(x)=1+3x10000–2x20000的多項式，上述表示也就不恰當了。一般情況下的一元多項式可寫成Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指數(shù)為ei的項的非零系數(shù)，0≤e1<e2<┄<em=n它可以用其數(shù)據(jù)元素為(系數(shù)項，指數(shù)項)的線性表來表示（（p1,e1）,(p2,e2),┄,(pm,em)）例如：線性表（(7,3),(-2,12),(-8,999)）表示多項式P999(x)=7x3-2x12-8x999抽象數(shù)據(jù)類型一元多項式的定義如下：ADTPolynomial{數(shù)據(jù)對象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0}{TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)}數(shù)據(jù)關系：R1＝{<ai-1,ai>|ai-1,ai∈D,且ai-1中的指數(shù)值＜ai中的指數(shù)值，i=2,...,n}基本操作：CreatPolyn(&P,m)操作結果：輸入m項的系數(shù)和指數(shù)，建立一元多項式P。DestroyPolyn(&P)初始條件：一元多項式P已存在。操作結果：銷毀一元多項式P。PrintPolyn(&P)初始條件：一元多項式P已存在。操作結果：打印輸出一元多項式P。AddPolyn(&Pa,&Pb)初始條件：一元多項式Pa和Pb已存在。操作結果：完成多項式相加運算，即：Pa=Pa＋Pb，并銷毀一元多項式Pb。SubtractPolyn(&Pa,&Pb)初始條件：一元多項式Pa和Pb已存在。操作結果：完成多項式相減運算，即：Pa=Pa－Pb，并銷毀一元多項式Pb。MultiplyPolyn(&Pa,&Pb)初始條件：一元多項式Pa和Pb已存在。操作結果：完成多項式相乘運算，即：Pa=Pa×Pb，并銷毀一元多項式Pb。PolynLength(P)初始條件：一元多項式P已存在。操作結果：返回一元多項式P中的項數(shù)。}ADTPolynomial如此定義的多項式可以看成是一個有序表(對其數(shù)據(jù)元素中的指數(shù)項而言),則多項式定義中的各個操作均可利用有序表的操作來完成。二、基本操作的實現(xiàn)//多項式

#include"common.h"

#defineflag32767

typedefstructPolyNode{

floa