數(shù)據(jù)結(jié)構(gòu)（C語言版）（第三版）（微課版）課件 梁海英第1章 緒論；第2章 線性表；第3章 棧和隊列

第1章緒論教學(xué)要求相關(guān)知識點(diǎn)相關(guān)術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)數(shù)據(jù)物理結(jié)構(gòu)：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)算法的五個特征、時間復(fù)雜度及空間復(fù)雜度學(xué)習(xí)重點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其之間的關(guān)系算法時間復(fù)雜度、空間復(fù)雜度及其計算目錄常用術(shù)語和基本概念數(shù)據(jù)類型算法和算法分析3數(shù)據(jù)結(jié)構(gòu)概述124本章小結(jié)51.1數(shù)據(jù)結(jié)構(gòu)概述1.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)(DataStructure)+算法(Algorithm)=程序(Program)數(shù)據(jù)結(jié)構(gòu)的意義計算機(jī)處理數(shù)值計算問題時，所用的數(shù)學(xué)模型是用數(shù)學(xué)方程描述的。因此程序的重點(diǎn)是程序設(shè)計技巧，而不是數(shù)據(jù)的存儲和組織。計算機(jī)應(yīng)用的更多領(lǐng)域是“非數(shù)值計算問題”，它們的數(shù)學(xué)模型無法用數(shù)學(xué)方程描述，而是用線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)來描述。1.1數(shù)據(jù)結(jié)構(gòu)概述【例1.1】學(xué)生信息登記表學(xué)生信息登記表可方便完成各種數(shù)據(jù)的統(tǒng)計，比如，統(tǒng)計男生和女生的比例等。二維表(即線性表)是經(jīng)常用到的數(shù)學(xué)模型。學(xué)號姓名性別民族籍貫20240108001蘇宏男漢族貴州市20240108002梁琪女滿族四平市20240108003韋華男壯族賀州市20240108004秦婷女漢族廣州市1.1數(shù)據(jù)結(jié)構(gòu)概述【例1.2】食堂就餐排隊管理問題。食堂就餐排隊的算法是“先到的同學(xué)先打飯離開”。相應(yīng)地，隊伍管理模型是一個“隊列”，即就餐窗口的服務(wù)人員應(yīng)該先為排在“隊頭”的同學(xué)提供就餐服務(wù)；當(dāng)陸續(xù)有同學(xué)再來就餐時，讓他在“隊尾”排隊等候。隊列是經(jīng)常用到的一種數(shù)學(xué)模型。1.1數(shù)據(jù)結(jié)構(gòu)概述【例1.3】大學(xué)組織架構(gòu)。一所大學(xué)會分成多個學(xué)院，每個學(xué)院會有多個系，每個系會包含多個班級。因此，一個學(xué)校的組織架構(gòu)就是一棵倒立的“樹”。1.2常用術(shù)語

和基本概念1.2常用術(shù)語和基本概念數(shù)據(jù)(Data)數(shù)據(jù)是指所有能輸入到計算機(jī)中，并能被程序處理的符號的集合，是程序加工處理的對象。客觀事物通過編碼變成能被計算機(jī)識別和處理的符號后才是數(shù)據(jù)。數(shù)據(jù)元素(DataElement)和數(shù)據(jù)項(DataItem)數(shù)據(jù)元素在程序中通常被作為整體進(jìn)行考慮和處理的基本單位。數(shù)據(jù)元素有時也被稱為節(jié)點(diǎn)(Node)、頂點(diǎn)(Vertex)、記錄(Record)等。數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是不可分割的、含有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項有時也稱為字段(Field)或域(Domain)。1.2常用術(shù)語和基本概念數(shù)據(jù)結(jié)構(gòu)(DataStructure)數(shù)據(jù)結(jié)構(gòu)由相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicStructure)數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)學(xué)模型，與數(shù)據(jù)在計算機(jī)中的具體存儲沒有關(guān)系。是數(shù)據(jù)本身所固有的特性。從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。主要包括：集合、線性、樹形和圖形結(jié)構(gòu)，其中集合、樹形和圖形結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。1.2常用術(shù)語和基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicStructure)根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有4類基本數(shù)據(jù)結(jié)構(gòu)：(1)集合結(jié)構(gòu)(Set)：該結(jié)構(gòu)中的數(shù)據(jù)元素除了存在“同屬于一個集合”的關(guān)系外，不存在任何其它關(guān)系。(2)線性結(jié)構(gòu)(LinearStructure)：該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對一的關(guān)系。(3)樹形結(jié)構(gòu)(TreeStructure)：該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對多的關(guān)系。(4)圖形結(jié)構(gòu)(GraphicStructure)：該結(jié)構(gòu)中的數(shù)據(jù)元素存在著多對多的關(guān)系。1.2常用術(shù)語和基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)(DataStructure)1.2常用術(shù)語和基本概念【例1.4】定義集合D={3,6,9,18,27}的數(shù)據(jù)結(jié)構(gòu)。DS1=(D,R1)，其中R1定義為D上的“>”(大于)關(guān)系，則數(shù)據(jù)結(jié)構(gòu)DS1為線性結(jié)構(gòu)。DS2=(D,R2)，其中R2定義為D上的“整除”關(guān)系，則R2={(3,6),(3,9),(3,18),(3,27),(6,18),(9,18),(9,27)}，數(shù)據(jù)結(jié)構(gòu)DS2為圖狀結(jié)構(gòu)。1.2常用術(shù)語和基本概念數(shù)據(jù)的物理結(jié)構(gòu)(PhysicalStructure)。數(shù)據(jù)的物理結(jié)構(gòu)又稱為存儲結(jié)構(gòu)(StorageStructure)。數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的存儲，它包括數(shù)據(jù)元素的機(jī)內(nèi)存儲和關(guān)系的機(jī)內(nèi)存儲。數(shù)據(jù)的存儲結(jié)構(gòu)包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲結(jié)構(gòu)、散列存儲結(jié)構(gòu)，其中前兩種結(jié)構(gòu)比較常用。常用術(shù)語和基本概念數(shù)據(jù)的物理結(jié)構(gòu)(PhysicalStructure)。順序存儲結(jié)構(gòu)(SequenceStorageStructure)是通過數(shù)據(jù)元素在計算機(jī)存儲器中的相對位置來表示出數(shù)據(jù)元素的邏輯關(guān)系，一般把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置相鄰的存儲單元中。鏈?zhǔn)酱鎯Y(jié)構(gòu)(LinkedStorageStructure)對邏輯上相鄰的數(shù)據(jù)元素不要求其存儲位置必須相鄰。鏈?zhǔn)酱鎯Y(jié)構(gòu)中的數(shù)據(jù)元素稱為節(jié)點(diǎn)(Node)，在節(jié)點(diǎn)中增設(shè)地址域(AddressDomain)來存儲與該節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的地址來實(shí)現(xiàn)節(jié)點(diǎn)間的邏輯關(guān)系。常用術(shù)語和基本概念數(shù)據(jù)的運(yùn)算算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于數(shù)據(jù)采用的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)實(shí)質(zhì)上是它的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實(shí)現(xiàn)，為了全面地反映一個數(shù)據(jù)的邏輯結(jié)構(gòu)，它在存儲器中的映象包括兩方面的內(nèi)容，即數(shù)據(jù)元素之間的信息和數(shù)據(jù)元素之間的關(guān)系。不同的數(shù)據(jù)結(jié)構(gòu)有其相應(yīng)的若干運(yùn)算。數(shù)據(jù)的運(yùn)算是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的而在物理結(jié)構(gòu)上實(shí)現(xiàn)操作的算法，如查找、插入、刪除、更新和排序等。1.3數(shù)據(jù)類型1.3數(shù)據(jù)類型數(shù)據(jù)類型(本書在用C語言描述時的約定)1.表示數(shù)據(jù)結(jié)構(gòu)時，數(shù)據(jù)元素的序號從0開始。2.數(shù)據(jù)元素的類型約定為ElemType。typedefintElemType/*定義數(shù)據(jù)類型為int*/3.數(shù)據(jù)存儲結(jié)構(gòu)用類型定義(typedef)描述，如：typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;/*SqList表示順序表的類型定義*/1.3數(shù)據(jù)類型數(shù)據(jù)類型(本書在用C語言描述時的約定)4.算法以函數(shù)形式描述：類型標(biāo)識符函數(shù)名(形參表)/*算法說明*/{

函數(shù)體語句}1.4算法和算法復(fù)雜度1.4算法和算法復(fù)雜度概念算法（Algorithm）是指在有限的時間范圍內(nèi)，為解決某一問題而采取的方法和步驟的準(zhǔn)確完整的描述，它是一個有窮的規(guī)則序列，這些規(guī)則規(guī)定了解決某一特定問題的一系列運(yùn)算。1.4算法和算法復(fù)雜度算法具備以下五個特征：1．有窮性：算法必須在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮的時間內(nèi)完成。2．確定性：算法中的每一條指令都必須有明確的含義，不應(yīng)使讀者產(chǎn)生二義性。3．可行性：算法中的每個操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來完成。4．有輸入：算法有零個或多個輸入，取決于算法本身要實(shí)現(xiàn)的功能5．有輸出：算法在執(zhí)行完畢后，一定要有一個或多個結(jié)果或結(jié)論。1.4算法和算法復(fù)雜度算法效率的度量1.正確性(Correctness)：滿足預(yù)定功能和性能的要求。2.可讀性(Readability)：層次分明、簡單明了、易讀易懂。3.健壯性(Robustness)：有很強(qiáng)的容錯能力，當(dāng)輸入不合法的數(shù)據(jù)時，能做適當(dāng)?shù)奶幚恚恢劣谝饑?yán)重的后果。4.高效率：運(yùn)行時間(RunningTime)是指在計算機(jī)上算法中每條語句執(zhí)行時間的總和。執(zhí)行時間越短，性能越好。5.低存儲：占用空間(StorageSpace)是指存儲算法本身、算法的輸入及輸出數(shù)據(jù)和算法在運(yùn)行過程中臨時占用的存儲空間總和。1.4算法和算法復(fù)雜度時間復(fù)雜度（TimeComplexity）1.時間復(fù)雜度的定義一個算法花費(fèi)的時間與算法中語句的執(zhí)行次數(shù)成正比。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的函數(shù)，用T(n)表示，若有輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n))，稱Ｏ(f(n))為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。其中大寫字母O為Order(數(shù)量級)的第一個字母，f(n)為函數(shù)形式，如T(n)=O(n2)。1.4算法和算法復(fù)雜度2.時間復(fù)雜度的計算方法(1)輸入輸出語句或賦值語句所需時間O(1)；(2)順序結(jié)構(gòu)需要所用的時間采用大O下“求和法則”；求和法則：是指若算法的2個部分時間復(fù)雜度分別為T1(n)=O(f(n))和T2(n)=O(g(n)),則T1(n)+T2(n)=O(max(f(n),g(n)))。(3)選擇結(jié)構(gòu)(如if語句)的主要時間耗費(fèi)是在執(zhí)行條件成立分支或不成立分支所用的時間，需注意的是檢驗條件也需要O(1)時間；1.4算法和算法復(fù)雜度(4)循環(huán)結(jié)構(gòu)中循環(huán)語句的運(yùn)行時間在多次執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費(fèi)，用大O下“乘法法則”；乘法法則：是指若算法的2個部分時間復(fù)雜度分別為T1(n)=O(f(n))和T2(n)=O(g(n))，則T1(n)*T2(n)=O(f(n)*g(n))。①找出基本語句（執(zhí)行次數(shù)最多的最內(nèi)層循環(huán)的循環(huán)體）②計算基本語句的執(zhí)行次數(shù)的數(shù)量級只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確，可以忽略所有低次冪和最高次冪的系數(shù)。③用大Ο記號表示算法的時間復(fù)雜度將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中。1.4算法和算法復(fù)雜度【例1.5】分析下列語句的時間復(fù)雜度時間復(fù)雜度s=0;for(i=1;i<=n;i++)

s=s+i;分析：s=0;執(zhí)行1次i=1;執(zhí)行1次 i<=n;執(zhí)行n+1次s=s+i;執(zhí)行n次 i++;執(zhí)行n次總的執(zhí)行次數(shù)為3(n+1)次，因此，該算法的時間復(fù)雜度為T(n)=O(3(n+1))=O(n)。1.4算法和算法復(fù)雜度空間復(fù)雜度（SpaceComplexity）1.空間復(fù)雜度的定義空間是指執(zhí)行算法所需要的存儲空間。算法對應(yīng)程序運(yùn)行所需存儲空間包括固定和可變兩部分。固定部分所占空間主要包括程序代碼、常量、簡單變量等所占的空間；可變部分所占空間與該算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)，即所需的輔助空間?？臻g復(fù)雜度記為：S(n)=O(f(n))。程序所占固定空間變化不大，所以主要考慮算法所需可變的輔助空間。算法和算法復(fù)雜度【例1.6】分析下面程序的時間復(fù)雜度和空間復(fù)雜度。RevArray(inta[],intn){

inti,j,*b;

b=(int*)malloc(sizeof(int)*n);

for(i=0,j=n-1;i<n;i++,j--)

b[j]=a[i];

for(i=j=0;i<n;i++,j++)

a[i]=b[i];

free(b);}算法空間復(fù)雜度的分析：算法輔助空間是一個與問題規(guī)模同量級的一維數(shù)組b所占用的空間，再加兩個控制變量i和j，共n+2個，所以S(n)=n+2=O(n)。1.5本章小結(jié)1.5本章小結(jié)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等基本概念數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系數(shù)據(jù)結(jié)構(gòu)的兩大邏輯結(jié)構(gòu)和兩種常用的存儲結(jié)構(gòu)算法、算法的時間復(fù)雜度和空間復(fù)雜度的概念算法描述和算法分析的方法，對于一般算法能分析出時間復(fù)雜度和空間復(fù)雜度第2章線性表教學(xué)要求相關(guān)知識點(diǎn)相關(guān)概念：線性表、順序表、鏈表（單鏈表、循環(huán)鏈表、雙向鏈表）、頭指針、頭節(jié)點(diǎn)順序表的存儲及基本操作鏈表的存儲及基本操作學(xué)習(xí)重點(diǎn)線性表的邏輯結(jié)構(gòu)及兩種不同的存儲結(jié)構(gòu)順序表的存儲和實(shí)現(xiàn)鏈表的存儲和實(shí)現(xiàn)目錄線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)3線性表概述12本章小結(jié)42.1線性表概述2.1線性表概述線性表的定義及特點(diǎn)1.線性表的定義線性表(Linear_List)簡稱為表，是n(n≥0)個類型相同的數(shù)據(jù)元素(也叫節(jié)點(diǎn)或表元素)組成的有限序列，各數(shù)據(jù)元素之間存在線性關(guān)系，記作：(a0，a1，a2，，……ai-1，ai，ai+1，……，an-1)表中ai-1領(lǐng)先于ai，稱ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后續(xù)元素。當(dāng)0≤i≤n-2時，ai有且僅有一個直接后繼；當(dāng)1≤i≤n-1時，ai有且僅有一個直接前驅(qū)。2.1線性表概述線性表中元素的個數(shù)n(n≥0)定義為線性表的長度，當(dāng)n=0時稱該線性表為空表。非空線性表中的每一個數(shù)據(jù)元素都有一個確定的位置，如a0是最前面一個數(shù)據(jù)元素，an-1是最后面一個數(shù)據(jù)元素，ai是第i(0≤i≤n-1)個數(shù)據(jù)元素，稱i為數(shù)據(jù)元素在線性表中的位序。2.1線性表概述2.線性表的特點(diǎn)(1)唯一首元素；(2)唯一尾元素；(3)除首元素外，任何元素都有一個直接前驅(qū)；(4)除尾元素外，任何元素都有一個直接后繼；(5)每個元素有一個位序。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)線性表的順序存儲1.線性表的順序存儲原理線性表的順序存儲(SequentialMapping，簡稱順序表)，是指用一組地址連續(xù)的存儲單元按線性表元素之間的邏輯順序，依次存儲線性表的數(shù)據(jù)元素。數(shù)據(jù)元素的邏輯順序和存儲順序是完全一致的。2.順序存儲的線性表抽象數(shù)據(jù)類型的定義由于C語言的一維數(shù)組在內(nèi)存中所占的正是一個地址連續(xù)的存儲區(qū)域，因此可以用C語言的一維數(shù)組來作為線性表的順序存儲結(jié)構(gòu)。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)#defineINIT_SIZE5/*存儲空間初始分配量*/#defineINCREMENT2/*存儲空間分配增量*/typedefintElemType;/*定義元素類型為int*/typedefstruct{

ElemType*elem;/*存儲空間的基地址*/intlength;

/*當(dāng)前長度*/intlistsize;

/*當(dāng)前分配的存儲容量*/}SqList;元素位序0length-1listsize-1元素表示L.elem[0]L.elem[L.length-1]L.elem[listsize-1]內(nèi)存狀態(tài)a0an-12.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)順序表的基本操作1.順序表的初始化

intInitList_Sq(SqList*L)/*初始化順序表，成功返回1，失敗返回0*/{L->elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L->elem)return0;/*初始化失敗*/L->length=0;L->listsize=INIT_SIZE;return1;/*初始化成功*/}2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)2.順序表的插入

順序表的插入操作是指在線性表L的第i-1個元素和第i個元素之間（即在第i個位置）插入一個新的元素e。表長為n的原表{a0，a1，……ai-1，ai，ai+1，……，an-1}插入新元素后，變?yōu)楸黹L為n+1的新表{a0，a1，……ai-1，e，ai，ai+1，……，an-1}。其中需要注意的是i的取值范圍0≤i≤n，當(dāng)i=n時，表示在整個順序表的末尾插入一個元素e。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(1)插入操作需要注意的問題①順序表中數(shù)據(jù)區(qū)域分配有l(wèi)istsize個存儲單元，在進(jìn)行插入操作時需要先檢查表空間是否已滿，表滿的情況下不能再進(jìn)行插入操作，否則會產(chǎn)生內(nèi)存溢出錯誤。②要檢查插入位置的有效性，i的有效范圍是0≤i≤n，其中n為原表長度。③注意數(shù)據(jù)移動的方向為向大的下標(biāo)移動（從后開始向后移動）2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(2)算法思路在第i(0≤i≤n)個位置插入一個元素時，需將第n-1至第i(共n-i)個元素向后移動一個位置。①從后開始向后移動：將an-1～ai順序向后移動一個位置，即an-1移動到an的位置，……，ai移動到ai+1的位置，為待插入的新數(shù)據(jù)元素讓出位置i。②將e放到空出的第i個位置上。③修改線性表當(dāng)前長度length的值。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(3)算法2.2順序表的插入intListInsert_Sq(SqList*L,inti,ElemTypee)/*在順序表L的第i個位置之前插入新的元素e，若插入成功則返回1，否則返回-1*/{intj;ElemType*newbase;if(i<0||i>L->length)return-1; /*插入位置不合法，插入失敗*/2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)if(L->length>=L->listsize)

/*當(dāng)前存儲空間已滿，增加分配*/{newbase=(ElemType*)realloc(L->elem,(L->listsize+INCREMENT)*sizeof(ElemType));if(!newbase)return-1;/*存儲分配失敗，插入失敗*/L->elem=newbase;L->listsize+=INCREMENT;}2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)for(j=L->length-1;j>=i;j--)L->elem[j+1]=L->elem[j];/*插入位置及之后的元素從后開始向后移動*/L->elem[i]=e; /*插入e*/++L->length; /*表長增1*/return1; /*插入成功*/}2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(4)插入操作的時間復(fù)雜度在順序表上進(jìn)行插入操作時，其時間主要消耗在插入位置之后的若干數(shù)據(jù)元素的移動上。在第i個位置插入元素e，則從ai到an-1都要向后移動一個位置，共需要移動(n-i)個元素，平均移動數(shù)據(jù)元素的次數(shù)為可見在順序表中插入一個數(shù)據(jù)元素，平均需要移動表中一半的數(shù)據(jù)元素，其時間復(fù)雜度為O(n)。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)3.順序表的刪除

順序表的刪除操作是指將表中的第i個元素從表中刪除，刪除第i個元素后原表長為n的線性表(a0，……ai-1，ai，ai+1，……，an-1)變?yōu)楸黹L為n-1的新表(a0，……ai-1，ai+1，……，an-1)。i的有效范圍為0≤i≤n-1。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(1)刪除操作需要注意的問題①刪除第i個元素時，要刪除的元素必須真實(shí)存在，所以需要檢查i的取值是否有效，i的有效取值范圍為0≤i≤n-1，否則操作失敗。②表為空表時不能執(zhí)行刪除操作。③注意數(shù)據(jù)移動的方向為向小的下標(biāo)移動（從前開始向前移動）(2)算法思路①從前開始向前移動：將ai+1～an-1向前移動一個位置。②修改線性表當(dāng)前長度length的值。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)intListDelete_Sq(SqList*L,inti,ElemType*e){intj;if(i<0||i>L->length-1)return-1*e=L->elem[i];/*將被刪除元素的值賦給e*/for(j=i+1;j<=L->length-1;j++)L->elem[j-1]=L->elem[j];--L->length;return1; /*刪除成功*/}2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(4)刪除操作的時間復(fù)雜度在順序表上進(jìn)行刪除操作時，其時間主要消耗在刪除元素之后的其他數(shù)據(jù)元素的移位上，要刪除第i個元素，其后面的元素ai+1～an-1都要向前移動一個位置，共移動了(n-i-1)個元素，平均移動數(shù)據(jù)元素的次數(shù)為由此可見，在順序表上刪除一個數(shù)據(jù)元素，平均需要移動表中一半的數(shù)據(jù)元素，故該算法的時間復(fù)雜度為O(n)。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)4.順序表的按值查找

順序表的按值查找是指在順序表L中查找是否存在與給定值e相等的數(shù)據(jù)元素。可將e和L中的數(shù)據(jù)元素逐個比較。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(1)算法思路從最前面一個元素a0開始向后依次將順序表中的元素ai與e相比較，直到找到一個與e相等的數(shù)據(jù)元素，返回這個數(shù)據(jù)元素在表中的位置；若順序表中的所有元素都與e不相等，即查找不到與e相等的數(shù)據(jù)元素，則返回-1，表示查找失敗。也可以從最后一個元素an-1開始向前依次將順序表中的元素ai與e相比較，直到找到一個與e相等的數(shù)據(jù)元素，返回這個數(shù)據(jù)元素在表中的位置；若順序表中的所有元素都與e不相等，即查找不到與e相等的數(shù)據(jù)元素，則返回-1，表示查找失敗。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)intLocateElem_Sq(SqListL,ElemTypee)/*在順序線性表L中查找第1個值與e相等的元素的位序，若找到，則返回其在L中的位序，否則返回-1*/{inti=0;/*i的初值為最前面一個元素的位序*/while(i<L.length&&L.elem[i]!=e)i++; /*從前向后逐一比較*/if(L.elem[i]==e)returni; /*查找成功，i為與e相等的第一個元素的位序*/elsereturn-1; /*查找失敗*/}2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(2)順序表按值查找的時間復(fù)雜度算法2.4的時間主要耗費(fèi)在e與ai的比較上，而比較的次數(shù)既與e在表中的位置有關(guān)，也與表長有關(guān)。設(shè)查找成功的最好情況是當(dāng)a0=e時，比較一次就成功；最壞的情況是當(dāng)an-1=e時，需要比較n次才成功。平均比較次數(shù)為(n+1)/2，故該算法的時間復(fù)雜度為O(n)。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)5.取順序表中的元素

取表中元素是指根據(jù)所給的序號i在順序表中查找相應(yīng)數(shù)據(jù)元素的過程。(1)算法思路首先確認(rèn)所查找的數(shù)據(jù)元素序號是否合法，若合法則直接返回對應(yīng)的元素值，否則操作失敗。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)intGet_SqList(SqListL,inti,ElemType*e)/*在順序線性表L中取第i個元素存入e中，若成功，則返回1，否則返回-1*/{

if(i<0||i>L.length-1) return-1；/*沒有第i個元素,讀取失敗*/

*e=L.elem[i];return1; /*讀取成功*/}2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)(2)取順序表中元素的時間復(fù)雜度順序表是隨機(jī)存儲結(jié)構(gòu)，具有按數(shù)據(jù)元素的序號隨機(jī)存取的特點(diǎn)，所以計算任意元素的存儲地址的時間是相等的，與數(shù)據(jù)元素所在位置無關(guān)，因此算法的時間復(fù)雜度為O(1)。2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)6.順序表的應(yīng)用

【例2-1】有順序表LA和LB，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表LC，要求LC的元素也是從小到大的升序排列。算法思路：依次掃描LA和LB的元素，比較線性表LA和LB當(dāng)前元素的值，將較小值的元素賦給LC，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給LC即可。因此線性表LC的容量應(yīng)不小于線性表LA和LB長度之和。算法描述如下：2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)intMergeList_Sq(SqListLA,SqListLB,SqList*LC)/*已知順序線性表LA和LB的元素按值非遞減排列，歸并LA和LB得到新的順序線性表LC，LC的元素也按值非遞減排列，成功返回1，失敗返回-1*/{inti=0,j=0,k=0;LC->listsize=LA.length+LB.length;LC->elem=(ElemType*)malloc(LC->listsize*sizeof(ElemType));if(!LC->elem)return-1;2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)while(i<LA.length&&j<LB.length){if(LA.elem[i]<=LB.elem[j])LC->elem[k++]=LA.elem[i++];elseLC->elem[k++]=LB.elem[j++];}while(i<LA.length)LC->elem[k++]=LA.elem[i++];while(j<LB.length)LC->elem[k++]=LB.elem[j++];LC->length=k;return1;}2.2線性表的順序存儲及運(yùn)算的實(shí)現(xiàn)6.順序表的應(yīng)用

本算法的基本操作為“元素賦值”，算法的時間復(fù)雜度為2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)單鏈表1.單鏈表存儲原理線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元存放線性表的數(shù)據(jù)元素，存儲單元可以連續(xù)，也可以不連續(xù)。對每個數(shù)據(jù)元素ai，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼存放位置的指針。這兩部分信息組成數(shù)據(jù)元素ai的存儲映像，稱為節(jié)點(diǎn)（node），它包括兩個域：其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域data；存儲直接后繼存放位置的域稱為指針域next。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)n個元素的線性表通過每個節(jié)點(diǎn)的指針域鏈接成一個鏈表。由于此鏈表的每個節(jié)點(diǎn)中只有一個指向后繼的指針，所以稱其為單鏈表或線性鏈表。其中，頭指針L指向鏈表的第一個節(jié)點(diǎn)，各節(jié)點(diǎn)的指針指向下一個節(jié)點(diǎn)，而最后一個節(jié)點(diǎn)的指針為“空”（NULL）。由于從頭指針開始便可沿著鏈找到鏈表各個元素，因此，可用頭指針來存儲一個單鏈表。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)2.單鏈表數(shù)據(jù)類型定義typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;其中LNode是節(jié)點(diǎn)的類型，LinkList是指向LNode節(jié)點(diǎn)類型的指針類型。可定義一個LinkList類型的變量L，如LinkListL，作為單鏈表的頭指針，來存儲一個單鏈表。若L為“空”（L=NULL），則所存儲的線性表為“空”表，其長度n為“零”。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)若定義了如下指針LNode*p;或LinkListp;則語句p=(LNode*)malloc(sizeof(LNode))

分配一個LNode型節(jié)點(diǎn)的存儲空間，并將其地址賦值給指針變量p，p所指節(jié)點(diǎn)為*p，*p的類型為LNode型，所以該節(jié)點(diǎn)的數(shù)據(jù)域為(*p).data或p->data，指針域為(*p).next或p->next，而語句free(p)則釋放該節(jié)點(diǎn)所占用的存儲空間。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)3.建立單鏈表由于單鏈表是一種動態(tài)結(jié)構(gòu)，每個鏈表占用的空間不需要預(yù)先分配，而是由系統(tǒng)根據(jù)需要動態(tài)生成，因此，建立單鏈表的過程就是一個動態(tài)生成鏈表的過程。即從“空表”的初始狀態(tài)起，依次建立各元素節(jié)點(diǎn)，并逐個插入鏈表。單鏈表的建立可以根據(jù)線性表元素的輸入順序與單鏈表中節(jié)點(diǎn)的順序是否相同分為以下兩種方法。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(1)頭插入法建立單鏈表鏈表是一種動態(tài)管理的存儲結(jié)構(gòu)，鏈表中的每個節(jié)點(diǎn)占用的存儲空間都不需要預(yù)先分配，一般是在運(yùn)行時系統(tǒng)根據(jù)需求而實(shí)時生成的，因此建立單鏈表都是從空表開始的，頭插入法建立單鏈表也稱為逆序建表，其算法思想是建立單鏈表時每讀入一個數(shù)據(jù)元素則向系統(tǒng)申請一個節(jié)點(diǎn)空間，然后插在鏈表的頭部。如圖2.7所示為線性表(35，48，28，67，59)對應(yīng)的單鏈表建立過程，因為是在鏈表的頭部插入，所以讀入數(shù)據(jù)的順序和線性表中各數(shù)據(jù)元素的邏輯順序是相反的。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(1)頭插入法建立單鏈表2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.6頭插入法建立單鏈表LinkListCreatHead_LinkList(intn)/*建立一個單鏈表L，輸入n個元素的值*/{LinkListL=NULL;/*建立空鏈表L*/

LNode*s;

inti;

for(i=0;i<=n-1;i++){s=(LNode*)malloc(sizeof(LNode));/*生成新節(jié)點(diǎn)*/2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)printf("請輸入第%d個元素的值:",i);scanf("%d",&s->data);/*輸入元素值*/

s->next=L;

L=s;}returnL;}2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(2)尾插入法建立單鏈表在尾插入法建表過程中，每次都要將新節(jié)點(diǎn)插入鏈表的尾部，而單鏈表一般都是用頭指針來指示的，所以如果要找到單鏈表的尾部，則每插入一次都要將插入點(diǎn)指針從頭到尾掃描一遍。很明顯，這樣會耗費(fèi)很多時間在重復(fù)的掃描工作上。為了精簡算法節(jié)約運(yùn)行時間，我們這里又專門設(shè)立了一個尾指針p始終指向單鏈表中當(dāng)前的尾部節(jié)點(diǎn)，這樣便能夠?qū)⑿鹿?jié)點(diǎn)直接插入鏈表尾部，使耗費(fèi)時間為一個常量。圖2.8顯示了在單鏈表尾部插入節(jié)點(diǎn)建立鏈表的過程。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(2)尾插入法建立單鏈表2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.7尾插入法建立單鏈表LinkListCreatRear_LinkList(intn)/*建立一個單鏈表L，輸入n個元素的值*/{LinkListL=NULL; /*定義一個空表*/

LNode*s,*p=NULL;//定義新節(jié)點(diǎn)指針和尾指針

inti;

for(i=0;i<=n-1;i++){s=(LNode*)malloc(sizeof(LNode)); /*生成新節(jié)點(diǎn)*/2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)printf("請輸入第%d個元素的值:",i);scanf("%d",&s>data);/*輸入元素值*/

if(L==NULL)L=s;//插入的節(jié)點(diǎn)是最前面的節(jié)點(diǎn)

elsep->next=s;

p=s; /*p恒指向插入后的鏈表尾節(jié)點(diǎn)*/}

if(p!=NULL)p->next=NULL/*如果鏈表非空，則尾節(jié)點(diǎn)的指針域置為空*/

returnL;}2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(3)建立單鏈表的算法時間復(fù)雜度兩個算法耗費(fèi)的時間與所建立的線性表中數(shù)據(jù)元素的數(shù)量有關(guān)，其時間復(fù)雜度為O(n)。(4)建立單鏈表時特殊節(jié)點(diǎn)的特殊處理在算法2.7中，插入鏈表的最前面的節(jié)點(diǎn)是做了額外處理的，其處理方法與其他節(jié)點(diǎn)不同，因為最前面的節(jié)點(diǎn)插入時原鏈表為空表，它作為鏈表的最前面的節(jié)點(diǎn)是沒有直接前驅(qū)節(jié)點(diǎn)的，所以它的地址就是整個鏈表的起始地址，該值需要放在鏈表的頭指針變量中，而后面再插入的其他節(jié)點(diǎn)都有直接前驅(qū)，所以只需要將新建節(jié)點(diǎn)的地址放入直接前驅(qū)節(jié)點(diǎn)的指針域即可。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)4.帶頭節(jié)點(diǎn)的單鏈表在單鏈表的第一個節(jié)點(diǎn)之前附設(shè)一個節(jié)點(diǎn)，稱為頭節(jié)點(diǎn)，在頭節(jié)點(diǎn)的數(shù)據(jù)域中存放諸如線性表長度等附加信息，也可以不存放任何信息，頭節(jié)點(diǎn)的指針域指向第一個元素節(jié)點(diǎn)（首元節(jié)點(diǎn)）。此時，頭指針應(yīng)指向頭節(jié)點(diǎn)。帶頭節(jié)點(diǎn)的單鏈表為空的條件為頭節(jié)點(diǎn)的指針域為“空”，即L->next==NULL。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.8帶頭節(jié)點(diǎn)的單鏈表初始化LinkListInit_LinkList(LinkListL)/*構(gòu)建一個帶頭節(jié)點(diǎn)的空鏈表，用L返回其頭指針，若失敗則返回-1*/{L=(LNode*)malloc(sizeof(LNode));//建頭節(jié)點(diǎn)if(!L)return-1;/*分配失敗*/L->next=NULL;/*頭節(jié)點(diǎn)的指針域為空*/returnL;}

算法2.8只創(chuàng)建了一個節(jié)點(diǎn)，故時間復(fù)雜度為O(1)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.9通過尾插入法建立帶頭節(jié)點(diǎn)的單鏈表LinkListCreate_LinkList(intn)/*建立帶頭節(jié)點(diǎn)的單鏈表L，輸入n個元素的值*/{LNode*L,*p,*s;inti;L=(LNode*)malloc(sizeof(LNode));L->next=NULL;//先建立一個帶頭節(jié)點(diǎn)的單鏈表p=L;/*p的初始值指向頭節(jié)點(diǎn)*/2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)for(i=0;i<=n-1;i++){s=(LNode*)malloc(sizeof(LNode));

printf("請輸入第%d個元素的值:",i);

scanf("%d",&s->data);/*輸入元素值*/

s->next=NULL;p->next=s;/*將新節(jié)點(diǎn)插入到表尾*/

p=s;/*p恒指向插入后的鏈表尾節(jié)點(diǎn)*/}returnL;}

統(tǒng)一處理所有節(jié)點(diǎn)的插入，算法的時間復(fù)雜度為O(n)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)5.求單鏈表的表長對單鏈表求表長需要將整個鏈表從最前面的節(jié)點(diǎn)一直到最后一個節(jié)點(diǎn)掃描一遍，并用累加器統(tǒng)計所有數(shù)據(jù)元素的個數(shù)。在算法實(shí)現(xiàn)上，設(shè)指針變量為p和計數(shù)器變量為i，當(dāng)p所指向的節(jié)點(diǎn)還有后繼節(jié)點(diǎn)時，p向后移動，同時計數(shù)器自加1，一直到p指向鏈表的最后一個節(jié)點(diǎn)。根據(jù)上面我們講到的鏈表創(chuàng)建可分為帶頭節(jié)點(diǎn)和不帶頭節(jié)點(diǎn)兩種，我們分別來設(shè)計算法。需要注意的是，頭節(jié)點(diǎn)不在鏈表長度統(tǒng)計范圍之內(nèi)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.10求帶頭節(jié)點(diǎn)的表長intLength_LinkList1(LinkListL) /*當(dāng)鏈表帶頭節(jié)點(diǎn)時*/{LNode*p=L; /*p指向頭節(jié)點(diǎn)*/

inti=0; /*設(shè)計數(shù)器變量i*/

while(p->next)

{p=p->next;i++; }/*p指針依次后移*/

returni;}2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.11求不帶頭節(jié)點(diǎn)的表長intLength_LinkList2(LinkListL) {LNode*p=L;

inti;/*設(shè)計數(shù)器變量i*/

if(p==NULL)return0;//為空表返回0

i=1; /*為非空表，p指向最前面的節(jié)點(diǎn)*/

while(p->next)

{p=p->next;i++; }

returni;}2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)從算法2.10和算法2.11可以看到，計算節(jié)點(diǎn)個數(shù)時，不帶頭節(jié)點(diǎn)的單鏈表如果是空表則需要單獨(dú)處理，而帶頭節(jié)點(diǎn)的單鏈表如果是空表則不用單獨(dú)處理，所以為了處理方便，在后面編寫的算法中若不加額外說明則認(rèn)為單鏈表都是帶頭節(jié)點(diǎn)的。算法2.10和算法2.11耗費(fèi)的時間明顯與所建立的線性表中的數(shù)據(jù)元素的個數(shù)有關(guān)，因此其時間復(fù)雜度均為O(n)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)6.查找操作查找操作一般分為兩種情況：(1)按序號查找；(2)按值查找。下面分別對這兩種情況進(jìn)行介紹。(1)按序號查找從單鏈表的最前面的節(jié)點(diǎn)開始，判斷當(dāng)前節(jié)點(diǎn)是否為第i個節(jié)點(diǎn)，若是則返回該節(jié)點(diǎn)的地址指針，否則沿著指針域的指向依次向下尋找，直至表結(jié)束為止。若沒有找到第i個節(jié)點(diǎn)，則返回空。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.12單鏈表的按序號查找LNode*Get_LinkList(LinkListL,inti)/*在帶頭節(jié)點(diǎn)的單鏈表L中查找第i個元素，若成功則返回該節(jié)點(diǎn)，否則返回空*/{LNode*p=L;/*p指向單鏈表L的頭節(jié)點(diǎn)*/

intj=-1;

/*從表頭開始找，初始位置為-1*/

while(p->next!=NULL&&j<i)

{p=p->next;j++;}

if(j==i)returnp;elsereturnNULL;}時間復(fù)雜度均為O(n)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(2)按值查找從單鏈表的最前面的節(jié)點(diǎn)開始，如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域的值與給定參數(shù)e相等，則返回該節(jié)點(diǎn)在單鏈表中的位序，否則沿著指針域依次向下尋找，直到表結(jié)束為止。若表中沒有符合要求的節(jié)點(diǎn)，則返回-1。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.13單鏈表的按值查找intLocate_LinkList(LinkListL,ElemTypee)/*在帶頭節(jié)點(diǎn)的單鏈表L中查找與給定值相同的元素的位序，若成功則返回該節(jié)點(diǎn)，否則返回-1*/{LNode*p=L->next;/*p指向L的最前面節(jié)點(diǎn)*/

inti=0;/*從表頭開始找，初始位置為0*/while(p->next!=NULL&&p->data!=e){p=p->next;i++; }if(p->data==e)returni;elsereturn-1;}算法的時間復(fù)雜度為O(n)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)單鏈表7.插入操作(1)在指定節(jié)點(diǎn)后面插入新節(jié)點(diǎn)假定p指向單鏈表中的某節(jié)點(diǎn)，s指向待插入的值為e的新節(jié)點(diǎn)，在指定節(jié)點(diǎn)后面p插入新節(jié)點(diǎn)s的語句如下：s->next=p->next;p->next=s;注意：這兩條指令的先后順序不能互換，否則會使鏈表斷開，從而無法準(zhǔn)確地完成新節(jié)點(diǎn)的插入操作。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(2)在指定節(jié)點(diǎn)前面插入新節(jié)點(diǎn)設(shè)q指向單鏈表中的某節(jié)點(diǎn)，s指向待插入的新節(jié)點(diǎn)e，將s插入到q的前面。先要找到q的直接前驅(qū)p，然后再在p之后插入s即可。插入語句如下：p=L;//單鏈表頭指針Lwhile(p->next!=q)

p=p->next; /*查找q的直接前驅(qū)節(jié)點(diǎn)p*/s->next=p->next;p->next=s;2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.14單鏈表的插入intInsert_LinkList(LinkListL,inti,ElemTypee)/*在帶頭節(jié)點(diǎn)的單鏈表L中第i個位置之前插入元素e，若插入成功則返回1，否則返回-1*/{LNode*p,*s;intj;p=L;j=-1;/*從表頭開始找前驅(qū)節(jié)點(diǎn)，初始位置為-1*/while(p->next&&j<i-1)/*找第i個節(jié)點(diǎn)的前驅(qū)p*/

{p=p->next;j++;} if(!p||j>i-1)return-1;/*i值不合法*/2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)s=(LNode*)malloc(sizeof(LNode)); /*生成新節(jié)點(diǎn)*/s->data=e;s->next=p->next;p->next=s;/*實(shí)現(xiàn)插入*/return1;}因為查找某個節(jié)點(diǎn)的時間復(fù)雜度是O(n)，所以該算法的時間復(fù)雜度為O(n)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)8.刪除操作(1)刪除單鏈表的指定節(jié)點(diǎn)要刪除單鏈表的第i個節(jié)點(diǎn)q，就是讓第i-1個節(jié)點(diǎn)p的指針指向第i+1個節(jié)點(diǎn)，并釋放該節(jié)點(diǎn)所占用的存儲空間。修改指針的語句如下：p->next=q->next;free(q);該操作的時間復(fù)雜度為O(n)。要實(shí)現(xiàn)對節(jié)點(diǎn)q的刪除操作，首先要找到q的直接前驅(qū)節(jié)點(diǎn)p，然后修改其指向后繼節(jié)點(diǎn)的指針。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(2)刪除單鏈表的指定節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)如果想要刪除的是p的直接后繼節(jié)點(diǎn)(假設(shè)存在)，則可以通過下列語句來完成：q=p->next;p->next=q->next;free(q);該操作的時間復(fù)雜度為O(1)。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.15單鏈表的刪除intDelete_LinkList(LinkListL,inti,ElemType*e)/*在帶頭節(jié)點(diǎn)的單鏈表L中，刪除第i個元素，并由e返回其值，若刪除成功，則返回1，否則返回-1*/{LNode*p,*q;intj;p=L;j=-1;/*從表頭開始找前驅(qū)節(jié)點(diǎn)，初始位置為-1*/while(p->next&&j<i-1)/*找第i個節(jié)點(diǎn)的前驅(qū)p*/

{p=p->next;j++;}

if(!(p->next)||j>i-1)return-1;/*刪除位置不合理*/2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)q=p->next/*q表示被刪節(jié)點(diǎn)*/p->next=q->next;/*刪除節(jié)點(diǎn)*/*e=q->data;/*用e返回被刪節(jié)點(diǎn)數(shù)據(jù)域的值*/free(q);/*釋放節(jié)點(diǎn)*/return1;}2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)9.單鏈表的應(yīng)用【例2-2】將兩個有序鏈表La和Lb合并為一個有序鏈表。算法思路：設(shè)合并后的鏈表為Lc，無需為Lc分配新的存儲空間，可直接利用兩個鏈表中原有的節(jié)點(diǎn)來鏈接成一個新表即可。設(shè)立3個指針pa、pb和pc，其中pa和pb分別指向La和Lb中當(dāng)前待比較插入的節(jié)點(diǎn)，而pc指向Lc表中當(dāng)前最后一個節(jié)點(diǎn)，若pa->data≤pb->data，則將pa所指節(jié)點(diǎn)鏈接到pc所指節(jié)點(diǎn)之后，否則將pb所指節(jié)點(diǎn)鏈接到pc所指節(jié)點(diǎn)之后。對兩個鏈表的節(jié)點(diǎn)進(jìn)行逐次比較時，可將循環(huán)條件設(shè)為pa和pb皆非空，當(dāng)其中一個為空時，說明有一個表的元素已歸并完，只需要將另一個表的剩余段鏈接在pc所指節(jié)點(diǎn)之后即可。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)LinkListMergeList_L(LinkListLa,LinkListLb)/*單鏈表La和Lb的元素按值非遞減排列。歸并La和Lb得到新的單鏈表Lc，Lc的元素也按值非遞減排列*/{LNode*pa,*pb,*pc,*Lc;pa=La->next;pb=Lb->next;Lc=pc=La;/*用La的頭節(jié)點(diǎn)作為Lc的頭節(jié)點(diǎn)*/

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;}}。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)

pc->next=pa?pa:pb;/*插入剩余段*/free(Lb);/*釋放Lb的頭節(jié)點(diǎn)*/returnLc;}。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)循環(huán)鏈表最后一個節(jié)點(diǎn)的指針域指向表頭節(jié)點(diǎn)，整個鏈表形成一個環(huán)。從表中任一節(jié)點(diǎn)出發(fā)均可找到鏈表中其它節(jié)點(diǎn)，如圖2.13所示。（b）空表（a）非空表2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)循環(huán)鏈表循環(huán)鏈表的操作與單鏈表基本一致，差別僅在于算法中判斷到達(dá)表尾的條件不是p或p->next是否為空，而是它們是否等于頭指針。使用圖2.13結(jié)構(gòu)時，為了找到最后一個節(jié)點(diǎn)，必須從表頭H去訪問每一個節(jié)點(diǎn)，而由于從循環(huán)鏈表的任一節(jié)點(diǎn)出發(fā)均可找到鏈表中其它節(jié)點(diǎn)，因此可改變一下鏈表的標(biāo)識方法，不用頭指針而用一個指向表尾節(jié)點(diǎn)的尾指針R來標(biāo)識，這樣，從尾節(jié)點(diǎn)的指針域立即可以得到表頭節(jié)點(diǎn)的地址，無論是查找第一個節(jié)點(diǎn)還是查找最后一個節(jié)點(diǎn)都很方便，并可使某些操作簡化。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)循環(huán)鏈表對例2.2中的兩個單循環(huán)鏈表L1、L2進(jìn)行連接操作，即將L2的第一個數(shù)據(jù)元素節(jié)點(diǎn)連接到L1的尾節(jié)點(diǎn)之后。若兩個單循環(huán)鏈表均通過頭指針h1、h2指示頭節(jié)點(diǎn)，則需要從頭節(jié)點(diǎn)開始依次搜索整個鏈表來找到單循環(huán)鏈表L1的尾節(jié)點(diǎn)，再完成相關(guān)連接工作，其時間復(fù)雜度為O(n1)。兩個單循環(huán)鏈表若通過尾指針r1、r2指示表尾節(jié)點(diǎn)來標(biāo)識單循環(huán)鏈表，則時間復(fù)雜度可優(yōu)化為O(1)。兩個單循環(huán)鏈表的連接過程如圖2.14所示。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)連接的具體代碼語句如下：q=r1->next; /*保存L1的頭節(jié)點(diǎn)指針*/r1->next=r2->next->next;

/*L1和L2的尾頭連接*/free(r2->next); /*釋放L2的頭節(jié)點(diǎn)*/r2->next=q; /*組成大的循環(huán)鏈表*/2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)雙向鏈表單鏈表節(jié)點(diǎn)中只有一個指向其后繼節(jié)點(diǎn)的指針域next，若已知某個節(jié)點(diǎn)，要找其前趨節(jié)點(diǎn)，則只能從表頭指針出發(fā)。也就是說，找后繼的時間復(fù)雜度為1，而找前趨的時間復(fù)雜度為O(n)，如果也希望找前趨的時間復(fù)雜度也為1，則需付出空間的代價，在每個節(jié)點(diǎn)中再設(shè)一個指向前趨的指針域，節(jié)點(diǎn)結(jié)構(gòu)如圖2.15所示，由這種節(jié)點(diǎn)組成的鏈表稱為雙向鏈表。圖2.15雙向鏈表的節(jié)點(diǎn)結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)1.雙向鏈表的存儲結(jié)構(gòu)描述typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)在雙向鏈表中，若p為指向表中某一節(jié)點(diǎn)的指針，則顯然有：p->next->prior=

=

p->prior->next==p在雙向鏈表中，有些操作，如ListLength、GetElem和LocateElem等僅需涉及一個方向的指針，則它們的算法描述和單鏈表的操作相同，但在插入、刪除時，在雙向鏈表中需同時修改兩個方向上的指針，下面是插入和刪除操作的過程。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)2.帶頭節(jié)點(diǎn)的雙向循環(huán)鏈表可以對前向單鏈表也同樣增加一個頭節(jié)點(diǎn)，如果把雙向鏈表的前向單鏈表和后向單鏈表共用一個頭節(jié)點(diǎn)首尾相接，構(gòu)成一個雙向循環(huán)鏈表，則就能統(tǒng)一了兩條鏈表的刪除算法，而且同時又具備了循環(huán)鏈表的優(yōu)點(diǎn)。帶頭節(jié)點(diǎn)的雙向循環(huán)鏈表如圖2.16所示。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)3.雙向鏈表的插入和刪除操作(1)雙向鏈表的插入操作設(shè)p指向雙向鏈表中某節(jié)點(diǎn)，s指向待插入的值為x的新節(jié)點(diǎn)，在p節(jié)點(diǎn)之前插入為s節(jié)點(diǎn)的操作如下：①s->prior=p->prior;

②p->prior->next=s;③s->next=p;

④p->prior=s;①必須在④前完成，否則*p的前趨節(jié)點(diǎn)的指針就丟失了。2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.16雙向循環(huán)鏈表的插入voidinselem(DuLinkListL,ElemTypee,DuLNode*p)/*設(shè)L為雙向循環(huán)鏈表，在p的節(jié)點(diǎn)之后插入s新節(jié)點(diǎn)*/{DuLNode*s,*r;

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

s->data=e; /*建立一個新節(jié)點(diǎn)s*/

r=p->next;

s->next=r;

r->prior=s; /*插在節(jié)點(diǎn)p之后*/

p->next=s;

s->prior=p;}2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)(2)雙向鏈表的刪除操作帶頭節(jié)點(diǎn)的雙向循環(huán)鏈表的插入與刪除操作的邏輯結(jié)構(gòu)如圖2.19所示，算法2.18是刪除地址為p的節(jié)點(diǎn)操作。圖2.19雙向鏈表中節(jié)點(diǎn)的刪除2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)算法2.18雙向循環(huán)鏈表的刪除voiddelelm(DuLinkListL,DuLNode*p)//設(shè)L為雙向循環(huán)鏈表的頭節(jié)點(diǎn)，刪除地址為p的節(jié)點(diǎn){DuLNode*q,*r;

q=p->prior;

r=p->next;

q->next=r;

r->prior=q;

free(p);}2.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算的實(shí)現(xiàn)3.雙向鏈表的插入和刪除操作由算法2.16和算法2.18可知，如果不計算查找節(jié)點(diǎn)的插入位置，則插入只需要修改四個指針，刪除只要修改兩個指針。而考慮查找，則和單鏈表相同，仍需要O(n)階的時間，但是每個節(jié)點(diǎn)卻要多占用一個指針的存儲空間，這是雙向鏈表額外耗費(fèi)的資源。2.4本章小結(jié)2.4本章小結(jié)小結(jié)本章所討論的線性表的各種存儲方法之間的關(guān)系如下所示。2.4本章小結(jié)順序表和鏈表的比較線性表的兩種存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)：1）順序表可以實(shí)現(xiàn)對表中元素的隨機(jī)存取，但在進(jìn)行插入或刪除操作時，需要移動大量元素。2）鏈表能合理利用存儲空間，插入刪除操作不需要移動大量元素，但不能實(shí)現(xiàn)元素的隨機(jī)存取。若主要進(jìn)行元素存取操作，則宜選用順序存儲結(jié)構(gòu)，若主要進(jìn)行插入、刪除操作，則宜選用鏈?zhǔn)酱鎯Y(jié)構(gòu)。由于鏈表在空間的合理利用上以及插入、刪除時不需要移動等優(yōu)點(diǎn)，因此在很多場合下，它是線性表的首選存儲結(jié)構(gòu)。第3章棧和隊列教學(xué)要求相關(guān)知識點(diǎn)相關(guān)術(shù)語：棧、隊列物理結(jié)構(gòu)：順序棧、鏈棧、順序隊列、鏈隊列學(xué)習(xí)重點(diǎn)棧的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法隊列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法目錄隊列本章小結(jié)3棧123.1棧3.1棧棧的定義棧(Stack)是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(base)。不含任何數(shù)據(jù)元素的棧稱為空棧。假設(shè)棧S=（a0，a1，…，an-1），則稱a0為棧底元素，an-1為棧頂元素。棧中元素按a1，a2，…，an-1的順序進(jìn)棧，退棧從棧頂元素開始出棧。所以，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧又稱為后進(jìn)先出（LIFO：lastinfirstout）的線性表。3.1棧棧的順序存儲與操作1.順序棧的定義順序棧是指利用順序存儲分配方式來實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。通常用一維數(shù)組存儲數(shù)據(jù)元素，并預(yù)設(shè)一個最大空間。把數(shù)組中下標(biāo)為0的一端作為棧底，為了指示棧中元素的位置，定義top指示棧頂元素在順序棧中的位置。3.1棧順序棧分為靜態(tài)順序存儲和動態(tài)順序存儲，靜態(tài)順序存儲的棧一次性分配空間，在棧滿后不能追加空間進(jìn)行入棧操作，而動態(tài)順序存儲是在靜態(tài)順序存儲的基礎(chǔ)上增加了可追加空間的功能。靜態(tài)存儲是將top定義為整數(shù)，而動態(tài)存儲是將top定義為指針。top可以指向棧頂元素的下一個位置，也可以指向棧頂元素。3.1棧(1)棧的靜態(tài)分配順序存儲結(jié)構(gòu)描述#defineMaxSize100 /*定義靜態(tài)棧最大長度*/typedefstruct{SElemTypebase[MaxSize];/*定義一個存放棧數(shù)據(jù)元素的一維數(shù)組*/inttop;/*棧頂指針*，可以指向棧頂元素的下一位置或者指向棧頂元素/intStackSize;/*存儲順序棧的當(dāng)前長度*/}SeqStack;3.1棧我們使用數(shù)組來實(shí)現(xiàn)棧中元素的存儲，并設(shè)存儲棧元素的數(shù)組長度為StackSize。當(dāng)棧滿時再進(jìn)行進(jìn)棧運(yùn)算必定產(chǎn)生溢出，簡稱“上溢”；當(dāng)?？諘r再做退棧運(yùn)算也將產(chǎn)生溢出，簡稱“下溢”。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免。下溢是正常現(xiàn)象，常常用來作為程序控制轉(zhuǎn)移的條件。3.1棧①top為整數(shù)且指向棧頂元素的下一個位置當(dāng)top為整數(shù)且指向棧頂元素的下一個位置時，初始化條件為S.top=0。(a)?？誗.top==0(b)入棧S.base[S.top++]=e3.1棧(c)棧滿S.top>=MaxSize

(d)出棧*e=S.base[--S.top]3.1棧②top為整數(shù)且指向棧頂元素當(dāng)top為整數(shù)且指向棧頂元素時，初始化條件S.top=-1(a)?？誗.top==-1(b)元素入棧S.base[++S.top]=e3.1棧

(c)棧滿S.top>=MaxSize-1

(d)元素出棧*e=S.base[S.top--]3.1棧(2)棧的動態(tài)分配順序存儲結(jié)構(gòu)描述棧的動態(tài)分配順序存儲結(jié)構(gòu)是通過將top定義為指針來實(shí)現(xiàn)的。#defineSTACK_INIT_SIZE10 /*存儲空間初始化分配量*/#defineSTACK_INCREMENT2 /*存儲空間分配增量*/typedefintSElemType;3.1棧typedefstructSqStack{SElemType*base;/*棧底指針，始終指向棧底的位置*/int*top; /*棧頂指針，可以指向棧頂元素的下一個位置或者指向棧頂元素*/intStackSize; /*當(dāng)前分配的?？墒褂玫囊栽貫閱挝坏淖畲蟠鎯θ萘?/}SqStack; /*順序棧*/3.1棧①top為指針且指向棧頂元素的下一個位置當(dāng)top為指針且指向棧頂元素的下一個位置時，初始化條件為S.top=S.base。(a)?？誗.top==S.base

(b)元素入棧*S.top++=e3.1棧(c)棧滿S.top-S.base>=StackSize

(d)元素出棧*e=*--S.top3.1棧②top為指針且指向棧頂元素當(dāng)top為指針且指向棧頂元素時，初始化條件為S.top=S.base-1。(a)?？誗.top==S.base-1(b)元素入棧*++S.top=e3.1棧

(c)棧滿S.top-S.base+1>=StackSize

(d)元素出棧*e=*S.top--3.1棧2.順序棧的基本操作（top為指針且指向棧頂元素下一個位置的動態(tài)順序棧存儲的基本操作）(1)構(gòu)造一個空棧SintInitStack(SqStack*S)/*成功返回1失敗返回0*/{S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S->base)return0;/*存儲分配失敗*/S->top=S->base;//top為指針且指向棧頂元素下一個位置S->StackSize=STACK_INIT_SIZE;return1;}3.1棧(2)銷毀棧算法3.2銷毀棧voidDestroyStack(SeqStack*S){if(S!=NULL){free(S->base);/*釋放棧*/S->top=S->base=NULL;//top為指針且指向棧頂元素下一個位置S->StackSize=0;}}3.1棧(3)清空棧voidClearStack(SqStack*S){S->top=S->base;}//top為指針且指向棧頂元素下一個位置(4)判斷一個棧是否為空intStackEmpty(SqStackS)/*若棧S為空棧，則返回1，否則返回0*/{if(S.top==S.base)return1;elsereturn0;}3.1棧(5)求棧的長度算法3.5求一個棧的長度intLengthStack(SqStackS){if((S.base)&&(S.top))

return(S.top-S.base);//top為指針且指向棧頂元素下一個位置}3.1棧(6)取棧頂元素算法3.6取棧頂元素intGetTop(SqStackS,SElemType*e)/*若棧不空，則用e返回S的棧頂元素，并返回1；否則返回0*/{if(S.top>S.base)//top為指針且指向棧頂元素下一個位置{*e=*(S.top-1);return1;}elsere