日本免费精品视频,男人的天堂在线免费视频,成人久久久精品乱码一区二区三区,高清成人爽a毛片免费网站

第3章棧和隊列

3.1本章知識體系1. 知識結構圖

本章的知識結構如圖3.1所示。

圖3.1第3章知識結構圖

2. 基本知識點(1) 棧、隊列和線性表的異同。(2) 順序棧的基本運算算法設計。(3) 鏈棧的基本運算算法設計。(4) 順序隊的基本運算算法設計。(5) 環形隊列和非環形隊列的特點。(6) 鏈隊的基本運算算法設計。(7) 利用棧/隊列求解復雜的應用問題。3. 要點歸納(1) 棧和隊列的共同點是它們的數據元素都呈線性關系，且只允許在端點處插入和刪除元素。(2) 棧是一種“后進先出”的數據結構，只能在同一端進行元素的插入和刪除。(3) 棧可以采用順序棧和鏈棧兩類存儲結構。(4) n個不同元素的進棧順序和出棧順序不一定相同。(5) 在順序棧中通常用棧頂指針指向當前棧頂的元素。(6) 在順序棧中用數組data［0..MaxSize-1］存放棧中元素，只能將一端作為棧底，另一端作為棧頂，通常的做法是將data［0］端作為棧底，data［MaxSize-1］端作為棧頂。用戶也可以將data［MaxSize-1］端作為棧底，data［0］端作為棧頂，但不能將中間位置作為棧底或者棧頂。(7) 初始時棧頂指針top設置為-1，棧空的條件為top=-1，棧滿的條件為top=MaxSize-1，元素x的進棧操作是top ; data［top］=x，出棧操作是x=data［top］; top--。這是經典做法，但不是的方法，如果初始時top設置為0，可以設置棧空的條件為top=0，棧滿的條件為top=MaxSize，元素x的進棧操作是data［top］=x; top ，出棧操作是top--; x=data［top］。(8) 在順序棧或鏈棧中，進棧和出棧操作不涉及棧中元素的移動。(9) 在鏈棧中，由于每個結點是單獨分配的，通常不考慮上溢出問題。(10) 無論是順序棧還是鏈棧，進棧和出棧運算的時間復雜度均為O(1)。(11) 隊列是一種“先進先出”的數據結構，只能從一端插入元素，從另一端刪除元素。(12) 隊列可以采用順序隊和鏈隊兩類存儲結構。(13) n個元素進隊的順序和出隊順序總是一致的。(14) 在順序隊中的元素個數可以由隊頭指針和隊尾指針計算出來。(15) 環形隊列也是一種順序隊，是通過邏輯方法使其首尾相連的，解決非環形隊列的假溢出現象。(16) 在環形隊列中，隊頭指針f指向隊頭元素的前一個位置，隊尾指針r指向隊尾元素，這是一種經典做法，但不是的方法，也可以讓隊頭指針f指向隊頭元素。(17) 無論是順序隊還是鏈隊，進隊和出隊運算的時間復雜度均為O(1)。(18) 在實際應用中，一般棧和隊列都是用來存放臨時數據的，如果先保存的元素先處理，應該采用隊列； 如果后保存的元素先處理，應該采用棧。

3.2教材中的練習題及參考答案1. 有5個元素，其進棧次序為A、B、C、D、E，在各種可能的出棧次序中以元素C、D出棧(即C及時個且D第二個出棧)的次序有哪幾個？答： 要使C及時個且D第二個出棧，應是A進棧，B進棧，C進棧，C出棧，D進棧，D出棧，之后可以有以下幾種情況： (1) B出棧，A出棧，E進棧，E出棧，輸出序列為CDBAE； (2) B出棧，E進棧，E出棧，A出棧，輸出序列為CDBEA； (3) E進棧，E出棧，B出棧，A出棧，輸出序列為CDEBA。所以可能的次序有CDBAE、CDBEA、CDEBA。2. 在一個算法中需要建立多個棧(假設3個棧或以上)時可以選用以下3種方案之一，試問這些方案相比各有什么優缺點？(1) 分別用多個順序存儲空間建立多個獨立的順序棧。(2) 多個棧共享一個順序存儲空間。(3) 分別建立多個獨立的鏈棧。答： (1) 優點是每個棧僅用一個順序存儲空間時操作簡單； 缺點是分配空間小了容易產生溢出，分配空間大了容易造成浪費，各棧不能共享空間。(2) 優點是多個棧僅用一個順序存儲空間，充分利用了存儲空間，只有在整個存儲空間都用完時才會產生溢出； 缺點是當一個棧滿時要向左、右查詢有無空閑單元，如果有，則要移動元素和修改相關的棧底和棧頂指針。當接近棧滿時要查詢空閑單元、移動元素和修改棧底、棧頂指針，這一過程計算復雜且十分耗時。(3) 優點是多個鏈棧一般不考慮棧的溢出； 缺點是棧中元素要以指針相鏈接，比順序存儲多占用了存儲空間。3. 在以下幾種存儲結構中哪個最適合用作鏈棧？(1) 帶頭結點的單鏈表。(2) 不帶頭結點的循環單鏈表。(3) 帶頭結點的雙鏈表。答： 棧中元素之間的邏輯關系屬線性關系，可以采用單鏈表、循環單鏈表和雙鏈表之一來存儲，而棧的主要運算是進棧和出棧。當采用(1)時，前端作為棧頂，進棧和出棧運算的時間復雜度為O(1)。當采用(2)時，前端作為棧頂，當進棧和出棧時首結點都發生變化，還需要找到尾結點，通過修改其next域使其變為循環單鏈表，算法的時間復雜度為O(n)。當采用(3)時，前端作為棧頂，進棧和出棧運算的時間復雜度為O(1)。但單鏈表和雙鏈表相比，其存儲密度更高，所以本題中最適合用作鏈棧的是帶頭結點的單鏈表。4. 簡述以下算法的功能(假設ElemType為int類型)。

void fun(ElemType a［］,int n)

{int i;ElemType e;

SqStack st1,st2;

InitStack(st1);

InitStack(st2);

for (i=0;i

if (a［i］%2==1)

Push(st1,a［i］);

else

Push(st2,a［i］);

i=0;

while (!StackEmpty(st1))

{Pop(st1,e);

a［i ］=e;

}

while (!StackEmpty(st2))

{Pop(st2,e);

a［i ］=e;

}

DestroyStack(st1);

DestroyStack(st2);

}

答： 算法的執行步驟如下。(1) 掃描數組a，將所有奇數進到st1棧中，將所有偶數進到st2棧中。(2) 先將st1的所有元素(奇數元素)退棧，放到數組a中并覆蓋原有位置的元素； 再將st2的所有元素(偶數元素)退棧，放到數組a中并覆蓋原有位置的元素。(3) 銷毀兩個棧st1和st2。所以本算法的功能是利用兩個棧將數組a中的所有奇數元素放到所有偶數元素的前面。例如ElemType a［］={1,2,3,4,5,6}，執行算法后數組a改變為{5,3,1,6,4,2}。5. 簡述以下算法的功能(順序棧的元素類型為ElemType)。

void fun(SqStack &st,ElemType x)

{SqStack tmps;

ElemType e;

InitStack(tmps);

while(!StackEmpty(st))

{Pop(st,e);

if(e!=x) Push(tmps,d);

}

while (!StackEmpty(tmps))

{Pop(tmps,e);

Push(st,e);

}

DestroyStack(tmps);

}

答： 算法的執行步驟如下。(1) 建立一個臨時棧tmps并初始化。(2) 退棧st中的所有元素，將不為x的元素進棧到tmps中。(3) 退棧tmps中的所有元素，并進棧到st中。(4) 銷毀棧tmps。所以本算法的功能是如果棧st中存在元素x，將其從棧中清除。例如，st棧中從棧底到棧頂為a、b、c、d、e，執行算法fun(st，'c')后，st棧中從棧底到棧頂為a、b、d、e。6. 簡述以下算法的功能(棧st和隊列qu的元素類型均為ElemType)。

bool fun(SqQueue &qu,int i)

{ElemType e;

int j=1;

int n=(qu->rear-qu->front MaxSize)%MaxSize;

if (jn) return false;

for (j=1;j

{deQueue(qu,e);

if (j!=i)

enQueue(qu,e);

}

return true;

}

答： 算法的執行步驟如下。(1) 求出隊列qu中的元素個數n，參數i錯誤時返回假。(2) qu出隊共計n次，除了第i個出隊的元素以外，其他出隊的元素立即進隊。(3) 返回真。所以本算法的功能是刪除qu中從隊頭開始的第i個元素。例如，qu中從隊頭到隊尾的元素是a、b、c、d、e，執行算法fun(qu，2)后，qu中從隊頭到隊尾的元素改變為a、c、d、e。7. 什么是環形隊列？采用什么方法實現環形隊列？答： 在用數組表示隊列時把數組看成是一個環形的，即令數組中的及時個元素緊跟在最末一個單元之后就形成了一個環形隊列。環形隊列解決了非環形隊列中出現的“假溢出”現象。通常采用邏輯上求余數的方法來實現環形隊列，假設數組的大小為n，當元素下標i增1時采用i=(i 1)%n來實現。8. 環形隊列一定優于非環形隊列嗎？在什么情況下使用非環形隊列？答： 隊列主要用于保存中間數據，而且保存的數據滿足先產生先處理的特點。非環形隊列可能存在數據假溢出現象，即隊列中還有空間，可是隊滿的條件卻成立了，為此改為環形隊列，這樣克服了假溢出現象。但并不能說環形隊列一定優于非環形隊列，因為環形隊列中出隊元素的空間可能被后來進隊的元素覆蓋，如果算法要求在隊列操作結束后利用進隊的所有元素實現某種功能，這樣環形隊列就不適合了，在這種情況下需要使用非環形隊列，例如利用非環形隊列求解迷宮路徑就是這種情況。9. 假設以I和O分別表示進棧和出棧操作，棧的初態和終棧均為空，進棧和出棧的操作序列可表示為僅由I和O組成的序列。(1) 在下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO(2) 通過對(1)的分析，設計一個算法判定所給的操作序列是否合法，若合法返回真，否則返回假(假設被判定的操作序列已存入一維數組中)。解： (1) 選項A、D均合法，而選項B、C不合法。因為在選項B中先進棧一次，立即出棧3次，這會造成棧下溢。在選項C中共進棧5次，出棧3次，棧的終態不為空。(2) 本題使用一個鏈棧來判斷操作序列是否合法，其中str為存放操作序列的字符數組，n為該數組的字符個數(這里的ElemType類型設定為char)。對應的算法如下：

bool judge(char str［］,int n)

{int i=0; ElemType x;

LinkStNode ls;

bool flag=true;

InitStack(ls);

while (i

{if (str［i］=='I')//進棧

Push(ls,str［i］);

else if (str［i］=='O')//出棧

{if (StackEmpty(ls))

flag=false;//棧空時

else

Pop(ls,x);

}

else

flag=false;//其他值無效

i ;

}

if (!StackEmpty(ls)) flag=false;

DestroyStack(ls);

return flag;

}

10. 假設表達式中允許包含圓括號、方括號和大括號3種括號，編寫一個算法判斷表達式中的括號是否正確配對。解： 設置一個棧st，掃描表達式exp，當遇到'('、'［'或'{'時將其進棧； 當遇到')'時，若棧頂是'('，則繼續處理，否則以不配對返回假； 當遇到'］'時，若棧頂是'［'，則繼續處理，否則以不配對返回假； 當遇到'}'時，若棧頂是'{'，則繼續處理，否則以不配對返回假。在exp掃描完畢后，若棧不空，則以不配對返回假； 否則以括號配對返回真。本題的算法如下：

bool Match(char exp［］,int n)

{LinkStNode ls;

InitStack(ls);

int i=0;

ElemType e;

bool flag=true;

while (i

{if (exp［i］=='(' | exp［i］=='［' | exp［i］=='{')

Push(ls,exp［i］);//遇到'('、'［'或'{',將其進棧

if (exp［i］==')')//遇到')',若棧頂是'(',繼續處理,否則以不配對返回

{if (GetTop(ls,e))

{if (e=='(') Pop(ls,e);

else flag=false;

}

else flag=false;

}

if (exp［i］=='］')//遇到'］',若棧頂是'［',繼續處理,否則以不配對返回

{if (GetTop(ls,e))

{if (e=='［') Pop(ls,e);

else flag=false;

}

else flag=false;

}

if (exp［i］=='}')//遇到'}',若棧頂是'{',繼續處理,否則以不配對返回

{if (GetTop(ls,e))

{if (e=='{') Pop(ls,e);

else flag=false;

}

else flag=false;

}

i ;

}

if (!StackEmpty(ls)) flag=false;//若棧不空,則不配對

DestroyStack(ls);

return flag;

}

11. 設從鍵盤輸入一序列的字符a1、a2、…、an。設計一個算法實現這樣的功能： 若ai為數字字符，ai進隊； 若ai為小寫字母，將隊首元素出隊； 若ai為其他字符，表示輸入結束。要求使用環形隊列。解： 先建立一個環形隊列qu，用while循環接收用戶的輸入，若輸入數字字符，將其進隊； 若輸入小寫字母，出隊一個元素，并輸出它； 若為其他字符，則退出循環。本題的算法如下：

void fun()

{ElemType a,e;

SqQueue qu;//定義隊列指針

InitQueue(qu);

while (true)

{printf("輸入a:");

scanf("%s",&a);

if (a>='0' && a

{if (!enQueue(qu,a))

printf("隊列滿,不能進隊\n");

}

else if (a>='a' && a

{if (!deQueue(qu,e))

printf("隊列空,不能出隊\n");

else

printf("出隊元素:%c\n",e);

}

else break;//為其他字符

}

DestroyQueue(qu);

}

12. 設計一個算法，將一個環形隊列(容量為n，元素下標從0到n-1)的元素倒置。例如，圖3.2(a)為倒置前的隊列(n=10)，圖3.2(b)為倒置后的隊列。

圖3.2一個環形隊列倒置前后的狀態

解： 使用一個臨時棧st，先將qu隊列中的所有元素出隊并將其進棧st，直到隊列空為止。然后初始化隊列qu(隊列清空)，再出棧st的所有元素并將其進隊qu，銷毀棧st。對應的算法如下：

void Reverse(SqQueue &qu)

{ElemType e;

SqStack st;

InitStack(st);

while (!QueueEmpty(qu))//隊不空時出隊并進棧

{deQueue(qu,e);

Push(st,e);

}

InitQueue(qu);//隊列初始化

while (!StackEmpty(st))//棧不空時出棧并將元素入隊

{Pop(st,e);

enQueue(qu,e);

}

DestroyStack(st);

}

13. 編寫一個程序，輸入n(由用戶輸入)個10以內的數，每輸入i(0≤i≤9)就把它插入到第i號隊列中，把10個隊中的非空隊列按隊列號從小到大的順序串接成一條鏈，并輸出該鏈的所有元素。解： 建立一個隊頭指針數組quh和隊尾指針數組qut，quh［i］和qut［i］表示i號(0≤i≤9)隊列的隊頭和隊尾，先將它們的所有元素置為NULL。對于輸入的x，采用尾插法將其鏈到x號隊列中。然后按0~9編號的順序把這些隊列中的結點構成一個不帶頭結點的單鏈表，其首結點指針為head。輸出單鏈表head的所有結點值并釋放所有結點。對應的程序如下：

#include

#include

#define MAXQNode 10//隊列的個數

typedef struct node

{int data;

struct node next;

} QNode;

void Insert(QNode quh［］,QNode qut［］,int x)//將x插入到相應隊列中

{QNode s;

s=(QNode )malloc(sizeof(QNode));//創建一個結點s

s->data=x; s->next=NULL;

if (quh［x］==NULL)//x號隊列為空隊時

{quh［x］=s;

qut［x］=s;

}

else//x號隊列不空隊時

{qut［x］->next=s;//將s結點鏈到qut［x］所指的結點之后

qut［x］=s;//讓qut［x］仍指向尾結點

}

}

void Create(QNode quh［］,QNode qut［］)//根據用戶的輸入創建隊列

{int n,x,i;

printf("n:");

scanf("%d",&n);

for (i=0;i

{do

{printf("輸入第%d個數:",i 1);

scanf("%d",&x);

} while (x10);

Insert(quh,qut,x);

}

}

void DestroyList(QNode &head)//釋放單鏈表

{QNode pre=head,p=pre->next;

while (p!=NULL)

{

free(pre);

pre=p; p=p->next;

}

free(pre);

}

void DispList(QNode head)//輸出單鏈表的所有結點值

{printf("\n輸出所有元素:");

while (head!=NULL)

{printf("%d ",head->data);

head=head->next;

}

printf("\n");

}

QNode Link(QNode quh［］,QNode qut［］)//將非空隊列鏈接起來并輸出

{QNode head=NULL,tail;//總鏈表的首結點指針和尾結點指針

int i;

for (i=0;i

if (quh［i］!=NULL)//i號隊列不空

{if (head==NULL)//若i號隊列為及時個非空隊列

{head=quh［i］;

tail=qut［i］;

}

else//若i號隊列不是及時個非空隊列

{tail->next=quh［i］;

tail=qut［i］;

}

}

tail->next=NULL;

return head;

}

int main()

{int i;

QNode head;

QNode quh［MAXQNode］,qut［MAXQNode］;//各隊列的隊頭quh和隊尾指針qut

for (i=0;i

quh［i］=qut［i］=NULL;//置初值空

Create(quh,qut);//建立隊列

head=Link(quh,qut);//鏈接各隊列產生單鏈表

DispList(head);//輸出單鏈表

DestroyList(head);//銷毀單鏈表

return 1;

}

3.3補充練習題及參考答案3.3.1單項選擇題

1. 以下數據結構中元素之間為線性關系的是。

A. 棧B. 隊列C. 線性表D. 以上都是答： D。2. 棧和隊列的共同點是。A. 都是先進后出B. 都是先進先出C. 只允許在端點處插入和刪除元素D. 沒有其同點答： 棧和隊列都是受限線性表，所謂“受限”指的是在端點處插入和刪除元素，所以本題的答案為C。3. 經過以下棧運算后x的值是。

InitStack(s);Push(s，a);Push(s，b);Pop(s，x);GetTop(s，x);

A. aB. bC. 1D. 0答： A。4. 經過以下棧運算后StackEmpty(s)的值是。

InitStack(s);Push(s，a);Push(s，b);Pop(s，x);Pop(s，y)

A. aB