指針、動態分配與鏈表

指針、引用和取值

指針是一個存儲計算機內存地址的變量。從指針指向的內存讀取數據稱作指針的取值。指針可以指向某些具體類型的變量地址，例如int、long和double。指針也可以是void類型、NULL指針和未初始化指針。

指針和數組

數組表示一段連續的內存空間，用來存儲多個特定類型的對象。與之相反，指針用來存儲單個內存地址。數組和指針不是同一種結構因此不可以互相轉換。

一個數組變量是一個常量。即使指針變量指向同樣的地址或者一個不同的數組，也不能把指針賦值給數組變量。也不可以將一個數組變量賦值給另一個數組。然而，可以把一個數組變量賦值給指針，這一點似乎讓人感到費解。把數組變量賦值給指針時，實際上是把指向數組第一個元素的地址賦給指針。

指針與結構體

就像數組一樣，指向結構體的指針存儲了結構體第一個元素的內存地址。與數組指針一樣，結構體的指針必須聲明和結構體類型保持一致，或者聲明為void類型。

需要注意兩個不同的符號，‘.’和‘->’。結構體實例可以通過使用‘.’符號訪問age變量。對于結構體實例的指針，我們可以通過‘->’符號訪問name變量，也可以同樣通過(*ptr).name來訪問name變量。

動態內存分配

所謂動態內存分配就是指在程序執行的過程中動態地分配或者回收存儲空間的分配內存的方法。動態內存分配不象數組等靜態內存分配方法那樣需要預先分配存儲空間，而是由系統根據程序的需要即時分配，且分配的大小就是程序要求的大小。

動態分配：程序在執行時調用malloc庫函數申請分配。

動態內存分配可以靈活地處理未知數目的。動態對象是沒有名字的變量，需要通過指針間接地對它進行操作。動態對象的分配與釋放必須由程序員顯式地管理，它通過malloc()和free()兩個函數（C++中為new和delete運算符）來完成。

以下是采用動態分配方式的例子：

p1=(char *)malloc(10*sizeof(int));

1.malloc函數

malloc函數的原型為：void *malloc(unsigned int size)
其作用是在內存的動態存儲區中分配一個長度為size的連續空間。其參數是一個無符號×××數，返回值是一個指向所分配的連續存儲域的起始地址的指針。還有一點必須注意的是，當函數未能成功分配存儲空間（如內存不足）就會返回一個NULL指針。所以在調用該函數時應該檢測返回值是否為NULL并執行相應的操作。
下例是一個動態分配的程序：

#include<stdio.h>

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <stdlib.h>

main()

{

int count,*array; /*count是一個計數器，array是一個整型指針，也可以理解為指向一個整型數組的首地址*/

if((array=(int *) malloc(10*sizeof(int)))==NULL)

{

     printf("不能成功分配存儲空間。");

     exit(1);

    }

    for(count=0;count<10;count++)/*給數組賦值*/

       array[count]=count;

    for(count=0;count<10;count++)/*打印數組元素*/

       printf("%d-",array[count]);

}

上例中動態分配了10個整型存儲區域，然后進行賦值并打印。例中if((array=(int *)malloc(10*sizeof(int)))==NULL)語句可以分為以下幾步：
1）分配10個整型的連續存儲空間，并返回一個指向其起始地址的整型指針
2）把此整型指針地址賦給array
3）檢測返回值是否為NULL
2.free函數

由于內存區域總是有限的，不能不限制地分配下去，而且一個程序要盡量節省資源，所以當所分配的內存區域不用時，就要釋放它，以便其它的變量或者程序使用。這時我們就要用到free函數。
其函數原型是：void free(void *p)
作用是釋放指針p所指向的內存區。
其參數p必須是先前調用malloc函數或calloc函數（另一個動態分配存儲區域的函數）時返回的指針。給free函數傳遞其它的值很可能造成死機或其它災難性的后果。
注意：這里重要的是指針的值，而不是用來申請動態內存的指針本身。例：
int *p1,*p2;
p1=malloc(10*sizeof(int));
p2=p1;
……
free(p1)/*或者free(p2)*/
malloc返回值賦給p1，又把p1的值賦給p2，所以此時p1，p2都可作為free函數的參數。
malloc函數是對存儲區域進行分配的。
free函數是釋放已經不用的內存區域的。
所以由這兩個函數就可以實現對內存區域進行動態分配并進行簡單的管理了。

鏈表

鏈表由一系列不必在內存中相連的結構組成。每一個結構均含有表元素和指向包含該元素后繼元的結構指針。我們稱之為next指針。最后一個單元的next指針指向NULL；該值由C定義并且不能與其它指針混淆。ANSI C規定NULL為零。

指針變量是包含存儲另外某個數據的地址的變量。因此，如果P被聲明為指向一個結構的指針，那么存儲在P中的值就被解釋為內存中的一個位置，在該位置能夠找到一個結構。 

typedef struct node

{

char name[20];

struct node *link;

}stud;

這樣就定義了一個單鏈表的結構，其中char name[20]是一個用來存儲姓名的字符型數組，指針*link是一個用來存儲其直接后繼的指針。定義好了鏈表的結構之后，只要在程序運行的時候在數據域中存儲適當的數據，如有后繼結點，則把鏈域指向其直接后繼，若沒有，則置為NULL。

建立了一個單鏈表之后，如果要進行一些如插入、刪除等操作該怎么辦？

1.查找

對單鏈表進行查找的思路為：對單鏈表的結點依次掃描，檢測其數據域是否是我們所要查好的值，若是返回該結點的指針，否則返回NULL。

2.插入

假設在一個單鏈表中存在2個連續結點p、q（其中p為q的直接前驅），若我們需要在p、q之間插入一個新結點s，那么我們必須先為s分配空間并賦值，然后使p的鏈域存儲s的地址，s的鏈域存儲q的地址即可。(p->link=s;s->link=q)，這樣就完成了插入操作。

插入命令需要使用一次malloc調用從系統得到一個新單元并在此后執行兩次指針調整。

3.刪除

假如我們已經知道了要刪除的結點p的位置，那么要刪除p結點時只要令p結點的前驅結點的鏈域由存儲p結點的地址該為存儲p的后繼結點的地址，并回收p結點即可。