國立成功大學

#新手 資料結構 問題

2020年10月19日 03:42
請幫我看看這段stack 的push()函式 (用Linked-list) 我的問題在top 的用法 top array的宣告都一樣 但我看不出兩者是否正確和兩者異同
有買資結聖經(Fondamantals of data structures using c) 但發現和老師上課投影片不一樣 都是2nd edition所以不知道到底為啥
25
留言 10
文章資訊
Logo
每天有 6 則貼文
共 10 則留言
史丹佛大學 電腦科技&電機
两个例子效果是一样的,都没错。
國立清華大學
差別在 一個 top 是用 array index 存取 一個是用 pointer 都是對的
原 PO - 國立成功大學
B1 B2 感謝! 那請問第二個是不是用*(top+i) 就能做到指定第幾個array存取的效果 和圖一一樣? 另外 這種寫法是代表每個 top[i] (0->n) 都有一串自己的stack ? top[i]是該串 stack 的指標(類似一串時我們用 *head or *first 的功用)?
國立清華大學
以 array 的定義來說 top[i] 確實可以改寫成 *(top + i) 沒看到完整程式碼 不過這裡 top 應該是指向 stack top 這樣的話第一個範例寫得不好 top 只有一個 不需要陣列
史丹佛大學 電腦科技&電機
是可以那样,但是你对pointer这样加可能会不安全,要先保证这个加一以后的地址是有意义的。
國立清華大學
稍微找了一下 "top array 的宣告都一樣" 這件事你要不要再確認一下? 第一個範例 我看原版是寫 stack pointer top[MAX_STACKS]; 看起來是想讓 top 兼具紀錄容量的功能 有點多餘
而第二個範例的 top 應該是宣告在 stack_pointer 裡
原 PO - 國立成功大學
B6 手邊沒有書 但我確定宣告是一樣的
你貼的第一個程式看起來幾乎等於我問的兩個 我在想 第二個用top來紀錄容量 而第一個的 stackpointer top[i]指向多個 stack 類似下圖(b)的功能
國立清華大學
看來兩個方法都有點冗... (我附的第一個連結提問就是你第一個截圖的程式碼 最佳解答也說了這做法不太好) --- 先把 element 替換成 int stack_pointer 的 typedef 拿掉 ``` struct stack{ int item; struct stack* link; }; struct stack* link top[MAX_STACKS]; ``` top 是紀錄 MAX_STACKS 個指向 struct stack 的 pointers --- 第一個範例: ``` void add(int i, int new_item) { ... } // call: add(i, new_item); i++; ``` i 是 top 的 element index --- 第二個範例 ``` void add(struct stack* *top, int new_item) { ... } // call: add(top, new_item); ``` 第一個 * 屬於 struct stack 代表"指向 struct stack 的 pointer" 也是 top 這個 array 中每個 elements 的 type 第二個 * 屬於 top 用來 pass array function 裡的 *top 相當於 top[0] call 之後必須把 array 的 首項往後移 或是當初傳進去的 top 只是原本宣告的 top 的 sub array 否則這個 add function 永遠都只會動到 top 的首項 (這部分你給的截圖還是沒寫到)
國立清華大學
比較好的方法 直接實作 linked list push 就是加在最後 pop 就是從最後刪並回傳值 (以上"最後"也可以改成"最前") 一個變數記 stack size 每次加之前檢查 這樣就好了 不需要寫得那麼複雜 也不需要那麼多空間存一堆 stacks
東海大學
這本中文翻譯超爛🤣