堆疊 - 使用鏈結實作(C 語言動態記憶體宣告)


說明

使用陣列實作堆疊,會受到陣列大小必須事先宣告好的限制,我們可以使用鏈結(link)的方式來實作堆疊,以動態記憶體宣告的方式來新增每一個元素。

解法

鏈結(link)是由節點組成,每一個節點儲存資料之外,還儲存下一個節點的位置,如下圖所示:
Link


對堆疊而言,加入新節點與刪除節點的方法如下圖所示:
新增節點:
Link


刪除節點:
Link


鏈結也可以使用陣列來實作,不過在這邊我們以動態記憶體宣告的方式來進行,在C語言中,這是實作鏈結的基本作法,可以不受陣列大小必須先行宣告的限制,所以使用鏈結實作堆疊時,就不會有堆疊已滿的問題(除了記憶體用盡之外)。

上面的圖說只是個示意,在演算的時候,會需要一些暫存變數來協助節點新增與刪除時的連結更動,請直接參照以下的程式實作。

實作

  • C
#include <stdio.h> 
#include <stdlib.h>

struct node {
int data;
struct node *next;
};

typedef struct node Node;

Node* creates(void); // 建立堆疊
int isEmpty(Node*); // 堆疊已空
int stacktop(Node*); // 傳回頂端元素
Node* add(Node*, int); // 新增元素
Node* delete(Node*); // 刪除元素
void list(Node*); // 顯示所有內容

int main(void) {
Node* sTop;
int input, select;

sTop = creates();

while(1) {
printf("\n\n請輸入選項(-1結束):");
printf("\n(1)插入值至堆疊");
printf("\n(2)顯示堆疊頂端");
printf("\n(3)刪除頂端值");
printf("\n(4)顯示所有內容");
printf("\n\$c>");
scanf("%d", &select);

if(select == -1)
break;

switch(select) {
case 1:
printf("\n輸入值:");
scanf("%d", &input);
sTop = add(sTop, input);
break;
case 2:
printf("\n頂端值:%d", stacktop(sTop));
break;
case 3:
sTop = delete(sTop);
break;
case 4:
list(sTop);
break;
default:
printf("\n選項錯誤!");
}
}

printf("\n");

return 0;
}

Node* creates() {
return NULL;
}

int isEmpty(Node* top) {
return (top == NULL);
}

int stacktop(Node* top) {
return top->data;
}

Node* add(Node* top, int item) {
Node* newnode;

newnode = (Node*) malloc(sizeof(Node));

if(newnode == NULL) {
printf("\n記憶體配置失敗!");
exit(1);
}

newnode->data = item;
newnode->next = top;
top = newnode;

return top;
}

Node* delete(Node* top) {
Node* tmpnode;

tmpnode = top;
if(tmpnode == NULL) {
printf("\n堆疊已空!");
return NULL;
}

top = top->next;
free(tmpnode);

return top;
}

void list(Node* top) {
getnode* tmpnode;
tmpnode = top;

printf("\n堆疊內容:");
while(tmpnode != NULL) {
printf("%d ", tmpnode->data);
tmpnode = tmpnode->next;
}
}