數(shù)據(jù)結(jié)構(gòu)與算法,線性表,矩陣,廣義表(3學(xué)時)

第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法什么是數(shù)據(jù)結(jié)構(gòu)？定義1--是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。定義2----按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計算機語言并按一定的存儲方式把它們存儲在計算機的存儲器中，并在其上定義了一個運算的集合。例如：數(shù)據(jù)的物理結(jié)構(gòu)包括

的表示和

的表示。答案：數(shù)據(jù)元素

，

數(shù)據(jù)元素間關(guān)系

。邏輯結(jié)構(gòu)--數(shù)據(jù)元素間的相互關(guān)系。存儲結(jié)構(gòu)（物理結(jié)構(gòu)）---數(shù)據(jù)元素及其關(guān)系（數(shù)據(jù)的邏輯結(jié)構(gòu)）在計算機存儲器中的存儲形式。邏輯結(jié)構(gòu)---劃分方法一（1）線性結(jié)構(gòu)（如：線性表、棧、隊列、串）（2）非線性結(jié)構(gòu)（如：樹、圖）邏輯結(jié)構(gòu)---劃分方法二（1）集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。（2）線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。（3）樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。例如：對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有集合________.________以及圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)四種。答案：線性結(jié)構(gòu)，樹型結(jié)構(gòu)例如：從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。

A、動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C、線性結(jié)構(gòu)、非線性結(jié)構(gòu)

D、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)（3）散列存儲結(jié)構(gòu)（4）索引存儲結(jié)構(gòu)例如：下面哪個不是數(shù)據(jù)結(jié)構(gòu)的基本存儲方法（）A順序方法B鏈接方法C隨機方法D索引方法答案：C5抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(AbstractDataType

，簡稱ADT)：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。

ADT的定義僅是一組邏輯特性描述，與其在計算機內(nèi)的表示和實現(xiàn)無關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。

ADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。例如：數(shù)據(jù)結(jié)構(gòu)的二元組定義DS={D,S}，D是數(shù)據(jù)元素的有限集合，而S則是D上的（）的有限集合。A.數(shù)組B.數(shù)據(jù)項C.關(guān)系D.操作答案：C

算法是解決某一類問題的步驟的描述。一般而言，算法應(yīng)該符合以下五項要求：(1)輸入：它接受一些輸入（有些情況下不需要輸入）；(2)輸出：至少產(chǎn)生一個輸出；(3)確定性：算法的每一步必須有充分明確的含義，不可以有歧義；(4)有窮性：算法是一個有限指令集，并一定在有限步驟之后終止；(5)可行性：算法的每一步必須在計算機能處理的范圍之內(nèi)

算法的描述不依賴于任何一種計算機語言以及具體的實現(xiàn)手段?？梢杂米匀徽Z言、流程圖，偽代碼等方法來描述。10/25算法

衡量、比較算法優(yōu)劣的指標(biāo)主要有兩個：

空間復(fù)雜度S(n)——根據(jù)算法寫成的程序在執(zhí)行時占用的存儲空間的大小。該存儲空間一般包括三個方面：（1）指令常數(shù)變量所占用的存儲空間;

（2）輸入數(shù)據(jù)所占用的存儲空間;

（3）輔助(存儲)空間。一般地，算法的空間復(fù)雜度指的是輔助空間。

時間復(fù)雜度

T(n)——根據(jù)算法寫成的程序在執(zhí)行時耗費時間的長度。常用程序中最深層循環(huán)內(nèi)的語句的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示12/25算法分析例如：一個算法具有以下5個重要特性。()A．有窮性、確定性、可行性、輸入、輸出

B．可行性、可移植性、可擴充性、輸入、輸出

C．確定性、有窮性、穩(wěn)定性、輸入、輸出

D．易讀性、穩(wěn)定性、安全性、輸入、輸出答案：A例如：下面敘述正確的是（）

A、算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)

B、算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)

C、算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止

D、以上三種描述都不對答案：C第二部分線性表、棧、隊列

線性表“線性表(LinearList)”是由同一類型的數(shù)據(jù)元素構(gòu)成的序列的線性結(jié)構(gòu)。

線性表中元素的個數(shù)稱為線性表的長度；當(dāng)一個線性表中沒有元素（長度為0）時，稱為空表。

線性表的順序存儲實現(xiàn)在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素。一維數(shù)組在內(nèi)存中占用的存儲空間就是一組連續(xù)的存儲區(qū)域。

在長度為n的線性表L中的第i(1≤i≤n+1)個位置插入新結(jié)點，平均需要移動元素的次數(shù)為n/2最壞：當(dāng)i=1,需移動全部n個結(jié)點（O(n)）最好：當(dāng)i=n+1（在表尾插入）,無需用移動結(jié)點。（O(1)）在長度為n的線性表L中刪除第i(1≤i≤n)個元素，其時間同樣主要耗費在表中結(jié)點的移動操作上，平均需要移動元素的次數(shù)為(n-1)/2最壞：當(dāng)i=1,需移動n-1個結(jié)點（O(n)）最好：當(dāng)i=n（刪除表尾元素）,無需用移動結(jié)點。（O(1)）

順序存儲的優(yōu)缺點優(yōu)點1）無須為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間（緊湊結(jié)構(gòu)）。2）可以方便地隨機存取表中的任一結(jié)點。缺點1）插入和刪除平均須移動一半結(jié)點。2）存儲分配只能預(yù)先進(jìn)行（靜態(tài)）例如1、若某線性表最常用的操作是存取任一個指定序號的元素和在最后進(jìn)行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。

A、順序表B、單鏈表C、帶頭結(jié)點的雙循環(huán)鏈表D、單循環(huán)鏈表2、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為()(1<=i<=n+1)。

A．0(O)B．0(1)C．0(n)D．0(n2)3、如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用()存儲方式最節(jié)省時間。

A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．順序表答案：A答案：C答案：D

線性表的鏈?zhǔn)酱鎯崿F(xiàn)不要求邏輯上相鄰的兩個數(shù)據(jù)元素物理上也相鄰，它是通過“鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系。因此對線性表的插入、刪除不需要移動數(shù)據(jù)元素，只需要修改“鏈”。12/25線性表單鏈表（帶頭結(jié)點，不帶頭結(jié)點）單向循環(huán)鏈表雙向循環(huán)鏈表頭結(jié)點的作用：頭結(jié)點指向整個鏈表，起標(biāo)識作用，此外，還能簡化插入、刪除等操作。例如1、從帶頭結(jié)點的雙向循環(huán)鏈表中刪除p指針?biāo)赶虻暮罄^結(jié)點的操作時如下哪個？（

）2、在單鏈表中設(shè)置頭結(jié)點的作用是

標(biāo)識該鏈表

且

能簡化插入、刪除等操作

。3、對于雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共（

）個。A、1B、2C、3D、44、帶頭結(jié)點的雙循環(huán)列表L為空表的條件是

L->prior==L==L->next.5、在一個雙鏈表中，在*p結(jié)點之前插入*q結(jié)點的操作是()。

A.p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;

B.q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;

C.q->next=p;p->next=q;q->prior->next=q;q->next=p;D.p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;答案：D答案：D答案：D編程題1、有一個帶頭結(jié)點的單鏈表L={a1，b1，a2，b2，……，an，bn}，請設(shè)計一個函數(shù)將其拆成兩個帶頭結(jié)點的單鏈表A和B，正序鏈表A={a1，a2，…，an}逆序鏈表B={bn，bn-1，……，b2，b1}。注：函數(shù)的頭部為voidsplit（Linklist*L，LinkList*A，LinkList*B）。2、假設(shè)用單鏈表方式來存儲整數(shù)序列，如下形式：請編寫一個遞歸算法，對這樣的鏈表進(jìn)行處理，重復(fù)結(jié)點（值相同的結(jié)點）僅保留排在最前面的一個，最后返回新鏈表的首地址。3、設(shè)有一個表頭指針為first的單鏈表（不帶頭結(jié)點），請設(shè)計算法通過一趟遍歷將鏈表就地逆轉(zhuǎn)（例如a->b->c->d變?yōu)閐->c->b->a),要求逆轉(zhuǎn)后表頭指針first指向原鏈表的最后一個結(jié)點，請寫出C語言程序。題型小結(jié)：鏈表逆置刪除鏈表中重復(fù)元素拆分+逆置

例：有一個帶頭結(jié)點的單鏈表L={a1，b1，a2，b2，……，an，bn}，請設(shè)計一個函數(shù)將其拆成兩個帶頭結(jié)點的單鏈表A和B，正序鏈表A={a1，a2，…，an}逆序鏈表B={bn，bn-1，……，b2，b1}。

注：函數(shù)的頭部為voidsplit（Linklist*L，LinkList*A，LinkList*B）。答：算法思想：掃描單鏈表L，將奇數(shù)位置的元素添加到鏈表A中，將偶數(shù)位置的元素逆向添加到鏈表B中。voidsplit（Linklist*L，LinkList*A，LinkList*B）{

Linklist*pL=L->next,*pA=A,*pB=B,*temp;

while(pL!=NULL){

pA->next=pL;pA=pL;//把奇數(shù)位置的結(jié)點正向添加到鏈表A中

pL=pL->next;//pL指向下一個結(jié)點

pA->next=NULL;（注意這兩句順序不能顛倒）

temp=pL->next;//把PL的下一個結(jié)點的地址先保存下來

pL->next=pB->next;//把偶數(shù)位置的結(jié)點逆向添加到鏈表B中

pB->next=pL;

（注意：實際上是鏈表逆置的主要操作）

pL=temp;}}鏈表A的建立過程類似于尾插入法，鏈表B的建立過程類似于頭插入法。刪除重復(fù)元素

例：假設(shè)用單鏈表方式來存儲整數(shù)序列，如下形式：

請編寫一個遞歸算法，對這樣的鏈表進(jìn)行處理，重復(fù)結(jié)點（值相同的結(jié)點）僅保留排在最前面的一個，最后返回新鏈表的首地址。例如，若有上述鏈表，則處理后的新鏈表如下：

算法思想：從單鏈表的第一個結(jié)點開始，對每個結(jié)點進(jìn)行檢查：檢查鏈表中該結(jié)點的所有后繼結(jié)點，只要有值和該結(jié)點的值相同，則刪除之；然后檢查下一個結(jié)點，直到所有的結(jié)點都檢查。遞歸算法：voidRecDelete_Node(LNode*L){//刪除以L為頭結(jié)點的單鏈表中所有值相同的結(jié)點

if(L==NULL)return;LNode*pre=L,*cur=pre->next;//pre始終指向當(dāng)前結(jié)點cur的前一個位置while(cur!=NULL)//檢查鏈表中所有結(jié)點{if(cur->data==L->data){pre->next=cur->next;free(cur);cur=pre->next;}else{pre=cur;cur=cur->next;}}L=L->next;

RecDeleteNote(L);}非遞歸算法：voidIterDeleteNode(LNode*L){//刪除以單鏈表L中所有值相同的結(jié)點

LNode*p=L,*q,*ptr;while(p!=NULL)//檢查鏈表中所有結(jié)點{q=p,ptr=p–>next;//檢查結(jié)點p的所有后繼結(jié)點ptrwhile(ptr!=NULL){if(ptr–>data==p->data){q->next=ptr->next;free(ptr);ptr=q->next;}else{q=ptr;ptr=ptr–>next;}}p=p->next;}}棧

堆棧的定義“堆棧（Stack）”可以認(rèn)為是操作受到一定約束的線性表，插入和刪除操作都作用在一個稱為棧頂(Top)的端點位置。入棧（Push）：把數(shù)據(jù)插入棧頂位置；出棧（Pop）

：從棧頂中取出數(shù)據(jù)。棧的特點：先進(jìn)后出（后進(jìn)先出）棧的應(yīng)用：數(shù)制轉(zhuǎn)換，表達(dá)式求值，括號匹配，函數(shù)（遞歸）調(diào)用3、設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用下列哪種數(shù)據(jù)結(jié)構(gòu)最好？（

）A、棧B、隊列C、線性表的順序存儲結(jié)構(gòu)D、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)答案：5答案：D答案：A棧例如

1、設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a1，a2，a3，a4，a5，a6，a7和a8依次通過棧S，一個元素出棧后立即進(jìn)入隊列Q，若8個元素出隊列的順序是a3，a6，a7，a5，a8，a4，a2，a1，則棧的容量至少應(yīng)該是_______.2、若5個元素的出棧序列為“e1，e2，e3，e4，e5”，則可能的入棧序列為（

）A、e2，e3,e4,e1,e5B、e3,e1,e4,e5,e2C、e5,e3,e4,e2,e1D、e4,e1,e3,e2,e5答案：B4．一個棧的進(jìn)棧序列是abcde，則棧的輸出序列不可能的是()。

A.edcbaB.decbaC.dceabD.abcde5．表達(dá)式a*(b+c)-d的后綴表達(dá)式是()。

A．a(chǎn)bcd*+-B．a(chǎn)bc+*d-C．a(chǎn)bc*+d-D．-+*abcd答案：C棧3、表達(dá)式“#3*2^(4+2*2-6*3)-5#”求值過程中當(dāng)掃描到6時，對象棧和算符棧為（），其中^為乘冪。A、3,2,4,1,1；#*^(+*-B、3,2,8；#*^-C、3,2,4,2,2；#*^(-D、3,2,8；#*^(-答案：D22將過程“中綴->后綴”與“對后綴求解”，合并為一個程序，邊掃描邊運算！算法的基本思想及處理規(guī)則定義兩個棧：一個稱為OPTR，用于存放運算符；另一個稱作OPND，用于寄存操作數(shù)或運算結(jié)果。初始化：首先置操作數(shù)棧為空；運算符棧OPTR棧低元素為“#”。依次讀入表達(dá)式中的各字符操作數(shù)：直接進(jìn)OPND棧。操作符：如當(dāng)前運算符<棧頂運算符，棧頂運算符出棧，并從OPND棧中退出兩個操作數(shù)，執(zhí)行棧頂元素的操作符的運算，再將計算結(jié)果入OPND棧。如當(dāng)前運算符>棧頂運算符：當(dāng)前運算符入OPTR棧。如當(dāng)前運算符=棧頂運算符（1）“（”=“）”，脫去括號并接收下一字符；（2）“#”=“#”，表示整個表達(dá)式求值完畢。

利用棧直接計算中綴表達(dá)式：＋－×／()#＋>><<<>>－>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=23步驟中綴表達(dá)式STACK(底

頂)OPND棧(底

頂)13＋(5－8／4)×2##2＋(5－8／4)×2##33(5－8／4)×2##＋345－8／4)×2##＋(35－8／4)×2##＋(3568／4)×2##+(－357／4)×2##＋(－35884)×2##＋(－/3589)×2##＋(－/358410)×2##＋(－35211)×2##＋(3312×2##＋33132##＋×3314##＋×33215##+3616##9

直接計算中綴表達(dá)式示例：（

3＋(5－8／4)×2

）24建立一個棧，用作符號進(jìn)出建立一個字符數(shù)組，用來存放后綴表達(dá)式轉(zhuǎn)換規(guī)則：從左到右遍歷中綴表達(dá)式的每個數(shù)字和符號。若是數(shù)字，則存入字符數(shù)組，作為后綴表達(dá)式的一部分；若是符號棧為空，則進(jìn)棧；左括號“（”，進(jìn)棧；右括號“）”，將棧頂元素依次取出存入字符數(shù)組（出棧），直到遇到左括號“（”，脫括號；其他情況，判斷其與棧頂符號的優(yōu)先級優(yōu)先級>

棧頂符號，進(jìn)棧優(yōu)先級<棧頂符號，則將優(yōu)先級高于該符號的那些棧頂符號依次出棧并存入字符數(shù)組，然后該符號進(jìn)棧。若到中綴表達(dá)式最后，則將棧中符號依次取出，存入字符數(shù)組。

中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式更好的辦法：利用樹型結(jié)構(gòu)實現(xiàn)！25隊列

入隊：在隊尾插入數(shù)據(jù)出隊：從隊列頭部取出數(shù)據(jù)。隊列的特點：

“先進(jìn)先出”

隊列的定義“隊列(Queue)”是具有一定操作約束的線性表，插入和刪除操作有一定要求：只能在一端（隊尾）插入，而在另一端（隊首）刪除。隊列的順序存儲：存在“假溢出”現(xiàn)象，用循環(huán)隊列可以克服“假溢出”現(xiàn)象。隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)循環(huán)隊列：隊空、隊滿的條件，入隊、出隊的操作，循環(huán)隊列中元素的個數(shù)等?！粞h(huán)隊列為空：Q.front==Q.rear

◆循環(huán)隊列滿：(Q.rear+1)%MaxSize==Q.front

◆入隊的操作：Q.rear

=(Q.rear+1)%MaxSize◆出隊的操作:Q.front

=(Q.front+1)%MaxSize◆循環(huán)隊列中元素的個數(shù):(Q.rear-Q.front+MaxSize)%MaxSize

2．循環(huán)隊列A[0．．m-1]存放其元素值，用front和rear分別表示隊共和隊尾，當(dāng)前隊列的長度是()。A．rear-front+lB．rear-frontC．(rear-front+m)％mD．(rear-front)％m答案：C例如1、棧和隊列都是

操作受限的線性表

，它們的共同點是只允許在它們的

端點

進(jìn)行插入和刪除。

答案：D3．環(huán)形隊列qu的隊空條件是()。

A.(qu.rear+l)%MaxSize==(qu.front+l)%MaxSize:

B.(qu.rear+l)%MaxSize==qu.front+l:

C.(qu.rear+l)%MaxSize==qu.front:

D.qu.rear==qu.front：1、設(shè)數(shù)組a[1…50,1…80]的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a[45,68]的存儲地址為

9174

；若以列序為主序順序存儲，則元素a[45,68]的存儲地址為

8788

。2、數(shù)組A[0…5，0…6]的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5,5]的地址是（）

A、1175B、1180C、1205D、1210二維數(shù)組采用順序存儲結(jié)構(gòu)，有行優(yōu)先和列優(yōu)先之分。答案：A數(shù)組與廣義表廣義表表長n表深h表頭表尾A=()01————B=(e)11e()C