數(shù)據(jù)結(jié)構單元1引例冒泡排序算法分析和每個人的學習效率、工作效率一樣，算法也有自己的運行效率。請分析下面一段算法的時間復雜度，它是用冒泡排序法對數(shù)組a中的n個整型數(shù)據(jù)進行從小到大排序，代碼如圖。引例描述：冒泡排序算法分析素質(zhì)小課堂：學習的“新發(fā)展理念”“欲窮千里目，更上一層樓?！痹趶男〉酱蟮呐判蜻^程中認識到珍惜時間的同時，要學會把“創(chuàng)新、協(xié)調(diào)、綠色、開放、共享”的新發(fā)展理念運用到專業(yè)知識的學習中。

分析引例分析與實現(xiàn)基本操作語句為標記（1）處數(shù)據(jù)之間兩兩比較語句以及標記（2）-（4）處數(shù)據(jù)兩兩交換語句；外層循環(huán)執(zhí)行n-1次內(nèi)層循環(huán)執(zhí)行n-i次若初始序列a中的數(shù)據(jù)已按關鍵字排好序，則交換數(shù)據(jù)的次數(shù)為0；反之，若初始序列中的數(shù)據(jù)按逆序排列，則每比較一次就要交換一次，且交換數(shù)據(jù)時移動數(shù)據(jù)的次數(shù)約為3n2/2。總的時間復雜度為O(n2)數(shù)據(jù)結(jié)構常州信息職業(yè)技術學院感謝您的耐心觀看數(shù)據(jù)結(jié)構主講人：張靜常州信息職業(yè)技術學院1.1數(shù)據(jù)結(jié)構的基本概念Part01基本概念和術語數(shù)據(jù)是信息的載體。數(shù)據(jù)是對客觀事物的邏輯歸納，是能夠被計算機識別、存儲和加工處理的數(shù)字、字符以及各種符號集合的統(tǒng)稱，是計算機程序加工的“原料”。姚明的身高為226厘米，是關于姚明身高的描述數(shù)據(jù)。數(shù)據(jù)（Data）示例基本概念和術語截止2020年3月31日，全球新冠肺炎確診病例80萬例。是全球新冠肺炎確診病例的時間和人數(shù)數(shù)據(jù)。數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，也稱為結(jié)點、頂點、記錄等，在計算機程序中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可以是一個不可分割的原子項，也可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)元素（DataElement）示例基本概念和術語圖書的信息包括：書號、書名、作者、出版社。一本圖書的信息就是一個數(shù)據(jù)元素。數(shù)據(jù)項是數(shù)據(jù)元素中具有獨立含義的最小標識單位，也稱為字段、域、屬性。數(shù)據(jù)項（DataItem）基本概念和術語姚明的的身高數(shù)據(jù)是一個不可再分的整型數(shù)據(jù)，這個整數(shù)既是數(shù)據(jù)元素也是數(shù)據(jù)項；示例一本圖書數(shù)據(jù)元素由書號、書名、作者、出版社等4個數(shù)據(jù)項組成。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。性質(zhì)相同指的是數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項。數(shù)據(jù)對象（DataObject）示例基本概念和術語每本圖書都有書號、書名、作者、出版社等相同的數(shù)據(jù)項?；靖拍詈托g語12存儲結(jié)構數(shù)據(jù)元素及其關系在計算機中的存儲表示或?qū)崿F(xiàn)，也稱為物理結(jié)構。數(shù)據(jù)的運算初始化、判斷是否為空、存取、遍歷、插入、刪除、更新、查找、排序。邏輯結(jié)構數(shù)據(jù)的邏輯結(jié)構是從具體問題抽象出來的數(shù)學模型，是數(shù)據(jù)元素之間的邏輯關系。數(shù)據(jù)的邏輯結(jié)構、數(shù)據(jù)的存儲結(jié)構、數(shù)據(jù)的運算（操作或算法）。數(shù)據(jù)結(jié)構書號書名作者出版社單價出版日期9787040528121計算機應用基礎任務化教程眭碧霞高等教育出版社49.52019.129787040527735信息技術基礎眭碧霞、張靜高等教育出版社39.52019.109787040487282數(shù)據(jù)結(jié)構(C語言描述)(第2版)李學剛高等教育出版社38.12018.039787040509946軟件開發(fā)與項目管理（第2版）朱利華高等教育出版社49.52019.019787040496628JavaEE企業(yè)級項目開發(fā)蔣衛(wèi)祥高等教育出版社47.42018.06Part02數(shù)據(jù)的邏輯結(jié)構數(shù)據(jù)的邏輯結(jié)構常被簡稱為數(shù)據(jù)結(jié)構，分為線性結(jié)構和非線性結(jié)構兩種，非線性結(jié)構主要包括樹形結(jié)構和圖狀結(jié)構。邏輯結(jié)構線性結(jié)構是數(shù)據(jù)元素之間具有線性關系的數(shù)據(jù)結(jié)構，數(shù)據(jù)元素之間形成一對一的關系。它的特征是：除第一個和最后一個元素外，每個數(shù)據(jù)元素有且僅有一個直接前驅(qū)和一個直接后繼元素，第一個元素只有一個直接后繼元素，最后一個元素只有一個直接前驅(qū)元素。數(shù)據(jù)的邏輯結(jié)構1.線性結(jié)構ABCD非線性結(jié)構之一。除了根結(jié)點和葉子結(jié)點之外，樹中任意一個結(jié)點只有一個直接前驅(qū)結(jié)點（父結(jié)點）和多個直接后繼結(jié)點（孩子結(jié)點），根結(jié)點沒有前驅(qū)結(jié)點，葉子結(jié)點沒有后繼結(jié)點。數(shù)據(jù)的邏輯結(jié)構2.樹形結(jié)構ABCDEFG根結(jié)點葉子結(jié)點圖狀結(jié)構也是非線性結(jié)構，數(shù)據(jù)元素之間存在多對多的關系，每個數(shù)據(jù)元素可有多個前驅(qū)元素和多個后繼元素。數(shù)據(jù)的邏輯結(jié)構3.圖狀結(jié)構ABCDEFG集合結(jié)構中的數(shù)據(jù)元素除了屬于同一個集合外，它們之間沒有其他關系。各個數(shù)據(jù)元素是“平等”的，它們的共同關系就只是屬于同一個集合。數(shù)據(jù)的邏輯結(jié)構4.集合結(jié)構Part03數(shù)據(jù)的存儲結(jié)構數(shù)據(jù)的存儲結(jié)構主要有兩種：順序存儲和鏈式存儲。為了加快查找速度，引入了索引（分塊）查找和散列（哈希）查找。因此，從形式上看有4種物理存儲方式，但算法實現(xiàn)主要采用順序存儲和鏈式存儲。存儲結(jié)構把數(shù)據(jù)元素依次存放在一組地址連續(xù)的存儲單元里，數(shù)據(jù)元素的物理存儲次序和它們的邏輯次序相同，即邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元中。通常，使用數(shù)組來實現(xiàn)順序存儲結(jié)構。數(shù)據(jù)的存儲結(jié)構1.順序存儲結(jié)構地址數(shù)據(jù)3000H273004H653008H43300CH893010H103014H3763018H

示例：序列A=(27,65,43,89,10,376)的順序存儲結(jié)構把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，通常，需要采用指針變量來記載前驅(qū)和后繼元素的存儲地址。數(shù)據(jù)的存儲結(jié)構2.鏈式存儲結(jié)構示例：序列A=(27,65,43,89,10,376)的鏈式存儲結(jié)構數(shù)據(jù)的存儲結(jié)構23索引散列建立附加的索引表來標識數(shù)據(jù)元素的地址。它不是獨立的存儲結(jié)構，只是為了在查找運算時，能夠減少查找的時間，提高數(shù)據(jù)查找的性能。3.索引存儲結(jié)構根據(jù)結(jié)點的關鍵字直接計算出該結(jié)點的存儲地址。它是一種能快速實現(xiàn)訪問的存儲方式，理想情況下，無需比較即可根據(jù)指定值直接定位記錄的存儲位置。4.散列存儲結(jié)構通常情況下，一種數(shù)據(jù)結(jié)構既可以用順序存儲結(jié)構實現(xiàn)，也可用鏈式存儲結(jié)構實現(xiàn)，還可以組合使用，具體可根據(jù)實際問題的需要而定。一般來說，若執(zhí)行的主要操作是插入或刪除，最好采用鏈式存儲結(jié)構，否則采用順序存儲結(jié)構；若預先可以估計出元素的個數(shù)，可采用順序存儲結(jié)構，否則宜采用鏈式存儲結(jié)構。注意事項數(shù)據(jù)結(jié)構常州信息職業(yè)技術學院感謝您的耐心觀看數(shù)據(jù)結(jié)構主講人：張靜常州信息職業(yè)技術學院1.2算法程序=算法+數(shù)據(jù)結(jié)構Part01算法及其特性算法（Algorithm）是描述解決特定問題的思路、方法和步驟，是求解步驟（指令）的有限序列。輸入：一個算法應該有零個或多個輸入。算法的概念算法的重要特性算法及其特性有窮性：一個算法必須在執(zhí)行有窮步驟之后正常結(jié)束，不能形成無窮循環(huán)，并且每一個步驟都在可接受的時間內(nèi)完成。確定性：算法中的每一條指令必須有確切的含義，不能產(chǎn)生多義性。可行性：算法中的每一條指令必須是切實可執(zhí)行的。輸出：一個算法應該有一個或多個輸出。算法和程序都是用來表達解決問題的邏輯步驟；算法是對解決問題的方法的具體描述，程序是用某種程序設計語言對算法的具體實現(xiàn)。算法和程序的關系區(qū)別算法及其特性程序和算法的最大區(qū)別是程序可以是無窮的，而算法必須滿足有窮性，即算法不允許無限循環(huán)。例如，操作系統(tǒng)是個程序，這個程序在不遭破壞的情況下永遠不會停止，即使沒有作業(yè)需要處理，它仍處于一個等待循環(huán)中。Part02算法的描述方法使用類似計算機程序設計語言的所謂偽語言來描述算法，接近高級程序設計語言的寫法，但不一定能直接編譯運行的代碼。偽代碼直接以可讀性高的高級程序設計語言來表示。高級程序設計語言使用中文、英文、數(shù)字等自然語言來描述算法。自然語言使用流程圖或N-S圖來描述算法?？驁D算法的描述方法本課程采用Java語言表示。Part03算法分析算法設計的要求算法分析正確性可讀性健壯性時間高效性-算法的時間復雜度空間高效性-算法的空間復雜度一個算法的時間耗費，就是該算法中所有語句的頻度之和。算法分析算法的時間復雜度表示算法的時間效率與算法所處理的數(shù)據(jù)元素個數(shù)n（問題規(guī)模）函數(shù)關系的最常用函數(shù)是O()函數(shù)（O()讀作大O）。算法的時間復雜度T(n)可記作：T(n)=O(f(n))O()說明O(1)稱為常數(shù)時間，表示算法的運行時間是一個常數(shù)倍，與問題規(guī)模無關。O(n)稱為線性時間，執(zhí)行時間增加的大小與問題規(guī)模成線性關系。O(log2n)稱為冪對數(shù)時間，成長速度比線性時間慢，比常數(shù)時間快。O(n2)稱為平方時間，算法的運行時間成二次方增長。O(n3)稱為立方時間，算法的運行時間成三次方增長。O(2n)稱為指數(shù)時間，算法的運行時間成2的n次方增長。O(nlog2n)稱為線性對數(shù)時間，介于線性和二次方增長之間。以上時間復雜度的順序：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)算法分析36示例1示例2示例3示例1假設某算法運行時間為T(n)=4n3+3n2+9n，求它的時間復雜度。例1-1示例4n3+3n2+9n4O(）算法分析37示例1示例2示例3分析下列程序段的時間復雜度public

static

voidmain(String[]args){ intn=100,sum=0;//(1)賦初值for(inti=1;i<=n;i++){sum=sum+i;//(2)累加和}System.out.println(sum);}例1-2示例2示例4sum=sum+i;O(n)算法分析38示例1示例2示例3分析下列程序段的時間復雜度public

static

voidmain(String[]args){intn=8,count=0;//(1)賦初值

for(inti=1;i<=n;i*=2){ count++;//(2)統(tǒng)計次數(shù)}System.out.println(count);}例1-3示例3示例4count++O(log2n)示例4算法分析39示例1示例2示例3分析下列程序段的時間復雜度public

static

voidmain(String[]args){intn=100,count=0;for(inti=1;i<=n;i++){

for(intj=1;j<=i;j++){ count++;} }System.out.println(count);}例1-4示例4O(n2)

最壞時間復雜度：最壞情況下的時間復雜度。最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的上界。平均時間復雜度：在所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間。算法分析算法分析41算法（程序）本身所占用的存儲空間；輔助變量所占用的存儲空間。輸入數(shù)據(jù)所占用的存儲空間；算法的空間復雜度是指算法在運行過程中所占用的輔助存儲空間大小?？臻g復雜度算法所占用的存儲空間包括：算法的空間復雜度通常也采用O()函數(shù)，記作S(n)=O(f(n))，其中n為問題規(guī)模。t=a;a=b;b=t;O(1)數(shù)據(jù)結(jié)構單元2引例一元多項式的表示及運算

引例描述：一元多項式的表示及運算數(shù)據(jù)結(jié)構（Java語言描述）常州信息職業(yè)技術學院思政小課堂：人生就是“單鏈表”“規(guī)劃好自己短暫的稍縱即逝的大學學習生涯，珍惜當下，不留遺憾?！狈治鲆治雠c實現(xiàn)

head∧datanext41系數(shù)x指數(shù)3385-67數(shù)據(jù)結(jié)構（Java語言描述）常州信息職業(yè)技術學院引例分析與實現(xiàn)數(shù)據(jù)結(jié)構（Java語言描述）常州信息職業(yè)技術學院1.一元多項式的項類引例分析與實現(xiàn)數(shù)據(jù)結(jié)構（Java語言描述）常州信息職業(yè)技術學院2.一元多項式排序單鏈表類引例分析與實現(xiàn)數(shù)據(jù)結(jié)構（Java語言描述）常州信息職業(yè)技術學院2.一元多項式排序單鏈表類引例分析與實現(xiàn)數(shù)據(jù)結(jié)構（Java語言描述）常州信息職業(yè)技術學院3.測試類數(shù)據(jù)結(jié)構主講人：張靜常州信息職業(yè)技術學院2.1線性表概述線性結(jié)構的特征是：除第一個和最后一個元素外，每個數(shù)據(jù)元素有且僅有一個直接前驅(qū)元素和一個直接后繼元素，第一個元素只有一個直接后繼元素，最后一個元素只有一個直接前驅(qū)元素。引言IntroductionPart01線性表的定義

線性表說明線性表的定義線性表的定義54示例1示例2示例3示例1英文字母表(A,B,C,…,Z)是一個長度為26的線性表，其中每個字母都是一個數(shù)據(jù)元素。示例1某圖書2020年每個月的銷售數(shù)量(1200,1000,2300,…,1800)(單位：冊)是一個長度為12的線性表，其中每個數(shù)值都是一個數(shù)據(jù)元素。示例2示例2線性表的定義55示例1示例2示例3示例3學生成績表就是一個線性表，表中每一個學生的信息就是一個數(shù)據(jù)元素，包含3個數(shù)據(jù)項：學號、姓名、成績。Part02線性表抽象數(shù)據(jù)類型描述及定義線性表的抽象數(shù)據(jù)類型主要包括兩個方面：數(shù)據(jù)集合和該數(shù)據(jù)集合上的操作集合。線性表上常見的操作有：插入、刪除、查找、獲取元素值、設置元素值等。線性表抽象數(shù)據(jù)類型描述及定義在Java語言中，抽象數(shù)據(jù)類型通常設計成接口。線性表抽象數(shù)據(jù)類型描述及定義T為泛型，表示線性表中數(shù)據(jù)元素的數(shù)據(jù)類型。Java語言約定，T的實際參數(shù)必須是類，不能是int、double、char等基本數(shù)據(jù)類型，若需表示基本數(shù)據(jù)類型，則須采用基本數(shù)據(jù)類型包裝類，如Integer、Double、Character等。java.util包中的List接口就是線性表，它的實現(xiàn)子類ArrayList就是順序表，LinkedList就是鏈表。數(shù)據(jù)結(jié)構常州信息職業(yè)技術學院感謝您的耐心觀看數(shù)據(jù)結(jié)構主講人：張靜常州信息職業(yè)技術學院2.2線性表的順序存儲結(jié)構順序表Part01順序表

使用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，該結(jié)構稱作線性表的順序存儲結(jié)構，簡稱為順序表（SequentialList）。順序表的定義順序表中數(shù)據(jù)元素存儲地址的計算順序表Part02順序表的基本操作1．順序表類聲明、構造方法、存取操作實現(xiàn)順序表的基本操作聲明構造方法publicSeqList(int

length){//構造容量為length的空表

this.data=newT[length];//創(chuàng)建長度為length的數(shù)組，元素均為null

this.n=0;//空表長度為0}publicSeqList(T[]values){//由values數(shù)組構造順序表this(values.length);//創(chuàng)建容量為values.length的空表for(int

i=0;i<values.length;i++){//復制數(shù)組元素

this.data[i]=values[i];//對象引用賦值}this.n=values.length;//順序表長度為數(shù)組values的長度} publicSeqList(){//創(chuàng)建默認容量為10的空表

this(10);//構造方法重載，調(diào)用本類已聲明的指定參數(shù)列表的構造方法}1．順序表類聲明、構造方法、存取操作實現(xiàn)順序表的基本操作獲取值設置值

2．求表長、清空、判斷表空順序表的基本操作求表長清空判斷表空3．遍歷順序表順序表的基本操作時間復雜度：O(n)public

voidprintList(){//遍歷順序表所有元素for(int

i=0;i<this.n;i++){System.out.println(this.data[i]);} }4．順序表的查找順序表的基本操作（1）查找算法//在順序表查找首次出現(xiàn)的與key相等元素，返回元素位置//若不存在返回-1public

intindexOf(Tkey){for(int

i=0;i<this.n;i++){if(key.equals(this.data[i])){

return

i;}}return-1;}（2）判斷是否包含某元素算法//判斷順序表中是否包含key元素public

booleancontains(Tkey){for(int

i=0;i<this.n;i++){if(key.equals(this.data[i])){

return

true;}}return

false;}時間復雜度：O(n)5．順序表的插入順序表的基本操作在ai位置插入40125439…a0a1a2…aiai+1…an-2an-15774…892840若插入位置不合理，拋出下標越界異常：下標范圍為0~n-1，允許直接在表尾后添加元素，因此合理的插入位置為0~n；如果順序表的長度大于等于數(shù)組長度，則動態(tài)擴容；從最后一個元素開始向前遍歷到下標i處，依次將它們后移1位；將要插入的元素填入下標i處；表長加1。5．順序表的插入順序表的基本操作public

intinsert(int

i,Tt){//在順序表的位置i處插入元素t,返回t序號if(t==null)throw

newNullPointerException("t==null");//拋出空對象異常if(i>=0&&i<=this.n){Tsrc[]=this.data;//保存原數(shù)組if(this.n==data.length){//若數(shù)組滿，則擴充順序表的數(shù)組容量

this.data=newT[src.length*2];//重新申請一個容量為原來2倍的數(shù)組

for(int

j=0;j<i;j++){

this.data[j]=src[j];//復制當前數(shù)組前i個元素} }

for(int

j=this.n-1;j>=i;j--){//從最后一個位置開始到位置i處，每一個元素向后移動1位

this.data[j+1]=src[j];}

this.data[i]=t;//把要插入的元素t存放在位置i處

this.n++;

return

i;//返回下標}else{

throw

newIndexOutOfBoundsException(i+"下標越界");//拋出下標越界異常} }

時間復雜度：O(n)6．順序表的刪除順序表的基本操作刪除ai位置上的元素74125439…a0a1a2…aiai+1…an-2an-15774…8928若是空表，拋出異常；若刪除位置不合理，拋出下標越界異常；從刪除元素位置開始遍歷到最后一個元素位置，依次將它們向前移動1位；表長減1。6．順序表的刪除順序表的基本操作

時間復雜度：O(n)publicTremove(int

i){if(this.n==0){try{

throw

newException("空表無法刪除！");}catch(Exceptione){

e.printStackTrace();}}

if(i>=0&&i<this.n){Told=this.data[i];//old中存放被刪除元素

for(int

j=i;j<this.n-1;j++){

this.data[j]=this.data[j+1];//從位置i+1開始每個元素依次前移一位}

this.data[this.n-1]=null;//設置最后一個位置元素為空

this.n--;

return

old;}else{

throw

newIndexOutOfBoundsException(i+"下標越界");

//拋出下標越界異常} }順序表結(jié)構簡單，便于隨機訪問表中的任一元素，但在順序表中進行插入、刪除操作時，平均移動次數(shù)大約為n/2（n為表中元素個數(shù)），當n較大時，順序表的插入、刪除操作執(zhí)行效率低。同時，通常用數(shù)組實現(xiàn)的順序表，需要預先分配適當?shù)拇鎯臻g，若預先分配過大，可能會導致空間浪費，若分配過小，又不利于擴容。小結(jié)用順序表實現(xiàn)學生信息的管理，包括學生信息的存取、插入、刪除、查找等操作，學生信息包括：學號、姓名、成績。提示：定義學生類Student，重寫equals方法，將順序表實現(xiàn)代碼中的泛型T替換成Student。課堂實踐數(shù)據(jù)結(jié)構常州信息職業(yè)技術學院感謝您的耐心觀看數(shù)據(jù)結(jié)構主講人：張靜常州信息職業(yè)技術學院2.3線性表的鏈式存儲結(jié)構鏈表線性表的鏈式存儲結(jié)構稱為線性鏈表，簡稱鏈表；常見的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表。引言Introduction存儲一個數(shù)據(jù)元素的存儲單元稱為結(jié)點（Node），一個結(jié)點至少包含兩個部分：結(jié)點（數(shù)據(jù)域，地址域）Part01單鏈表的結(jié)構每個結(jié)點只有一個地址域的線性鏈表稱為單鏈表（SinglyLinkedList），結(jié)點結(jié)構如下：單鏈表結(jié)點（數(shù)據(jù)域data，后繼結(jié)點地址域next）單鏈表的定義單鏈表有帶頭結(jié)點和不帶頭結(jié)點兩種單鏈表的結(jié)構不帶頭結(jié)點單鏈表的插入操作實現(xiàn)兩種單鏈表的區(qū)別objhead…∧datanexts…p在非開始結(jié)點前插入一個新結(jié)點不帶頭結(jié)點單鏈表的插入操作實現(xiàn)兩種單鏈表的區(qū)別objhead…∧datanexts…p在開始結(jié)點前插入一個新結(jié)點帶頭結(jié)點單鏈表的插入操作實現(xiàn)兩種單鏈表的區(qū)別objhead…∧datanextspPart02單鏈表的Java表示public

classNode<T>{//單鏈表結(jié)點類，T是數(shù)據(jù)元素的類型

publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素

publicNode<T>next;//地址域，引用后續(xù)結(jié)點

publicNode(Tdata,Node<T>next){//由指定的兩個域來構造結(jié)點

this.data=data;

this.next=next;}

publicNode(){//空構造

this(null,null);}

publicStringtoString(){

return

this.data.toString();//返回結(jié)點數(shù)據(jù)域的描述字符串}}單鏈表結(jié)點類單鏈表的Java表示public

classSinglyLinkedList<T>implementsLinearList<T>{

publicNode<T>head;//單鏈表的頭指針，指向頭結(jié)點

publicSinglyLinkedList(){//構造空單鏈表

head=newNode<T>();//創(chuàng)建頭結(jié)點，data和next的值均為null} //實現(xiàn)接口方法，具體代碼在2.3.3節(jié)介紹

publicTget(int

i){ … }

public

voidset(int

i,Tt){ … }

public

intinsert(Tt){… }

public

intinsert(int

i,Tt){… }

publicTremove(int

i){ … }

public

booleancontains(Tkey){… }

public

intindexOf(Tkey){… }

public

intsize(){ … }

public

voidclear(){ … }

public

booleanisEmpty(){… }

public

voidprintList(){ … }}單鏈表類單鏈表的Java表示Part03單鏈表的基本操作1.尾插法創(chuàng)建單鏈表單鏈表的基本操作headrear（1）創(chuàng)建只有頭結(jié)點的單鏈表；（2）將指向尾結(jié)點的指針指向頭結(jié)點；values[0]∧（3）從數(shù)組中讀入數(shù)據(jù)，由數(shù)組中的數(shù)據(jù)生成一個新結(jié)點，將新結(jié)點插入表尾；∧（4）使尾指針指向新的表尾；重復執(zhí)行（3）~（4），直到數(shù)組中所有數(shù)據(jù)均插入鏈表。1.尾插法創(chuàng)建單鏈表單鏈表的基本操作publicSinglyLinkedList(T[]values){//構造單鏈表，由數(shù)組提供元素

this();//創(chuàng)建只有頭結(jié)點的單鏈表Node<T>rear=this.head;//rear指向單鏈表的尾結(jié)點

for(int

i=0;i<values.length;i++){

rear.next=newNode<T>(values[i],null);

//尾插法，創(chuàng)建結(jié)點鏈接入rear結(jié)點之后

rear=rear.next;//rear指向新的尾結(jié)點}}2.存取操作單鏈表的基本操作

獲取值設置值

3.求表長、清空、判斷表空單鏈表的基本操作public

intsize(){//返回單鏈表的長度int

n=0;Nodep=this.head.next;

while(p!=null){

n++;p=p.next;}

return

n;}求表長//清空單鏈表public

voidclear(){

this.head.next=null; }//判斷單鏈表是否為空

public

booleanisEmpty(){return

this.head.next==null;}清空判斷表空4.遍歷單鏈表單鏈表的基本操作public

voidprintList(){//遍歷單鏈表Nodep=this.head.next;

while(p!=null){System.out.println(p.data);//輸出結(jié)點的數(shù)據(jù)域

p=p.next;//指針后移一個結(jié)點}}時間復雜度：O(n)5.單鏈表的查找單鏈表的基本操作//在單鏈表查找首次出現(xiàn)的與key相等元素，返回元素位置，若不存在返回-1public

intindexOf(Tkey){int

i=0; Nodep=this.head.next;for(;p!=null;p=p.next){//遍歷單鏈表if(p.data.equals(key)){

return

i;}

i++;}

return-1;}//判斷單鏈表中是否包含key元素public

booleancontains(Tkey){ Nodep=this.head.next;for(;p!=null;p=p.next){//遍歷單鏈表

if(p.data.equals(key)){

return

true;} }

return

false; }時間復雜度：O(n)6.單鏈表的插入單鏈表的基本操作head…∧datanextp…頭結(jié)點

ts（3）使p的地址域引用新結(jié)點s，即p.next=s，最后完成插入并返回i的值。單鏈表的插入-算法實現(xiàn)單鏈表的基本操作時間復雜度：O(n)

//在順序表的最后插入元素t，返回t序號public

intinsert(Tt){

return

this.insert(this.size(),t);}7.單鏈表的刪除單鏈表的基本操作head…datanextp頭結(jié)點

∧…單鏈表的刪除-算法實現(xiàn)單鏈表的基本操作時間復雜度：O(n)

用單鏈表實現(xiàn)學生信息的管理，包括學生信息的存取、插入、刪除、查找等操作，學生信息包括：學號、姓名、成績。提示：定義學生類Student，重寫equals方法，將單鏈表實現(xiàn)代碼中的泛型T替換成Student。課堂實踐Part04循環(huán)單鏈表循環(huán)鏈表是一種首尾相接的鏈表。將單鏈表中的尾結(jié)點的next域指向head，則整個鏈表成為一個環(huán)，這樣從鏈表中的任意結(jié)點出發(fā)都可找到表中其他的結(jié)點，這樣的單鏈表稱為循環(huán)單鏈表（CircularSinglyLinkedList）。基本概念循環(huán)單鏈表的結(jié)構空表：head.next=head循環(huán)單鏈表非空表：rear.next=head循環(huán)單鏈表的基本操作循環(huán)單鏈表帶頭結(jié)點的循環(huán)單鏈表的各種操作的實現(xiàn)算法與帶頭結(jié)點的單鏈表的實現(xiàn)算法類似，只需將相應算法中p!=null或p.next!=null改為p!=head或p.next!=headPart05雙向鏈表雙向鏈表的結(jié)點類雙向鏈表給單鏈表的每個結(jié)點再增加一個指向其直接前驅(qū)結(jié)點的引用域prev，這樣鏈表中就有兩條不同方向的鏈，此鏈表稱為雙向鏈表（DoublyLinkedList）。public

classDoubleNode<T>{//雙向鏈表結(jié)點類，T是數(shù)據(jù)元素的類型publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素publicDoubleNode<T>prev,next;//地址域，prev引用前驅(qū)結(jié)點，next引用后續(xù)結(jié)點publicDoubleNode(Tdata,DoubleNode<T>prev,DoubleNode<T>next){//由指定域值構造結(jié)點

this.data=data; this.prev=prev;

this.next=next;}publicDoubleNode(){//空構造

this(null,null,null);}publicStringtoString(){

return

this.data.toString();//返回結(jié)點數(shù)據(jù)域的描述字符串}}雙向鏈表的結(jié)構雙向鏈表空表：head.next==nullhead.prev==null非空表：p.next.prev==pp.prev.next==p雙向鏈表的基本操作雙向鏈表…pts①②③④…①s.prev=p.prev;②p.prev.next=s;③p.prev=s;④s.next=p;【思考】如果②和③兩步操作次序顛倒，會怎樣？（1）雙向鏈表的前插操作雙向鏈表的基本操作雙向鏈表…①p.prev.next=p.next;②p.next.prev=p.prev;若p是尾結(jié)點，即p.next=null。只需完成p.prev.next=null;即可。（2）雙向鏈表的刪除當前結(jié)點操作…p①②…╳╳循環(huán)雙鏈表雙向鏈表若雙向鏈表尾結(jié)點的next域指向頭結(jié)點，頭結(jié)點的prev域指向尾結(jié)點，則構成循環(huán)雙鏈表（CircularDoublyLinkedList），數(shù)據(jù)結(jié)構常州信息職業(yè)技術學院感謝您的耐心觀看數(shù)據(jù)結(jié)構主講人：張靜常州信息職業(yè)技術學院2.4線性表的應用Part01順序表的應用

1.順序表的就地逆置順序表的應用6925201260453730順序表的應用//順序表逆置public

voidreverse(SeqList<Integer>list){int

t;//i下標從頭開始往后,j下標從尾開始往前

for(int

i=0,j=list.size()-1;i<j;i++,j--){

t=list.data[i];list.data[i]=list.data[j];list.data[j]=t; }}public

classReverseListTest{public

static

voidmain(String[]args){ Integera[]={25,30,20,45,60,12,37,69}; SeqListlist=newSeqList(a);

System.out.println("逆置前：");

list.printList();//輸出逆置前的順序表

list.reverse(list);//順序表逆置

System.out.println("\n逆置后：");

list.printList();//輸出逆置后的順序表

}}算法實現(xiàn)假設有兩個包含若干整數(shù)的有序順序表listA和listB，其元素均已按從小到大的升序排列。編寫一個算法將它們合并成一個有序順序表listC，要求listC的元素也是從小到大排列的。2.有序順序表的合并順序表的應用123689100224391112123689100120ListAListBListCij12<2222<362236<434391112120順序表的應用public

classMergeList{//有序順序表的合并public

voidmerge(SeqListlistA,SeqListlistB,SeqListlistC){int

i,j;i=j=0;//兩表均從第一個元素開始依次掃描、比較while(i<listA.size()&&j<listB.size()){

if(listA.get(i)<listB.get(j)){//將兩表中較小的數(shù)插入到listC表中

listC.insert(listA.get(i));

i++; }else{

listC.insert(listB.get(j));

j++; } }while(i<listA.size()){//若剩余的是listA表，將表中剩余元素全部插入到listC表中

listC.insert(listA.get(i));

i++;}while(j<listB.size()){//若剩余的是listB表，將表中剩余元素全部插入到listC表中

listC.insert(listB.get(j));

j++;}}}public

classMergeListTest{public

static

voidmain(String[]args){ //通過有序數(shù)組創(chuàng)建順序表listA，listBIntegera[]={12,36,89,100};Integerb[]={22,43,91,112,120}; SeqListlistA=newSeqList(a); SeqListlistB=newSeqList(b);

SeqListlistC=newSeqList();//創(chuàng)建順序表listC-空表

MergeListml=newMergeList();ml.merge(listA,listB,listC);//有序順序表合并

listC.printList();//輸出順序表listC}}算法實現(xiàn)Part02單鏈表的應用和順序表的就地逆置一樣，單鏈表的就地逆置是在原鏈表上進行逆置，不額外增加新結(jié)點，不重新建鏈表。1.單鏈表的就地逆置單鏈表的應用head2147∧65逆置前head476515∧21逆置后單鏈表的應用head2147∧65逆置前head∧2147∧65qpr算法分析phead2115∧47∧65qpr單鏈表的應用public

voidreverse(SinglyLinkedList<Integer>list){Nodep,q,r;p=list.head.next;if(p==null||p.next==null){//若單鏈表為空或只有一個結(jié)點，無需逆置

return;}

q=p;p=p.next;//p指向第二個結(jié)點，準備和前面的結(jié)點斷開，成一無頭結(jié)點的鏈表q.next=null;//將第一個結(jié)點的next域置空，將原鏈表一分為二while(p!=null){

r=p.next;

p.next=q;//將無頭結(jié)點鏈表上的第一個結(jié)點摘下，插入到帶頭結(jié)點的第一個結(jié)點處

q=p;

p=r;}list.head.next=q; } }public

classReverseLinkedListTest{public

static

voidmain(String[]args){Integera[]={25,30,20,45,60,12,37,69}; SinglyLinkedListlist=newSinglyLinkedList(a);

System.out.println("逆置前：");list.printList();//輸出逆置前的單鏈表

list.reverse(list);//單鏈表逆置System.out.println("\n逆置后：");list.printList();//輸出逆置前的單鏈表}}算法實現(xiàn)與有序順序表的合并類似，有序單鏈表的合并采用“指針平行移動，依次掃描比較”的方法。從兩張表listA和listB的開始結(jié)點沿著鏈表逐個將對應數(shù)據(jù)元素進行比較，將較小的數(shù)據(jù)元素插入listC表尾。當兩表之一掃描完畢時，將另一個鏈表的剩余結(jié)點插入listC表尾即可。2.有序單鏈表的合并單鏈表的應用單鏈表的應用public

classSortedSinglyList<TimplementsComparable<T>>extendsSinglyLinkedList<T>{publicSortedSinglyList(){

super();}publicSortedSinglyList(T[]values){//數(shù)組中所有對象排序插入for(int

i=0;i<values.length;i++){

this.insert(values[i]);//排序單鏈表按對象大小插入}}//不支持父類的以下兩個方法，將其覆蓋并拋出異常@Overridepublic

voidset(int

i,Tt){

throw

newjava.lang.UnsupportedOperationException("set(inti,Tx)");}public

intinsert(int

i,Tt){

throw

newjava.lang.UnsupportedOperationException("insert(inti,Tx)");}

排序單鏈表類//重寫父類的insert(t)方法，根據(jù)t的大小插入在相應位置，保證鏈表是按數(shù)據(jù)遞增排列public

intinsert(Tt){int

i=0;Nodefront=this.head,p=front.next;//front指向p的前驅(qū)結(jié)點while(p!=null&&t.compareTo(p.data)>0){//尋找插入位置

front=p;

p=p.next;

i++;}front.next=newNode(t,p);//在front之后p之前插入值為t的結(jié)點

return

i;}}單鏈表的應用public

classMergeLinkedList{//有序單鏈表的合并public

voidmerge(SortedSinglyListlistA,SortedSinglyListlistB,SortedSinglyListlistC){Nodepa=listA.head.next;Nodepb=listB.head.next;

//兩表均從第一個元素開始依次掃描、比較

while(pa!=null&&pb!=null){

if(pa.data<pb.data){//將兩表中較小的數(shù)插入到listC表中

listC.insert(pa.data);

pa=pa.next; }else{

listC.insert(pb.data);

pb=pb.next; }}while(pa!=null){//若剩余的是listA表，將表中剩余元素全部插入到listC表中

listC.insert(pa.data);

pa=pa.next;}while(pb!=null){//若剩余的是listB表，將表中剩余元素全部插入到listC表中

listC.insert(pb.data);

pb=pb.next;}}}算法實現(xiàn)在一個有序單鏈表（元素為整數(shù)，升序排列）中插入一個整數(shù)x，保證插入后的單鏈表仍然為升序。課堂實踐數(shù)據(jù)結(jié)構常州信息職業(yè)技術學院感謝您的耐心觀看數(shù)據(jù)結(jié)構單元3引例括號匹配的檢查括號匹配是指一個算術表達式中括號要成對并以正確的順序出現(xiàn)，才是合法的。假設表達式中包含兩種括號：[]和()，嵌套順序任意，則正確的嵌套模式為：([]())、[([])()]，錯誤的嵌套模式為：([](])、(()[]。引例描述：括號匹配的檢查編譯系統(tǒng)對算術表達式進行語法檢查時，若括號不匹配，系統(tǒng)則會給出語法錯誤，不能通過編譯。思政小課堂：樹立正確的技能觀“遵守規(guī)則，樹立正確的技能觀”遵守規(guī)則，敬畏規(guī)則，堅定自我，堅守正確之路，是我們每個人都應該做到的。同時我們要自強自信，學好專業(yè)技能，造福社會。引例分析與實現(xiàn)引例分析：編譯系統(tǒng)對算術表達式進行語法檢查時，表達式中的左右括號不僅要個數(shù)相等，而且先左后右的順序要正確。括號可以嵌套使用，嵌套使用時，右括號與其前最近的一個左括號匹配。若括號不匹配，系統(tǒng)則會給出語法錯誤，不能通過編譯。算法思路：讀取表達式字符串，依次對其中的字符ch進行判斷若ch是右括號，則先判斷棧是否為空若棧為空，則表示此右括號是多余的若ch是左括號，則入棧若棧不空，則與棧頂左括號比較，判斷是否是同類括號若是同類括號，則表示這一對括號匹配成功，棧頂元素出棧若不是同類括號，則表示括號嵌套錯誤表達式讀取結(jié)束時：棧為空，則表達式括號匹配成功棧不空，說明左括號有多余的引例分析與實現(xiàn)1*2+3/5-3[(檢測到左中括號[，入棧檢測到右小括號)，判斷棧不空，且括號匹配，則棧頂左小括號(出棧；檢測到右中括號]，判斷棧不空，且括號匹配，則棧頂左中括號[出棧檢測到左小括號(，入棧檢測到左小括號(，入棧；檢測到右小括號)，判斷棧不空，且括號匹配，則棧頂左小括號(出棧。[(])()(表達式讀取結(jié)束，最后棧為空，表達式括號匹配數(shù)據(jù)結(jié)構主講人：閭楓常州信息職業(yè)技術學院3.1棧棧（Stack）是一種操作受限的線性表，其插入和刪除操作只允許在線性表的一端進行。引言IntroductionPart01棧的抽象數(shù)據(jù)類型棧的插入和刪除操作只允許在線性表的一端進行。允許進行操作的一端稱為棧頂（top），不允許操作的一端則稱為棧底（bottom）。棧的插入操作通常稱為入棧（push），棧的刪除操作則稱為出棧（pop）。如果棧中無數(shù)據(jù)元素，則稱為空棧。棧頂元素是最后入棧，最先出棧，棧底元素是最先入棧，最后出棧，棧具有后進先出（LIFO，LastInFirstOut）的特征。棧（Stack）說明棧的定義棧的定義棧操作限定的是元素插入和刪除的位置，元素插入和刪除操作進行的時間并未限定。即出?？梢噪S時進行，只要出棧的是棧頂元素即可。a有三個元素a，b，c依次進棧并且每個元素只進一次棧，則出棧的次序可以有：abc、acb、bac、bca、cba五種。示例若進出棧操作為：a進棧然后出棧，b、c進棧，然后c出棧，b出棧，則最終的出棧次序為：acbbcbb初始a進棧a出棧c進棧c出棧b出棧b進棧雖然棧的操作受限降低了棧操作的靈活性，但也使棧的操作更有效和更容易實現(xiàn)。棧的基本操作主要有創(chuàng)建棧、入棧、出棧、取棧頂元素、判斷棧是否為空等。棧的抽象數(shù)據(jù)類型描述及定義Part02順序棧順序棧的存儲結(jié)構棧作為一種特殊的線性表，可以采用順序存儲結(jié)構和鏈式存儲結(jié)構。采用順序存儲結(jié)構的棧稱為順序棧（SequentialStack）。順序棧的存儲結(jié)構棧滿設數(shù)組的長度為length，當top=length-1時，表示棧滿?？諚Ｖ杏幸粋€元素時，top值為0，因此一般用top=-1，表示棧空棧底數(shù)組下標為0的一端表示棧底棧頂用變量top表示棧頂元素在數(shù)組中的位置，也把top稱為棧頂指針一維數(shù)組順序棧一維數(shù)組順序棧的基本操作定義順序棧類SeqStack實現(xiàn)順序棧接口Stack，類中實現(xiàn)接口中相應操作方法，定義泛型數(shù)組stack用于存儲數(shù)據(jù)元素，定義變量length表示棧的初始容量，定義整型變量top表示棧頂指針，指向棧頂元素位置。構造方法用來對棧進行初始化，創(chuàng)建一維的泛型數(shù)組，并指定棧的容量大小，設置棧頂指針為-1，代表是一個空棧。//順序棧類public

classSeqStack<T>implementsStack<T>{

privateT[]stack=null;//聲明一維數(shù)組，表示順序棧

private

int

length;//表示順序棧的容量

private

int

top;//棧頂指針

//棧初始化

publicSeqStack(){

stack=(T[])newObject[16];//構造一維的泛型數(shù)組，默認大小為16

length=16;

top=-1;//棧初始化，棧中沒有元素 }

publicSeqStack(int

size){

stack=(T[])newObject[size];//構造一維的泛型數(shù)組，大小由參數(shù)決定

length=size;

top=-1;//棧初始化，棧中沒有元素 }……}順序棧的基本操作出棧時，先取出棧頂元素，然后top減1。出棧操作入棧時，top加1，指向新的棧頂位置，新元素放置到棧頂入棧操作atop03120312初始棧空,top=-1

元素a,b,c入棧0312元素c,b出棧abctoptopcb順序棧的基本操作元素入棧先判斷棧是否滿，若棧已滿，則拋出異常；若棧未滿，則先將棧頂指針加1，再將元素放入棧頂位置。元素出棧需要判斷棧是否空，若?？眨瑒t拋出異常；若棧不空，則先獲取頂元素，再將棧頂指針減1。//元素入棧@Overridepublic

voidpush(Tt){//判斷棧是否已滿，如果已滿，則拋出異常，如果未滿，則元素入棧

if(top==length-1){

throw

newRuntimeException("棧已經(jīng)滿，元素不能再進棧");}else{

stack[++top]=t;//棧頂指針先加1，再將元素放入棧頂位置}}

//元素出棧@OverridepublicTpop(){//判斷棧是否為空，若為空，則拋出異常，若不空，則元素出棧

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒有元素出棧");}else{

//先將棧頂元素值獲取返回，并將棧頂指針減1

return

stack[top--];}}時間復雜度為O(1)順序棧的基本操作判?？諚？諛酥臼菞ｍ斨羔榯op值為-1，判斷top值是否為-1即可。取棧頂元素判斷棧不空，則直接返回棧頂元素值，棧頂指針不移動。//獲取棧頂元素@OverridepublicTpeek(){//判斷棧是否為空，若為空，則拋出異常，若不空，則返回棧頂元素 if(this.isEmpty()){

throw

newRuntimeException("棧為空"); }else{

return

stack[top];//直接將棧頂元素值返回 }}//判斷棧是否為空@Overridepublic

booleanisEmpty(){

//top為-1,代表棧中沒有元素，為空棧

return

top==-1;}棧中的元素是Integer類型,從棧頂?shù)綏５滓来问牵?、2、3、4，定義逆置方法，修改棧中元素的次序從棧頂?shù)綏５鬃優(yōu)?4、3、2、1。注意：只使用順序棧的基本操作方法。課堂實踐Part03鏈式棧鏈式棧的存儲結(jié)構采用鏈式存儲結(jié)構的棧稱為鏈式棧，簡稱為鏈棧（LinkedStack）鏈棧一般用不帶頭結(jié)點單鏈表實現(xiàn)，單鏈表頭部作為棧頂，頭指針即為棧頂指針topantopa2a1^……棧底棧頂鏈式棧的基本操作public

classLinkedNode<T>{

privateTdata;

private

LinkedNodenext;

//構造方法

publicLinkedNode(){ }

publicLinkedNode(Tdata){

this.data=data;

this.next=null; } publicLinkedNode(Tdata,LinkedNode<T>next){

this.data=data;

this.next=next; }

//省略相應屬性的setter和getter方法 …...}鏈棧的結(jié)點結(jié)構鏈棧的結(jié)點同樣包含數(shù)據(jù)域和指向下一個結(jié)點的指針域next變量用于指向下一個結(jié)點data變量用于存放數(shù)據(jù)鏈式棧的基本操作//鏈棧類public

classLinkedStack<T>implementsStack<T>{

privateLinkedNode<T>top;//代表棧頂指針

//棧初始化

publicLinkedStack(){

top=null;//將棧頂指針top置空，構造一個空鏈棧 }

//實現(xiàn)棧接口的相關方法

……鏈棧類結(jié)構鏈棧類LinkedStack實現(xiàn)棧接口Stack，除了實現(xiàn)棧接口的相應方法外，鏈棧中定義一個LinkedNode類型的棧頂指針top，指向棧頂元素。鏈式棧的基本操作初始鏈棧中有3個元素ctopba^新結(jié)點入棧(1)先創(chuàng)建新結(jié)點noded^node(2)將新結(jié)點node指向棧頂指針(3)再移動棧頂指針指向新結(jié)點鏈式棧的基本操作//元素入棧@Overridepublic

voidpush(Tt){

//將新結(jié)點指向棧頂，再移動棧頂指針指向新結(jié)點，新結(jié)點成為棧頂元素 LinkedNode<T>node=newLinkedNode<T>(t);//使用傳遞的進棧數(shù)值，先構造新結(jié)點

node.setNext(top);//設置新結(jié)點指向棧頂指針

top=node;//設置棧頂指針指向新結(jié)點}入棧操作實現(xiàn)鏈式棧的基本操作初始鏈棧中有3個元素ctopba^出棧(1)棧頂元素值先保存到變量topData(2)移動棧頂指針指向其下一個結(jié)點先保存棧頂元素值(3)返回變量topData的值鏈式棧的基本操作//元素出棧@OverridepublicTpop(){

//判斷鏈棧是否為空，若為空，拋出異常，若不為空，則取棧頂元素的值并返回，修改棧頂指針指向下一個結(jié)點

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒有元素可出棧"); } TtopData=top.getData();//獲取棧頂元素值

top=top.getNext();//修改棧頂指針，指向下一個結(jié)點

return

topData;}出棧操作實現(xiàn)鏈式棧的基本操作判斷棧空取棧頂元素//獲取棧頂元素@OverridepublicTpeek(){

//判斷鏈棧是否為空，若為空，拋出異常，若不為空，則取棧頂元素的值并返回

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒有元素可出棧"); }

return

top.getData();//返回棧頂元素的值}//判斷棧是否為空@Overridepublic

booleanisEmpty(){

if(top==null)ret