C语言的指针、链表的原理
一、指针
1、运用指针
什么是指针？什么是内存地址？什么叫做指针的取值？指针是一个存储计算机内存地址的变量。从指针指向的内存读取数据称作指针的取值。指针可以指向某些具体类型的变量地址，例如int、long和double。指针也可以是void类型、NULL指针和未初始化指针。
根据出现的位置不同，操作符 * 既可以用来声明一个指针变量，也可以用作指针的取值。当用在声明一个变量时，*表示这里声明了一个指针。其它情况用到*表示指针的取值。&是地址操作符，用来引用一个内存地址。通过在变量名字前使用&操作符，我们可以得到该变量的内存地址。
例如：
#include
int main()
{
int*ptr; // 声明一个int指针
int val =1; // 声明一个int值
ptr =&val; // 为指针分配一个int值的引用
int deref =*ptr; // 对指针进行取值，打印存储在指针地址中的内容
printf("deref地址=%ld,值=%d\n",ptr, deref);
第2行，我们通过*操作符声明了一个int指针。接着我们声明了一个int变量并赋值为1。然后我们用int变量的地址初始化我们的int指针。接下来对int指针取值，用变量的内存地址初始化int指针。最终，我们打印输出变量值，内容为1。
第6行的&val是一个引用。在val变量声明并初始化内存之后，通过在变量名之前使用地址操作符&我们可以直接引用变量的内存地址。
第8行，我们再一次使用*操作符来对该指针取值，可直接获得指针指向的内存地址中的数据。由于指针声明的类型是int，所以取到的值是指针指向的内存地址存储的int值。
这里可以把指针、引用和值的关系类比为信封、邮箱地址和房子。一个指针就好像是一个信封，我们可以在上面填写邮寄地址。一个引用（地址）就像是一个邮件地址，它是实际的地址。取值就像是地址对应的房子。我们可以把信封上的地址擦掉，写上另外一个我们想要的地址，但这个行为对房子没有任何影响。
2、指针和数组
C语言的数组表示一段连续的内存空间，用来存储多个特定类型的对象。与之相反，指针用来存储单个内存地址。数组和指针不是同一种结构因此不可以互相转换。而数组变量指向了数组的第一个元素的内存地址。
例如：
#include
int main()
{
int myarray[4] = {1,2,3,0};
int *ptr = myarray;
printf("ptr地址=%ld,值*ptr=%d\n", ptr,*ptr);
ptr++;
printf("ptr地址=%ld,值*ptr=%d\n", ptr,*ptr);
ptr++;
printf("ptr地址=%ld,值*ptr=%d\n", ptr,*ptr);
ptr++;
printf("ptr地址=%ld,值*ptr=%d\n", ptr,*ptr);
}
总结：
指向指针的指针，可以这样理解，首先指向指针的指针可以把他看成一种特殊的变量，既然是变量就可以存储不同的元素，比如×××变量int a，a可以存储2,3,4这种普通的整型数据，只要将值付给a就行了，但指向指针的指针所存的元素比较特殊，存放的元素一般是存放地址的指针变量，比如我有三个指针变量，int *p1,*p2,*p3,那么我可以定义一个特殊的变量 int **p,我可以将p1的地址付给p,也可以将p2的地址付给p.比如p=&p1,(类似于int a,int *t,t=&a),那么p就代表了他所指向的变量p1或者p2的地址，而p所指向的变量是一个指针变量，*p代表着这个指针变量里面的值（注意值实际上是一个地址），**p代表着它所指向的指针变量的内容(地址)所指向的存储单元的内容（数值）。
二、链表
链表是一种数据结构 ，其最大的的好处就是能够为数据分配动态内存，就不用像一开始那样先为系统分配一个都不知道够不够用的空间来存贮学生的信息。
链表，首先可以细分为一小块一小块的结构体变量，这一小块一小块的结构体变量在链表中是首尾相连的顾名思义 就像一条铁链一样 而这每一小块的结构体变量中又可以从大方向地分成两个部分， 其中一个部分就是--涵盖着该结构体变量里的所有信息，另一个部分就是链接每块结构体变量的部分--指针。
例如：
typedefstruct node
{
char name[20];
struct node *link;
}stud;
这样就定义了一个单链表的结构，其中char name[20]是一个用来存储姓名的字符型数组，指针*link是一个用来存储其直接后继的指针。定义好了链表的结构之后，只要在程序运行的时候在数据域中存储适当的数据，如有后继结点，则把链域指向其直接后继，若没有，则置为NULL。
三、指针和数组的区别
1.声明的区别
指针：exterenint * x;
数组：externint[] y[];
2.指针是保存数据的地址。
数组是保存数据。
3.指针是用于的动态的数据结构。
数组是用于储存固定的数目且数据类型相同的数据结构。
数组一经定义，其基址和大小便固定了，在该数组的有效使用范围内是不可变的；
但是指针则具有很强的动态特征，可以动态地指向任一该类型（定义决定）变量，这也就决定了它 有更大的灵活性。
4.数组是开辟一块连续的内存空间,数组本身的标示符代表整个数组。
指针则是只分配一个指针大小的内存,并可把它的值指向某个有效的内存空间。
5.指针是一个变量，可以被赋值，变量的值是另外一个变量的地址。那么，既然指针是变量，那么指 针必然有自己的存储空间，只不过是该存储空间内的值是一个地址值，而不是别的内容。
数组名仅仅是一个符号，不是变量，不可以被赋值，它没有自己的存储空间。
6.运算速度上的差异。一般来说，用指针要快些，因为在实际的运算中，总是把数组下标表示通过存储映象函数转换为指针表示，按其地址访问内存，这种转换要进行乘法和加法的运算。
7.数组具有较好的可读性，指针具有更强的灵活性。一般，对某些多维数组中非连续的元素的随机访问用下标表示比较方便，当按递增（减）顺序访问数组时，使用指针快捷而且方便。
8.访问方式：指针是间接访问，首先取得指针的内容作为地址，再去该地址访问数据；
数组是直接访问，数组名即是地址。
四、学生姓名管理系统
#include
#include
#include
#include
#define N 3
typedef struct node
{
charname[20];
struct node*link;
}stud;
stud * creat(int n) /*建立单链表的函数*/
{
stud*p,*h,*s;
int i;
if((h=(stud*)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
h->name[0]='\0';
h->link=NULL;
p=h;
for(i=0;i { if((s=(stud *) malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } p->link=s; printf("请输入第%d个人的姓名:",i+1); scanf("%s",s->name); s->link=NULL; p=s; } return(h); } stud * search(stud *h,char *x) /*查找函数*/ { stud *p; char *y; p=h->link; while(p!=NULL) { y=p->name; if(strcmp(y,x)==0) return(p); elsep=p->link; } if(p==NULL) printf("没有查找到该数据!"); } stud * search3(stud *h,char*x) /*另一个查找函数，返回的是上一个查找函数的直接前驱结点的指针， h为表头指针，x为指向要查找的姓名的指针 其实此函数的算法与上面的查找算法是一样的，只是多了一个指针s，并且s总是指向指针p所指向的结点的直接前驱， 结果返回s即是要查找的结点的前一个结点*/ { stud *p,*s; char *y; p=h->link; s=h; while(p!=NULL) { y=p->name; if(strcmp(y,x)==0) return(s); else { p=p->link; s=s->link; } } if(p==NULL) printf("没有查找到该数据!"); } void insert(stud *p) /*插入函数，在指针p后插入*/ { charstuname[20]; stud *s; /*指针s是保存新结点地址的*/ if((s= (stud*) malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } printf("请输入你要插入的人的姓名:"); scanf("%s",stuname); strcpy(s->name,stuname); /*把指针stuname所指向的数组元素拷贝给新结点的数据域*/ s->link=p->link; /*把新结点的链域指向原来p结点的后继结点*/ p->link=s;/*p结点的链域指向新结点*/ } void del(stud *x,stud *y) /*删除函数，其中y为要删除的结点的指针，x为要删除的结点的前一个结点的指针*/ { stud *s; s=y; x->link=y->link; free(s); } void print(stud *h) { stud *p; p=h->link; printf("数据信息为：\n"); while(p!=NULL) { printf("%s \n",&*(p->name)); p=p->link; } } void quit() { exit(0); } void menu(void) { system("cls"); printf("\t\t\t单链表C语言实现实例\n"); printf("\t\t|----------------|\n"); printf("\t\t| |\n"); printf("\t\t| [1] 建 立 新 表 |\n"); printf("\t\t| [2] 查 找 数 据 |\n"); printf("\t\t| [3] 插 入 数 据 |\n"); printf("\t\t| [4] 删 除 数 据 |\n"); printf("\t\t| [5] 打 印 数 据 |\n"); printf("\t\t| [6] 退 出 |\n"); printf("\t\t| |\n"); printf("\t\t| 如未建立新表，请先建立！ |\n"); printf("\t\t| |\n"); printf("\t\t|----------------|\n"); printf("\t\t 请输入你的选项(1-6):"); } main() { int choose; stud*head,*searchpoint,*forepoint; charfullname[20]; while(1) { menu(); scanf("%d",&choose); switch(choose) { case 1: head=creat(N); break; case 2: printf("输入你所要查找的人的姓名:"); scanf("%s",fullname); searchpoint=search(head,fullname); printf("你所查找的人的姓名为:%s",*&searchpoint->name); printf("\n按回车键回到主菜单。"); getchar();getchar(); break; case 3:printf("输入你要在哪个人后面插入:"); scanf("%s",fullname); searchpoint=search(head,fullname); printf("你所查找的人的姓名为:%s",*&searchpoint->name); insert(searchpoint); print(head); printf("\n按回车键回到主菜单。"); getchar();getchar(); break; case 4: print(head); printf("\n输入你所要删除的人的姓名:"); scanf("%s",fullname); searchpoint=search(head,fullname); forepoint=search3(head,fullname); del(forepoint,searchpoint); break; case 5: print(head); printf("\n按回车键回到主菜单。"); getchar();getchar(); break; case6:quit(); break; default: printf("你输入了非法字符!按回车键回到主菜单。"); system("cls"); menu(); getchar(); } } }
