指针、动态分配与链表

指针、引用和取值

指针是一个存储计算机内存地址的变量。从指针指向的内存读取数据称作指针的取值。指针可以指向某些具体类型的变量地址，例如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结点即可。