數據結構（Java語言實現） 課件 陳銳 第1、2章 數據結構概述、線性表

數據結構（Java語言實現）結構Java實據現數學習目標LearningObjectives1數據結構能做什么2數據結構與算法的相關概念3能利用數據結構知識對問題建模6提高Java語言開發(fā)水平和調試技巧4能編寫出算法解決實際問題5會分析算法的時間復雜度和空間復雜度7提高算法設計能力內容與特點ContentandCharacteristics1突出體現數據結構的算法實踐2案例豐富，精選自考研、軟考試題3圖文并茂，內容講解細致4配套PPT、源代碼、視頻等，資源豐富5內容講解理論與實踐并重，實用性強第1章緒論結構Java實據現數目錄CONTENTS1.1數據結構相關概念1.2抽象數據類型1.5算法分析1.3數據的邏輯結構與存儲結構1.4算法的特性與算法的描述1.6關于數據結構的地位及學習方法1.1數據結構相關概念學習基礎學習認知能力數據元素（dataelement）是數據的基本單位，在計算機程序中通常作為一個整體來考慮和處理。一個數據元素可由若干個數據項（dataitem）組成，數據項是數據不可分割的最小單位。0102數據（data）是描述客觀事物的符號，能輸入到計算機中并能被計算機程序處理的符號集合。工

號姓

名性

別籍

貫所在院系出生年月職

稱2006002孫冬平男河南計算機學院1970.10教

授2019056朱

琳女北京文學院1985.08講師2015028劉曉光男陜西軟件學院1981.11副教授表1-1教職工基本情況1.1數據結構相關概念學習基礎學習認知能力數據結構（datastructure）即數據的組織形式，它是數據元素之間存在的一種或多種特定關系的數據元素集合。0304數據對象（dataobject）是性質相同的數據元素的集合，是數據的一個子集。1.1數據結構相關概念學習基礎學習認知能力在Java語言中，按照數據的構造，數據類型可分為兩類：基本數據類型和引用數據類型，其中，基本數據類型有char、byte、short、int、long、float、double、boolean等8種，引用數據類型有數組、class（類）、接口。05數據類型（datatype）用來刻畫一組性質相同的數據及其上的操作。1.2抽象數據類型及其描述1.2.1抽象數據類型的定義抽象數據類型（AbstractDataType，ADT）是對具有某種邏輯關系的數據類型進行描述，并在該類型上進行的一組操作。抽象數據類型描述的是一組邏輯上的特性，與在計算機內部表示無關。計算機中的整數數據類型是一個抽象數據類型，不同的處理器可能實現方法不同，但其邏輯特性相同，即加、減、乘、除等運算是一致的。抽象數據類型，就是對象的數據模型，它定義了數據對象、數據對象之間的關系及對數據對象的操作。抽象數據類型通常是指用戶定義的解決應用問題的數據模型，包括數據的定義和操作。例如，Java、C++、Python中的類就是一個抽象數據類型，它包括用戶類型的定義和在用戶類型上的一組操作。1.2抽象數據類型及其描述1.2.2抽象數據類型的描述抽象數據類型包括3個方面的內容：數據對象、數據關系和基本運算，通常采用三元組(D,SP)來表示。其基本格式如下：ADT抽象數據類型名{

數據對象：數據對象的描述數據關系：數據關系的描述基本運算：基本運算的聲明}ADT抽象數據類型名1.2抽象數據類型及其描述1.2.2抽象數據類型描述ADTMySet{數據對象：{ai|0≤ai≤n-1,ai∈R}。數據關系：無?；静僮鳎海?）InitSet(&S)：初始化操作，建立一個空的集合S。（2）SetEmpty(S)：若集合S為空，返回True，否則返回False。（3）GetSetElem(S,i,&e)：返回集合S的第i個位置元素值給e。（4）LocateElem(S,e)：在集合S中查找與給定值e相等的元素，如果查找成功返回該元素在表中的序號，否則返回0。（5）InsertSet(&S,e)：在集合S中插入一個新元素e。（6）DelSet(&S,i,&e)：刪除集合S中的第i個位置元素，并用e返回其值。（7）SetLength(S)：返回集合S中的元素個數。（8）ClearSet(&L)：將集合S清空。（9）UnionSet(&S,T)：合并集合S和T，即將T中的元素插入到S中，相同的元素只保留一個。（10）DiffSet(&S,T)：求兩個集合的差集，即S-T，即刪除S中與T中相同的元素。（11）DispSet(S)：輸出集合S中的元素。}ADTMySet1.2抽象數據類型及其描述1.2.2抽象數據類型描述publicclassMySet<T>//集合的類型定義{

Tlist[];

intlength;

finalintMAXSIZE=100;

MySet()//集合的初始化

{

list=(T[])newObject[MAXSIZE];

length=0;

}

publicbooleanSetEmpty()

//判斷集合是否為空，若為空，則返回true；否則，返回false

{

if(length<=0)

returntrue;

else

returnfalse;

}

1.2抽象數據類型及其描述1.2.2抽象數據類型描述publicintSetLength()//返回集合中元素個數

{

returnlength;

}

publicvoidClearSet()//清空集合

{

length=0;

}

publicbooleanInsertSet(Te)//在集合中插入一個元素e

{

if(length>=MAXSIZE-1){

System.out.println("下標越界，不能插入!");

returnfalse;

}

else{

list[length++]=e;

returntrue;

}

}

1.2抽象數據類型及其描述1.2.2抽象數據類型描述publicbooleanDelSet(intpos)

//刪除集合中的第pos個元素

{

if(length<=0)

{

System.out.println("集合為空，不能進行刪除操作!");

returnfalse;

}

else{

for(inti=pos-1;i<length-1;i++)

{

list[i]=list[i+1];

length--;

}

returntrue;

}

}

1.2抽象數據類型及其描述1.2.2抽象數據類型描述publicTGetSetElem(inti)throwsException//獲取集合中第i個元素賦給e

{

if(length<=0){System.out.println("集合為空，不能獲取任何元素!");}

elseif(i<1&&i>length){

thrownewException("下標錯誤!");

}else{

Te=list[i-1];

returne;}

}

publicintLocateElem(Te)//查找集合中元素值為e的元素，返回其序號

{

for(inti=1;i<length+1;i++)

{

if(list[i-1]==e)

returni;

}

return0;

}

1.2抽象數據類型及其描述1.2.2抽象數據類型描述publicintUnionSet(MySetS,MySetT)throwsException

//合并集合S和T

{

if(S.length+T.length>=S.MAXSIZE)

return-1;

else{

for(inti=1;i<T.length+1;i++){

Te=(T)T.GetSetElem(i);

if(S.LocateElem(e)==0)

S.InsertSet(e);

}

}

}

1.2抽象數據類型及其描述1.2.2抽象數據類型描述publicintDiffSet(MySetS,MySetT)throwsException//求集合S和T的差集

{

if(S.length<=0)

return-1;

else{

for(inti=1;i<T.length+1;i++){

Te=(T)T.GetSetElem(i);

intpos=S.LocateElem(e);

if(pos!=0)

S.DelSet(pos);

}

return1;

}

}

1.3數據的邏輯結構與存儲結構1.3.1邏輯結構（1）集合。數據元素除了同屬于一個集合外，數據元素之間沒有其他關系。（2）線性結構。結構中的數據元素之間是一對一的關系。（3）樹形結構。結構中的數據元素之間存在一種一對多的層次關系。（4）圖結構。結構中的數據元素是多對多的關系。1.3數據的邏輯結構與存儲結構1.3.2存儲結構存儲結構也稱為物理結構，數據的邏輯結構在計算機中存儲形式。通常有兩種：順序存儲結構和鏈式存儲結構。采用順序存儲的字符串“abcdef”地址連續(xù)的存儲的存儲結構如圖1-9所示。鏈式存儲是把數據元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的1.4算法的特性與算法的描述算法與數據結構關系密切。兩者既有聯系又有區(qū)別。數據結構與算法的聯系可用一個公式描述：程序=算法+數據結構數據結構是算法實現的基礎，算法依賴于某種數據結構才能實現。數據結構與算法相輔相成，不是相互孤立存在的。數據結構關注的是數據的邏輯結構、存儲結構以及基本操作，而算法更多的是關注如何在數據結構的基礎上怎樣設計解決實際問題的方法。算法是編程思想，數據結構則是為了算法實現方便而提供的存儲結構及基本操作，是算法設計的基礎。：1.4算法的特性與算法的描述1.4.1算法的定義算法（algorithm）是解決特定問題求解步驟的描述，在計算機中表現為有限的操作序列。求n個數中最大者的問題for(i=0;i<a.length;i++)//for循環(huán)處理if(max<a[i])

//判斷是否滿足max小于a[i]的條件

max=a[i];

//如果滿足條件，將a[i]賦值給maxSystem.out.println("max=:"+max);1.4算法的特征與算法的描述1.4.2算法的五大特性（1）有窮性（finiteness）。有窮性指的是算法在執(zhí)行有限的步驟之后，自動結束而不會出現無限循環(huán)，并且每一個步驟在可接受的時間內完成。（2）確定性（definiteness）。算法的每一步驟都具有確定的含義，不會出現二義性。算法在一定條件下只有一條執(zhí)行路徑，也就是相同的輸入只能有一個唯一的輸出結果。（3）可行性（feasibility）。算法的每個操作都能夠通過執(zhí)行有限次基本運算完成。（4）輸入（input）。算法具有零個或多個輸入。（5）輸出（output）。算法至少有一個或多個輸出。輸出的形式可以是打印輸出，也可以是返回一個或多個值。1.4算法的特征與算法的描述算法的描述方式有多種，如自然語言、偽代碼（或稱為類語言）、程序流程圖及程序設計語言（如Java、Python、C、C++）等。1.4.3算法的描述1.4算法的特征與算法的描述2.程序流程圖法判斷m是否為質數的程序流程圖如圖1-9所示。

采用自然語言描述算法直觀性和可讀性不強；

采用程序流程圖描述算法比較直觀，可讀性好，缺點是不能直接轉化為計算機程序，移植性不好。1.4.3算法的描述1.4算法的特征與算法的描述3.類語言法voiddcf()//求最大公約數{ input(m,n); //輸入兩個正整數

r=m; do{ m=n; n=r; r=m%n; //r表示兩個數的余數

}while(r); print(n); //輸出最大公約數}1.4.3算法的描述1.4算法的特性與算法的描述4.程序設計語言法voiddcf()//求最大公約數{intm,n,r;System.out.println("請輸入兩個正整數m和n：");Scannersc=newScanner(System.in);Stringa[]=sc.nextLine().split("");m=Integer.parseInt(a[0]);n=Integer.parseInt(a[1]);System.out.print(String.format("dcf（%d，%d）=",m,n));r=m;1.4.3算法的描述do{

//使用輾轉相除法法求解最大公約數

m=n;n=r;r=m%n;//r存放兩個數的余數

}while(r!=0);System.out.println(n);//輸出最大公約數}1.5算法分析1.算法的正確性（correctness）算法至少應該包括對于輸入、輸出和處理無歧義性的描述，能正確反映問題的需求，且能夠得到問題的正確答案。通常算法的正確性應包括以下4個層次。（1）算法對應的程序沒有語法錯誤。（2）對于幾組輸入數據能得到滿足規(guī)格要求的結果。（3）對于典型的、苛刻的帶有刁難性的輸入數據，能得到滿足規(guī)格要求的結果。（4）對于一切合法的輸入都能得到滿足要求的結果。1.5.1算法設計的四個目標1.5算法分析2.可讀性（readability）算法主要是為了人們方便閱讀和交流，其次才是計算機執(zhí)行?？勺x性好有助于人們對算法的理解，晦澀難懂的程序往往隱含著不易被發(fā)現的錯誤，難以調試和修改。3.健壯性（robustness）當輸入數據不合法時，算法也應該能做出反應或進行處理，而不會產生異常或莫名其妙的輸出結果。4.高效率和低存儲量（Highefficiencyandlowstorage）效率指的是算法的執(zhí)行時間。對于同一個問題，如果有多個算法能夠解決，執(zhí)行時間短的算法效率高，執(zhí)行時間長的效率低。1.5.1算法設計的四個目標1.5算法分析1.事后統計方法目前計算機內部大都有計時功能，有的甚至可精確到毫秒級，不同算法的程序可通過一組或若干組相同的測試程序和數據以分辨算法的優(yōu)劣。缺點：一是必須依據算法事先編制好程序，這通常需要花費大量的時間與精力；

二是時間的長短依賴計算機硬件和軟件等環(huán)境因素，有時會掩蓋算法本身的優(yōu)劣。1.5.2算法效率評價1.5算法分析2.事前分析估算方法在計算機程序編制前，對算法依據數學中的統計方法進行估算。這個方法可行，主要是因為算法的程序在計算機上的運行時間取決于以下因素： 算法采用的策略、方法。 編譯產生的代碼質量。 問題的規(guī)模。 書寫的程序語言，對于同一個算法，語言級別越高，執(zhí)行效率越低。 機器執(zhí)行指令的速度。1.5.2算法效率評價1.5算法分析例如，兩個n×n矩陣相乘的算法和語句的的頻度如下。

每條語句的頻度for(i=0;i<n;i++)n

for(j=0;j<n;j++)n2{

a[i][j]=0;

n2

for(k=0;k<n;k++)n3

a[i][j]=a[i][j]+a[i][k]*a[k][j];n3}總的執(zhí)行次數為1.5.2算法效率評價f(n)=n+n2+n2+n3+n3=2n3+2n2+n1.5算法分析1.什么是算法時間復雜度在進行算法分析時，語句總的執(zhí)行次數T(n)是關于問題規(guī)模n的函數，進而分析T(n)隨n的變化情況并確定T(n)的數量級。算法的時間復雜度，也就是算法的時間量度，記作T(n)=O(f(n))。它表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱為時間復雜度。1.5.3算法時間復雜度1.5算法分析（1）x=x+1;（2）for(i=1;i<n+1;i++)x=x+1;（3）for(i=1;i<n+1;i++)for(j=1;j<n+1;j++)

x=x+1;程序段（1）的時間復雜度為O(1)，稱為常量階；程序段（2）的時間復雜度為O(n)，稱為線性階；程序段（3）的時間復雜度為O(n2)，稱為平方階。此外算法的時間復雜度還有對數階O(log2n)、指數階O(2n)等1.5.3算法時間復雜度1.5算法分析常用的時間復雜度所耗費的時間從小到大依次是O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)1.5.3算法時間復雜度1.5算法分析2.算法時間復雜度分析舉例例1.1分析以下程序段的時間復雜度。for(i=1;i<n;i++)

for(j=1;j<I;j++){

x=x+1;//基本操作

a[i][j]=x;//基本操作}該程序段中的基本操作是第二層for循環(huán)中的語句，即x=x+1和a[i][j]=x，其語句頻度為(n-1)(n-2)/2。因此，其時間復雜度為O(n2)。1.5算法分析2.算法時間復雜度分析舉例例1.2分析以下算法的時間復雜度。voidFun(){

inti=1;

while(i<=n)

i=i*2;//基本操作}該函數fun()的基本運算是i=i*2，設執(zhí)行時間次數為f(n)，則2f(n)≤n，則有f(n)≤log2n。因此，時間復雜度為O(log2n)。1.5算法分析2.算法時間復雜度分析舉例例1.3分析以下算法的時間復雜度。

voidFunc(){

inti=0;

ints=0;

while(s<n){

i=i+1;//基本操作

s+=i;//基本操作}}該算法中的基本操作是while循環(huán)中的語句，設while循環(huán)次數為f(n)，則變量i從0到f(n)，因此循環(huán)次數為f(n)*(f(n)+1)/2≤n，則f(n)≤

，故時間復雜度為O()。1.5算法分析例1.4一個算法所需時間由以下遞歸方程表示，分析算法的時間復雜度。

根據以上遞歸方程，可得T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=2*2T(n-2)+2+1=2*2*(2T(n-3)+1)+2+1=……=2k-1(2T(n-k)+1)+2k-2+…+2+1=…=2n-2(2T(1)+1)+2n-2+…+2+1=2n-1+…+2+1=2n-1因此，該算法的時間復雜度為O(2n)。1.5算法分析1.5.4算法空間復雜度空間復雜度（spacecomplexity）作為算法所需存儲空間的量度，記作S(n)=O(f(n))。n為問題的規(guī)模，f(n)為語句關于n的所占存儲空間的函數。例1.5以下是一個簡單插入排序算法，分析算法的空間復雜度。for(i=0;i<n-1;i++){

t=a[i+1];

j=i;

while(j>=0&&t<a[j]){

a[j+1]=a[j];

j=j-1;}

a[j+1]=t;}該算法借助了變量t，與問題規(guī)模n的大小無關，空間復雜度為O(1)。1.5算法分析1.5.4算法空間復雜度例1.6以下算法是求n個數中的最大者，分析算法的空間復雜度。intFindMax(inta[],intn){

if(n<=1)

returna[0];

else:

intm=FindMax(a,n-1);

returna[n-1]>=m?a[n-1]:m;}設FindMax(a,n)占用的臨時空間為S(n)，由以上算法可得到以下占用臨時空間的遞推式。因此，該算法的空間復雜度為O(n)。1.6關于數據結構課程的地位及學習方法明確數據結構的重要性，樹立學好數據結構的信心熟練掌握程序設計語言，變腐朽為神奇結合生活實際，變抽象為具體多思考，多上機實踐1.6關于數據結構課程的地位及學習方法1.數據結構的前世今生唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。數據結構作為一門獨立的課程是從1968年開始在美國設立的。Donald的經典巨著《計算機程序設計的藝術》（TheArtofComputerProgramming），與愛因斯坦《相對論》、狄拉克《量子力學》、理查?費曼《量子電動力學》等經典比肩。高德納在36歲時就榮獲1974年度的圖靈獎。DonaldErvinKnuth教授開創(chuàng)了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。1.6關于數據結構課程的地位及學習方法2.數據結構的地位與作用數據結構是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程。數據結構已經不僅僅是計算機相關專業(yè)的核心課程，還是其他非計算機專業(yè)的主要選修課程之一。算術表達式求值問題、迷宮求解、機器學習中的決策樹分類等分別利用了數據結構中的棧、樹進行解決。數據結構也是學習操作系統、軟件工程、人工智能、算法設計與分析、機器學習、大數據等眾多后繼課程的重要基礎。參考書目：1、李春葆，《數據結構（第5版）》，清華大學出版社。2、耿國華，《數據結構（C語言版）》，高等教育出版社。3、陳銳，馬軍霞，張建偉等，《數據結構（C語言實現）》，機械工業(yè)出版社4、陳銳、張志鋒、馬軍霞等，《數據結構與算法詳解》，人民郵電出版社。5、嚴蔚敏，吳偉民，《數據結構（C語言版）》，清華大學出版社。6、潘金貴譯，《算法導論》，機械工業(yè)出版社。7、《算法（第4版）》，人民郵電出版社。8、陳銳、張建偉、馬軍霞等，《數據結構習題精解》，清華大學出版社。感謝聆聽主講：結構實據現數Java第2章線性表結構Java實據現數目錄CONTENTS2.1

線性表的定義及抽象數據類型2.2線性表的順序表示與實現2.3線性表的鏈式表示與實現2.7小結2.6一元多項式的表示與相乘2.4循環(huán)單鏈表2.5雙向鏈表2.1線性表的定義及抽象數據類型1.線性表的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。英文單詞“China”“Science”“Structure”等就屬于線性結構，其中的每一個英文字母就是一個數據元素，數據元素之間存在著一對一的順序關系。如“China”中字母“C”的直接后繼是字母“h”，字母“h”的直接后繼是字母“i”。線性表是由n個類型相同的數據元素組成的有限序列，記(a1,a2,…,ai-1,ai,ai+1,…,an)。數據元素可以是原子類型，也可以是結構類型。在線性表中，數據元素ai-1稱為ai的直接前驅元素，ai稱為ai-1的直接后繼元素。2.1線性表的定義及抽象數據類型一個數據元素可以由若干個數據項組成，如圖2.2所示的一個學校的教職工情況表，一個數據元素由姓名、性別、出生年月、籍貫、學歷、職稱及任職時間七個數據項組成。數據元素也稱為記錄。2.1線性表的定義及抽象數據類型學習基礎學習認知能力ADTList{

數據對象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

數據關系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}

基本操作：（1）InitList(&L)

初始條件：表L不存在。操作結果：建立一個空的線性表L。這就像日常生活中，新生入學剛建立一個學生情況表，準備登記學生信息。（2）ListEmpty(L)

初始條件：表L存在。操作結果：若表L為空，返回1，否則返回0。這就像日常生活中，剛剛建立了學生情況表，還沒有學生來登記。2.1線性表的定義及抽象數據類型學習基礎學習認知能力（3）GetElem(L,i,&e)

初始條件：表L存在，且i值合法，即1≤i≤ListLength(L)。操作結果：返回表L的第i個位置元素值給e。這就像在學生情況表查找一個學生，將查到的學生情況報告給老師。（4）LocateElem(L,e)

初始條件：表L存在，且e為合法元素值。操作結果：在表L中查找與給定值e相等的元素。如果查找成功，則返回該元素在表中的序號；如果這樣的元素不存在，則返回0。這就像在學生情況表查找一個學生，只報告是否找到這個學生，并不報告這個學生的基本情況。（5）InsertList(&L,i,e)

初始條件：表L存在，e為合法元素且1≤i≤ListLength(L)。操作結果：在表L中的第i個位置插入新元素e。這就像新來了一個學生報到，被登記到學生情況表中。2.1線性表的定義及抽象數據類型學習基礎學習認知能力（6）DeleteList(&L,i,&e)

初始條件：表L存在且1≤i≤ListLength(L)。操作結果：刪除表L中的第i個位置元素，并用e返回其值。這就像一個學生違反了校規(guī)，被學校開除，需要把該學生從學生情況表中刪除。（7）ListLength(L)

初始條件：表L存在。操作結果：返回表L的元素個數。這就像學校招了新生之后，需要統計下學生的總人數，查找下學生情況表，看有多少個學生。（8）ClearList(&L)

初始條件：表L存在。操作結果：將表L清空。這就像學生已經畢業(yè)，不再需要保留這些學生信息，將這些學生信息全部清空。}ADTList2.2線性表的順序表示與實現2.2.1線性表的順序存儲線性表的順序存儲指的是將線性表中的各個元素依次存放在一組地址連續(xù)的存儲單元中。用這種方法存儲的線性表稱為順序表。順序表具有以下特征：邏輯上相鄰的元素，在物理上也是相鄰的。

假設線性表有n個元素，每個元素占用m個存儲單元，如果第一個元素的存儲位置為LOC(a1)，第i個元素的存儲位置為LOC(ai)，第i+1個元素的存儲位置為LOC(ai+1)。則線性表的第i+1個元素的存儲位置與第i個元素的存儲位置滿足以下關系：LOC(ai+1)=LOC(ai)+m2.2線性表的順序表示與實現2.2.1線性表的順序存儲線性表的順序存儲結構是一種隨機存取的存儲結構。只要知道其中一個元素的存儲地址，就可以得到線性表中任何一個元素的存儲地址。線性表的順序存儲結構如圖2.3所示。2.2線性表的順序表示與實現2.2.1線性表的順序存儲由于在Java語言中，數組具有隨機存取、且存儲地址連續(xù)的特點，因此，可采用數組來存儲順序表中的元素。publicclassSeqList<T>{staticfinalintLISTSIZE=100;privateintlength;Tlist[];}LISTSIZE表示數組能容納的元素個數，length表示當前數組中存儲的元素個數，list[]用于存儲線性表中的元素。2.2線性表的順序表示與實現2.2.2順序表的基本運算①順序表的構造方法。SeqList(){list=(T[])newInteger[LISTSIZE];length=0;}②判斷線性表是否為空。publicbooleanListEmpty()//判斷線性表是否為空{if(length==0)returntrue;elsereturnfalse;

}2.2線性表的順序表示與實現2.2.2順序表的基本運算③按序號查找。publicTGetElem(inti)//取線性表中某一位置上的元素值{if(i>=1&&i<=length)returnlist[i-1];elsethrownewIllegalArgumentException("i超出了線性表的有效范圍！");}2.2線性表的順序表示與實現2.2.2順序表的基本運算④按內容查找。從線性表中的第一個元素開始，依次與e比較，如果相等，返回該序號表示成功；否則返回0表示查找失敗。publicintLocateElem(Tx){inti;for(i=0;i<length;i++){if(list[i]==x)returni+1;}return-1;}2.2線性表的順序表示與實現2.2.2順序表的基本運算⑤插入操作。插入操作就是在線性表L中的第i個位置插入新元素e，使線性表{a1,a2,…,ai-1,ai,…,an}變?yōu)閧a1,a2,…,ai-1,e,ai,…,an}，線性表的長度也由n變成n+1。例如，在線性表{9,12,6,15,20,10,4,22}中，要在第5個元素之前插入1個元素28，需要將序號為8、7、6、5的元素依次向后移動1個位置，然后在第5號位置插入元素28，這樣，線性表就變成了{9,12,6,15,28,20,10,4,22}，如圖2-3所示。2.2線性表的順序表示與實現2.2.2順序表的基本運算publicbooleanInsertList(inti,Te){if(length>=LISTSIZE){System.out.println("順序表空間已滿!");returnfalse;}if(i<1||i>length+1){System.out.println("插入位置不合法");returnfalse;}else{for(intj=length;j>i-1;j=j-1)list[j]=list[j-1];list[i-1]=e;length+=1;returntrue;}}2.2線性表的順序表示與實現2.2.2順序表的基本運算⑥刪除第i個元素。刪除第i個元素之后，線性表{a1,a2,…,ai-1,ai,ai+1,…,an}變?yōu)閧a1,a2,…,ai-1,ai+1,…,an}，線性表的長度由n變成n-1。例如要刪除線性表{9,12,6,15,28,20,10,4,22}的第4個元素，需要依次將序號為5、6、7、8、9的元素向前移動一個位置，并將表長減1，如圖2-4所示。2.2線性表的順序表示與實現2.2.2順序表的基本運算publicbooleanDeleteList(inti)

{

if(i>=1&&i<length){

for(intj=i;j<length;j++)

list[j-1]=list[j];

length-=1;

returntrue;

}

else

returnfalse;

}2.2線性表的順序表示與實現⑦求線性表的長度。publicintListlength(){returnlength;}⑧清空順序表。publicvoidClearList(){length=0;}2.2.2順序表的基本運算2.2線性表的順序表示與實現在順序表的實現算法中，除了按內容查找運算、插入和刪除操作外，算法的時間復雜度均為O（1）。在按內容查找的算法中，若要查找的是第一個元素，則僅需要進行一次比較；若要查找的是最后一個元素，則需要比較n次才能找到該元素（設線性表的長度為n）。設Pi表示在第i個位置上找到與e相等的元素的概率，若在任何位置上找到元素的概率相等，即Pi=1/n，則查找元素需要的平均比較次數為

==，因此，按內容查找的平均時間復雜度為O（n）。2.2.3基本操作性能分析=2.2線性表的順序表示與實現在順序表的插入算法中，時間的耗費主要集中在移動元素上。設pi為在第i個位置上插入元素的概率，假設在任何位置上找到元素的概率相等，即pi=1/(n+1)，則順序表的插入操作需要移動元素的平均次數為：2.2.3基本算法性能分析插入操作的平均時間復雜度為O(n)。2.2線性表的順序表示與實現在順序表的刪除算法中，時間的耗費同樣在移動元素上。設pi表示刪除第i個位置上的元素的概率，假設在任何位置上找到元素的概率相等，即pi=1/n，則順序表的刪除操作需要移動元素的平均次數為：2.2.3基本操作的性能分析刪除操作的平均時間復雜度為O(n)。2.2線性表的順序表示與實現staticvoidUnionAB(SeqList<Integer>LA,SeqList<Integer>LB)//合并順序表LA和LB的元素，并保持非遞減排列{inti=1,pos;Integere;while(i<=LB.Listlength()){e=LB.GetElem(i);//取出順序表LA中第i個元素

pos=LA.LocateElem(e);if(pos==-1)//若LA中的元素小于LB中的元素

{LA.InsertList(LA.Listlength()+1,e);//則將當前元素插入到LA中

}i+=1;}

}【例2.1】假設線性表LA和LB分別表示兩個集合A和B，利用線性表的基本運算實現新的集合A=AB，即擴大線性表ListA，將存在于線性表LB中且不存在于LA中的順序表LA中有10個元素:11121314151617181920順序表LB中有6個元素:4812162024將LB中不存在LA的元素合并到LA中，LA中有13個元素:1112131415161718192048242.2線性表的順序表示與實現【例2-2】編寫一個算法，把一個順序表分拆成兩個部分，使順序表中小于等于0的元素位于左端，大于0的元素位于右端。要求不占用額外的存儲空間。例如順序表（-12,3,-6,-10,20,-7,9,-20）經過分拆調整后變?yōu)椋?12,-20,-6,-10,-7,20,9,3）。staticvoidSplitSeqList(SeqList<Integer>L){inti=0,j=L.Listlength()-1;//指示器i和j分別指示順序表的左端和右端元素

Integere;Integerzero=newInteger(0);while(i<j)//若未掃描完畢所有元素

{while(L.list[i].compareTo(zero)<=-1)//i遇到小于等于0的元素

i++;//略過

while(L.list[j].compareTo(Integer.valueOf(0))>0)//j遇到大于0的元素

j--;//略過

if(i<j){e=L.list[i];L.list[i]=L.list[j];L.list[j]=e;}}

}順序表L中有8個元素:-123-6-1020-79-20調整后的順序表L的元素依次為：

-12-20-6-10-72093【考研真題】設將n（n>1）個整數存放到一維數組R中，試設計一個在時間和空間兩方面都盡可能高效的算法，將R中保存的序列循環(huán)左移p（0<p<n）個位置，即把R中的數據序列由(x0,x1,…,xn-1)變換為(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。要求如下。（1）給出算法的基本設計思想。（2）根據設計思想，采用Java語言描述算法。（3）說明所設計算法的時間復雜度和空間復雜度?！痉治觥吭擃}目主要考查對順序表的掌握情況，具有一定的靈活性。（1）先將這n個元素序列(x0,x1,…,xp,xp+1,…,xn-1)就地逆置，得到(xn-1,xn-2,…,xp,xp-1,…,x0)，然后再將前n-p個元素(xn-1,xn-2,…,xp)和后p個元素(xp-1,xp-2,…,x0)分別就地逆置，得到最終結果(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。publicstaticvoidReverse(SeqListR,intleft,intright)

//將n個元素序列逆置{intk=left;intj=right;while(k<j)//若未完成逆置{//將這n個元素序列逆置處理過程

t=R.mylist[k];R.mylist[k]=R.mylist[j];R.mylist[j]=t;k++;j--;}}publicstaticvoidLeftShift(SeqListR,intn,intp)

//將R中保存的序列循環(huán)左移p（0<p<n）個位置{

if(p>0&&p<n)//若循環(huán)左移的位置合法{

Reverse(R,0,n-1);//將全部元素逆置

Reverse(R,0,n-p-1);//逆置前n-p個元素

Reverse(R,n-p,n-1);//逆置后n個元素}}2.3線性表的鏈式表示與實現為了表示這些元素之間的邏輯關系，除了需要存儲元素本身的信息外，還需要存儲指示其后繼元素的地址信息。這兩部分組成的存儲結構，稱為結點。結點包括兩個域：數據域和指針域。一個采用鏈式存儲結構的線性表(Hou,Geng,Zhou,Hao,Chen,Liu,Yang)的存儲結構如圖2.9所示。2.3.1單鏈表的存儲結構2.3線性表的鏈式表示與實現一般情況下，我們只關心鏈表的邏輯順序，而不關心鏈表的實際存儲位置。通常用箭頭代替指針來連接結點序列。因此，圖2.9所示的線性表可以形象化為圖2.10所示的序列。

2.3.1單鏈表的存儲結構2.3線性表的鏈式表示與實現在單鏈表的第一個結點之前增加一個結點，稱為頭結點。頭結點的數據域可以存放線性表的附加信息，如線性表的長度。若帶頭結點的鏈表為空鏈表，則頭結點的指針域為“空”，如圖2.12所示。2.3.1單鏈表的存儲結構2.3線性表的鏈式表示與實現classListNode//單鏈表中結點的存儲結構{intdata;ListNodenext;ListNode(intdata,ListNodenext){this.data=data;this.next=next;}ListNode(intdata){this.data=data;}}2.3.1單鏈表的存儲結構2.3線性表的鏈式表示與實現①判斷單鏈表是否為空。若單鏈表為空，返回true；否則返回false。publicbooleanListEmpty(){if(head.next==null)returntrue;elsereturnfalse;}2.3.2單鏈表上的基本運算2.3線性表的鏈式表示與實現②按序號查找操作。從單鏈表的頭指針head出發(fā)，利用結點的指針域依次掃描鏈表的結點，并進行計數，直到計數為i，就找到了第i個結點。如果查找成功，返回該結點的指針，否則返回null表示查找失敗。publicListNodeGetNode(inti){ListNodecur=head;//標記當前結點

intj=1;while(cur!=null&&j<i){cur=cur.next;j++;}if(j==i)returncur;elsereturnnull;}2.3線性表的鏈式表示與實現③按內容查找，查找元素值為e的結點。從單鏈表中的頭指針開始，依次與e比較，如果找到返回該元素結點的指針；否則返回null。publicListNodeLocateElem(inte)

{ListNodep=head.next;//p指向第一個結點

while(p!=null){if(p.data!=e)//沒有找到與e相等的元素

p=p.next;//繼續(xù)找下一個元素

else//找到與e相等的元素

break;//退出循環(huán)

}returnp;//返回元素值為e的結點引用

}2.3線性表的鏈式表示與實現④定位操作。定位操作與按內容查找類似，只是返回的是該結點的序號。publicintLocatePos(inte){inti;ListNodep;if(ListEmpty())//查找第i個元素之前，判斷鏈表是否為空

return0;p=head.next;i=1;//從第一個結點開始查找while(p!=null){if(p.data==e)//找到與e相等的元素

returni;//返回該序號

else

//否則繼續(xù)查找

{p=p.next;i=i+1;}}if(p==null)//如果沒有找到與e相等的元素，返回0，表示失敗

return0;}2.3線性表的鏈式表示與實現⑤在第i個位置插入元素e。插入成功返回1，否則返回0；如果沒有與e值相等的元素，返回0表示失敗。假設p指向存儲元素e的結點，要將p指向的結點插入pre和pre.next之間，無需移動其他結點，只需要修改p指向結點的指針域和pre指向結點的指針域即可。即先把pre指向結點的直接后繼結點變成p的直接后繼結點，然后把p變成pre的直接后繼結點，如圖2-14所示booleanInsertList(inti,inte){intj=1;ListNodepre;if(i<1)returnfalse;if(i==1){ListNodenewNode=newListNode(e);head=newNode;returntrue;}

else{pre=head;while(pre.next!=null&&j<i-1){pre=pre.next;j++;}if(j!=i-1){System.out.println("插入位置錯誤!");returnfalse;}ListNodenewNode=newListNode(e);newNode.next=pre.next;pre.next=newNode;returntrue;}}2.3線性表的鏈式表示與實現⑥刪除第i個結點。假設p指向第i個結點，要將該結點刪除，只需要使它的直接前驅結點的指針指向它的直接后繼結點，即可刪除鏈表的第i個結點。將單鏈表中第i個結點刪除可分為3步：

第1步找到第i個結點的直接前驅結點，即第i-1個結點，并用pre指向該結點，p指向其直接后繼結點，即第i個結點，如圖2-19所示；

第2步將p指向結點的數據域賦值給e；

第3步刪除第i個結點，即pre.next=p.next，并釋放p指向結點的內存空間。刪除過程如圖2-20所示。2.3線性表的鏈式表示與實現publicintDeleteList(inti)//刪除單鏈表中的第i個位置的結點。刪除成功返回1，失敗返回0{ListNodepre,p;intj,e;pre=head;j=0;while(pre.next!=null&&j<i-1)//在尋找的過程中確保被刪除結點存在

pre=pre.next;j++;if(pre.next==null||j!=i-1)//如果沒找到要刪除的結點位置，說明刪除位置錯誤

{System.out.println("刪除位置錯誤");return0;}

p=pre.next;pre.next=p.next;//將前驅結點的指針域指向要刪除結點的下一個結點

e=p.data;returne;}2.3線性表的鏈式表示與實現⑦求表長操作。求表長操作即返回單鏈表的元素個數。publicintListLength(){intlength=0;ListNodecur=head;while(cur!=null){cur=cur.next;length++;}returnlength;}2.3.3單鏈表存儲結構與順序存儲結構的優(yōu)缺點1．存儲分配方式順序存儲結構用一組連續(xù)的存儲單元依次存儲線性表的數據元素。單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表的數據元素。2．時間性能采用順序存儲結構時，查找操作時間復雜度為O（1），插入和刪除操作時間復雜度為O（n）。采用單鏈表存儲結構時，查找操作時間復雜度為O（n），插入和刪除操作時間復雜度僅為O(1)。3．空間性能采用順序存儲結構時，需要預先分配存儲空間。采用單鏈表存儲結構時，可根據需要臨時分配，不需要估計問題的規(guī)模大小。2.3線性表的鏈式表示與實現【例2-3】已知兩個單鏈表A和B，其中的元素都是非遞減排列，編寫算法將單鏈表A和B合并得到一個遞減有序的單鏈表C（值相同的元素只保留一個），并要求利用原鏈表結點空間。staticLinkListMergeList(LinkListA,LinkListB)//將非遞減排列的單鏈表A和B中的元素合并到C中，使C中的元素按遞減排列，相同值的元素只保留一個

{ListNodepa,pb,qa,qb;LinkListC=newLinkList();pa=A.head;pb=B.head;

//利用頭插法將鏈表A和B中的結點插入到鏈表C中（先插入元素值較小的結點）

while(pa!=null&&pb!=null)//單鏈表A和B均不空時

{if(pa.data<pb.data)//pa指向結點元素值較小時，將pa指向的結點插入到C中

{qa=pa;pa=pa.next;

//qa指向待插入結點，pa指向下一個結點

if(C.head==null)//單鏈表C為空時，直接將結點插入到C中

{qa.next=C.head;C.head=qa;}

elseif(C.head.data<qa.data)//pa指向的結點元素值不同于已有結點元素值

{qa.next=C.head;C.head=qa;}}2.3線性表的鏈式表示與實現else//pb指向結點元素值較小，將pb指向的結點插入到C中

{qb=pb;pb=pb.next;//qb指向待插入結點，pb指向下一個結點

if(C.head==null)//單鏈表C為空時，直接將結點插入到C中

{qb.next=C.head;C.head=qb;}

elseif(C.head.data<qb.data)//pb指向的結點元素值不同于已有結點元素時

{qb.next=C.head;C.head=qb;}}}while(pa!=null)//如果pb為空、pa不為空，則將pa指向的后繼結點插入到C中

{qa=pa;pa=pa.next;//qa指向待插入結點，pa指向下一個結點

if(C.head!=null&&C.head.data<qa.data){//pa指向的結點元素值不同于已有結點元素時，才將結點插入

qa.next=C.head;C.head=qa;}}

while(pb!=null)//將pb指向的后繼結點插入C中

{qb=pb;

//qb指向待插入結點

pb=pb.next;//pb指向下一個結點

if(C.head!=null&&C.head.data<qb.data)//pb指向的結點元素值不同于已有結點元素

{qb.next=C.head;C.head=qb;}}returnC;}}程序的運行結果如下所示。表A中的元素有6個：81015