實習課第五次作業

tags: NTOU CSE C++ Programming

教學文件和作業說明文件： https://hackmd.io/@kogiokka/ntou-cse-cpp-nav

範例程式和範例專案：Google Drive

本次主題是堆疊（stack）資料結構。

題目

程式要以下列三個方式實作三個版本的堆疊（stack），儲存值的型態為float：

1. 版本一、巨集（#define ...）
2. 版本二、動態陣列（malloc）
3. 版本三、連結串列（linked-list）

要求

• 不可使用全域變數（global variables）。
• 程式要包含一個無窮迴圈，每次供使用者輸入選項 1 到 4，分別執行下列功能：

輸入	動作
1	版本一
2	版本二
3	版本三
4	結束程式

• 每一個版本在 Demo 時要執行下列功能：
  a) push
  b) pop
  c) printStack
  d) 結束（回到選擇版本的迴圈）

• 定義下列結構（struct）：

方法	名稱	成員
巨集	struct Stack_define	stack_array、size、top
動態陣列	struct Stack_malloc	stack_array、size、top
連結串列	struct Stack_linked	headPtr

• 定義下列函式（functions）：

函式名稱	回傳值型態	回傳值意義
push	bool	true 代表成功，false 代表失敗。
pop	bool	true 代表成功，false 代表失敗。
isEmpty	bool	true 代表成功，false 代表失敗。
isFull	bool	true 代表成功，false 代表失敗。
printStack	void	無回傳值

• 三個版本皆包含在同一個專案內。使用一個標頭檔：
  → stack.h

• 每個實作版本和main函式必須分別放在不同檔案內:
  → main.cpp
  → stack_define.cpp
  → stack_malloc.cpp
  → stack_linked.cpp

• 使用 reference 語法寫push、pop：

// 改為 bool push(StackNodePtr&,float); 
// 回傳 bool true代表成功，false代表失敗
void push(StackNodePtr *, int);

// 改為 bool pop(StackNodePtr&, float&);
int pop(StackNodePtr *);

參考文章：Lvalue references - Learn C++

版本一、巨集

使用 #define 來定義陣列大小：

// Example
#define STACK_SIZE 10
float stack[STACK_SIZE];

版本二、動態陣列

使用函式來初始化堆疊的大小：

/* 定義 stackInitial 函式
 *
 *  - 使用 malloc
 *  - 回傳成功或失敗
 *  - 參數 size 為堆疊初始化的大小
 *  - size 預設值為 10
 */ 
bool stackInitial(int size);

版本三、連結串列

不用定義 isFull 函式。

作業上傳規定

格式：<學號>-<姓名>.zip，例如：11057022-江柏毅.zip

如果你是用 Visual Studio，請刪除下列資料夾再上傳：.vs、out、Debug、x64。
使用其他 IDE 的同學也請刪掉建置資料夾再上傳，例如：build、out。

參考資料

• Implementation of Stack Using Array in C
• Linked List: Intro(簡介)
• Stack: 以Array與Linked list實作
• 如何在 C++ 中建立一個動態陣列