指標、串列 (Linked List).

Presentation on theme: "指標、串列 (Linked List)."— Presentation transcript:

1 指標、串列 (Linked List)

2 使用malloc()或calloc()配置動態記憶體
變數指標 = malloc(sizeof 資料型態); 例 int num = 100; int *numPtr = # //*numPtr指向num變數 int *newPtr; //宣告指標變數 newPtr = malloc(sizeof int); //配置動態指標變數 *newPtr = 200; //起始指標變數值=200 int *ptr1 = (int *)malloc(10*sizeof(int); int *ptr2 = (int *)calloc(10, sizeof(int))

3 /* Program -- malloc-example.c
*/ #include <stdio.h> #include <stdlib.h> /* for malloc() */ int main() { int num, i, *ptr, sum = 0; printf("將動態配置陣列，陣列內的元素個數？"); scanf("%d", &num); ptr = (int*)malloc(num*sizeof(int)); //ptr = (int*)calloc(num, sizeof(int)); //calloc()將把空間清除為0 if (ptr == NULL) { printf("無法配置足夠的記憶體，sorry! 程式關閉"); exit(0); } printf("\n從鍵盤輸入每一筆元素內容，鍵入整數之後按<Enter>鍵繼續\n\n"); for (i = 0; i < num; ++i) { printf("輸入值--> "); scanf("%d", &ptr[i]); sum += ptr[i]; //scanf("%d", ptr + i); //sum += *(ptr + i); printf("\n陣列中的元素總和 = %d", sum); free(ptr); return 0;

4 malloc()配置的記憶體空間指定給指標變數
char *pc = (char *)malloc(sizeof char); int *pi = (int *)malloc(sizeof int); float *px = (float *)malloc(sizeof(float)); pc A008 (沒有名稱) A308 A309 A30A A30B A008 pi A000 (沒有名稱) A300 A301 A302 A303 A000 A001 A002 A003 px A004 (沒有名稱) A304 A305 A306 A307 A004 A005 A006 A007

5 存取指標變數與目的內容 pc pi px *pc = ‘y’; *pi = 2518; *px = 2.7182; A008 ‘y’
(沒有名稱) A308 A309 A30A A30B A008 pi A000 2518 (沒有名稱) A300 A301 A302 A303 A000 A001 A002 A003 px A004 2.7182 (沒有名稱) A304 A305 A306 A307 A004 A005 A006 A007

6 free 敘述 pc pi px free(pc); free(pi); free(px); A008 ‘y’ A000 2518 A004
A30B A008 pi A000 2518 A300 A301 A302 A303 A000 A001 A002 A003 px A004 2.7182 A304 A305 A306 A307 A004 A005 A006 A007

7 30 50 觀念釐清 (1/3) pi pj int *pi = (int *)malloc(sizeof int);
int *pj = (int *)malloc(sizeof int); *pi = 30; *pj = 50; 30 pi pj 50

8 觀念釐清 (2/3) *pj = *pi; 30 pi pj 30

9 觀念釐清 (3/3) pj = pi; 30 pi pj 50 因為失去指標的指向，這4個 bytes 的資料，無法存取，也不能刪除

10 泛型指標(Generic Pointer)
「泛型指標」不侷限於特定的資料型態，可指向任何資料型態的記憶體空間，具彈性，例： int x; void∗ p = &x; /∗ 指向x的整數儲存空間 ∗/ float f; p = &f; /∗指向f的浮點數儲存空間 ∗/ 泛型指標無法直接依址取值(dereference)，須作指定適當的資料型態，用以轉換(typecasting)或解讀資料的意義 void∗ p; printf (“%d”,∗p); /∗ 不對的寫法 ∗/ void∗ p; int ∗px=(int∗)p; printf (“%d”,∗px); /∗ 正確 ∗/

11

12 陣列的起始位址 陣列的起始位址也是整個陣列的指標 陣列 x[]的起始位址，就是陣列第一個元素的位址 &x[0] 在C/C++中，陣列名稱單獨出現時，也代表陣列的起始位址，因此，x 也是陣列的起始位址 x 和&x[0]的意義相同

13 如果 x 是陣列的起始位址(也就是整個陣列的指標)，那 x+1 的意義為何?
指標(位址)的加法 如果 x 是陣列的起始位址(也就是整個陣列的指標)，那 x+1 的意義為何? 在C/C++中，陣列的指標加1，不是單純的只是將 x 中所存的位址值加1，實際上是加上每一個陣列元素所使用記憶體 byte 數 如果是整數或浮點數則加 4 如果是字元則加 1 若 x 是一陣列的起始位址 x 是 x[0]的位址 (即&x[0]) x+1 是 x[1]的位址 (即&x[1]) x+2 是 x[2]的位址 (即&x[2]) . . . x+n 是 x[n]的位址 (即&x[n])

14 指標的目的物與陣列元素 如果 x 是一陣列的起始位址 另例 *x 就是 x[0] *(x+1)就是 x[1] *(x+2)就是 x[2]
. . . *(x+n)就是 x[n] 另例 short array[] = {30, 47, 26, 17, 22, 23}; //宣告字串變數 short *arrayPtr = array; //指標=array起始位址 printf("array 的第0個元素=%d“, *arrayPtr); //輸出第0元素=30 printf("array 的第1個元素=%d", *(arrayPtr+=1)); //輸出第1元素=47 printf("array 的第4個元素=%d", *(arrayPtr+=3)); //輸出第4元素=22

15 字元陣列與字元指標參數 在函式的參數中， 字元陣列參數 char s[] 與 字元指標參數 char *s
都是接受傳入的陣列起始位址， 兩者意義相同

16 但是在字串的定義與初值設定上，以字元陣列和字元指標，兩者的意義略有不同 字元陣列的定義：
以字元陣列定義字串 但是在字串的定義與初值設定上，以字元陣列和字元指標，兩者的意義略有不同 字元陣列的定義： char s[] = “apple”; 位址 &S[0] &S[1] &S[2] &S[3] &S[4] &S[5] S ‘a’ ‘p’ ‘p’ ‘l’ ‘e’ ‘\0’ S[0] S[1] S[2] S[3] S[4] S[5]

17 字元指標不僅可以指向單一字元，也可以指向字元陣列(字串) 字元指標的定義：
以字元指標定義字串 字元指標不僅可以指向單一字元，也可以指向字元陣列(字串) 字元指標的定義： char *t = “apple”; t t+0 t+1 t+2 t+3 t+4 t+5 位址 ‘a’ ‘p’ ‘p’ ‘l’ ‘e’ ‘\0’ *(t+0) *(t+2) *(t+4) *(t+1) *(t+3) *(t+5)

18 以字元陣列的起始位址 s，或是以指標 t 都可以代表字串 下列兩個敘述，都可以印出字串內容
兩者的相同點 以字元陣列的起始位址 s，或是以指標 t 都可以代表字串 下列兩個敘述，都可以印出字串內容 cout << s; cout << t;

19 兩者的差異 字元陣列可以直接儲存字串 字元指標必須另有初值設定或是以malloc()配置記憶體，才能儲存字串 字串陣列的名稱是一個常數
char s[10]; scanf(“%s”, s); 字元指標必須另有初值設定或是以malloc()配置記憶體，才能儲存字串 char *t; t = malloc(10); scanf(“%s”, t); 字串陣列的名稱是一個常數 s+3; 合法敘述 s++; 不合法敘述 字元指標的名稱是一個變數 t+3; 合法敘述 t++; 合法敘述

20 x 是整個陣列的起始位址 (即&x[0][0])
指標與二維陣列 宣告二維陣列範例：int x[3][2]; x 是整個陣列的起始位址 (即&x[0][0]) x[0], x[1], x[2] 分別是第一、二、三列的起始位址 (即 &x[0][0], &x[1][0], &x[2][0]) x[0] x[0][0] x[0][1] x[1] x[1][0] x[1][1] x[2] x[2][0] x[2][1]

21 sizeof array / sizeof array[0] 範例
長度運算符號 sizeof 變數名稱 sizeof array / sizeof array[0] 範例 printf(“%d”, sizeof(int)); //輸出int型態的長度4 printf(“%d”, sizeof(float)); //輸出float型態的長度4 printf(“%d”, sizeof(double)); //輸出double型態的長度8 char *array[] = {"床前明月光，", "疑似地上霜；", "舉頭望明月，", "低頭思故鄉。" }; //宣告陣列指標 int count = (sizeof array)/(sizeof array[0]); //計算元素個數

22 字元指標 (1/2) char* 字元指標名稱 = "字串資料";
char string[ ] = "ANSI/ISO C++"; //string為字串變數 char *pstring = "Visual C++"; //pstring為字串指標 printf(“%s”, string); //顯示字串變數值 printf(“%s”, pstring); //顯示指標位址到字串結束 printf(“%c”, string[7]); //顯示字串第7元素值 printf(“%s”, pstring + 7); //顯示指標第7元素至結束

23 字元指標 (2/2) 範例 char array[4][] = { "床前明月光", "疑似地上霜", "舉頭望明月",
"低頭思故鄉" }; //宣告二維字串陣列 char *parray [4] = { "床前明月光", "低頭思故鄉" }; //宣告一維字串指標

24 傳遞常數指標 (1/2) 範例 void main(void) { const int LEN = 5; //宣告整常數符號
void power(const int *); //計算平方函數原型 void main(void) { const int LEN = 5; //宣告整常數符號 power(&LEN); //傳遞常數指標 } void power(const int *NUM) //計算平方函數 cout << (*NUM) * (*NUM);

25 傳遞常數指標 (2/2) 範例二 int main() { int LEN = 5; //宣告整整數變數
void power(const int *); //計算平方函數原型 int main() { int LEN = 5; //宣告整整數變數 power(&LEN); //傳指呼叫, 傳遞變數位址 } void power(const int *NUM) //接收指標常數 cout << *NUM * *NUM;

26 傳回函數指標 範例 int main() { cout << *getNumber(); //取得getNumber()指標值
} float *getNumber() //輸入浮點數函數 float *num = (float *)malloc(sizeof float); cin >> *num; return num;

27 指標與結構綜合應用: 以Linked List為例

28 利用malloc()配置記憶體給一個結構指標
配置記憶體給結構指標 利用malloc()配置記憶體給一個結構指標 typedef struct { char name[10]; int age; char sex; } person; struct person *p; p = (person *)malloc(sizeof person); p age name sex

29 鍊結串列(Linked List) 利用指標，將許多個結構串接在一起 每一個結構體稱為一個“節點” 建立鍊結串列是將節點逐一加入 p
null

30 鍊結串列相較於陣列的優缺點 優點 (鍊結串列優於陣列之處)： 缺點 (鍊結串列不及陣列之處)： 依照實際資料個數來動態配置記憶體
每個節點可以依照需求，加入任意位置 缺點 (鍊結串列不及陣列之處)： 每個節點都需要有一個指標變數 存取速度較慢

31 鍊結串列節點的結構 「節點」的結構至少需包括 兩個欄位 data next 資料欄位，存放資料 指標欄位，用於指向下一個節點
struct node //結構的名稱為 node { int data; //存放資料 struct node *next; //存放下一節點的指標 }; data next

32 「堆疊」是一種常見的資料結 構，可使用鍊結串列加以實作
鍊結串列應用 -- 堆疊 (Stack) 「堆疊」是一種常見的資料結 構，可使用鍊結串列加以實作 後進先出(last-in first-out): 節點從頂端 top 加入，也從頂端刪除 top 指標指向堆疊的頂端 p指標指向擬加入之新節點 top null p top null

33 定義top指標(全域變數)，指向堆疊頂端
實作堆疊 宣告一個節點的結構 struct node struct node { int data; struct node *next; }; 定義top指標(全域變數)，指向堆疊頂端 struct node *top; data next top

34 堆疊初始化 -- InitStack() void InitStack() { top = NULL; } top null

35 加入節點 -- PushStack() top null p top null p void PushStack(int value) {
struct node *p; p = new struct node; p->data = value;//與(*p).data = value等義 p->next = top; top = p; } top null p top null p

36 移除節點 -- PopStack() top null p top null p int PopStack() {
struct node *p; int value; p = top; top = top->next; value = p->data; // p = p->data ?? delete p; return (value); } top null p top null p

37 使用鍊結串列實作「佇列」(queue)資料結構 先進先出(first-in first-out) Enqueue()與Dequeue()函式
延伸思考 使用鍊結串列實作「佇列」(queue)資料結構 先進先出(first-in first-out) Enqueue()與Dequeue()函式 一般形式 變形：環狀佇列 配置固定大小的空間將結構的首尾相連，Front和Back分別指示讀出與寫入資料的位置，簡化運作