Linked List（串列） Why Linked List? Pointer Dynamic Allocation

Presentation on theme: "Linked List（串列） Why Linked List? Pointer Dynamic Allocation"— Presentation transcript:

1 Linked List（串列） Why Linked List? Pointer Dynamic Allocation
Pointer-Based ADT: List, Stack, and Queue Pointer-Based Polynomial ADT Pointer-Based Sparse Matrix ADT Varirants of Linked List Circular Linked List Doubly Linked List

2 Array-Based List ADT 的缺失：
1. Array has a fixed size. Size Items 1 2 n-1 MAX_SIZE - 1 n 45 21 33 16 ? Items[i] stores the ith item of the list. #define MAX_ITEM 100 typedef int itemType; typedef struct { int Size; Items[MAX_ITEM]; } list; 嚴格言之，用固定大小的陣列並不能完全表示出概念上該是可存無限多資料項的 ADT Lists。

3 2. Insert 時必須搬動大量的資料項 ListInsert (&L, 2, 44) k 12 3 19 ? 18 10 k+1 5
1 2 k-1 MAX_LIST-1 12 3 19 ? 18 10 k+1 5 44

4 3. Delete 時必須搬動大量的資料項 ListDelete(&L, 2) Delete k 12 3 19 10 18 ? ? k
1 2 k-1 MAX_LIST-1 k 12 3 19 10 18 ? ? 1 2 k-1 MAX_LIST-1 k 12 3 10 18 ? ? 1 2 k-2 k-1 MAX_LIST-1 k-1 12 3 34 18 ? ? ?

5 答案 Linked Lists 結論：是否有辦法避免這些缺失？亦即： 1. 所需的記憶體可隨 List 大小伸縮。
2. Insert 時「不須」搬動大量的資料項 3. Delete 時「不須」搬動大量的資料項 答案 Linked Lists

6 A Linked List 20 45 51 76 84 Insertion: 20 45 51 76 84 60 Deletion: 20
data next a link Insertion: old link 20 45 51 76 84 60 Inserted item Deletion: 20 45 51 60 76 84 Deleted item

7 Problem : How to implement the links? 答案 Pointer

8 Pointers（指標） 電腦將編譯後的可執行程式載入記憶體時，會先在記憶體中的
靜宜大學資訊管理學系 資料結構講義 2018/11/12 Pointers（指標） 電腦將編譯後的可執行程式載入記憶體時，會先在記憶體中的 資料區（heap）中預留一些空間給全域變數（global variables） 以儲存其資料。 address /* global variables */ int i; /* 4 bytes */ char c; /* 1 bytes */ float f; /* 4 bytes */ main () { int x; /* local variable */ i = i + 1; } 100 101 i 102 103 c 104 mention the relationship between variables and address. 105 106 f 107 108 將 i 中的值加 1 後存回 i 中 蔡奇偉副教授 編製

9 haep 我們稱直接存放資料值的變數為「資料變數（data variable）」。 【範例】 變數 i 儲存一個整數資料值 int i;
靜宜大學資訊管理學系 資料結構講義 2018/11/12 我們稱直接存放資料值的變數為「資料變數（data variable）」。 【範例】 變數 i 儲存一個整數資料值 int i; 變數 c 儲存一個字元資料值 char c; 變數 f 儲存一個實數資料值 float f; 變數 p 儲存一個由兩個整數組成 的結構資料值 struct point2DType { int x, y; }; point2DType P; i c f x y p haep 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 蔡奇偉副教授 編製

10 若一個變數存放的是位址而非實際的資料值，則該變數 稱為「指標變數（pointer variable）」，或簡稱為「指標
靜宜大學資訊管理學系 資料結構講義 2018/11/12 若一個變數存放的是位址而非實際的資料值，則該變數 稱為「指標變數（pointer variable）」，或簡稱為「指標 （pointer）」。 Look in location 344 for what you want 340 26 344 10 348 344 5 352 pointer p p should be drawn inside the memor area. 9 356 蔡奇偉副教授 編製

11 指標的宣告 type_name *pointer_name; 宣告變數 pointer_name 為指標變數，且其所指的位址是用來
【範例】 int *iPtr; iPtr 是整數指標變數，其指的位址所存放的資料值 將被視為整數值。 char *cPtr; cPtr 是字元指標變數，其指的位址所存放的資料值 將被視為字元值。

12 float *fPtr; fPtr 是實數指標變數，其指的位址所存放的資料值 將被視為實數值。 point2DType *pPtr; pPtr 是指標變數，其指的位址所存放的資料值將被 視為 PointType 值。 int *p, q; p 是整數指標變數，而 q 是整數變數。此宣告相當於 底下的宣告： int *p; int q;

13 如果想將 p 和 q 均宣告為指標，則必須用下列宣告：
int *p, *q; 或者是： typedef int* intPtrType; intPtrType p, q;

14 address-of operator（位址運算子）
&variable_name 位址運算元是用來求取變數的記憶體位址。上式的值是 變數 variable_name 的位址。 【範例】 int i, *ip; i ip ? i = 6; i ip 6 ? ip存著i的位址 將變數 i 的位址存入指標 ip 中 ip = &i; 6 ip i

15 ip = i /* error */ ip = 100; /* error */ OK, ip 存放記憶體絕對位址 100 ip = (int *) 100 i ip 6 100

16 利用指標來間接存取資料值： 【範例】 *pointer_name
* : indirection or dereferencing operator. 此式的值是指標 pointer_name 所指記憶體位址中的資料值。 【範例】 int i, *ip; i ip ? i = 6; i ip 6 ? 將變數 i 的位址存入指標 ip 中 ip = &i; 6 ip i or *ip

17 注意!!! *ip = 7; 和 i = 7 效果一樣 7 ip i or *ip *ip = *ip + 1;
8 ip i or *ip 注意!!! int *ip; /* 宣告 ip 是一個整數指標變數 */ *ip = 100; /* 將 100 存入指標 ip 所指的位址中 */

18 Pointer & Function Arguments
Since C passes arguments to functions by value, there is no direct way for the called function to alter a variable in the calling function. void swap (int x, int y) { int temp; temp = x; x = y; y = temp; } main () { int a = 3, b = 4; ... swap(a, b); } Because of call by value, swap can’t affect the arguments a and b in the routine that called it. The function above only swap copies of a and b.

19 The way to obtain the desired effect is for the calling program to
pass pointers to the values to be changed. void swap (int *x, int *y) { int temp; temp = *x; *x = *y; *y = temp; } main () { int a = 3, b = 4; ... swap(&a, &b); } a b x y main swap

20 Dynamic Allocation（動態配置）
如前所述，電腦將編譯後的可執行程式載入記憶體時，會 先在記憶體中的資料區（heap）中預留一些空間給全域變 數（global variables）以儲存其資料。此類配置的方式稱為 「靜態配置（static allocation）」; 這類的變數稱為「靜態 配置的變數（statically allocated variables）。如果所需的記 憶體是在程式執行時才配置的，則稱之為「動態配置 （dynamic allocation）」; 這類的變數稱為「動態配置的變 數（dynamically allocated variables）。同時，這些變數並沒 有名稱，而必須倚靠指標來間接存取其中的資料值。

21 C 提供以下的動態配置函數（定義於 stdlib.h 中）：
void *malloc(size_t size) malloc returns a pointer to space for an objects of size size, or NULL if the request cannot be satisfied. The space is uninitialized. void *calloc(size_t nobj, size_t size) calloc returns a pointer to space for an array of nobj objects, each of size size, or NULL if the request cannot be satisfied. The space is initialized to zero bytes. void *realloc(void *p, size_t size) realloc changes the size of the object pointed to by p to size. The contents will be unchanged up to the minimum of the old and new sizes. If the new size is larger, the new space is uninitialized. realloc returns a pointer to the new space, or NULL if the request cannot be satisfied, in which case *p is unchanged.

22 【範例】 type casting int *ip = (int *) malloc(sizeof(int));
動態配置一塊記憶體來儲存整數資料，並將此記憶體的 位址存入指標變數 ip 中。 float *fp = (float *) malloc(sizeof(float)); 動態配置一塊記憶體來儲存浮點數資料，並將此記憶體 的位址存入指標變數 fp 中。 typedef struct { int x, y; } point; point *pp = (point *) malloc(sizeof(point)); 動態配置一塊記憶體來儲存 point 型態的資料，並將此 記憶體的位址存入指標變數 pp 中。 fp *fp pp *pp x y

23 int *ip = (int *) calloc(1, sizeof(int)); 動態配置一塊記憶體來儲存整數資料，並將此記憶體的
int *ip = (int *) malloc(sizeof(int)); int *iArray = (int *) calloc(100, sizeof(int)); 動態配置一塊記憶體來儲存 100 個整數資料，並將此記 憶體的位址存入指標變數 iArray 中。 iArray 1 98 99 int *iArray = (int *) malloc(100*sizeof(int)); iArray 1 98 99 ?

24 【範例】 C 提供下面的函式來解除一塊經由動態配置而得的記憶體 區塊，並將之歸還給系統。（定義於 stdlib.h 中）
void free (void *p) free deallocates the space pointed by p; it does nothing if p is NULL. p must be a pointer to space previuosly allocated by calloc, malloc, or realloc. 【範例】 int *ip = (int *) malloc(sizeof(int)); int *iArray = (int *) calloc(100, sizeof(int)); free(ip); free(iArray);

25 在以後的討論中，我們將採用下列的巨集定義：
/************************************************* * FILE: new.h *************************************************/ #ifndef NEW_H_ #define NEW_H_ #include <stdlib.h> #ifndef NULL #define NULL ((void *) 0) #endif #define NEW1(type) (((type) *) calloc(1,sizeof(type))) #define NEW(n,type) (((type) *) calloc((n), sizeof(type))) #define FREE(ptr) (free(ptr))

26 【範例】 int * P, *Q; int X; P Q ? X P = &X; P X ? *P = 6; P X or *P 6
P = NEW1(int); P *P X 6 *P = 7; P *P X 7 6

27 Q = P; P *P or *Q X 7 6 Q Q = NEW1(int); *Q = 8 P *P X 7 6 Q *Q 8
P = NULL; P X 7 6 Q *Q 8 FREE(Q); Q = NULL; P X 7 6 Q memory leak

28 指標和陣列 int iArray[100]; int *iPtr = NEW(100, int);
iArray 和 iPtr 都是含有 100 個整數的陣列。兩者都可以 用 index 的方式來存取其中的元素，比方說： iArray[50] 和 iPtr[50] 分別代表 iArray 和 iPtr 中的第 51 個整數。兩者的區別在 於 iArray 是以靜態配置的方式產生，而iPtr是以動態配置 的方式產生。因此，iArray 無法用 free 函數去除其所佔 的記憶體空間，而 iPtr 卻可以。比方說：

29 Question: FREE(iArray); /* error */ FREE(iPtr); /* OK */
iPtr = NEW(200, int); iPtr is now an integer array of 200 elements. Question: What are the values of the following sizeof operations? sizeof(iArray) sizeof(iPtr)

30 指標算式 If p is a pointer to some element of an array, then p++ increments p to point to the next element, and p += i increments it to point i elements beyond where it currently does. 1 i MAX_ARRAY - 1 p p+1 p+i p + MAX_ARRAY - 1 If p and q point to members of the same array, then relations like ==, !=, <, >=, etc., work properly. For example, p < q is true if p points to an earlier member of the array than q does.

31 int *iA = NEW(MAX_SIZE, int); char *cA = NEW(MAX_SIZE, char);
#define MAX_SIZE 26 int *iA = NEW(MAX_SIZE, int); char *cA = NEW(MAX_SIZE, char); int *iEnd = iA + MAX_SIZE, *ip; for (ip = iA; ip < iEnd; ip++) *ip = ip - iA; for (int i = 0; i < MAX_SIZE; i++) iA[i] = i; for (int i = 0; i < MAX_SIZE; i++) cA[i] = 'A' + i; char *cEnd = cA + MAX_SIZE, *cp; for (cp = cA; cp < cEnd; cp++) *cp = 'A' + (cp - cA);

32 struct 指標中的成員存取 or struct_pointer_name->member_name
typedef struct { int x, y; } point2DType; point2DType *P = NEW1(point2DType), *Q = NEW1(point2DType); P->x = 100; P->y = 200; Q->x = P->x + 1; Q->y = Q->x * 2; or (*P).x = 100; (*P).y = 200; (*Q).x = (*P).x + 1; (*Q).y = (*Q).x * 2; P *P x y Q *Q x y

33 A Linked List 如何表示節點？ 節點 20 45 51 76 84 由上圖可知，每一個節點包含兩個部份：data 和 link。
next a link 由上圖可知，每一個節點包含兩個部份：data 和 link。 我們可以用 struct 的方式來表示這樣的結構，以及用指 標來表示 link。節點的結構如下： struct node { int Data; struct node *Next; }

34 或者： struct node; /* forward definition */ typedef struct node* ptrType; struct node { int Data; ptrType Next; } 節點變數的宣告如下： struct node aNode; struct node *aNodePtr;

35 A Pointer-Based Implementation of the ADT List
List ADT List Copy Dummy Head Node Link List

36 List ADT OBJECTS: A list that contains a sequence of data items.
FUNCTIONS: list CreateList () boolean IsEmpty(list L) int ListLength (list L) boolean ListRetrieve (list L, int i, itemType Data) boolean ListInsert (list L, int i, ItemType Data) boolean ListDelete (list L, int i)

37 typedef int listItemType; typedef struct node { listItemType Item;
下圖顯示串列的表示法： aList NULL 20 45 76 84 typedef int listItemType; typedef struct node { listItemType Item; struct node *Next; } nodeType, *nodePtrType; typedef nodePtrType list;

38 /* Create an empty list */
list CreateList (void) { return NULL; } list L = CreateList(); L /* Check if L is an empty list */ boolean IsEmpty(list L) { return (L == NULL)? TRUE : FALSE; }

39 /* Calculate the length of list L */ int ListLength (list L) {
nodePtrType p; int len; len = 0; for (p = L; p != NULL; p = p->Next) len++; return len; } 20 45 76 84 L NULL Item Next p p p p

40 /* Get the address of the n-th node of L for n = 0, 1, ...,
* ListLength(L) - 1. */ static nodePtrType Ptrto (list L, int n) { nodePtrType p; if (n < 0) return NULL; for (p = L; n > 0 && p != NULL; n--, p = p->Next) ; return p; } 20 45 76 84 L 1 n ListLength(L) - 1 p p p

41 boolean ListRetrieve (list L, int n, listItemType *Data) {
nodePtrType p = PtrTo(L, n); if (p == NULL) return FALSE; else { *Data = p->Item; return TRUE; } 20 45 76 84 L 1 n ListLength(L) - 1 p p p

42 Insert Operation 我們考慮將資料項插入串列的二種情形： 一、資料項插在最前面的位置： L 20 45 51
ListInsert(L, 0, 56); L 20 45 51 56

43 L 20 45 51 ListInsert(L, 0, 56); NewPtr 56 L 20 45 51 nodePtrType NewPtr = NEW1(nodeType); NewPtr->Item = 56; NewPtr->Next = L; L = NewPtr;

44 先建後拆 L 20 45 51 ListInsert(L, 0, 56); NewPtr 56 L 20 45 51
nodePtrType NewPtr = NEW1(nodeType); NewPtr->Item = 56; L = NewPtr; NewPtr->Next = L;

45 二、資料項不是插在最前面的位置： L 20 45 51 ListInsert(L, 1, 56); 56 L 20 45 51

46 L 20 45 51 ListInsert(L, 1, 56); NewPtr 56 L 20 45 51 Prev nodePtrType NewPtr = NEW1(nodeType); NewPtr->Item = 56; nodePtrType Prev = PtrTo(L, 1-1); NewPtr->Next = Prev->Next; Prev->Next = NewPtr;

47 boolean ListInsert(list *L, int n, listItemType NewItem)
{ boolean Success = (n >= 0 && n <= ListLength(*L)) ? TRUE : FALSE; nodePtrType NewPtr, Prev; if (Success) { NewPtr = NEW1(nodeType); Success = (NewPtr != NULL) ? TRUE : FALSE; NewPtr->Item = NewItem; /* attach new node to list */ if (n == 0) { /* insert new node at beginning of list */ NewPtr->Next = *L; *L = NewPtr; }

48 else { Prev = PtrTo(*L, n - 1); /* Insert new node after node to which Prev points */ NewPtr->Next = Prev->Next; Prev->Next = NewPtr; } /* end if */ return Success; } /* end ListInsert */

49 Delete Operation 我們考慮將資料項從串列中刪除的二種情形： 一、刪除在最前面的資料項： L 20 45 51 76
ListDelete(L, 0) L 45 51 76

50 L 20 45 51 76 ListDelete(L, 0) L 20 45 51 76 Cur nodePtrType Cur = L; /* save pointer to node */ L = L->Next; Free(Cur);

51 一、刪除不在最前面的資料項： L 20 45 51 76 ListDelete(L, 1) L 20 45 51 76 Prev Cur nodePtrType Prev = PtrTo(1-1); nodePtrType Cur = Prev->Next Prev->Next = Cur->Next; Free(Cur);

52 boolean ListDelete(list *L, int n)
{ ptrType Cur, Prev; boolean Success = (n >= 0) && n < ListLength(*L) )? TRUE : FALSE; if (Success) { if (n == 0) { /* delete the first node from the list */ Cur = *L; /* save pointer to node */ *L = (*L)->Next; } else { Prev = PtrTo(*L, n - 1); /* delete the node after the node to which Prev points */ Cur = Prev->Next; /* save pointer to node */ Prev->Next = Cur->Next; FREE(Cur); return Success;

53 List Copy 串列有兩種拷貝的方式： 淺拷貝（shallow copy）：不拷貝資料項目 深拷貝（deep copy）：拷貝資料項目
以下圖為例： 淺拷貝 L 20 45 51 76 Copy of L L 20 45 51 76 深拷貝 Copy of L 20 45 51 76

54 淺拷貝 list ListShallowCopy (list L) { return L; } 20 45 51 76 L list M;
M = ListShallowCopy(L); 20 45 51 76 M L

55 20 45 51 76 M L ListDelete(M, 1); L 20 51 76 M ListInsert(L, 1, 99); 20 99 51 76 M L

56 深拷貝 p M q 20 45 51 76 L 20 45 51 76 L p M 20 q 45

57 M 20 45 51 76 L p q M 20 45 51 76 L p q

58 list ListDeepCopy (list L)
{ nodePtrType p, q; list M; if (IsEmpty(L)) return NULL; /* original list is empty */ p = L; M = q = NEW1(nodeType); assert(q != NULL); while (TRUE) { q->Item = p->Item; if (p->Next != NULL) { p = p->Next; q->Next = NEW1(nodeType); assert(q->Next != NULL); q = q->Next; } else break; q->Next = NULL; return M;

59 L 20 45 51 76 M 20 45 51 76 ListDelete(&M, 1); L 20 45 51 76 M 20 51 76 ListInsert(&M, 1, 99); L 20 45 51 76 M 20 99 51 76

60 Linked Lists with Dummy Head Nodes
首先，我們回憶一下：在做串列的 insert 和 delete 時 ，由於第一個節點異於其他節點，我們的處理方法就 必須分為兩種狀況來處理： 增刪第一個節點 增刪非第一個節點

61 L 20 45 51 一、資料項插在最前面的位置： ListInsert(L, 0, 56); L 20 45 51 56 二、資料項不是插在最前面的位置： ListInsert(L, 1, 56); L 20 45 51 56

62 L 20 45 51 76 一、刪除在最前面的資料項： ListDelete(L, 0) L 20 45 51 76 二、刪除不在最前面的資料項： ListDelete(L, 1) L 20 45 51 76

63 如何避免這樣的區分呢？ 答案 Dummy Head Node

64 前面所指出的問題，完全是因為第一個節點異於其他節點的 緣故。因此破解的方法就是想辦法讓第一個節點和其他的節
點一樣。為此，我們構建一個「空頭」節點來取代指標 L： L 20 45 51 76 ? 20 45 51 76 Dummy Head Node 如此一來，第一個節點就和其他的節點一樣是靠前一個節點 （即空頭節點）的 Next 指標所串接起來的。 接下來，我們看看這一個新的表示方式，是否真的解決了 前述的問題。

65 哈！哈！ 果然很像 Insert 56 第一個節點： ? 20 45 51 Dummy Head Node 56 非第一個節點： ? 20

66 哈！哈！ 真的很像 Delete 第一個節點： ? Dummy Head Node 20 45 51 76 非第一個節點： ? Dummy

67 /* Create an empty list */
void CreateList (list L) { L->Next = NULL; } nodeType L; CreateList(&L); ? Dummy Head Node /* Check if L is an empty list */ boolean IsEmpty(list L) { return (L->Next == NULL)? TRUE : FALSE; }

68 /* Calculate the length of list L */ int ListLength (list L) {
nodePtrType p; int len; len = 0; for (p = L->Next; p != NULL; p = p->Next) len++; return len; } ? Dummy Head Node 20 45 76 84 Item Next p p p p

69 /* Get the address of the n-th node of L for n = 0, 1, ...,
* ListLength(L) - 1. */ static nodePtrType Ptrto (list L, int n) { nodePtrType p; if (n < -1) return NULL; else if (n == -1) return L; for (p = L->Next; n > 0 && p != NULL; n--, p = p->Next) ; return p; } 1 n ListLength(L) - 1 ? Dummy Head Node 20 45 76 84 p p p

70 boolean ListRetrieve (list L, int n, listItemType *Data) {
nodePtrType p = PtrTo(L, n); if (p == NULL || p == L) return FALSE; else { *Data = p->Item; return TRUE; } 1 n ListLength(L) - 1 ? Dummy Head Node 20 45 76 84 p p p

71 boolean ListInsert(list L, int n, listItemType NewItem)
{ boolean Success = (n >= 0 && n <= ListLength(L)) ? TRUE : FALSE; nodePtrType NewPtr, Prev; if (Success) { NewPtr = NEW1(nodeType); Success = (NewPtr != NULL) ? TRUE : FALSE; NewPtr->Item = NewItem; Prev = PtrTo(L, n - 1); /* Insert new node after node to which Prev points */ NewPtr->Next = Prev->Next; Prev->Next = NewPtr; } return Success;

72 boolean ListDelete(list L, int n)
{ ptrType Cur, Prev; boolean Success = (n >= 0) && n < ListLength(L) )? TRUE : FALSE; if (Success) { Prev = PtrTo(L, n - 1); /* delete the node after the node to which Prev points */ Cur = Prev->Next; /* save pointer to node */ Prev->Next = Cur->Next; } FREE(Cur); return Success;

73 Linked List Data with an Aggregate Type
為了簡化的緣故，在前面的說明中，我們僅用 int 的資料型態， 然而，在實際的情形中，資料不是如此的簡單。比方說，我們 可以建立一個學生資料的串列如下： struct studentType { char Name[20]; // 姓名 char Address[30]; // 地址 char PhoneNumber[10]; // 電話 int Age; // 年齡 char Department[4]; // 系別 int Year; // 年級 char Class; // 班級 }; typedef studentType listItemType;

74 char PhoneNumber[10]; // 電話 int Age; // 年齡 char Department[4]; // 系別
struct studentType { char Name[20]; // 姓名 char Address[30]; // 地址 char PhoneNumber[10]; // 電話 int Age; // 年齡 char Department[4]; // 系別 int Year; // 年級 char Class; // 班級 }; typedef studentType listItemType; L Name Address