實用數(shù)據(jù)結(jié)構(gòu)電子教案第二章數(shù)組與線性表

實用數(shù)據(jù)結(jié)構(gòu)電子教案第二章數(shù)組與線性表第1頁，課件共58頁，創(chuàng)作于2023年2月第二章數(shù)組與線性表

知識點

數(shù)組的基本特點及尋址方式線性數(shù)據(jù)結(jié)構(gòu)的基本特征和基本運算堆棧的定義和基本運算隊列的定義和基本運算循環(huán)隊列的特征，運算以及判斷溢出的條件與普通隊列的差別堆棧、隊列的簡單應用難點

循環(huán)隊列的特點及判斷溢出的條件利用本章的基本知識設計有效的算法解決與線性相關(guān)的應用問題第二章數(shù)組與線性表第2頁，課件共58頁，創(chuàng)作于2023年2月要求

熟練掌握以下內(nèi)容：線性表的基本運算堆棧的特征、基本運算并能設計簡單算法隊列、循環(huán)隊列的特征、基本運算并能設計簡單算法了解以下內(nèi)容：線性表運算時間復雜性分析堆棧、隊列實際應用第二章數(shù)組與線性表第3頁，課件共58頁，創(chuàng)作于2023年2月第二章目錄2.1數(shù)組及其順序存儲結(jié)構(gòu)2.2線性表及其運算2.3堆棧及其應用2.4隊列及其應用2.5應用實例及分析小結(jié)習題與練習第二章數(shù)組與線性表第4頁，課件共58頁，創(chuàng)作于2023年2月2.1.1

數(shù)組數(shù)組是由一些單元組成的，每個單元對應著一組下標值和一個數(shù)組元素。n維數(shù)組的每個單元對應n個下標值。數(shù)組元素可以是基本數(shù)據(jù)類型，如整數(shù)型、實數(shù)型、字符型等，也可以是有多個數(shù)據(jù)項的一種結(jié)構(gòu)。同一數(shù)組中各個元素必須是同一數(shù)據(jù)類型，每個數(shù)組元素都占有相同數(shù)量的存儲單元，才能用下標來唯一的確定數(shù)組中的元素。 第二章數(shù)組與線性表第5頁，課件共58頁，創(chuàng)作于2023年2月2.1.2

數(shù)組的順序存儲結(jié)構(gòu)在計算機中，表示數(shù)組是采用一組連續(xù)的存儲單元順序地存儲各數(shù)組元素?？梢杂孟聵酥惦S機的訪問該數(shù)組的任意一個元素。計算數(shù)組元素存儲地址的公式稱為尋址公式。設數(shù)組為A，每個數(shù)組元素占s個存儲單元，一旦定義了它的維數(shù)和各維的上、下界，就可以得到計算數(shù)組元素地址的尋址公式。第二章數(shù)組與線性表第6頁，課件共58頁，創(chuàng)作于2023年2月1.

一維數(shù)組尋址公式對于一維數(shù)組，若其下標的下界為LB，上界為UB，第一元素（其下標為LB）的地址為Loc(LB)，下標為i的數(shù)組元素A[i]的地址為Loc(i)，則計算Loc(i)的尋址公式為：

Loc(i)=Loc(LB)+(i-LB)*s在C語言中，數(shù)組下標的下界為0，則數(shù)組中任意一元素A[i]的尋址公式為：

Loc(i)=Loc(0)+i*s0≤i≤n-1第二章數(shù)組與線性表第7頁，課件共58頁，創(chuàng)作于2023年2月2.

二維數(shù)組尋址公式在C語言中，采用矩陣元素以行為主存儲，即同一行的元素連續(xù)存放，存儲完一行再存儲下一行。設二維數(shù)組A[m][n]，m、n分別表示數(shù)組的行和列，用Loc(i,j)表示數(shù)組元素A[i][j]的地址，每個單元占用s個存儲單元，則尋址公式為：

Loc(i,j)=Loc(0,0)+(i*n+j)*s0<i≤m-1,0<j≤n-1第二章數(shù)組與線性表第8頁，課件共58頁，創(chuàng)作于2023年2月定義一A[2][3]數(shù)組，對應的矩陣如下：

數(shù)組元素A[1][2]，其下標i=1，j=2，故它前面已經(jīng)有i=1行，每行有3個元素，另外本行有j=2個元素，所以在元素A[1][2]之前，本數(shù)組已有5個元素。第二章數(shù)組與線性表第9頁，課件共58頁，創(chuàng)作于2023年2月3.

三維數(shù)組尋址公式三維數(shù)組A[m][n][p]可分解為p個m*n的二維數(shù)組。按行為主存儲的數(shù)組元素A[i][j][k]的尋址公式為：Loc[i][j][k]=Loc[0][0][0]+(i*n*p+j*p+k)*s0<i≤m-1,0<j≤n-1，0<p≤p-1對于更多維的數(shù)組，數(shù)組元素在內(nèi)存中的存儲可以此類推。返回第二章數(shù)組與線性表第10頁，課件共58頁，創(chuàng)作于2023年2月2.2.1

線性表（LinearList）線性表是由有限數(shù)目的相同類型元素組成的序列。表中的數(shù)據(jù)元素，除了第一個和最后一個以外，都有一個且只有一個前驅(qū)元素，同時也都有一個且只有一個后繼元素；第一個元素只有一個后繼元素而無前驅(qū)元素；最后一個元素只有一個前驅(qū)元素而無后繼元素。線性表的元素個數(shù)n稱為這個表的長度，當n=0時，這個表叫做空表。第二章數(shù)組與線性表第11頁，課件共58頁，創(chuàng)作于2023年2月線性表在計算機內(nèi)存中采用各元素順序存儲的方式，這種存儲結(jié)構(gòu)叫做向量。每個線性表元素叫做這個向量的一個分量。如果已知線性表第一個元素的地址和每個元素占用的存儲單元數(shù)，由任一元素的序號就可以計算出該元素在內(nèi)存中的地址。在編程時以一維數(shù)組表示線性表最簡單，用的也最普遍。第二章數(shù)組與線性表第12頁，課件共58頁，創(chuàng)作于2023年2月2.2.2

線性表的運算對于給定的線性表，可進行如下的基本運算：1.求線性表的長度n；2.在第i個數(shù)據(jù)元素前面插入一個新的數(shù)據(jù)元素；3.刪除第i個數(shù)據(jù)元素；4.存取或更新線性表第i個元素；5.將兩個或兩個以上的線性表合并成一個線性表；6.將一個線性表拆成多個線性表；7.將線性表中各數(shù)據(jù)元素按某個域值（如關(guān)鍵字）遞增或遞減的順序重新排列；8.在線性表中查找滿足某種條件的數(shù)據(jù)元素；第二章數(shù)組與線性表第13頁，課件共58頁，創(chuàng)作于2023年2月1.數(shù)據(jù)元素的插入(insert)設用一個一維數(shù)組A[n]表示此線性表，原來有m個元素（m<n），元素值已給定。規(guī)定數(shù)組的下標從1開始，即這里數(shù)據(jù)元素對應的數(shù)組下標從1到n。要求在第i個元素前插入一個新數(shù)據(jù)元素，值為G，因原線性表的數(shù)據(jù)元素是連續(xù)排列的，中間沒有空單元，所以第i個元素及其后面的各元素均需向后移動一個單元位置，這樣才能將G插入到i位置，且元素總數(shù)由m增加為（m+1）。第二章數(shù)組與線性表第14頁，課件共58頁，創(chuàng)作于2023年2月插入函數(shù)voidinsert(A,intn,m,i,G){intj;if(i<1||i>n+1)printf(“i值錯！\n”); else { for(j=m;j>=i;j--)A[j+1]=A[j];/*將第i個元素及其后面的元素后移*/ A[i]=G; m++;/*線性表長度加1*/ }}

第二章數(shù)組與線性表第15頁，課件共58頁，創(chuàng)作于2023年2月插入函數(shù)分析在循環(huán)語句中，當i=1時，須循環(huán)m次，表示元素插入線性表頭的前面，則原線性表中m個元素均須向后移動一個單元，這是最不利的情況。

當i=m+1時，則循環(huán)一次也不進行，這時元素直接插入到線性表尾的后面，所以線性表的所有m個元素均不移動，這是最好的情況。第二章數(shù)組與線性表第16頁，課件共58頁，創(chuàng)作于2023年2月2.

數(shù)據(jù)元素的刪除(Delete)設用一個一維數(shù)組A[n]表示此線性表，原來有n個元素，元素值已給定。要求刪除第i個數(shù)據(jù)元素，由于線性表元素在數(shù)組中必須連續(xù)排列，中間不能有空單元，故將此元素刪除后，它后面的所有元素都需要向前移動一個單元，且數(shù)據(jù)元素總數(shù)由原來的n減少到n-1.第二章數(shù)組與線性表第17頁，課件共58頁，創(chuàng)作于2023年2月刪除函數(shù)voiddelete(A,intn,i){intj;if(i<1||i>n)printf(“i值錯！\n”);else { for(j=i;j<=n;j++)A[j]=A[j+1]; n--; }}第二章數(shù)組與線性表第18頁，課件共58頁，創(chuàng)作于2023年2月刪除函數(shù)分析在循環(huán)語句中，當i=1時，需循環(huán)(n-1)次，這是要刪除線性表表頭元素，是最不利的情況；當i=n時，則循環(huán)一次也不執(zhí)行，只是將元素數(shù)目n比原來減少一個，而第n個數(shù)據(jù)元素不必再考慮，其余的各單元的元素均維持不變，這是最好的情況。第二章數(shù)組與線性表第19頁，課件共58頁，創(chuàng)作于2023年2月3.

算法的時間復雜性可以用數(shù)據(jù)元素的移動次數(shù)來度量這兩個算法的時間復雜性。插入時，最少循環(huán)0次，最多循環(huán)n次，如i的各種取值概率相同，則平均循環(huán)次數(shù)為n/2；刪除時最少的循環(huán)次數(shù)為0次，最多為n-1次，當i取值概率相同時，平均循環(huán)次數(shù)為(n-1)/2。用數(shù)量級的形式表示線性表插入、刪除運算的時間復雜性均為O(n)。返回第二章數(shù)組與線性表第20頁，課件共58頁，創(chuàng)作于2023年2月2.3.1堆棧(Stack)堆棧也簡稱為棧，是限定在表的一端進行插入或刪除操作的線性表。進行插入或刪除操作的一段稱為棧頂（top），另一端稱為棧底（bottom）。插入元素又稱為入棧（push），刪除元素操作稱為出棧（pop）。不含元素的棧稱為空棧。堆棧元素的插入和刪除只在棧頂進行，總是后進去的元素先出來，所以堆棧又稱為后進先出線性表或LIFO（Last-In-First-Out）表。第二章數(shù)組與線性表第21頁，課件共58頁，創(chuàng)作于2023年2月堆棧的表示堆棧的最簡單的表示方法是采用一維數(shù)組，為形象起見，一般在圖中將堆棧畫成豎直的。設數(shù)組名為STACK，其下標的下界為1，上界為n。一般需用一個變量top記錄當前棧頂?shù)南聵酥?，top也叫做棧指針。第二章數(shù)組與線性表第22頁，課件共58頁，創(chuàng)作于2023年2月本例中top=4topADCB4753216STACK第二章數(shù)組與線性表第23頁，課件共58頁，創(chuàng)作于2023年2月1.入棧（push）

入棧的主要操作是先將棧頂指針加1；然后將入棧元素放到棧頂指針所指示下標值的位置上。設用下標從1到n的數(shù)組ST表示堆棧，入棧的元素值為G，則可得到入棧函數(shù)如下：第二章數(shù)組與線性表第24頁，課件共58頁，創(chuàng)作于2023年2月入棧函數(shù)voidpush(ST,intn,top,G){if(top==n)printf(“棧溢出!\n”);/*顯示棧滿信息*/else {top=top+1;ST[top]=G;}}第二章數(shù)組與線性表第25頁，課件共58頁，創(chuàng)作于2023年2月2.出棧（Pop）

出棧運算時，先將棧頂?shù)脑刂蒂x給某個變量，以備后面的運算應用；然后棧頂指針減1，將棧頂位置下移。假設已指定的變量為x，則出棧的函數(shù)如下：第二章數(shù)組與線性表第26頁，課件共58頁，創(chuàng)作于2023年2月出棧函數(shù)voidpop(ST,inttop,x){if(top==0)printf(“空棧!\n”);/*棧為空顯示相應的信息*/else{x=ST[top];top=top-1;/*棧頂位置下移*/}}第二章數(shù)組與線性表第27頁，課件共58頁，創(chuàng)作于2023年2月2.3.2

堆棧的應用1.堆棧在函數(shù)調(diào)用中的應用:

設有三個函數(shù)A1，A2，A3，這三個函數(shù)有如下的調(diào)用關(guān)系：函數(shù)A1在其函數(shù)體的某處r調(diào)用函數(shù)A2，函數(shù)A2又在其函數(shù)體某處t調(diào)用函數(shù)A3，函數(shù)A3不調(diào)用其他函數(shù)。rtA1A2A3第二章數(shù)組與線性表第28頁，課件共58頁，創(chuàng)作于2023年2月函數(shù)嵌套調(diào)用A1調(diào)用A2，A2調(diào)用A3時的返回地址在堆棧中的情況如右圖所示。toprtSTACK第二章數(shù)組與線性表第29頁，課件共58頁，創(chuàng)作于2023年2月2.堆棧在表達式計算中的應用一個算術(shù)表達式，例如A+B，其中加號“+”稱作運算符，而A，B稱為運算數(shù)。對于由兩個運算數(shù)和一個運算符組成的表達式，習慣上是將運算符寫在兩個運算數(shù)中間，這叫做中綴形式。計算機處理表達式時，常把運算符放在兩個運算數(shù)的后面或前面。1.把運算符放在兩個運算數(shù)的后面，例如AB+，稱為后綴形式，也叫做波蘭式。2.把運算符放在兩個運算數(shù)的前面，例如+AB，則稱做前綴形式，也叫做逆波蘭表達式。第二章數(shù)組與線性表第30頁，課件共58頁，創(chuàng)作于2023年2月算術(shù)表達式的不同運算符有不同的運算優(yōu)先順序，如，在沒有括號時，乘除運算（*或/）要比加減運算（+或-）優(yōu)先進行。下面用一個簡單的例子說明編譯系統(tǒng)在處理算術(shù)表達式時，是如何應用堆棧這種數(shù)據(jù)結(jié)構(gòu)的。假定表達式的運算數(shù)都是使用單個字母表示的，式中無括號且只有加、減、乘、除4種運算，而沒有更復雜的運算，例如表達式X+Y*Z。第二章數(shù)組與線性表第31頁，課件共58頁，創(chuàng)作于2023年2月使用S1和S2兩個堆棧，S1用于存儲運算數(shù)，S2用于存儲運算符。編譯系統(tǒng)處理時，將表達式從左向右逐個掃視一遍，并根據(jù)不同情況按以下原則處理:1)若是運算數(shù)，則將其壓入S1棧；2)若是運算符且S2棧是空棧則將其壓入S2棧；3)若是運算符且S2棧為非空棧，且此運算符的級別高于S2棧頂運算符的級別，則將此運算符壓入S2棧；4)凡不屬于上面三條的情況，則將S2的棧頂運算符與S1棧最上面的兩個運算數(shù)出棧進行運算，并將運算結(jié)果壓入S1棧。第二章數(shù)組與線性表第32頁，課件共58頁，創(chuàng)作于2023年2月圖中每一步上面括號中的數(shù)字表示該步是按哪一條原則處理的。返回第二章數(shù)組與線性表第33頁，課件共58頁，創(chuàng)作于2023年2月2.4.1隊列（Queue）

隊列是一種運算受限制的線性表，元素的添加在表的一端進行，而元素的刪除在表的另一端進行。允許添加元素的一端稱為隊尾（Rear）；允許刪除元素的一端稱為隊頭（Front）。向隊列添加元素稱為入隊，從隊列中刪除元素稱為出隊。新入隊的元素只能添加在隊尾，出隊的元素只能是刪除隊頭的元素，隊列的特點是先進入隊列的元素先出隊，所以隊列也稱作先進先出表或FIFO（First-In-First-Out）表。第二章數(shù)組與線性表第34頁，課件共58頁，創(chuàng)作于2023年2月隊列的表示與堆棧類似，隊列也可以簡單的用一維數(shù)組表示。設數(shù)組名為Queue，其下標下界為1，上界為n。一般使用一個變量r指示隊尾的下標值，叫做隊尾指針；用另一個變量f指示隊頭的下標值，稱為隊頭指針。隊列中元素的數(shù)目等于零稱為空隊列，此時隊頭指針和隊尾指針均為零，即f=r=0。第二章數(shù)組與線性表第35頁，課件共58頁，創(chuàng)作于2023年2月假定有A～F6個元素先后進入隊列，但A、B兩個元素已陸續(xù)出隊了，故隊尾指針r=6，而隊頭指針f=3。第二章數(shù)組與線性表第36頁，課件共58頁，創(chuàng)作于2023年2月1.入隊（insert）

當給隊列插入元素時，隊尾指針r后移而隊頭指針不動，但有一個情況例外，即當向空隊列插入第一個元素時，隊頭指針與隊尾指針同時由0變?yōu)?。

設用下標從1到n的數(shù)組Q表示隊列，且已知待添加的元素在變量x中。第二章數(shù)組與線性表第37頁，課件共58頁，創(chuàng)作于2023年2月入隊函數(shù)voidinsert(Q,intn,f,r,x){if(r==n)printf(“溢出!\n”);/*判斷是否已到數(shù)組末端*/else{r=r+1；

Q[r]=x; /*插入元素*/if(f==0)f=1;/*判斷原來是否為空隊列*/}}第二章數(shù)組與線性表第38頁，課件共58頁，創(chuàng)作于2023年2月2.出隊（Delete）

當從隊列刪除元素時，隊頭指針f后移而隊尾指針r不動，但也有一個情況例外，即當刪除了最后一個元素，隊列成為了空隊列時，隊頭指針與隊尾指針同時變?yōu)?。假設要求將出隊的元素值賦給變量x。第二章數(shù)組與線性表第39頁，課件共58頁，創(chuàng)作于2023年2月出隊函數(shù)voidDelete(Q,intf,r,n,x){if(f==0)printf(“下溢出!\n”);/*判斷是否為空隊列*/else{x=Q[f];/*取隊頭元素給x賦值*/if(f==r){f=0;/*若出隊的是最后一個元素，變成空隊列*/r=0;}elsef=f+1;/*隊頭指針后移*/}}第二章數(shù)組與線性表第40頁，課件共58頁，創(chuàng)作于2023年2月3.

隊列存在的問題由于隊列的入隊操作是在兩端進行的，隨著元素的不斷插入，刪除，兩端都向后移動，隊列會很快移動到數(shù)組末端造成溢出，而前面的單元無法利用。解決辦法：1)每次刪除一個元素后，將整個隊列向前移動一個單元，保持隊列頭總固定在數(shù)組的第一個單元。2)將所用的數(shù)組想象成是頭尾相接的圓環(huán)，當隊列的尾端到達數(shù)組的末端（第n個單元）時，如果再插入元素可繼續(xù)使隊列向數(shù)組的前端（第1個單元）延長，此隊列稱為循環(huán)隊列。第二章數(shù)組與線性表第41頁，課件共58頁，創(chuàng)作于2023年2月2.4.2

循環(huán)隊列圖中陰影部分為隊列中元素。如何判斷一個循環(huán)隊列是滿還是空？第二章數(shù)組與線性表第42頁，課件共58頁，創(chuàng)作于2023年2月判斷循環(huán)隊列是否滿或空滿：隊尾經(jīng)過一個循環(huán)而到達隊首的前一個單元時，這種情況下如果再插入新的元素時，新元素就要把原隊頭的元素覆蓋，因此，當r=f時，插入新的元素會造成隊列首尾重疊；

空：在隊列進行刪除運算時，當f=r時表明刪除的是隊列的最后一個元素，刪除這個元素后，隊列就變成空隊列。第二章數(shù)組與線性表第43頁，課件共58頁，創(chuàng)作于2023年2月循環(huán)隊列入隊函數(shù)voidinsert(Q,intn,f,r,i){if(r==n)r=1;/*到達數(shù)組末端則向前端延長*/else r=r+1;if(r==f)printf(“溢出！\n”);else{Q[r]=i; /*插入新元素*/if(f==0)f=1;/*判定是否原來是空隊列*/}}

第二章數(shù)組與線性表第44頁，課件共58頁，創(chuàng)作于2023年2月循環(huán)隊列出隊函數(shù)voidDelete(Q,intn,f,r,x){if(f==0)printf(“是空隊列！\n”);/*是否為空*/else{x=Q[f]; /*取隊頭元素賦給變量x*/if(f==r) {f=0;r=0;}elseif(f==n)f=1;/*由數(shù)組末端移到前端*/ elsef=f+1;/*隊頭指針后移*/}}

第二章數(shù)組與線性表第45頁，課件共58頁，創(chuàng)作于2023年2月2.4.3隊列的應用

對于各種具有“先進先出”需排隊處理的問題，都可以應用隊列來解決。例如，操作系統(tǒng)在管理和分配系統(tǒng)資源時，大量的應用了隊列這種數(shù)據(jù)結(jié)構(gòu)。1)隊列在輸入/輸出管理中的應用2)對CPU的分配管理返回第二章數(shù)組與線性表第46頁，課件共58頁，創(chuàng)作于2023年2月例2.1一個雙向棧是將兩個棧用一個數(shù)組構(gòu)成，它們的棧底分別設在數(shù)組的兩端。當一個棧中元素的數(shù)目小于n/2時，另一個棧相應的可以大于n/2。試寫出以數(shù)組高端為底的棧的入棧和出棧的算法。第二章數(shù)組與線性表第47頁，課件共58頁，創(chuàng)作于2023年2月例2.1解答這個棧的棧頂指針top2是按相反的方向移動的，因此算法有所不同： 入棧時為：top2=top2-1

出棧時為：top2=top2+1兩個棧在進棧過程中防止溢出的條件是：top2=top1+1。出棧過程中防止下溢出及判斷空棧的條件分別為：top1=0，top2=（n+1）。第二章數(shù)組與線性表第48頁，課件共58頁，創(chuàng)作于2023年2月入棧算法voidpush(ST,intn,top1,top2,G){if(top2==top1+1)printf(“溢出!\n”);else{top2=top2-1;ST[top2]=G; /*插入新元素*/}}第二章數(shù)組與線性表第49頁，課件共58頁，創(chuàng)作于2023年2月出棧算法voidpop(ST,intn,top1,top2,x){if(top2==n+1)printf(“下溢出!\n”);else{x=ST[top2];top2=top2+1;}}第二章數(shù)組與線性表第50頁，課件共58頁，創(chuàng)作于2023年2月例2.2對于循環(huán)隊列，試寫出求隊列長度的算法。解1：設隊列的最大元素個數(shù)為n，設一個計數(shù)器，將其初始值設為0。從隊首開始，沿著隊列順序搜索，每走過一個元素，計數(shù)器加1，直到隊尾，則計數(shù)器的最終值即為隊列的長度。解2：利用隊頭指針與隊尾指針也可求出隊列的長度：當r≥f時，length=r-f；當r<f時，length=(r+n+1)-f。第二章數(shù)組與線性表第51頁，課件共58頁，創(chuàng)作于2023年2月例2.2算法1intQue_Length(Queue,intf,r,n){intlength,k;length=0;k=f;while(k!=r){