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

程序设计与实践C,第4集指针与链表,地址和指针的概念,内存区的每一个字节有一个编号，这就是“地址” 。如果在程序中定义了一个变量，在对程序进行编译时，系统就会给这个变量分配内存单元。,、按变量地址存取变量值的方式称为“直接访问”方式 （，）； （，）； ；,2. 另一种存取变量值的方式称为“间接访问”的方式。即，将变量的地址存放在另一个变量中。,在语言中，指针是一种特殊的变量，它是存放地址的。,一个变量的地址称为该变量的“指针”。例如，地址2000是变量的指针。如果有一个变量专门用来存放另一变量的地址（即指针），则它称为“指针变量”。上述的i_pointer就是一个指针变量。,指针和指针变量的定义：,变量的指针和指向变量的指针变量,怎样定义指针变量,定义指针变量的一般形式为基类型 *指针变量名；,下面都是合法的定义：float *pointer_； char *pointer_； 可以用赋值语句使一个指针变量得到另一个变量的地址，从而使它指向一个该变量。例如：pointer_；pointer_；,在定义指针变量时要注意两点：,在对指针变量赋值时需要注意两点：, 指针变量中只能存放地址（指针），不要将一个整数赋给一个指针变量。 例: pointer_1； /* pointer_1是指针变量,是整数，不合法 */ (2) 赋给指针变量的是变量地址不能是任意的类型，而只能是与指针变量的基类型具有相同类型的变量的地址。,在引用指针变量时，可能有三种情况：给指针变量赋值。如： p=引用指针变量指向的变量。有关的两个运算符： 取地址运算符。 &a是变量a的地址。 * 指针运算符 （或称“间接访问”运算符），*p是指针变量p指向的对象的值。,怎样引用指针变量,例10. 通过指针变量访问整型变量,#include voidmain ( ) 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原来指向a0，执行+p后p的值改变了，在p的原值基础上加d，这样p就指向数组的下一个元素a1。(3) 如果的初值为，则和就是数组元素的地址，或者说，它们指向数组的第个元素 。*（）或*（）是或所指向的数组元素，即。 (5) 如果指针变量p1和p2都指向同一数组，如执行p2-p1，结果是两个地址之差除以数组元素的长度。,通过指针引用数组元素,引用一个数组元素，可以用：（） 下标法，如形式；（） 指针法，如*（）或*（）。其中是数组名，是指向数组元素的指针变量，其初值。,例10.5 输出数组中的全部元素,假设有一个数组，整型，有个元素。要输出各元素的值有三种方法：,(1)下标法#include void main（） int ； int；for（；）scanf（，）； printf（）；for（；）printf（，）； ,(2) 通过数组名计算数组元素地址，找出元素的值。#include voidmain（） int ； int ；for（； ）scanf（，）；printf（）； for（；） printf（，*（）； ,(3) 用指针变量指向数组元素。#include void main（） int ； int *，； for（；） scanf（，）； printf（）； for（；（）；） printf（ ，*）； ,22,例：跳马。依下图将每一步跳马之后的位置(x,y)放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。,结构的概念与应用,23,依上图有7个结点,为了表示这种既有数据又有指针的情况，引入结构这种数据类型。,24,用指针处理链表,链表是程序设计中一种重要的动态数据结构，它是动态地进行存储分配的一种结构。,动态性体现为：链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；元素的位置可以变化，即可以从某个位置删除，然后再插入到一个新的地方；,25,1、链表中的元素称为“结点”，每个结点包括两个域：数据域和指针域；2、单向链表通常由一个头指针（head)，用于指向链表头；3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL) 。,Head 1249 1356 1475 1021,结点里的指针是存放下一个结点的地址,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,一个指针类型的成员既可指向其它类型的结构体数据，也可以指向自己所在的结构体类型的数据,numScorenext,next是struct student类型中的一个成员，它又指向struct student类型的数据。换名话说：next存放下一个结点的地址,30,11.7.2 简单链表,#define NULL 0struct student long num; float score; struct student *next; ;main() struct student a, b, c, *head, *p; a.num=99101; a.score=89.5; b. num=99103; b.score=90; c.num=99107 ; c.score=85; head= ,例11.7,建立和输出一个简单链表,各结点在程序中定义，不是临时开辟的，始终占有内容不放，这种链表称为“静态链表”,31,11.7.3 处理动态链表所需的函数,C 语言使用系统函数动态开辟和释放存储单元,1.malloc 函数,函数原形：void *malloc(unsigned int size);作用：在内存的动态存储区中分配 一个 长度为size的连续空间。返回值：是一个指向分配域起始地址的指针（基本类型void）。执行失败：返回NULL,32,函数原形:void *calloc(unsigned n,unsigned size);作用：在内存动态区中分配 n个 长度为size的连续空间。函数返回值：指向分配域起始地址的指针执行失败：返回null主要用途：为一维数组开辟动态存储空间。n 为数组元素个数，每个元素长度为size,2. calloc 函数,33,3. free 函数,函数原形： void free(void *p);作用：释放由 p 指向的内存区。P:是最近一次调用 calloc 或 malloc 函数时返回的值。free 函数无返回值动态分配的存储单元在用完后一定要释放，否则内存会因申请空间过多引起资源不足而出现故障。,34,结点的动态分配,ANSI C 的三个函数(头文件 malloc.h) void *malloc(unsigned int size)void *calloc(unsigned n, unsigned size)void free(void *p)C+ 的两个函数new 类型（初值） delete 指针变量 /* 表示释放数组，可有可无）*/使用 new 的优点：可以通过对象的大小直接分配，而不管对象的具体长度是多少（p340 例14.10）,35,建立动态链表,基本方法: 三个结点（头结点head、尾结点 NULL 和待插入结点 P）第一步：定义头结点head、尾结点 p2 和待插入结点p1，待插入的结点数据部分初始化；第二步：该结点被头结点、尾结点同时指向。P1=p2=(struct student*)malloc(LEN);头指针部分为空，head=NULL; 第三步：重复申请待插入结点空间，对该结点的数据部分赋值（或输入值），将该结点插入在最前面，或者最后面（书上在尾部插入）. P2-next=P1; P2=P1; 最后:P2-next=NULL;,*head,*p1,*p2,使用malloc(LEN),P2-next=NULL;,36,建立动态链表,head,P1p2,1.任务是开辟结点和输入数据2.并建立前后相链的关系,待插入的结点p1数据部分初始化,该结点被头结点head、尾结点p2同时指向.,37,图11.14,head,p2,p1,head,p2,p1,(a),(b),p1重复申请待插入结点空间，对该结点的数据部分赋值（或输入值）,P2-next 指向p1新开辟的结点。,38,图11.14,head,p1,p2,(c),P2指向新结点p2=p1,39,图11.15,p2,p1,head,p2,p1,head,(a),(b),40,图11.16,p2,p1,head,p2,p1,head,41,例11.8 建立一个有3名学生数据的单向动态链表,#define NULL 0#define LEN sizeof(struct student)struct studentlong num; float score; struct student *next; ;int n;struct student *creat(void) struct student *head; struct student*p1,*p2; n=0; p1=p2=(struct student*) malloc(LEN); scanf(%1d,%f,结构体类型数据的长度，sizeof是“字节数运算符”,定义指针类型的函数。带回链表的起始地址,开辟长度为LEN的内存区,P1,p2是指向结构体类型数据的指针变量，强行转换成结构体类型,假设头指向空结点,42,续,while(p1-num!=0) n=n+1; /*n 是结点的个数*/ if(n=1)head=p1; else p2-next=p1; p2=p1; p1=(struct student*)malloc(LEN); scanf(%1d,%f, /返回链表的头指针,算法：p1指向新开的结点: p1=(stuct student*)malloc(LEN);p1的所指向的结点连接在p2所指向结点后面，用p2-next=p1来实现。p2 指向链表中最后建立的结点，: p2=p1;,头指针指向p1结点,P1开辟的新结点链到了p2的后面,P1继续开辟新结点,给新结点赋值此,43,输出链表,链表遍历1.单向链表总是从头结点开始的；2.每访问一个结点，就将当前指针向该结点的下一个结点移动： p=p-next;3.直至下一结点为空 P=NULL,44,图 11.18,head,p,P,P,45,例题 9,void print (struct student *head) struct student * p; printf(nNow,These %d records are:n,n); p=head; if(head!=NULL) do printf(%ld %5.lfn,p - num,p - score); p=p - next; while(p!=NULL); ,46,对链表的删除操作,删除结点原则：不改变原来的排列顺序，只是从链表中分离开来，撤消原来的链接关系。两种情况：1、要删的结点是头指针所指的结点则直接操作；2、不是头结点，要依次往下找。另外要考虑：空表和找不到要删除的结点,47,链表中结点删除,需要由两个临时指针：P1: 判断指向的结点是不是要删除的结点（用于寻找）；P2: 始终指向P1的前面一个结点；,48,图11.19,(a),(B),49,图11.20,head,p1,（a）,(b),head,p2,p1,原链表P1指向头结点,P2指向p1指向的结点。P1指向下移一个结点。,50,图11.20,head,p1,head,p2,p1,(c),(d),经判断后，第1个结点是要删除的结点，head指向第2个结点，第1个结点脱离。,经P1找到要删除的结点后使之脱离。,51,例 题 10,struct student *del( struct student *head, long num ) struct student *p1, *p2; if(head=NULL) printf(nlist null!n); goto end; p1=head; while(num!=p1-num ,找到了,没找到,52,对链表的插入操作,插入结点：将一个结点插入到已有的链表中插入原则：1、插入操作不应破坏原链接关系2、插入的结点应该在它该在的位置实现方法： 应该有一个插入位置的查找子过程共有三种情况：1、插入的结最小2、插入的结点最大3、插入的结在中间,53,操 作 分 析,同删除一样，需要几个临时指针：P0: 指向待插的结点;初始化：p0=数组stu;P1: 指向要在P1之前插入结点；初始化: p1=head;P2: 指向要在P2之后插入结点；插入操作：当符合以下条件时：p0-num 与 p1-num 比较找位置if(p0-nump1-num),54,图11.22,head,p1,（a）,p0,55,图11.22,p2,p1,(b),56,例 题 11,struct student insert(struct student *head,struct student *stud) struct student *p0,*p1,*p2; p1=head; p0=stud; if( head=NULL; ) head=p0;p0-next=NULL; else while( p0-nump1-num) ,原来的链表是空表,P0指向要插的结点,使p0指向的结点作为头结点,使p2指向刚才p1指向的结点,插到原来第一个结点之前,插到p2指向的结点之后,插到最后的结点之后,链接,57,head,课堂举例：已有一个如图所示的链表；它是按结点中的整数域从小到大排序的，现在要插入一个结点，该结点中的数为10,待插入结点,此结点已插入链表,58,分析：按三种情况1、第一种情况，链表还未建成（空链表），待插入结点p实际上是第一个结点。这时必然有head=null。只要让头指针指向 p 就可以了。语句为,headp,head = p;p-next = null;,2、第二种情况，链表已建成，待插入结点 p 的数据要比头结点的数据还要小，这时有(p-num )num)当然p结点要插在head结点前。,59,head,head,p,p-next=head;head=p;,语句为,null,60,3、第三种情况，链表已建成，待插入结点 p 的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r 和 g，利用循环比较来找到正确位置。然后将结点 p 插入到链表中正确的位置。参见下面的图示,61,head,p,g,r,说明：这种情况下，p 结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。138，继续比较。,62,head,p,g,r,说明：1312，继续比较。,63,head,p,g,r,null,说明：13next = p;p-next = g;,64,/ 结构7.c#include / 预编译命令#include / 内存空间分配#define null 0/ 定义空指针常量#define LEN sizeof(struct numST)/ 定义常量，表示结构长度struct numST/ 结构声明int num;/ 整型数struct numST *next;/ numST结构指针;,参考程序,65,/ 被调用函数insert()，两个形参分别表示链表和待插入的结点void insert (struct numST *phead, struct numST *p)/ 函数体开始struct numST *q,*r;/ 定义结构指针q,rif (*phead)=null)/ 第一种情况，链表为空*phead = p;/ 链表头指向preturn;/ 完成插入操作，返回else/ 链表不为空/ 第二种情况，p结点num值小于链表头结点的num值if ( (*phead)-num p-num) / 将p结点插到链表头部 p-next = *phead;/ 将p的next指针指向链表头(*phead) *phead = p;/ 将链表头赋值为p return;/ 返回,66,/ 第三种情况，循环查找正确位置r = *phead;/ r赋值为链表头q = (*phead)-next;/ q赋值为链表的下一个结点while (q!=null) / 利用循环查找正确位置/ 判断当前结点num是否小于p结点的numif (q-num