SlideFinderPowerPoint search engine with thumbnail results
Newest Viewed Downloaded

3-2 單向鏈結串列

第3章 串列結構 指標與結構 單向鏈結串列 環狀串列 雙向鏈結串列 多項式的串列表示法

指標簡介(1)

3-1 指標與結構 資料型態* 指標變數名稱; 或 資料型態 *指標變數名稱; int* a; /* 宣告一個「指向int型態變數」的指標a */ float* b; /* 宣告一個「指向float型態變數」的指標b */ double* c; /* 宣告一個「指向double型態變數」的指標c*/ 在C++語言中，指標的宣告必須利用「*」運算子。宣告方式如下： 上述兩種宣告方式的「*」位置不一樣。舉例如下：

指標簡介(2)

3-1 指標與結構 隨堂範例：ch03_01.cpp

3-1 指標與結構 執行結果

動態記憶體與節點配置(1)

3-1 指標與結構 資料型態 *指標變數=new 資料型態(初始值); 在C++中，可以分別使用new與delete運算子於程式執行期間動態配置與釋放記憶體空間。 其中new運算子會依據所要求的記憶體大小，在記憶體中配置足夠空間，並傳回所配置記憶體的指標值，也就是記憶體位址。 C++動態配置變數的方式，也就是在執行階段時，依照資料型態來動態配置一個記憶體空間，並將配置空間位址傳回指派的指標變數。宣告格式如下：

3-1 指標與結構 delete 指標名稱； int *ptr=new int; // 配置動態記憶體，並指定到*ptr指標變數 ptr++; // 指標變數所指位址遞增1，即往後位移4byte(int型態) delete ptr; 當配置的記憶體已不再使用時，就要使用delete運算子來釋放該記憶體空間。 否則當配置記憶體越多時，將影響到程式可用空間，而降低程式執行效能。宣告方法如下： 使用delete運算子釋放動態記憶體時，該指標變數所指的記憶體位址，必須是原來new運算子所配置的位址，否則將會造成無法預期的執行結果。如下所示：

動態記憶體與節點配置(2)

3-1 指標與結構 隨堂範例：ch03_02.cpp

3-1 指標與結構 執行結果

單向鏈結串列定義(1)

3-2 單向鏈結串列 串列中的每一個節點均不需儲存於連續的記憶體位置，且是一個指向節點的指標。 也就是說，而這個結構中至少要有兩個或以上的欄位，分別存放資料及鏈結欄位。 struct node { int data; struct node *next; }; struct node *newnode; struct node * t; 詳細定義如下： 例如串列A={a，b，c，d，x}，其單向串列資料結構如下：

3-2 單向鏈結串列 struct student { char name[20]; // 資料欄位 int score; // 資料欄位 struct student *next; // 鏈結欄位 } s1, s2; // 宣告s1 與 s2 兩個節點 簡單定義一個學生成績串列元素的student結構。 這是一個巢狀結構，而內層結構也是使用student進行宣告，但是宣告成指標變數next，表示它可以用來存放一個student結構的記憶體位址。如下所示：

單向鏈結串列定義(2)

3-2 單向鏈結串列 隨堂範例：ch03_03.cpp

3-2 單向鏈結串列

3-2 單向鏈結串列 執行結果

單向鏈結串列的新增節點(1)

3-2 單向鏈結串列 只需把新節點的指標指向串列首，再把串列首移到新節點上即可。 newnode = new node; newnode -> next = first; first = newnode; 把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可。 newnode= new node; last -> next = newnode; last = newnode; 在串列的第一節點插入節點 節點加於最後一個節點之後

單向鏈結串列的新增節點(2)

3-2 單向鏈結串列 newnode= new node; newnode->next = y; x->next = newnode; 加於節點中間任何一個位置 在串列的中間位置插入節點。 例如插入的節點是在X與Y之間，只要將X節點的指標指向新節點，新節點的指標指向Y節點即可。

單向鏈結串列的刪除節點(1)

3-2 單向鏈結串列 只要指向最後一個節點的指標，直接指向NULL即可。 只要把串列首指標指向第二個節點即可 first = first->next; 1.刪除串列的第一個節點 2.刪除串列後的最後一個節點

單向鏈結串列的刪除節點(2)

3-2 單向鏈結串列 3.刪除串列內的中間節點 完成這樣的動作需要以下兩個步驟: 第一步，將節點ptr結構中的指標，指向結構Y中指標所指向的同一個位址。 第二步，釋放節點Y在記憶體中的資料，如此即可完成刪除一個節點的動作。以上兩個步驟如下圖所示：

單向鏈結串列的反轉

3-2 單向鏈結串列 int invert(*node X) { node* p, q, r; P=X;q=NULL; while (p!=NULL) { r=q;q=p; //r接到q之後，q接到p之後 p = p->next; //p移到下一個節點 q->next = r; //q連結到之前的節點 } X=q; return 0; } 如下圖所示： 演算法可以如下表示：

環狀串列

3-3 環狀串列 環狀串列可以從串列中任一節點來追蹤所有串列的其他節點，也無所謂哪一個節點是首節點，建立的過程與單向鏈結串列相似，唯一的不同點是必須要將最後一個節點指向第一個節點。 範例 3.3.1 請繪圖及寫出回收環狀串列節點到可用空間串列(AV串列)的演算法，並比較回收單向鏈結串列與環狀串列的時間複雜度。

環狀串列的節點插入(1)

3-3 環狀串列 將新節點X直接插入原串列首之前，成為新的串列首，圖形如下： 步驟： 1.將新節點X的指標指向原串列首節點。 2.移動整個串列。 3.將串列首指向新節點。

Showing 1 - 20 of 38 items Details

Name: 
03
Author: 
小潘
Company: 
榮欽科技
Description: 
3-2 單向鏈結串列
Tags: 
rlink | node | llink | ptr | 單向鏈結串列 | newnode | 多項式的串列表示法 | struct
Created: 
1/8/2008 3:16:01 AM
Slides: 
38
Views: 
1
Downloads: 
0
Rating: 
0


> Comment



Share this presentation
|
12 Next >>

Comments

Share this presentation:

|
Sitemap