考研倒計時！速記棧、隊列和數(shù)組重要知識點！

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

01棧和隊列的定義及特性

棧

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

特性：棧的操作具有“后進先出”的特性。

隊列

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

特性：隊列的操作具有“先進先出”的特性。

02棧的順序儲存

順序棧

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

基本操作：

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

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

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

共享棧

定義：將兩個棧放在數(shù)組的兩端，一個從數(shù)組首端開始壓棧，一個從數(shù)組尾部開始壓棧，等到兩邊棧頂在中間相遇時，棧滿。

基本操作：

?？諚l件：棧1為空top1=-1；棧2為空top2=maxsize；

棧滿條件：top1+1=top2；

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

03循環(huán)隊列

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

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

判斷條件：

判斷隊空：rear==front。

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

基本操作：

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

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

隊列長度：(rear-front+maxsize)%maxsize。

04鏈式隊列

定義：用鏈表表示的隊列簡稱為鏈隊列。一個鏈隊列有一個隊頭指針和一個隊尾指針，為了操作方便，給鏈隊列添加一個頭結點，并令頭指針指向頭結點。

基本操作：

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

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

05壓縮儲存

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

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

特殊矩陣的壓縮儲存：

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

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

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

稀疏矩陣的存儲方法：

三元組：僅存儲稀疏矩陣中的非零元素，即存儲非零元素的行坐標、列坐標、元素值。

十字鏈表：在十字鏈表中，我們可以用一個包含五個域的結點來表示每個非零元素。這五個域分別是i、j、e、right、down。其中，i表示該非零元素所在的行號，j表示非零元素所在的列號，而e代表了這個非零元素的實際值。向右域right用以鏈接同一行中下一個非零元，向下域down用以鏈接同一列中下一個非零元。每個非零元素既是某個行鏈表中的一個結點。