《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)》(王路群 主編)第三章課件

第三章通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。線性表?xiàng)ｊ?duì)列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊(duì)列是兩種常用的數(shù)據(jù)類型3.1棧的類型定義3.2棧的應(yīng)用舉例3.3棧類型的實(shí)現(xiàn)3.4隊(duì)列的類型定義3.5隊(duì)列類型的實(shí)現(xiàn)InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())

InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀。

StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。a1a2anan-1

……例一、數(shù)制轉(zhuǎn)換

算法基于原理：

N=(Ndivd)×d+Nmodd

例如：（1348)10=(2504)8，其運(yùn)算過程如下：

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序voidconversion(){InitStack(S);

scanf("%d",N);

while(N){Push(S,N%8);N=N/8;

}

while(!StackEmpty(S))

{

Pop(S,e);

printf("%d",e);

}}//conversion例二、括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或(()])均為不正確的格式。則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。分析可能出現(xiàn)的不匹配的情況:到來的右括弧非是所“期待”的;例如：考慮下列括號(hào)序列：[([][])]12345678到來的是“不速之客”;直到結(jié)束，也沒有到來所“期待”的括弧;Statusmatching(string&exp){

intstate=1;initstack(s);

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...例三、行編輯程序問題如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器”?

并不恰當(dāng)！假設(shè)從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：

while(*s)

putchar(*s++);

while(ch!=EOF&&ch!='\n'){

switch(ch){

case'#':Pop(S,c);break;

case'@':ClearStack(S);break;//重置S為空棧

default

:Push(S,ch);break;

}ch=getchar();//從終端接收下一個(gè)字符

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();}while(ch!=EOF){//EOF為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；11112222

232133

134

424

125

126

416

315

314

43$$$$$$$$求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無通路”，則將當(dāng)前位置從路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置；

do｛

若當(dāng)前位置可通，

則｛將當(dāng)前位置插入棧頂；

若該位置是出口位置，則算法結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條從入口到出口的路徑的算法：

……限于二元運(yùn)算符的表達(dá)式定義:

表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))操作數(shù)::=簡(jiǎn)單變量|表達(dá)式簡(jiǎn)單變量::=標(biāo)識(shí)符|無符號(hào)整數(shù)例五、表達(dá)式求值

表達(dá)式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1+OP+S2則稱

OP+S1+S2為前綴表示法

S1+OP+S2為中綴表示法

S1+S2+OP為后綴表示法

例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+

結(jié)論:1）操作數(shù)之間的相對(duì)次序不變;2）運(yùn)算符的相對(duì)次序不同;3）中綴式丟失了括弧信息，致使運(yùn)算的次序不確定;

4)前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;

5)后綴式的運(yùn)算規(guī)則為:

運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)運(yùn)算符和在它之前出現(xiàn)

且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式;如何從后綴式求值？先找運(yùn)算符,再找操作數(shù)例如：

abcde/f+abd/ec-d/e(c-d/e)f如何從原表達(dá)式求得后綴式？

每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定，在后綴式中,優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。分析“原表達(dá)式”和“后綴式”中的運(yùn)算符:原表達(dá)式:a+bcd/ef后綴式:abc+de/f

從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立暫存運(yùn)算符的棧;2)設(shè)表達(dá)式的結(jié)束符為“#”,

予設(shè)運(yùn)算符棧的棧底為“#”3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式;6)

“(”

對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。從原表達(dá)式求得后綴式的規(guī)律為：voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=#){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

()

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(!Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}

//switch例六、實(shí)現(xiàn)遞歸將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，

需先完成三項(xiàng)任務(wù)：保存被調(diào)函數(shù)的計(jì)算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項(xiàng)任務(wù)：遞歸工作棧：遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個(gè)記錄。當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，例如：多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是:此時(shí)的內(nèi)存管理實(shí)行“棧式管理”后調(diào)用先返回！例如：voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號(hào)為1至n//的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號(hào)為１的圓盤從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號(hào)為１至n-1的//圓盤移到y(tǒng),z作輔助塔5move(x,n,z);//將編號(hào)為n的圓盤從x移到z6hanoi(n-1,y,x,z);//將y上編號(hào)為１至n-1的//圓盤移到z,x作輔助塔7}8}83abc返址nxyz52acb51abc71cabvoidhanoi(intn,charx,chary,charz){1if(n==1)2move(x,1,z);3else{4hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7}8}

3.3 棧類型的實(shí)現(xiàn)順序棧鏈棧//-----棧的順序存儲(chǔ)表示-----

#defineSTACK_INIT_SIZE100;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。

StatusInitStack(SqStack&S,intmaxsize){

//構(gòu)造一個(gè)最大空間為maxsize的空順序棧SS.base=new

ElemType[maxsize];

if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base;S.stacksize=maxsize;

returnOK;}

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize)

//棧滿

returnOVERFLOW;

*S.top++=e;

returnOK;}StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，//用e返回其值，并返回OK；//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;e=*--S.top;

returnOK;}棧頂指針鏈?！腶1an注意:鏈棧中指針的方向an-1ADTQueue{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定其中a1端為隊(duì)列頭，an端為隊(duì)列尾基本操作：3.4隊(duì)列的類型定義}

ADTQueue隊(duì)列是一種運(yùn)算受限制的線性表，元素的添加在表的一端進(jìn)行，而元素的刪除在表的另一端進(jìn)行。允許添加元素的一端稱為隊(duì)尾（Rear）；允許刪除元素的一端稱為隊(duì)頭（Front）。向隊(duì)列添加元素稱為入隊(duì)，從隊(duì)列中刪除元素稱為出隊(duì)。新入隊(duì)的元素只能添加在隊(duì)尾，出隊(duì)的元素只能是刪除隊(duì)頭的元素，隊(duì)列的特點(diǎn)是先進(jìn)入隊(duì)列的元素先出隊(duì)，所以隊(duì)列也稱作先進(jìn)先出表或FIFO（First-In-First-Out）表。隊(duì)列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列QDestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：隊(duì)列Q被銷毀，

不再存在。QueueEmpty(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。

QueueLength(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。

GetHead(Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：用e返回Q的隊(duì)頭元素。a1a2an……

ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。

EnQueue(&Q,e)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。a1a2ane……

DeQueue(&Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。a1a2an……

3.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚笱h(huán)隊(duì)列——順序映象

typedefstructQNode{//結(jié)點(diǎn)類型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;鏈隊(duì)列——鏈?zhǔn)接诚髏ypedefstruct{//鏈隊(duì)列類型QueuePtrfront;//隊(duì)頭指針QueuePtrrear;//隊(duì)尾指針}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊(duì)列

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個(gè)空隊(duì)列Q

Q.front=Q.rear=newQNode;

if(!Q.front)exit(OVERFLOW);//存儲(chǔ)分配失敗Q.front->next=NULL;

returnOK;}

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素p=newQNode;

if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;

returnOK;}

StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，//用e返回其值，并返回OK；否則返回ERROR

if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;delete(p);returnOK;}if(Q.rear==p)Q.rear=Q.front;隊(duì)列的順序表示與堆棧類似，隊(duì)列也可以簡(jiǎn)單的用一維數(shù)組表示。設(shè)數(shù)組名為Queue，其下標(biāo)下界為0，上界為n-1。一般使用一個(gè)變量r指示隊(duì)尾的下一個(gè)位置的下標(biāo)值，叫做隊(duì)尾指針；用另一個(gè)變量f指示隊(duì)頭的下標(biāo)值，稱為隊(duì)頭指針。隊(duì)列中元素的數(shù)目等于零稱為空隊(duì)列，此時(shí)隊(duì)頭指針和隊(duì)尾指針均為零，即f=r=0。假定有A～E5個(gè)元素先后進(jìn)入隊(duì)列，但A、B兩個(gè)元素已陸續(xù)出隊(duì)了，故隊(duì)尾指針r=6，而隊(duì)頭指針f=3。1.入隊(duì)（insert）

當(dāng)給隊(duì)列插入元素時(shí)，隊(duì)尾指針r后移而隊(duì)頭指針不動(dòng)，但有一個(gè)情況例外，即當(dāng)向空隊(duì)列插入第一個(gè)元素時(shí)，隊(duì)頭指針與隊(duì)尾指針同時(shí)由0變?yōu)?。

設(shè)用下標(biāo)從1到n的數(shù)組Q表示隊(duì)列，且已知待添加的元素在變量x中。入隊(duì)函數(shù)voidinsert(Q,intn,f,r,x){if(r==n-1)printf(“溢出!\n”);/*判斷是否已到數(shù)組末端*/else{r=r+1；Q[r]=x; /*插入元素*/if(f==0)f=1;/*判斷原來是否為空隊(duì)列*/}}2.出隊(duì)（Delete）

當(dāng)從隊(duì)列刪除元素時(shí)，隊(duì)頭指針f后移而隊(duì)尾指針r不動(dòng)，但也有一個(gè)情況例外，即當(dāng)刪除了最后一個(gè)元素，隊(duì)列成為了空隊(duì)列時(shí)，隊(duì)頭指針與隊(duì)尾指針同時(shí)變?yōu)?。假設(shè)要求將出隊(duì)的元素值賦給變量x。出隊(duì)函數(shù)voidDelete(Q,intf,r,n,x){if(f==0)printf(“下溢出!\n”);/*判斷是否為空隊(duì)列*/else{x=Q[f];/*取隊(duì)頭元素給x賦值*/if(f==r){f=0;/*若出隊(duì)的是最后一個(gè)元素，變成空隊(duì)列*/r=0;}elsef=f+1;/*隊(duì)頭指針后移*/}}3.隊(duì)列存在的問題由于隊(duì)列的入隊(duì)操作是在兩端進(jìn)行的，隨著元素的不斷插入，刪除，兩端都向后移動(dòng)，隊(duì)列會(huì)很快移動(dòng)到數(shù)組末端造成溢出，而前面的單元無法利用。解決辦法：1)每次刪除一個(gè)元素后，將整個(gè)隊(duì)列向前移動(dòng)一個(gè)單元，保持隊(duì)列頭總固定在數(shù)組的第一個(gè)單元。2)將所用的數(shù)組想象成是頭尾相接的圓環(huán)，當(dāng)隊(duì)列的尾端到達(dá)數(shù)組的末端（第n個(gè)單元）時(shí)，如果再插入元素可繼續(xù)使隊(duì)列向數(shù)組的前端（第1個(gè)單元）延長(zhǎng)，此隊(duì)列稱為循環(huán)隊(duì)列。#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{QElemType*base;//動(dòng)態(tài)分配存儲(chǔ)空間

intfront;//頭指針，若隊(duì)列不空，//指向隊(duì)列頭元素intrear;//尾指針，若隊(duì)列不空，指向//隊(duì)列尾元素的下一個(gè)位置

intqueuesize;}SqQueue;循環(huán)隊(duì)列——順序映象圖中陰影部分為隊(duì)列中元素。如何判斷一個(gè)循環(huán)隊(duì)列是滿還是空？

StatusInitQueue(SqQueue&Q,

intmaxsize){//構(gòu)造一個(gè)最大存儲(chǔ)空間為maxsize的//空循環(huán)隊(duì)列QQ.base=newElemType[maxsize];

if(!Q.base)exit(OVERFLOW);Q.queuesize=maxsize;Q.front=Q.rear=0;

returnOK;

}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e為Q的新的隊(duì)尾元素

if((Q.rear+1)%Q.queuesize==Q.front)

returnERROR;//隊(duì)列滿Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%Q.queuesize;

returnOK;}

StatusDeQueue(SqQueue&Q,ElemType&e){

//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，//用e返回其值，并返回OK;否則返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

Q.front=(Q.front+1)%Q.queuesize;

returnOK;}隊(duì)列應(yīng)用示例一、計(jì)算n行楊輝三角的值二、“劃分無沖突子集問題”求解第1行11第2行121第3行1331第4行14641二項(xiàng)式系數(shù)值（楊輝三角）設(shè)第i-1行的值：(a[0]=0)a[1]..a[i](a[i+1]=0)則第i行的值：b[j]=a[j-1]+a[j],j=1,2,…,i+1利用循環(huán)隊(duì)列計(jì)算二項(xiàng)式的過程：假設(shè)只計(jì)算四行，則隊(duì)列的最大容量為5。1100q.frontq.rear11001q.frontq.rear11021q.frontq.rear11021q.frontq.rear10021q.frontq.rear10121q.frontq.rear10121q.frontq.rear10123q.frontq.rear10133q.frontq.rear10133q.frontq.reardo{DeQueue(Q,s);GetHead(Q,e);if(e!=0)printf(“%d”,e);EnQueue(Q,s+e);}while(e!=0);

某運(yùn)動(dòng)會(huì)設(shè)立N個(gè)比賽項(xiàng)目，每個(gè)運(yùn)動(dòng)員可以參加一至三個(gè)項(xiàng)目。試問如何安排比賽日程既可以使同一運(yùn)動(dòng)員參加的項(xiàng)目不安排在同一單位時(shí)間進(jìn)行，又使總的競(jìng)賽日程最短。

若將此問題抽象成數(shù)學(xué)模型，則歸屬于“劃分子集”問題。N個(gè)比賽項(xiàng)目構(gòu)成一個(gè)大小為n的集合，有同一運(yùn)動(dòng)員參加的項(xiàng)目則抽象為“沖突”關(guān)系。

例如：某運(yùn)動(dòng)會(huì)設(shè)有9個(gè)項(xiàng)目:A={0，1，2，3，4，5，6，7，8}，七名運(yùn)動(dòng)員報(bào)名參加的項(xiàng)目分別為：（1，4，8）、（1，7）、（8，3）、（1，0，5）、（3，4）、（5，6，2）、（6，4）它們之間的沖突關(guān)系為:R={（1，4）,（4，8）,（1，8）,（1，7）,（8，3）,（1，0）,（0，5）,（1，5）,（3，4）,（5，6）,（5，2）,（6，2）,（6，4）}將集合A劃分成k個(gè)互不相交的子集A1，A2，…，Ak（k≤n），使同一子集中的元素均無沖突關(guān)系，并要求劃分的子集數(shù)目盡可能地少?！皠澐肿蛹眴栴}即為:

對(duì)前述例子而言，問題即為:同一子集的項(xiàng)目為可以同時(shí)進(jìn)行的項(xiàng)目，顯然希望運(yùn)動(dòng)會(huì)的日程盡可能短。

可利用“過篩”的方法來解決劃分子集問題。從第一個(gè)元素考慮起，凡不和第一個(gè)元素發(fā)生沖突的元素都可以和它分在同一子集中，然后再“過篩”出一批互不沖突的元素為第二個(gè)子集，依次類推，直至所有元素都進(jìn)入某個(gè)子集為止。

012345678001000100011000110112000001100300001000140101001015111000100600101100070100000008010110000012345678145684588

010001000

010002100

010012101

020012101

為了減少重復(fù)察看R數(shù)組的時(shí)間，可另設(shè)一個(gè)數(shù)組clash[n]記錄和當(dāng)前已入組元素發(fā)生沖突的元素的信息。每次新開辟一組時(shí)，令clash數(shù)組各分量的值均為“0”，當(dāng)序號(hào)為“i”的元素入組時(shí)，將和該元素發(fā)生沖突的信息記入clash數(shù)組。pre(前一個(gè)出隊(duì)列的元素序號(hào))=n;組號(hào)=0;全體元素入隊(duì)列;while(隊(duì)列不空){隊(duì)頭元素i出隊(duì)列;if(i<pre)//開辟新的組{組號(hào)++;clash數(shù)組初始化;}if(i能入組){i入組，記下序號(hào)為i的元素所屬組號(hào);修改clash數(shù)組;

}elsei重新入隊(duì)列;pre=i;}劃分子集算法的基本思想:

1.掌握棧和隊(duì)列類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng)注意棧滿和棧空的條件以及它們的描述方法。3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述方法。

4.理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。QUICKQUIZ(3)一、基本知識(shí)題1.什么是棧？什么是隊(duì)列？它們各自的特點(diǎn)是什么？2.線性表、棧、隊(duì)列有什么異同？3.簡(jiǎn)述棧的入棧、出棧操作的過程。4.在循環(huán)隊(duì)列中簡(jiǎn)述入隊(duì)、出隊(duì)操作的過程。二、算法設(shè)計(jì)題1.設(shè)用一維數(shù)組stack[n]表示一個(gè)堆棧，若堆棧中一個(gè)元素需占用length個(gè)數(shù)組單元（length>1），試寫出其入棧、出棧操作的算法。2.試編寫一個(gè)遍歷及顯示隊(duì)列中元素的算法。

3.設(shè)一循環(huán)隊(duì)列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)內(nèi)含元素個(gè)數(shù)的計(jì)數(shù)器，試寫出相應(yīng)的入隊(duì)、出隊(duì)算法。4.設(shè)計(jì)一算法能判斷一個(gè)算術(shù)表達(dá)式中的圓括號(hào)配對(duì)是否正確。（提示：對(duì)表達(dá)式進(jìn)行掃描，凡遇到“（”就進(jìn)棧，遇到“）”就退出棧頂?shù)摹埃ā?，表達(dá)式掃描完畢時(shí)棧若為空則圓括號(hào)配對(duì)正確。）返回習(xí)題解答(3)一、基本知識(shí)題答案1.答：棧是限定在表的一端進(jìn)行插入或刪除操作的線性表；隊(duì)列是元素的添加在表的一端進(jìn)行，而元素的刪除在表的另一端進(jìn)行的線性表；棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。2.答：棧和隊(duì)列都是線性表，但是是受限的線性表，對(duì)插入、刪除運(yùn)算加以限制。棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表；而隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表。3.答：棧的入棧、出棧操作均在棧頂進(jìn)行，棧頂指針指向棧頂元素的下一個(gè)位置。入棧操作先將入棧元素放到棧頂指針?biāo)甘镜奈恢蒙?，然后將棧頂指針?。出棧操作先將棧頂指針減1，然后從棧頂指針指向位置取值。

4.答：在循環(huán)隊(duì)列中，設(shè)隊(duì)首指針指向隊(duì)首元素，隊(duì)尾指針指向隊(duì)尾元素后的一個(gè)空閑元素。在隊(duì)列不滿時(shí)，可執(zhí)行入隊(duì)操作，此時(shí)先送值到隊(duì)尾指針指向的空閑元素，隊(duì)尾指針再加1（要取模）。在隊(duì)列不空時(shí)，可執(zhí)行出隊(duì)操作，此時(shí)先從隊(duì)首指針指向處取值，隊(duì)首指針再加1（要取模）。二、算法設(shè)計(jì)題答案1.解：用一整型變量top表示棧頂指針，top為0時(shí)表示棧為空。如果棧不空，則從