※ 引述《yantchen (球童Yanting)》之銘言：
: ※ 引述《gingkoginkgo (人中拉拉!)》之銘言：
: : node本身就是像int一樣的資料型別(型態?)嗎?
: : 還是說他還有其他的功用?
: node 在標準的 C++ 裡面不存在喔
: 要用 class 自己定義
: : 那 所謂的heap(head?)是什麼呢?
: : 今天上課看到老師似乎有宣告了出這個鬼O_O?
: : 就我那一天只要一碗飯一瓢水的大腦 理解出來是這樣Orz
: : 每個data被存放的記憶體位置不同 但是我們在讀取時必須要照順序
: : 所以需要利用指標來標記
: : 記 憶 體 位 置 非 連 續
: : heap(?) A1 B2 C3 D4 E5
: : ▔▔▔▔ ▔▔▔▔ ▔▔▔▔ ▔▔▔▔ ▔▔▔▔ ▔▔▔▔
: : 我是空的 data01 data02 data03 data04 null
: : 沒資料 ↘ ↑ ↘ ↑
: : 指標L1 指標L2
: heap是一種父親一定比小孩大或小的complete binary tree
: link list 裡面只向第一個項目的指標叫做 head
: 用箭頭是我們示意的表示法 實際上電腦記憶體裡面長這個樣子
: instance | head a1 a2 a3 a4
: --------------------------------------------
: address | 0x12 0x18 0x23 0x11 0x56
: |
: data | null 1 3 2 7
: |
: link | 0x18 0x23 0x11 0x56 null
: 只要有head指向第一個資料 就可以利用link找到下一個資料
: 另外語法的部份
: C++裡面
: int a; // a 是 int 型態的變數
: mystack b; // b 是 mystack 型態的變數
: int* c;
: int *c; // c 是 指標變數 指向 int 型態的變數 *號兩個位置都OK
: mystack* d;// d 是 指摽變數 指向 mystack 型態的變數
: 指標變數的用法:
: c=&a; // &a代表a的位址(例如0x8793) c是指標 所以裡面存的是位址
: e=*c; // *c代表c這個位址裡面的資料 因為c指向a 所以 e 會得到 a 的數值
: 假設class mystack的定義如下
: class mystack{
: int data;
: mystack* link;
: }
: b.data=10;
: b.link=&e;
: d->data=15;
: d->link=&b;
: class裡面定義的屬性
: 一般變數用.來存取 例如上面的b.data
: 指標變數用->來存取 例如上面的d->data
: : 就概念來講 電腦讀完data01後 接著找的是指標L1 而L1本身是紀錄data02的位置
: : 就可以讀取到data02 後面就一直跟著指標走到null
: : 有錯請用力鞭<(_ _)>
: : 不過 還是有不知道該怎麼打的問題
: : 問題(a).和-> 兩個差在那裡? 要用在哪裡?(因為像老師在黑板上用的是->而非.)
: : (b)如果是三個data還好 不過如果是50個的話 我猜就會用迴圈來寫了
: : 不過要怎麼寫?(建立一個陣列去存指標嗎? )
: : 引申的問題有兩個(1)怎麼才能存那堆指標的? 用陣列? stack?
: : (2)要怎樣才能輸出?
: : 插入和刪除的部分我還要再研究(嘆)
: 的確是用迴圈
: 假設你要找第50筆資料
: 就用迴圈從head的link往下找50次
前面就恕我不整理了
有關於 (b)如果是三個data還好 不過如果是50個的話 我猜就會用迴圈來寫了
不過要怎麼寫?(建立一個陣列去存指標嗎? )
引申的問題有兩個(1)怎麼才能存那堆指標的? 用陣列? stack?
(2)要怎樣才能輸出?
建立陣列去存指標會遇到一點問題
比如說
建立了一個50個指標的陣列
但是你還是只得到了50個指標而已
並沒有得到50個物件
如果未了產生這些物件而去建立一個50個物件的陣列
那就失去做這樣一個串鏈(?)的意義了
在下經過一些嘗試後寫出了以下的碗公 不嫌棄的話就加減看看吧
以下是我的物件寫法
先大概看一下有啥就好後面會在介紹哪裏用到什麼東西
class chain{ //因為覺得有點像鏈子的資料型態 所以用chain命名
public:
void dti(int &i){data=i;} //輸入資料用函數 讀入一個整數參考
int dto(){return data;} //輸出資料用 回傳"data"
void pti(chain *i){link=i;} //輸入連結對象用 讀入一個"chain的指標"
/*(這裡雖然用"i"和上面的"dti(int &i)"相同 不過這個讀入部分取的名稱
只會作用在這個函數之內 所以只要讀入的名稱和含數裡用的名稱相呼應
和其他函數重複也沒有關係)*/
chain *pto(){return link;} //輸出連結對象 回傳"link"
private:
int data; //存放一個整數資料
//(如果要存放其他型態的資料或著更多其他資料也是在這邊宣告.命名)
chain *link; //存放連結到下一個資料的指標
};
要怎麼用這碗公
該include的那些 該using namespace那些 就掠過
灰字的部份是詳細解釋
main(){
int i=0,j=0,k=0,sum=0;//操作用
//(這些東西用來操縱迴圈 輸入資料 妙用無窮(?!))
chain *h = new chain;//標示串鏈起始位置的指標
/*(就是所謂的頭(head?) 用來標示資料串的起始位置
並確保資料串的起始位置不會在程式執行中遺失)*/
chain *ptct = new chain;//指定作業對象的指標
/*(就是讓程式記憶 "現在" 東西執行到哪裡(哪一個資料)
如果將資料比喻成很多台電腦 那麼這個指標就好像是我的"手"
將它放在哪一台電腦的鍵盤滑鼠上 就可以控制那一台電腦做事)*/
//製造chain
ptct=h; //先將我的控制目標指向這串資料的頭
cin >> j; //指定要建造幾個資料
while(i<j){ //會執行j次(0,1,2...(j-1))
(/*我曾經試著用for 不過好像會失敗 編譯沒有問題
但是程式會作業無效)*/
ptct->pti(new chain);
/*(都知道"new"這個指令是向程式要求一個資料(變數) "並且回傳他的位置"
EX:int char ...當然包含用class定義過的chain
課本裡可以找到的用法如 int *a = new int;
"建立一個新的指標"a" 然後將他的值 指定為"一個新的int資料的位置"
而ptct->pti(xxx)則是會將"xxx"輸入到ptct的"link"
也就是說 這句話的意思相當於
"用ptct->pti()這個函數存入一個位置到"指標ptct->link" 而這個位置是
來自於 new chain 這個指令(建立一個新的chain資料並回傳其位置)
所以 在這一行裡 我們同時執行了
1.建立新chain
2.將新chain的位置儲存到ptct->link(存放連結到下一個資料的指標))*/
ptct=ptct->pto();//將ptct->pto()的回傳值送回ptct
/*(ptct->pto()這個函式是將ptct->link中的位置讀出來
當這個位置送入了ptct(指標)的時候 ptct也就指向了一個不同的資料
也就是我們剛剛將他的地址存入的 新chain資料
注意 在執行完這行指令之前 我們操縱的是"h" 執行完這行指令之後
我們操縱的就是一個新資料 我們姑且稱之為"h1"
(因為使用new產生的資料並不具備程式中的名稱))*/
sum++;//這部份是為了將來輸出全部資料和掌握總資料數而設定的
i++;//這部份是為了控制迴圈
/*(要分開兩個變數是因為以後i在其他地方使用的時候還會改變
所以無法取代sum的功能 i在此只做為這個迴圈的控制變數而已)*/
}
}
這樣就把資料建立好嚕
那要怎麼存東西進去咧
有一個方法是建立的時候同時輸入
也就是ptct->pti(new chain);的下面
直接加上
cin >> k;
ptct->dti(k);
這樣就可以在建立資料的同時輸入資料值
另外的方法則是建立後利用for迴圈
ptct=h; //一樣 在進行操作前先將控制目標轉移到頭
for(i=0;i<sum;i++){ //這時候sum的功能就出來了
ptct=ptct->pto();//將控制目標轉到下一個資料
/*(也就是說 你一開始進來的時候指向"h"跑完這行就會指向"h1"
等到迴圈跑完又回到這裡 就會從指向"h1"變成指向"h2" 依此類推)*/
cin >> k;
ptct->dti(k);//這邊就是將資料輸入到目前指向的資料
}
ok 迴圈跑完也輸入完了
讀取 就將輸入那2行換成cout << ptct->dto(); //(排版的部份可以適當使用endl之類)
至於其他的 目前我想到的 像是 指定目標編輯/讀取.搜尋 等等 都是用類似的概念
至於怎麼"插入"新資料 之類的 我還沒研究 可能就以後再說 或著交給能人啦 XD~
另外因為個人函數名稱變數名稱啥的都取的怪裡怪氣 造成各位閱讀困擾 在此致歉嚕
其實也不難看出涵義 EX:dto 就是 data out. ;pt則是連結的簡寫 ;ct是control之類
那...明天還要早起...
各位晚安~
祝 遊戲愉快 (?!)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.221.141
※ 編輯: cpfmarnbg 來自: 118.166.221.141 (03/28 23:55)
※ 編輯: cpfmarnbg 來自: 118.166.221.141 (03/28 23:57)