C语言程序设计之入门课程4

程序设计与实践C第4集指针与链表地址和指针的概念

内存区的每一个字节有一个编号，这就是“地址”。如果在程序中定义了一个变量，在对程序进行编译时，系统就会给这个变量分配内存单元。１、按变量地址存取变量值的方式称为“直接访问”方式ｐｒｉｎｔｆ（″％ｄ″，ｉ）；ｓｃａｎｆ（″％ｄ″，＆ｉ）；ｋ＝ｉ＋ｊ；2.另一种存取变量值的方式称为“间接访问”的方式。即，将变量ｉ的地址存放在另一个变量中。在Ｃ语言中，指针是一种特殊的变量，它是存放地址的。一个变量的地址称为该变量的“指针”。例如，地址2000是变量ｉ的指针。如果有一个变量专门用来存放另一变量的地址（即指针），则它称为“指针变量”。上述的i_pointer就是一个指针变量。指针和指针变量的定义：变量的指针和指向变量的指针变量怎样定义指针变量定义指针变量的一般形式为基类型*指针变量名；下面都是合法的定义：float*pointer_３；

char*pointer_４；可以用赋值语句使一个指针变量得到另一个变量的地址，从而使它指向一个该变量。例如：pointer_１＝＆ｉ；pointer_２＝＆ｊ；在定义指针变量时要注意两点：指针变量前面的“*”，表示该变量的类型为指针型变量。例:float*pointer_1；指针变量名是pointer_1

，而不是*pointer_1

。(2)在定义指针变量时必须指定基类型。需要特别注意的是，只有整型变量的地址才能放到指向整型变量的指针变量中。下面的赋值是错误的∶

floata;int*pointer_1;pointer_1=&a;在对指针变量赋值时需要注意两点：⑴指针变量中只能存放地址（指针），不要将一个整数赋给一个指针变量。例:pointer_1＝１００；

/*pointer_1是指针变量,１００是整数，不合法*/(2)赋给指针变量的是变量地址不能是任意的类型，而只能是与指针变量的基类型具有相同类型的变量的地址。

在引用指针变量时，可能有三种情况：⑴给指针变量赋值。如：

p=&a;⑵引用指针变量的值。如：

printf(“%o”,p);⑶引用指针变量指向的变量。有关的两个运算符：＆取地址运算符。&a是变量a的地址。*指针运算符（或称“间接访问”运算符），*p是指针变量p指向的对象的值。怎样引用指针变量例10.１通过指针变量访问整型变量#include<stdio.h>void

main()｛intａ，ｂ；

int*pointer_１，*pointer_２；ａ＝１００；ｂ＝１０；

pointer_１＝＆ａ；/*把变量ａ的地址赋给

pointer_1*/pointer_２＝＆ｂ；/*把变量ｂ的地址赋给

pointer_２*/printf（″%ｄ，%ｄ\ｎ″,ａ,ｂ）；printf（″%ｄ，%ｄ\ｎ″,*pointer_１,*pointer_２）；｝通过指针引用数组一个变量有地址，一个数组包含若干元素，每个数组元素都在内存中占用存储单元，它们都有相应的地址。指针变量既然可以指向变量，当然也可以指向数组元素（把某一元素的地址放到一个指针变量中）。所谓数组元素的指针就是数组元素的地址。数组元素的指针可以用一个指针变量指向一个数组元素。例如：ｉｎｔａ［１０］；

(定义ａ为包含１０个整型数据的数组)

ｉｎｔ*ｐ；

(定义ｐ为指向整型变量的指针变量)

ｐ＝＆ａ［０］；

(把ａ［０］元素的地址赋给指针变量ｐ)也就是使ｐ指向ａ数组的第０号元素。Ｃ语言规定在指针指向数组元素时，可以对指针进行以下运算：加一个整数(用+或+=)，如p+1

减一个整数(用-或-=)，如p-1

自加运算，如p++，++p

自减运算，如p--，--p

两个指针相减，如p1-p2(只有p1和p2都指向同一数组中的元素时才有意义)。指针的运算分别说明如下：如果指针变量p已指向数组中的一个元素，则ｐ＋１指向同一数组中的下一个元素，ｐ-１指向同一数组中的上一个元素。(2)如果p原来指向a[0]，执行++p后p的值改变了，在p的原值基础上加d，这样p就指向数组的下一个元素a[1]。(3)如果ｐ的初值为＆ａ[０]，则ｐ＋ｉ和ａ＋ｉ就是数组元素ａ［ｉ］的地址，或者说，它们指向ａ数组的第ｉ个元素。*（ｐ＋ｉ）或*（ａ＋ｉ）是ｐ＋ｉ或ａ＋ｉ所指向的数组元素，即ａ［ｉ］。(5)如果指针变量p1和p2都指向同一数组，如执行p2-p1，结果是两个地址之差除以数组元素的长度。通过指针引用数组元素引用一个数组元素，可以用：

（１）下标法，如ａ［ｉ］形式；（２）指针法，如*（ａ＋ｉ）或*（ｐ＋ｉ）。其中ａ是数组名，ｐ是指向数组元素的指针变量，其初值ｐ＝ａ。例10.5输出数组中的全部元素

假设有一个ａ数组，整型，有１０个元素。要输出各元素的值有三种方法：(1)下标法#include<stdio.h>voidmain（）｛intａ［１０］；

intｉ；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

scanf（″％ｄ″，＆ａ［ｉ］）；

printf（″＼ｎ″）；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

printf（″％ｄ″，ａ［ｉ］）；｝(2)通过数组名计算数组元素地址，找出元素的值。#include<stdio.h>void

main（）｛intａ［１０］；

intｉ；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

scanf（″％ｄ″，＆ａ［ｉ］）；

printf（″＼ｎ″）；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

printf（″％ｄ″，*（ａ＋ｉ））；｝(3)用指针变量指向数组元素。#include<stdio.h>voidmain（）｛intａ［１０］；

int*ｐ，ｉ；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

scanf（″％ｄ″，＆ａ［ｉ］）；

printf（″＼ｎ″）；

for（ｐ＝ａ；ｐ＜（ａ＋１０）；ｐ＋＋）

printf（″％ｄ″，*ｐ）；｝22例：跳马。依下图将每一步跳马之后的位置(x,y)放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。结构的概念与应用23依上图有7个结点(x1,y1)(x2,y2)(x6,y6)(x7,y7)为了表示这种既有数据又有指针的情况，引入结构这种数据类型。24用指针处理链表链表是程序设计中一种重要的动态数据结构，它是动态地进行存储分配的一种结构。动态性体现为：链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；元素的位置可以变化，即可以从某个位置删除，然后再插入到一个新的地方；251249A1356B1475C1021DNull1、链表中的元素称为“结点”，每个结点包括两个域：数据域和指针域；2、单向链表通常由一个头指针（head)，用于指向链表头；3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL)。Head1249135614751021结点里的指针是存放下一个结点的地址26链表中结点的定义链表是由结点构成的，关键是定义结点;链表的结点定义打破了先定义再使用的限制,即可以用自己定义自己；递归函数的定义也违反了先定义再使用；这是C语言程序设计上的两大特例27

链表的基本操作对链表的基本操作有：（1）创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。（2）检索操作是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。（3）插入操作是指，在结点ki-1与ki之间插入一个新的结点k’，使线性表的长度增1，且ki-1与ki的逻辑关系发生如下变化：插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新插入的结点k’成为ki-1的后继、ki的前驱.28（4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继.(5)打印输出29一个指针类型的成员既可指向其它类型的结构体数据，也可以指向自己所在的结构体类型的数据9910189.599103909910785numScorenextnext是structstudent类型中的一个成员，它又指向structstudent类型的数据。换名话说：next存放下一个结点的地址3011.7.2简单链表#defineNULL0structstudent{longnum;floatscore;structstudent*next;};main(){structstudenta,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;

a.next=&b;b.next=&c;

c.next=NULL;p=head;

do{printf("%ld%5.1f\n",p->num,p->score);

p=p->next;}while(p!=NULL);}例11.7建立和输出一个简单链表各结点在程序中定义，不是临时开辟的，始终占有内容不放，这种链表称为“静态链表”3111.7.3处理动态链表所需的函数C语言使用系统函数动态开辟和释放存储单元1.malloc函数

函数原形：void*malloc(unsignedintsize);作用：在内存的动态存储区中分配一个

长度为size的连续空间。返回值：是一个指向分配域起始地址的指针（基本类型void）。执行失败：返回NULL32函数原形:void*calloc(unsignedn,unsignedsize);作用：在内存动态区中分配n个

长度为size的连续空间。函数返回值：指向分配域起始地址的指针执行失败：返回null主要用途：为一维数组开辟动态存储空间。n

为数组元素个数，每个元素长度为size2.calloc

函数333.free函数函数原形：

voidfree(void*p);作用：释放由p指向的内存区。P:是最近一次调用calloc或malloc函数时返回的值。free函数无返回值动态分配的存储单元在用完后一定要释放，否则内存会因申请空间过多引起资源不足而出现故障。34结点的动态分配ANSIC的三个函数(头文件malloc.h)void*malloc(unsignedintsize)void*calloc(unsignedn,unsignedsize)voidfree(void*p)C++的两个函数new类型（初值）delete[]指针变量

/*[]表示释放数组，可有可无）*/使用new的优点：可以通过对象的大小直接分配，而不管对象的具体长度是多少（p340例14.10）35建立动态链表基本方法:

三个结点（头结点head、尾结点NULL和待插入结点P）第一步：定义头结点head、尾结点

p2

和待插入结点p1，待插入的结点数据部分初始化；第二步：该结点被头结点、尾结点同时指向。P1=p2=(structstudent*)malloc(LEN);头指针部分为空，head=NULL;

第三步：重复申请待插入结点空间，对该结点的数据部分赋值（或输入值），将该结点插入在最前面，或者最后面（书上在尾部插入）.

P2->next=P1;P2=P1;

最后:P2->next=NULL;*head,*p1,*p2使用malloc(LEN)P2->next=NULL;36建立动态链表9910189.5headP1p21.任务是开辟结点和输入数据2.并建立前后相链的关系待插入的结点p1数据部分初始化,该结点被头结点head、尾结点p2同时指向.37图11.149910189.5headp29910390p19910189.5headp29910390p1(a)(b)p1重复申请待插入结点空间，对该结点的数据部分赋值（或输入值）P2->next指向p1新开辟的结点。38图11.14head9910189.5p1p29910390(c)P2指向新结点p2=p139图11.159910189.59910189.5p29910785p1head9910189.59910189.5p29910785p1head(a)(b)40

图11.16 99103909910785p200p1head9910189.599103909910785NULLp200p1head9910189.541例11.8建立一个有3名学生数据的单向动态链表#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum;floatscore;structstudent*next;};intn;structstudent*creat(void){structstudent*head;structstudent*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);scanf("%1d,%f",&p1->num,&p1->score);head=NULL;结构体类型数据的长度，sizeof是“字节数运算符”定义指针类型的函数。带回链表的起始地址开辟长度为LEN的内存区P1,p2是指向结构体类型数据的指针变量，强行转换成结构体类型假设头指向空结点42续while(p1->num!=0){n=n+1;/*n是结点的个数*/if(n==1)head=p1;elsep2->next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf("%1d,%f",&p1->num,&p1->score);}p2->next=NULL;return(head);}//返回链表的头指针算法：p1指向新开的结点:p1=(stuctstudent*)malloc(LEN);p1的所指向的结点连接在p2所指向结点后面，用p2->next=p1来实现。p2指向链表中最后建立的结点，:p2=p1;

头指针指向p1结点P1开辟的新结点链到了p2的后面P1继续开辟新结点给新结点赋值此43输出链表链表遍历1.单向链表总是从头结点开始的；2.每访问一个结点，就将当前指针向该结点的下一个结点移动：

p=p->next;3.直至下一结点为空

P=NULL44图11.18headp

P’P’NULL45例题9voidprint(structstudent*head){structstudent*p;printf("\nNow,These%drecordsare:\n",n);

p=head;if(head!=NULL)do{printf("%ld%5.lf\n",p->num,p->score);

p=p->next;}while(p!=NULL);}46对链表的删除操作删除结点原则：不改变原来的排列顺序，只是从链表中分离开来，撤消原来的链接关系。两种情况：1、要删的结点是头指针所指的结点则直接操作；2、不是头结点，要依次往下找。另外要考虑：空表和找不到要删除的结点47链表中结点删除需要由两个临时指针：P1:判断指向的结点是不是要删除的结点（用于寻找）；P2:始终指向P1的前面一个结点；48图11.19ABDECABDEC(a)(B)49图11.2099101headp19910399107NULL（a）(b)99101head9910399107NULLp2p1原链表P1指向头结点P2指向p1指向的结点。P1指向下移一个结点。50图11.2099101head9910399107NULLp199101head9910399107NULLp2p1(c)(d)经判断后，第1个结点是要删除的结点，head指向第2个结点，第1个结点脱离。经P1找到要删除的结点后使之脱离。51例题10structstudent*del(structstudent*head,longnum){structstudent*p1,*p2;if(head==NULL){printf("\nlistnull!\n");gotoend;}p1=head;while(num!=p1->num&&p1->next!==NULL){p2=p1;p1=p1->next;}

if(num==p1->num)

{if(p1==head)head=p1->next;elsep2->next=p1->next;printf("delete:%ld\n",num);n=n-1;}elseprintf("%ldnotbeenfound!\n",num);

end:return(head);}找到了没找到52对链表的插入操作插入结点：将一个结点插入到已有的链表中插入原则：1、插入操作不应破坏原链接关系2、插入的结点应该在它该在的位置实现方法：应该有一个插入位置的查找子过程共有三种情况：1、插入的结最小2、插入的结点最大3、插入的结在中间53

操作分析同删除一样，需要几个临时指针：P0:指向待插的结点;初始化：p0=数组stu;P1:指向要在P1之前插入结点；初始化:p1=head;P2:指向要在P2之后插入结点；插入操作：当符合以下条件时：p0->num与p1->num比较找位置if(p0->num>p1->num)&&(p1->next!=NULL)

则插入的结点不在p1所指结点之前；指针后移，交给p2；

p1=p1->next;p2=p1;则继续与

p0

指向的数组去比，直到（p1->next!=NULL)为止。

否则有两种情况发生：

if(head==p1)head=p0;p0->next=p1插到原来第一个结点之前；elsep2->next=p0;p0->next=p1;

插到p2指向的结点之后；还有另外一种情况：插到最后的结点之后；p1->next=p0;p0->next=NULL;54图11.2299101headp19910399107NULL（a）99102p055图11.2299101head9910399107NULL99102p0p2p1(b)56例题11structstudentinsert(structstudent*head,struct

student*stud){structstudent*p0,*p1,*p2;p1=head;p0=stud;if(head==NULL;){head=p0;p0->next=NULL;}elsewhile((p0->num>p1->num)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p0->num<=p1->num) {if(head==p1)head=p0; elsep2->next=p0;p0->next=p1;}else{p1->next=p0;p0->next=NULL;}n=n+1;return(head);}原来的链表是空表P0指向要插的结点使p0指向的结点作为头结点使p2指向刚才p1指向的结点插到原来第一个结点之前插到p2指向的结点之后插到最后的结点之后链接575head61015null128课堂举例：已有一个如图所示的链表；它是按结点中的整数域从小到大排序的，现在要插入一个结点，该结点中的数为10待插入结点此结点已插入链表58分析：按三种情况1、第一种情况，链表还未建成（空链表），待插入结点p实际上是第一个结点。这时必然有head==null。只要让头指针指向p

就可以了。语句为6nullheadphead=p;p->next=null;2、第二种情况，链表已建成，待插入结点p

的数据要比头结点的数据还要小，这时有

(p->num)<(head->num)当然p结点要插在head结点前。596head8512nullheadpp->next=head;head=p;语句为null603、第三种情况，链表已建成，待插入结点p的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r和g，利用循环比较来找到正确位置。然后将结点p

插入到链表中正确的位置。 参见下面的图示616head81213nullp15gr说明：这种情况下，p结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。13>8，继续比较。626head81213nullp15gr说明：13>12，继续比较。636head81213p15grnull说明：13<15，找到了正确的插入位置，则插入结点p;语句为：r>next=p;p->next=g;64//结构7.c#include<stdio.h> //预编译命令#include<malloc.h> //内存空间分配#definenull0 //定义空指针常量#defineLENsizeof(structnumST) //定义常量，表示结构长度structnumST //结构声明{ intnum; //整型数 structnumST*next; //numST结构指针};参考程序65//被调用函数insert()，两个形参分别表示链表和待插入的结点voidinsert(structnumST**phead,structnumST*p){ //函数体开始

structnumST*q,*r; //定义结构指针q,r if((*phead)==null) //第一种情况，链表为空

{ *phead=p; //链表头指向p return; //完成插入操作，返回

}

else //链表不为空 {

//第二种情况，p结点num值小于链表头结点的num值 if((*phead)->num>p->num) {

//将p结点插到链表头部

p->next=*phead;//将p的next指针指向链表头(*phead)

*phead=p;

//将链表头赋值为p

return;

//返回 }6