摘要:分享有關(guān)棧、隊(duì)列和數(shù)組的知識點(diǎn)。
在考研的最后沖刺階段,時(shí)間緊迫,每個(gè)知識點(diǎn)都顯得至關(guān)重要。今天,我們一起來速記棧、隊(duì)列和數(shù)組的重要知識點(diǎn),幫助你在考試中迅速答題,取得好成績。
01棧和隊(duì)列的定義及特性
棧
定義:棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中允許插入和刪除的一端稱為“棧頂”,不允許插入和刪除的一端稱為“棧底”。
特性:棧的操作具有“后進(jìn)先出”的特性。
隊(duì)列
定義:隊(duì)列是限定在表的一端進(jìn)行插入在表的另一端進(jìn)行刪除的線性表。在表中允許插入的一端稱為“隊(duì)尾”,允許刪除的一端稱為“隊(duì)頭”。
特性:隊(duì)列的操作具有“先進(jìn)先出”的特性。
02棧的順序儲存
順序棧
定義:棧的順序存儲結(jié)構(gòu)是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,top為棧頂指針,base為棧底指針。
基本操作:
獲取棧頂元素:若top初始時(shí)為0,則操作語句為e=*(s.top-1);
入棧操作:若top初始時(shí)為0,則操作語句為*S.top=e; S.top++;
出棧操作:若top初始時(shí)為0,則操作語句為S.top--;e=*S.top;
共享?xiàng)?/strong>
定義:將兩個(gè)棧放在數(shù)組的兩端,一個(gè)從數(shù)組首端開始壓棧,一個(gè)從數(shù)組尾部開始壓棧,等到兩邊棧頂在中間相遇時(shí),棧滿。
基本操作:
??諚l件:棧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ì)列長度:(rear-front+maxsize)%maxsize。
04鏈?zhǔn)疥?duì)列
定義:用鏈表表示的隊(duì)列簡稱為鏈隊(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壓縮儲存
壓縮存儲的目的:節(jié)省存儲空間。
特殊矩陣的定義:假若值相同的元素或者零元素在矩陣中的分布有一定規(guī)律,則我們稱此類矩陣為特殊矩陣。
特殊矩陣的壓縮儲存:
對稱矩陣:對于對稱矩陣的一對對稱元只需分配一個(gè)存儲空間,則可將N2個(gè)元壓縮存儲到N(N+1)/2個(gè)元的空間中,因此對于對稱矩陣我們只需存儲其包含對角線的上三角部分(包括對角線)或下三角部分(包括對角線)即可。
對角矩陣:對角矩陣的所有非零元都集中在以主對角線為中心的帶狀區(qū)域中。即除了主對角線上和直接在對角線上、下方若干條對角線上的元之外,所有其他的元皆為零。
稀疏矩陣的定義:稀疏矩陣是指矩陣中非零元素<=50%,且分布無規(guī)律的矩陣。
稀疏矩陣的存儲方法:
三元組:僅存儲稀疏矩陣中的非零元素,即存儲非零元素的行坐標(biāo)、列坐標(biāo)、元素值。
十字鏈表:在十字鏈表中,我們可以用一個(gè)包含五個(gè)域的結(jié)點(diǎn)來表示每個(gè)非零元素。這五個(gè)域分別是i、j、e、right、down。其中,i表示該非零元素所在的行號,j表示非零元素所在的列號,而e代表了這個(gè)非零元素的實(shí)際值。向右域right用以鏈接同一行中下一個(gè)非零元,向下域down用以鏈接同一列中下一個(gè)非零元。每個(gè)非零元素既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)。
考研備考資料免費(fèi)領(lǐng)取
去領(lǐng)取
共收錄117.93萬道題
已有25.02萬小伙伴參與做題