考研倒計(jì)時(shí)！速記棧、隊(duì)列和數(shù)組重要知識(shí)點(diǎn)！

在考研的最后沖刺階段，時(shí)間緊迫，每個(gè)知識(shí)點(diǎn)都顯得至關(guān)重要。今天，我們一起來(lái)速記棧、隊(duì)列和數(shù)組的重要知識(shí)點(diǎn)，幫助你在考試中迅速答題，取得好成績(jī)。

01棧和隊(duì)列的定義及特性

棧

定義：棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中允許插入和刪除的一端稱為“棧頂”，不允許插入和刪除的一端稱為“棧底”。

特性：棧的操作具有“后進(jìn)先出”的特性。

隊(duì)列

定義：隊(duì)列是限定在表的一端進(jìn)行插入在表的另一端進(jìn)行刪除的線性表。在表中允許插入的一端稱為“隊(duì)尾”，允許刪除的一端稱為“隊(duì)頭”。

特性：隊(duì)列的操作具有“先進(jìn)先出”的特性。

02棧的順序儲(chǔ)存

順序棧

定義：棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，top為棧頂指針，base為棧底指針。

基本操作：

獲取棧頂元素：若top初始時(shí)為0，則操作語(yǔ)句為e=*(s.top-1)；

入棧操作：若top初始時(shí)為0，則操作語(yǔ)句為*S.top=e; S.top++；

出棧操作：若top初始時(shí)為0，則操作語(yǔ)句為S.top--;e=*S.top；

共享?xiàng)?/strong>

定義：將兩個(gè)棧放在數(shù)組的兩端，一個(gè)從數(shù)組首端開(kāi)始?jí)簵?，一個(gè)從數(shù)組尾部開(kāi)始?jí)簵?，等到兩邊棧頂在中間相遇時(shí)，棧滿。

基本操作：

棧空條件：棧1為空top1=-1；棧2為空top2=maxsize；

棧滿條件：top1+1=top2；

元素X進(jìn)棧操作：進(jìn)棧1操作為top1++；data[top1]=x；進(jìn)棧2操作為top2--；data[top2]=x。

03循環(huán)隊(duì)列

目的：為了解決順序隊(duì)列“假溢出”的弊端，構(gòu)造了循環(huán)隊(duì)列。

定義：將順序隊(duì)列首尾相接成環(huán)狀空間即為循環(huán)隊(duì)列。隊(duì)頭指針front指向頭元素，隊(duì)尾指針rear指向尾元素的下一個(gè)位置。

判斷條件：

判斷隊(duì)空：rear==front。

判斷隊(duì)滿：(rear+1)%maxsize==front。

基本操作：

入隊(duì)操作：隊(duì)尾指針應(yīng)該更新為：rear=e;rear=(rear+1)%maxsize。

出隊(duì)操作：隊(duì)首指針應(yīng)該更新為：e=front；front=(front+1)%maxsize。

隊(duì)列長(zhǎng)度：(rear-front+maxsize)%maxsize。

04鏈?zhǔn)疥?duì)列

定義：用鏈表表示的隊(duì)列簡(jiǎn)稱為鏈隊(duì)列。一個(gè)鏈隊(duì)列有一個(gè)隊(duì)頭指針和一個(gè)隊(duì)尾指針，為了操作方便，給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)。

基本操作：

插入元素e為Q的新的隊(duì)尾元素：p->data=e; p->next=NULL；Q.rear->next=p；Q.rear=p。

刪除Q的隊(duì)頭元素用e返回其值：p=Q.front->next；e=p->data；Q.front->next=p->next。

05壓縮儲(chǔ)存

壓縮存儲(chǔ)的目的：節(jié)省存儲(chǔ)空間。

特殊矩陣的定義：假若值相同的元素或者零元素在矩陣中的分布有一定規(guī)律，則我們稱此類矩陣為特殊矩陣。

特殊矩陣的壓縮儲(chǔ)存：

對(duì)稱矩陣：對(duì)于對(duì)稱矩陣的一對(duì)對(duì)稱元只需分配一個(gè)存儲(chǔ)空間，則可將N2個(gè)元壓縮存儲(chǔ)到N(N+1)/2個(gè)元的空間中，因此對(duì)于對(duì)稱矩陣我們只需存儲(chǔ)其包含對(duì)角線的上三角部分(包括對(duì)角線)或下三角部分(包括對(duì)角線)即可。

對(duì)角矩陣：對(duì)角矩陣的所有非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中。即除了主對(duì)角線上和直接在對(duì)角線上、下方若干條對(duì)角線上的元之外，所有其他的元皆為零。

稀疏矩陣的定義：稀疏矩陣是指矩陣中非零元素<=50%，且分布無(wú)規(guī)律的矩陣。

稀疏矩陣的存儲(chǔ)方法：

三元組：僅存儲(chǔ)稀疏矩陣中的非零元素，即存儲(chǔ)非零元素的行坐標(biāo)、列坐標(biāo)、元素值。

十字鏈表：在十字鏈表中，我們可以用一個(gè)包含五個(gè)域的結(jié)點(diǎn)來(lái)表示每個(gè)非零元素。這五個(gè)域分別是i、j、e、right、down。其中，i表示該非零元素所在的行號(hào)，j表示非零元素所在的列號(hào)，而e代表了這個(gè)非零元素的實(shí)際值。向右域right用以鏈接同一行中下一個(gè)非零元，向下域down用以鏈接同一列中下一個(gè)非零元。每個(gè)非零元素既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)。