在這篇文章里渤刃，我們來(lái)實(shí)現(xiàn)自定義的鏈?zhǔn)綏３枘Ｊ紫任覀儊?lái)看看鏈?zhǔn)綏５慕Y(jié)構(gòu)及操作定義。
鏈?zhǔn)綏＝Y(jié)構(gòu)定義
首先运怖，新建兩個(gè)文件拼弃，分別為 mystack.h 和 mystack.cpp。在 mystack.h 中給出鏈?zhǔn)綏５慕Y(jié)構(gòu)定義及接口聲明摇展。
#ifndef _MYSTACK_H_
#define _MYSTACK_H_
#include <iostream>
using namespace std;
typedef char ELEMTYPE;
struct Node;
typedef struct Node *PNode;
struct Node {
ELEMTYPE info;
PNode link;
};
struct stStack {
PNode top;
size_t length;
};
typedef struct stStack *PLStack;
PLStack create();
bool destroy(PLStack *pstack);
bool print(PLStack pstack);
bool clear(PLStack pstack);
bool push(PLStack pstack, ELEMTYPE x);
bool pop(PLStack pstack);
bool top(PLStack pstack, ELEMTYPE *x);
bool isEmpty(PLStack pstack);
bool isFull(PLStack pstack);
#endif
從本次實(shí)驗(yàn)開始吻氧，我們使用 C++語(yǔ)言 的標(biāo)準(zhǔn)輸入輸出流進(jìn)行程序的輸入輸出操作。
要使用 C++語(yǔ)言的標(biāo)準(zhǔn)輸入輸出流咏连，我們需要在 mystack.h 頭文件中加入如下語(yǔ)句：
#include <iostream>
using namespace std;
C++語(yǔ)言中頭文件均不需要加 .h 作為后綴盯孙。iostream 頭文件對(duì)C++語(yǔ)言的 I/O 流進(jìn)行了定義及聲明。此外祟滴，C++語(yǔ)言還引入了 命名空間 的概念振惰，其本質(zhì)上就是定義一個(gè)新的作用域，在該作用域范圍內(nèi)再定義類踱启、變量及函數(shù)等报账，從而避免不同開發(fā)者因類、變量及函數(shù)命名同名而導(dǎo)致的沖突問(wèn)題埠偿。
因?yàn)镃++的標(biāo)準(zhǔn)輸入輸出流在 std 命名空間內(nèi)進(jìn)行定義透罢，因此我們需要加入using namespace std;這條語(yǔ)句，以便引入 std 這個(gè)命名空間冠蒋。
我們接下來(lái)解釋一下 mystack.h 頭文件中各數(shù)據(jù)結(jié)構(gòu)及函數(shù)聲明的含義羽圃。
首先，我們定義了兩個(gè)結(jié)構(gòu)體抖剿，分別是 struct Node 與 struct stStack 朽寞。其中 Node 結(jié)構(gòu)用于表示鏈?zhǔn)綏Ｖ械墓?jié)點(diǎn)，其包含數(shù)據(jù)域 info 以及指針域 link斩郎。而 stStack 結(jié)構(gòu)體表示鏈?zhǔn)綏?duì)象脑融，其包含指向鏈?zhǔn)綏ｍ數(shù)?top 指針，以及表示鏈?zhǔn)綏０?jié)點(diǎn)元素個(gè)數(shù)的 length 變量缩宜。
其次肘迎，對(duì)于鏈?zhǔn)綏＃覀兌x其所能進(jìn)行的操作如下：
- 創(chuàng)建棧 : create
- 銷毀棧 : destroy
- 清空棧 : clear
- 打印棧元素 : print
- 元素入棧 : push
- 元素出棧 : pop
- 取棧頂元素 : top
- 判斷棧是否為空 : isEmpty
- 判斷棧是否為滿 : isFull
當(dāng)然對(duì)于鏈?zhǔn)綏６远突停袧M操作應(yīng)該返回 true妓布。我們?cè)诒疚闹薪o出該操作只是為了兼容性的目的。
鏈?zhǔn)綏＝涌趯?shí)現(xiàn)
接下來(lái)我們依次來(lái)實(shí)現(xiàn)鏈?zhǔn)綏５母鱾€(gè)接口宋梧。首先實(shí)現(xiàn) create匣沼、 destroy 操作。
創(chuàng)建棧-create接口
創(chuàng)建棧接口原型如下所示：
PLStack create();
接口返回值為 PLStack 類型捂龄，該類型是 struct stStack 結(jié)構(gòu)體指針释涛，因此我們需要在接口中動(dòng)態(tài)分配該結(jié)構(gòu)體空間加叁，并初始化該結(jié)構(gòu)體。
由于 struct stStack結(jié)構(gòu)體包含兩個(gè)域：
- top 為鏈?zhǔn)綏９?jié)點(diǎn)指針枢贿，指向鏈?zhǔn)綏ｍ敼?jié)點(diǎn)殉农；
- length 為鏈?zhǔn)綏９?jié)點(diǎn)元素計(jì)數(shù)器，用于記錄鏈?zhǔn)綏Ｖ挟?dāng)前節(jié)點(diǎn)元素個(gè)數(shù)局荚；
初始化時(shí)超凳，top 指針直接賦值為 NULL 即可，而由于初始化鏈?zhǔn)綏r(shí)耀态，棧內(nèi)無(wú)元素轮傍，因此 length 計(jì)數(shù)器直接置為 0 即可。以下是 create 接口的實(shí)現(xiàn)：
PLStack create()
{
PLStack pstack = (PLStack) malloc (sizeof(struct stStack));
if (pstack != NULL)
{
pstack->top = NULL;
pstack->length = 0;
return pstack;
}
return NULL;
}
銷毀棧-destroy接口
接下來(lái)首装，我們來(lái)完成銷毀棧的操作创夜。因?yàn)槭擎準(zhǔn)綏＃卦谌霔r(shí)均需要分配新的節(jié)點(diǎn)空間用于存儲(chǔ)棧元素仙逻。因此在銷毀棧時(shí)驰吓，需要將其中每個(gè)節(jié)點(diǎn)的空間都釋放掉。完成節(jié)點(diǎn)空間釋放操作后系奉，還需要將棧結(jié)構(gòu)體(struct stStack)分配的空間也一并釋放掉檬贰。
因此這兩步操作可以分解為：
- 釋放棧中所有節(jié)點(diǎn)(清空棧節(jié)點(diǎn))；
- 釋放棧結(jié)構(gòu)體指針指向的內(nèi)存空間缺亮；
其中第一步操作可以利用我們后續(xù)將實(shí)現(xiàn)的 clear 操作來(lái)完成翁涤，而釋放棧結(jié)構(gòu)體指針這直接使用 free 函數(shù)即可。以下給出銷毀棧的接口實(shí)現(xiàn)：
bool destroy(PLStack pstack)
{
if (pstack == NULL)
{
return false;
}
clear(pstack);
free(pstack);
return true;
}
在銷毀棧時(shí)萌踱，我們首先判斷 pstack 指針是否為空葵礼，如果為空則不做任何操作。否則調(diào)用 clear 接口清空該棧并鸵，接著調(diào)用 free 函數(shù)釋放 pstack 指針指向的內(nèi)存空間鸳粉。
我們?cè)谥暗奈恼轮兄v過(guò)，盡快使項(xiàng)目的原型運(yùn)行起來(lái)园担，不要試圖將所有代碼編寫完成后再進(jìn)行編譯届谈。目前我們實(shí)現(xiàn)了 create 和 destroy兩個(gè)接口，但由于在 destroy 接口中還調(diào)用了 clear 接口粉铐，因此我們先實(shí)現(xiàn) clear 接口后再進(jìn)行編譯工作疼约。
清空棧-clear接口
清空棧操作卤档，需要依次將元素從棧頂逐個(gè)彈出(元素出棧蝙泼，pop)，直到棧為空為止(isEmpty)劝枣√捞ぃ可見织鲸，在 clear 接口中我們還需要調(diào)用pop、isEmpty接口溪胶。以下給出 clear 接口的實(shí)現(xiàn)：
bool clear(PLStack pstack)
{
if (pstack == NULL)
{
return false;
}
while (!isEmpty(pstack))
{
pop(pstack);
}
return true;
}
判斷棧是否為空-isEmpty接口
既然清空棧 clear 接口使用到了判斷棧是否為空操作搂擦，我們接著實(shí)現(xiàn) isEmpty 及 isFull 兩個(gè)接口。
判斷棧是否為空哗脖，可以根據(jù)以下兩個(gè)情況：
- top 指針指向?yàn)榭眨?/li>
- length 計(jì)數(shù)器為 0瀑踢；
以上兩種情況均可用于判斷棧是否為空。以下給出 isEmpty 接口的實(shí)現(xiàn)：
bool isEmpty(PLStack pstack)
{
if (pstack == NULL)
{
return true;
}
return (pstack->length == 0);
}
判斷棧是否為滿-isFull接口
判斷棧是否未滿才避，只有在順序棧中才具有實(shí)際意義橱夭。鏈?zhǔn)綏Ｒ蚱涔?jié)點(diǎn)均是在元素入棧時(shí)進(jìn)行內(nèi)存空間動(dòng)態(tài)分配的。因此桑逝，此處給出的判滿接口僅僅為了兼容性的需求棘劣。
bool isFull(PLStack pstack)
{
if (pstack == NULL)
{
return true;
}
return true;
}
元素出棧-pop接口
鏈?zhǔn)綏＿M(jìn)行 pop 操作的示意圖如下：
首先判斷棧是否為空，若不為空則更新棧頂 top 指針楞遏，其次釋放原棧頂元素內(nèi)存空間(由 tmp 指針指向)茬暇，最后更新 length 計(jì)數(shù)器。
以下我們給出鏈?zhǔn)綏Ｔ爻鰲２僮鞯膶?shí)現(xiàn)：
bool pop(PLStack pstack)
{
PNode p;
if (pstack == NULL)
{
return false;
}
if (!isEmpty(pstack))
{
return false;
}
p = pstack->top;
pstack->top = pstack->top->link;
pstack->length = pstack->length - 1;
free (p);
return true;
}
元素入棧-push接口
鏈?zhǔn)綏＿M(jìn)行 push 操作的示意圖如下：
首先嘗試分配新節(jié)點(diǎn)空間用于新入棧元素寡喝，其次更新 top 指針指向新棧頂元素糙俗，最后更新 length 計(jì)數(shù)器。
據(jù)此拘荡，我們給出鏈?zhǔn)綏?push 操作接口的實(shí)現(xiàn)：
bool push(PLStack pstack, ELEMTYPE x)
{
if (pstack == NULL)
{
return false;
}
PNode p = (PNode) malloc (sizeof(struct Node));
if (p != NULL)
{
p->info = x;
p->link = pstack->top;
pstack->top = p;
pstack->length = pstack->length + 1;
return true;
}
return false;
}
注： 在 push 接口中臼节，我們還應(yīng)該考慮判斷棧是否為滿的情況(該情況在順序棧中需要進(jìn)行考慮)。
取棧頂元素-top操作
獲取棧頂元素時(shí)珊皿，需要首先判斷棧是否為空网缝，只有棧不為空時(shí)才可獲取棧頂元素，否則應(yīng)返回操作失敗蟋定。以下是 top 操作的函數(shù)聲明：
bool top(PLStack pstack, ELEMTYPE *x);
需要引起我們注意的是粉臊，top 操作返回值為bool類型，也就是說(shuō)棧頂元素并不通過(guò)函數(shù)返回值獲取驶兜，而是通過(guò)參數(shù) ELEMTYPE 指針類型返回扼仲。這樣設(shè)計(jì)的原因很簡(jiǎn)單，因?yàn)楫?dāng)棧為空時(shí)抄淑，當(dāng)然無(wú)法取得棧頂屠凶，從而通過(guò) top 操作的返回值即可知道操作是否成功。
當(dāng) top 操作返回為true時(shí)肆资，可以直接通過(guò) ELEMTYPE *x獲取到棧頂元素矗愧；但當(dāng) top 操作返回為false時(shí)，ELEMTYPE *x指針指向無(wú)意義的內(nèi)存空間郑原。
打印棧當(dāng)前元素-print接口
在完成了鏈?zhǔn)綏５乃泻诵牟僮骱蟀拢覀儊?lái)完成幫助函數(shù) print 接口的實(shí)現(xiàn)夜涕。 print 接口主要用于打印棧當(dāng)前的所有元素，以便我們對(duì)棧的狀態(tài)有所了解属愤。它可以在建棧后女器、元素入棧、元素出棧住诸、清空棧等操作前后進(jìn)行調(diào)用驾胆，以方便我們通過(guò)輸出結(jié)果觀察、判斷這些操作的業(yè)務(wù)邏輯是否正確贱呐。
如何實(shí)現(xiàn) print 接口以及該接口需要輸出什么信息俏拱，取決于你需要觀察的棧狀態(tài)信息。以鏈?zhǔn)綏槔鹁洌页诵枰喇?dāng)前棧中所有元素以及其在棧中的位置外锅必，我還希望知道每個(gè)棧元素的內(nèi)存地址。以下給出 print 接口的實(shí)現(xiàn)：
bool print(PLStack pstack)
{
PNode p;
size_t i;
char buffer[255];
if (pstack == NULL)
{
return false;
}
p = pstack->top;
i = length(pstack);
#ifdef DEBUG
cout << "--------- STACK ----------" << endl;
sprintf(buffer, "------- %ld ELEMENTS ---------", i);
cout << buffer << endl;
#endif
while (p != NULL)
{
sprintf(buffer, "%ld [%p] : %c", i, p, p->info);
cout << buffer << endl;
i--;
p = p->link;
}
#ifdef DEBUG
cout << endl;
#endif
return true;
}
在 print 接口中惕艳，我們通過(guò)一個(gè) while 循環(huán)依次遍歷從棧頂?shù)綏５椎乃性馗阋⒚總€(gè)棧元素在棧中的 節(jié)點(diǎn)序號(hào) 、 節(jié)點(diǎn)結(jié)構(gòu)體內(nèi)存地址远搪、 節(jié)點(diǎn)數(shù)據(jù)域均打印輸出劣纲。
此外，在 print 接口中通過(guò)條件編譯語(yǔ)句#ifdef谁鳍、#endif語(yǔ)句用于在調(diào)試模式下額外輸出更多信息癞季。
測(cè)試鏈?zhǔn)綏８鞑僮鹘涌?/h2>
在講解 create、destroy 兩個(gè)操作接口的過(guò)程中倘潜，我們將鏈?zhǔn)綏５氖Ｓ嗖僮鹘涌诘膶?shí)現(xiàn)思路及過(guò)程都做了詳細(xì)的講解绷柒。
與我們之前所說(shuō)的 盡可能早的讓程序跑起來(lái) 不同的事，這次實(shí)驗(yàn)過(guò)程中涮因，我們依據(jù)每個(gè)接口的實(shí)現(xiàn)及嵌套調(diào)用關(guān)系依次實(shí)現(xiàn)了所有的接口废睦。不過(guò)這并不影響我們后續(xù)的測(cè)試工作。
以下我們給出測(cè)試主文件 main.cpp的代碼：
#include <iostream>
#include "mystack.h"
using namespace std;
int main ()
{
PLStack pstack;
ELEMTYPE x;
pstack = create();
push(pstack, 'a');
push(pstack, 'b');
push(pstack, 'c');
print(pstack);
while (!isEmpty(pstack))
{
top(pstack, &x);
cout << "stack top element: " << x << endl;
pop(pstack);
}
print(pstack);
destroy(pstack);
return 0;
}
在 main.cpp 中养泡，我們對(duì)鏈?zhǔn)綏５慕^大多數(shù)接口進(jìn)行了測(cè)試嗜湃，且 clear 接口在 destroy 接口中被調(diào)用。我們來(lái)看看編譯后的運(yùn)行結(jié)果：
[localhost@lab02:stack xgqin]$ ls
a.out main.cpp mystack.cpp mystack.h
[localhost@lab02:stack xgqin]$ vim mystack.cpp
[localhost@lab02:stack xgqin]$ g++ -DDEBUG main.cpp mystack.cpp
[localhost@lab02:stack xgqin]$ ./a.out
--------- STACK ----------
------- 3 ELEMENTS ---------
3 [0x7fc6ded00030] : c
2 [0x7fc6ded00020] : b
1 [0x7fc6ded00010] : a
stack top element: c
stack top element: b
stack top element: a
--------- STACK ----------
------- 0 ELEMENTS ---------
從運(yùn)行結(jié)果結(jié)合 main.cpp 文件源碼來(lái)看澜掩，鏈?zhǔn)綏５母鞑僮鹘涌诰９号@并不能說(shuō)明我們編寫的代碼沒有問(wèn)題，你可以嘗試編寫幾個(gè)額外的測(cè)試用例對(duì)接口進(jìn)行測(cè)試肩榕。
總結(jié)
在本文中刚陡，我們首先給出了鏈?zhǔn)綏＝Y(jié)構(gòu)的定義，并給出了需要實(shí)現(xiàn)的接口聲明形式；其次橘荠，在各個(gè)不同接口中，我們通過(guò)嵌套調(diào)用等形式復(fù)用了不少接口郎逃，這需要大家對(duì)棧的邏輯結(jié)構(gòu)保持清晰的概念哥童；最后，我們通過(guò)一段測(cè)試代碼褒翰，對(duì)所編寫的程序進(jìn)行了測(cè)試贮懈。
