国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

2年前作者：木瓜星靈TT分類：Toy博客閱讀(49)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

三、棧、隊(duì)列和數(shù)組

棧

基本概念

棧是只允許在一端進(jìn)行插入或刪除操作的線性表。

  • 棧頂：線性表允許進(jìn)行插入刪除的那一端
  • 棧底：固定的，不允許進(jìn)行插入刪除的那一端
  • 空棧：不含任何元素的空表

特點(diǎn)：先進(jìn)后出

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

基本操作：

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

?？碱}型：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-yAQLivaR-1686635232177)(null)]

順序棧

結(jié)構(gòu)體：

//結(jié)構(gòu)體
#define MaxSize 10 //定義棧中元素的最大個(gè)數(shù)
typedef struct
{
	int data[MaxSize];//靜態(tài)數(shù)組存放棧中元素
	int top;//棧頂指針
} SqStack;

初始化：

//初始化
void InitStack(SqStack& S)
{
	S.top = -1;//初始化棧頂指針 若為0.則指向下一個(gè)插入的位置
}

判空：

//判空
bool StackEmpty(SqStack S)
{
	if (S.top == -1) return true;//判空
	else return false;
}

進(jìn)棧：

//進(jìn)棧
bool Push(SqStack& S, int x)
{
	if (S.top == MaxSize - 1)//棧滿，報(bào)錯(cuò)
		return false;
	S.top = S.top + 1;//先加1
	S.data[S.top] = x;//新元素入棧 這兩行等價(jià)于S.data[++S.top]=x;
	return true;
}

出棧：

//出棧
bool Pop(SqStack& S, int& x)
{
	if (S.top == -1) return false;//?？?，報(bào)錯(cuò)
	x = S.data[S.top];//棧頂元素先出棧
	S.top = S.top - 1;//指針再減一 這兩行等價(jià)于 x=S.data[S.top--]
	return true;
}

獲取棧頂元素：

//讀取棧頂元素
bool GetTop(SqStack& S, int& x)
{
	if (S.top == -1) return false;//?？眨瑘?bào)錯(cuò)
	x = S.data[S.top];//棧頂元素出棧
	return true;
}

讓top指向待插入位置的寫法：（初始化top=0）

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

缺點(diǎn)：棧的大小不可變

可以使用共享?xiàng)＿M(jìn)行優(yōu)化，提高內(nèi)存運(yùn)用率。

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

共享?xiàng)６x：

//共享?xiàng)?/span>
typedef struct
{
	int data[MaxSize]; //靜態(tài)數(shù)組存放棧中元素
	int top0; //0號(hào)棧棧頂指針
	int top1; //1號(hào)棧棧頂指針
} ShStack;

//初始化共享?xiàng)?/span>
void InitStack(ShStack& S)
{
	S.top0 = -1;
	S.top1 = MaxSize; 
	//棧滿條件為top0+1==top1
}

鏈?zhǔn)綏?/h4>

鏈?zhǔn)綏５臉?gòu)建和單鏈表十分相似，主要限制與進(jìn)棧出棧都只能在棧頂一端進(jìn)行（鏈頭作為棧頂）

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-Qpnymbqf-1686635230993)(null)]

結(jié)構(gòu)體：

# define MaxSize 10
typedef struct LinkNode {
    int data;
    struct LinkNode* next;
} *LinkStack;

初始化：

//初始化
bool InitStack(LinkStack& LS) {
    LS = (LinkNode*)malloc(sizeof(LinkNode));//分配一個(gè)頭節(jié)點(diǎn)
    if (LS == NULL) {
        return false;
    }
    LS->next = NULL;
    return true;
}

入棧：

//入棧
bool Push(LinkStack& LS, int t) {
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    if (s == NULL)return false;
    s->data = t;
    s->next = LS->next;
    LS->next = s;
    return true;
}

出棧：

//出棧
bool Pop(LinkStack& LS, int& x) {
    //判斷
    if (LS->next == NULL)return false;//?？?這里的條件
    LinkNode* q;
    q = LS->next;
    LS->next = q->next;
    x = q->data;
    free(q);
    return true;
}

獲取棧頂元素：

//獲取棧頂元素
bool GetTop(LinkStack LS, int& x) {
    if (LS == NULL)return false;
    x = LS->next->data;
    return true;
}

隊(duì)列

基本概念

隊(duì)列是只允許在一端進(jìn)行插入，在另一端刪除操作的線性表。（分別稱為入隊(duì)，出隊(duì)）

  • 特點(diǎn)：先進(jìn)先出，后進(jìn)后出(FIFO)
  • 隊(duì)頭：允許刪除的一端
  • 隊(duì)尾：允許插入的一端

基本操作：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-Do0UhQza-1686635229210)(C:\Software\PicGo\1683358362151.png)]

順序存儲(chǔ)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-pZhiTig2-1686635230819)(null)]

結(jié)構(gòu)體：

#define MaxSize 10 //定義隊(duì)列中元素的最大個(gè)數(shù)
typedef struct
{
	int data[MaxSize];//用靜態(tài)數(shù)組存放隊(duì)列元素、
	int front, rear;//隊(duì)頭指針和隊(duì)尾指針
} SqQueue;

初始化：

//初始化隊(duì)列
void InitQueue(SqQueue& Q)
{
	//初始，隊(duì)頭隊(duì)尾指針指向0
	Q.front = Q.rear = 0;//隊(duì)尾指針始終指向下一個(gè)插入的位置
}

判空：

//判空
bool QueueEmpty(SqQueue Q)
{
	if (Q.rear == Q.front) return true;
	else return false;
}

入隊(duì)：

//入隊(duì)
bool EnQueue(SqQueue& Q, int x)
{
	if ((Q.rear+1)%MaxSize==Q.front)//判斷隊(duì)滿
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1)%MaxSize;//隊(duì)尾指針加1取模，以循環(huán)隊(duì)列的形式進(jìn)行存儲(chǔ)
}

出隊(duì)：

//出隊(duì)
bool DeQueue(SqQueue& Q, int& x)
{
	if (Q.rear == Q.front)//判空
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;//隊(duì)頭后移
	return true;
}

獲取隊(duì)頭元素：

//獲取隊(duì)頭元素
bool GetHead(SqQueue& Q, int& x)
{
	if (Q.rear == Q.front)//判空
		return false;
	x = Q.data[Q.front];
	return true;
}

判斷隊(duì)滿的三種方式：
【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

對(duì)于rear和front指針的初始化方式可能會(huì)有所不同，由此會(huì)有不同的出題方式。

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

鏈?zhǔn)酱鎯?chǔ)

以下為帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列：

結(jié)構(gòu)體：

//結(jié)構(gòu)體
typedef struct LinkNode
{
	int data;
	struct LinkNode* next;
}LinkNode;

typedef struct
{
	LinkNode* front, * rear;//隊(duì)頭隊(duì)尾指針
}LinkQueue;

初始化：

//初始化
void InitQueue(LinkQueue& Q)
{
	//初始時(shí) front、rear都指向頭結(jié)點(diǎn)
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}

判空：

//判空
bool IsEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
		return true;
	else return false;
}

入隊(duì)：

//入隊(duì)
void EnQueue(LinkQueue& Q, int x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next = s;//新節(jié)點(diǎn)插入到rear后面
	Q.rear = s;//修改表尾指針
}

出隊(duì)：出隊(duì)時(shí)需要進(jìn)行特判，當(dāng)出隊(duì)元素為最后一個(gè)結(jié)點(diǎn)時(shí)，需要修改rear指針。

//出隊(duì)
bool DeQueue(LinkQueue& Q, int& x)
{
	if (Q.front == Q.rear) return false;//判空
	LinkNode* p = Q.front->next;
	x = p->data;//用變量x返回隊(duì)頭元素
	Q.front->next = p->next;//修改頭結(jié)點(diǎn)的next指針
	if (Q.rear == p)//此次是最后一個(gè)結(jié)點(diǎn)出隊(duì)
		Q.rear = Q.front;//修改rear指針
	free(p);//釋放結(jié)點(diǎn)空間
	return true;
}

以下是不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列：

初始化：

//初始化（不帶頭結(jié)點(diǎn)）
void InitQueue2(LinkQueue& Q)
{
	//初始時(shí)，front、rear都指向NULL
	Q.front = NULL;
	Q.rear = NULL;
}

判空：

//判空（不帶頭結(jié)點(diǎn)）
bool IsEmpty2(LinkQueue Q)
{
	if (Q.front == NULL) return true;
	else return false;
}

入隊(duì)：

//入隊(duì)（不帶頭結(jié)點(diǎn)）
void EnQueue2(LinkQueue& Q, int x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if (Q.front == NULL)//在空序列中插入第一個(gè)元素
	{
		Q.front = s;
		Q.rear = s;
	}
	else
	{
		Q.rear->next = s;
		Q.rear = s;
	}
}

出隊(duì)：

//出隊(duì)（不帶頭結(jié)點(diǎn)）
bool DeQueue2(LinkQueue& Q, int& x)
{
	if (Q.front == NULL) return false;
	LinkNode* p = Q.front;//p指向此次出隊(duì)的結(jié)點(diǎn)
	x = p->data;//用變量x返回隊(duì)頭元素
	Q.front = p->next;//修改front指針
	if (Q.rear == p)//此次是最后一個(gè)結(jié)點(diǎn)出隊(duì)
	{
		Q.front = NULL;
		Q.rear = NULL;
	}
	free(p);//釋放結(jié)點(diǎn)
}

雙端隊(duì)列

雙端隊(duì)列是指兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

應(yīng)用

括號(hào)匹配

用棧實(shí)現(xiàn)括號(hào)匹配：

依次掃描所有字符，遇到左括號(hào)入棧，遇到右括號(hào)則彈出棧頂元素檢查是否匹配。

匹配失敗情況：

  1. 左括號(hào)單身
  2. 右括號(hào)單身
  3. 左右括號(hào)不匹配

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-ux1zXkJz-1686635230730)(null)]

//括號(hào)匹配
bool bracketCheck(char* str, int length) {
    SqStack S;
    InitStack(S);//初始化一個(gè)棧
    for (int i = 0; i < length; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            Push(S, str[i]);//掃描到左括號(hào)，入棧
        }
        else {
            if (StackEmpty(S))return false;//掃描到右括號(hào)且當(dāng)前棧空，匹配失敗
            char topElem;
            Pop(S, topElem);//棧頂元素出棧進(jìn)行匹配
            if (str[i] == ')' && topElem != '(')
                return false;
            if (str[i] == ']' && topElem != '[')
                return false;
            if (str[i] == '}' && topElem != '{')
                return false;
        }
    }
    return StackEmpty(S);//最后檢查棧，若空匹配成功，非空匹配失敗
}

前中后綴表達(dá)式

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

中綴轉(zhuǎn)后綴（左優(yōu)先）：

當(dāng)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式時(shí)，由于運(yùn)算順序的不同，可能存在轉(zhuǎn)換為幾種不同后綴表達(dá)式的情況，此時(shí)我們采用左優(yōu)先原則，保證手算和機(jī)算的結(jié)果相同。

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

中綴轉(zhuǎn)后綴的機(jī)算方法：

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

后綴表達(dá)式的手算方法：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-LQohQ0cw-1686635230708)(null)]

后綴表達(dá)式機(jī)算：利用棧 先彈出的元素為右操作數(shù)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-hquCC1K8-1686635232135)(null)]

中綴轉(zhuǎn)前綴（右優(yōu)先）：下圖以右邊的為準(zhǔn)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-GWXSUUrm-1686635230687)(null)]

前綴表達(dá)式機(jī)算：利用棧 先彈出的元素是左操作數(shù)

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

中綴表達(dá)式的計(jì)算（用棧實(shí)現(xiàn)）

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

棧在遞歸中的運(yùn)用

適合用“遞歸”解決：可以把原始問題轉(zhuǎn)換為屬性相同，但規(guī)模較小的問題。

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

隊(duì)列的運(yùn)用

樹的層次遍歷

圖的廣度優(yōu)先遍歷

操作系統(tǒng)中FCFS先來先服務(wù)的策略

數(shù)組

數(shù)組的存儲(chǔ)

一維數(shù)組：

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

二維數(shù)組（分為按行存儲(chǔ)以及按列存儲(chǔ)）：

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

對(duì)稱矩陣

若n階方陣中任意一個(gè)元素aij都有aij=aji則該矩陣為對(duì)稱矩陣。

同樣分為行優(yōu)先以及列優(yōu)先

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

三角矩陣

下三角矩陣：除了主對(duì)角線和下三角區(qū)，其余的元素都相同。

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

上三角矩陣：除了主對(duì)角線和上三角區(qū)，其余的元素都相同。

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組

三對(duì)角矩陣

又稱帶狀矩陣，當(dāng)|i-j|>1時(shí)，有aij=0(1<=i,j<=n)

由i,j得到k：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-OrvwDtj5-1686635230798)(null)]

由k得到i,j：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-jVAIDTvc-1686635230774)(null)]

由k以及i的表達(dá)式可以進(jìn)一步得到j(luò)的表達(dá)式

稀疏矩陣

非零元素遠(yuǎn)遠(yuǎn)少于矩陣元素的個(gè)數(shù)

使用三元組存儲(chǔ)：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-HFGHxhSc-1686635230753)(null)]

使用十字鏈表法存儲(chǔ)：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-xMbahDSY-1686635230660)(null)]

總結(jié)：

【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組
主要參考：王道考研課程
后續(xù)會(huì)持續(xù)更新考研408部分的學(xué)習(xí)筆記，歡迎關(guān)注。
github倉庫（含所有相關(guān)源碼）：408數(shù)據(jù)結(jié)構(gòu)筆記文章來源地址http://www.zghlxwxcb.cn/news/detail-486560.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】24王道考研筆記——棧、隊(duì)列和數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包