用指针处理链表

1、链表概述链表概述 链表是一种链表是一种动态动态地进行存储分配的地进行存储分配的数据结构数据结构，用数组存放数据时，必须，用数组存放数据时，必须申请一块申请一块连续空间连续空间，若元素有，若元素有100个，则必须申请长度为个，则必须申请长度为100个元素的数组，个元素的数组，若数组元素个数不定，则需要定义足够大的数组长度，这势必浪费内存。而若数组元素个数不定，则需要定义足够大的数组长度，这势必浪费内存。而 用链表可以根据需要来开辟内存单元。用链表可以根据需要来开辟内存单元。 一种简单的链表结构图示如下一种简单的链表结构图示如下 : 链表有一个链表有一个头指针变量头指针变量head，指向第一个元素

2、指向第一个元素(表头表头)。 链表中的每一个元素称为链表中的每一个元素称为结点。结点。 一个结点包括两个部分一个结点包括两个部分: 实际数据实际数据 下一个下一个同类型同类型结点的地址结点的地址。 链表有一个链表有一个表尾表尾，该元素不再指向其它元素，它的地址部分存放一，该元素不再指向其它元素，它的地址部分存放一个个空地址空地址(NULL)， ( NULL 是一个符号常量，是一个符号常量，代表整数代表整数 0， 指针变量指针变量等于等于0(NULL) 表示一个表示一个空指针空指针 )。 A1356headB1475C1021DNULL1249 1356 1475 10211249用指针处理链表

3、用指针处理链表可见可见: 链表中的各元素链表中的各元素 在内存中可以在内存中可以不连续存放。不连续存放。整个链表的访问，整个链表的访问，必须从表头指针开始必须从表头指针开始，根据上一个元素所提供的，根据上一个元素所提供的地址找到下一个元素。地址找到下一个元素。1.链表的数据结构链表的数据结构必须利用指针变量必须利用指针变量才能实现，一个结点中除了包含才能实现，一个结点中除了包含 数据变量外，还应包含一个指针变量，用来存放下一结点的地址。数据变量外，还应包含一个指针变量，用来存放下一结点的地址。因此，前面介绍的因此，前面介绍的结构体类型用作链表中的结点结构体类型用作链表中的结点是最合适的：是最合

4、适的： 例如，例如， 要建立一个链表，首先要定义结点的类型要建立一个链表，首先要定义结点的类型 ：struct student int num; float score ; struct student *next; /* next 是指针变量，指向下一个结点是指针变量，指向下一个结点*/ ；数据数据指针指针指向下一个结点指向下一个结点89.59910190991038599107nextscorenum#define NULL 0struct student long int num ;float score ;struct student *next ; ;/* 声明一个结构体声明一个结构

5、体 */ 建立链表是指从无到有地建立起一个链表建立链表是指从无到有地建立起一个链表，包括一个一个地输入各，包括一个一个地输入各结点数据结点数据, 并建立起前后相链的关系。并建立起前后相链的关系。例例11.7 建立如下图所示的链表，它由建立如下图所示的链表，它由3各学生数据的结点组成。各学生数据的结点组成。 建立简单链表建立简单链表 a b cnumnextscore &b &c NULL 89.5 90.0 85.0 99101 99103 99107main( ) /* a,b,c 是结构变量，是结构变量，head 和和 p是指针是指针 */ struct student a, b, c ,

6、 *head , *p ; a. num=99101 ; a. score=89.5 ; b. num=99103 ; b. score=90.0 ; c. num=99107 ; c . score=85.0 ; a. next=&b ; b. next=&c ; c. next=NULL ; p=head=&a ; while( p !=NULL) printf(%ld %5.1f n , p-num , p-score) ; p=p-next ; /* 建立链表建立链表 */* 输出各结点内容输出各结点内容 */ a b cnumnextscore &b &c NULL 89.5 90.

7、0 85.0 99101 99103 99107/* 结点赋值结点赋值 */ 链表是动态地分配存储的，链表是动态地分配存储的，C语言中提供了语言中提供了动态地开辟和释放存储单动态地开辟和释放存储单元的库函数元的库函数（其信息包含在（其信息包含在 malloc.h 文件中）。文件中）。1. malloc 函数函数 函数原型为：函数原型为： void *malloc(unsigned int size) ; 其作用是：在内存的动态存储区中分配一个长度为其作用是：在内存的动态存储区中分配一个长度为size的连续空间。的连续空间。此此 函数的值（即返回值）是一个指向函数的值（即返回值）是一个指向该分配

8、域起始地址该分配域起始地址的指针（基类型为的指针（基类型为 void）。如果函数未能成功地执行，则返回值为）。如果函数未能成功地执行，则返回值为NULL。 处理处理动态链表动态链表所需的函数所需的函数2. calloc函数函数 函数原型为：函数原型为： void * calloc(unsigned n, unsigned size) ; 其作用是：在内存的动态存储区中分配其作用是：在内存的动态存储区中分配 n 个长度为个长度为 size 的连续空间。的连续空间。 函数返回一个函数返回一个 指向该分配指向该分配空间的起始地址的指针；空间的起始地址的指针； 如果函数不能成功执如果函数不能成功执行行

9、,则返回值为则返回值为NULL。链表的操作包括：链表的操作包括： 建立链表、插入或建立链表、插入或 删除链表中的一个结点等。删除链表中的一个结点等。建立动态链表建立动态链表例例 写一个函数，建立有三个学生数据的单向动态链表。写一个函数，建立有三个学生数据的单向动态链表。head num score *next 1 2 3 NULL3. free 函数函数 函数原型为：函数原型为：void free(void *ptr) 作用是：释放由作用是：释放由 ptr 所指向的内存区，所指向的内存区， ptr 是最近一次调用是最近一次调用malloc 或或 calloc 函数函数 时返回的地址。时返回的地

10、址。free 函数无返回值。函数无返回值。注意：以前注意：以前C版本提供的版本提供的malloc 和和 calloc 函数得到的是指向字符型函数得到的是指向字符型数据的指针。数据的指针。ANSI C 规定为规定为 void * 类型。类型。步骤步骤:1. 定义结点类型（结构体类型）：定义结点类型（结构体类型）： struct student2. 定义指向结点的指针变量定义指向结点的指针变量 head, p1, p2： head 指向表头，指向表头，p1 指向指向当前当前新建立的结点新建立的结点， p2 指向链表中最后一个结点指向链表中最后一个结点；3. 新建一个结点新建一个结点 （开辟内存单元

11、，（开辟内存单元， 输入学号和成绩输入学号和成绩 数据）；数据）；4. 建立表头建立表头5. 建立链表建立链表 如果新结点是第一个结点，如果新结点是第一个结点，则表头则表头 head 指向该结点指向该结点， 否则该结点链否则该结点链入链表，并让入链表，并让 p2 指向新链入的这个结点，重复指向新链入的这个结点，重复3、 5； 如果是第如果是第3个结点，则个结点，则让让 p1 所指的结点中的指向下一个结点的指针为所指的结点中的指向下一个结点的指针为空指针空指针NULL，链表建立结束。，链表建立结束。head num score *next 1 p1 1 23head num score *nex

12、tp2p1*nextNULL#include #define NULL 0struct student long num; float score; struct student *next; ; void main( ) struct student *head , *p1 , *p2 ; int n ; head=NULL ; for(n=1 ; n num , &p1 - score) ;if(head = NULL) head=p1 ;else p2-next=p1 ;p2=p1 ; p1-next=NULL ; free(p1) ; /* 释放结点空间释放结点空间*/ return

13、;三次动态三次动态申请空间申请空间定义结点的数据结构定义结点的数据结构 现在，我们用一个现在，我们用一个函数函数来建立一个有来建立一个有若干若干个学生的学号和成绩数据的个学生的学号和成绩数据的单向链表（假设输入学号为单向链表（假设输入学号为 0 时结束）。时结束）。步骤步骤:1. 定义结点类型（结构体类型）：定义结点类型（结构体类型）： struct student2. 定义指向结点的指针变量定义指向结点的指针变量 head, p1, p2； head 指向表头，指向表头，p1 指向指向当前当前新建立的结点新建立的结点，p2 指向表中最后一个结点指向表中最后一个结点。 把把p1所指的结点连接在

14、所指的结点连接在p2所指的结点后面，用所指的结点后面，用“p2-next=p1; ”来实现来实现。3. 新建一个结点新建一个结点 （开辟内存单元、输入学号、成绩等数据）；（开辟内存单元、输入学号、成绩等数据）；4. 建立表头建立表头 （head=NULL;）5. 建立链表建立链表 如果新结点是第一个结点，如果新结点是第一个结点，则表头则表头 head 指向该结点指向该结点， 否则该结点否则该结点链入链表，并让链入链表，并让 p2 指向新链入的这个结点，重复指向新链入的这个结点，重复 3、5； 如果输入学号为如果输入学号为0，则该结点不链入链表，前一个结点是表尾，即，则该结点不链入链表，前一个结

15、点是表尾，即让让 p2 所指的结点中的指向下一个结点的指针为空指针所指的结点中的指向下一个结点的指针为空指针NULL（p2 - next=NULL;），链表建立结束。），链表建立结束。int n; /* 全局变量全局变量 n 统计结点数统计结点数 ，本模块中各函数，本模块中各函数 均可使用它均可使用它*/struct student * creat (void) /* 定义函数定义函数 。此函数带回一个。此函数带回一个指向链表头的指针指向链表头的指针*/ struct student *head, *p1 , *p2 ; head=NULL; n=0; p1= (struct student

16、*) malloc (sizeof (struct student) ; /* 开辟内存单元准备建立第一个结点开辟内存单元准备建立第一个结点 */ scanf(%ld , %f, &p1-num , &p1-score) ; while ( p1-num != 0) n+; if (head= NULL) head=p1; /* head 指向第一个结点指向第一个结点 */ else p2-next=p1 ; /* 将新结点将新结点 p1 链入链表链入链表 */ p2=p1 ; /* 保保留当前留当前结点的地址结点的地址 */ p1=(struct student *) malloc(size

17、of (struct student) ; scanf(%ld,%f, &p1-num , &p1-score) ; p2 - next=NULL ; free(p1) ; return (head);p2p1输出链表输出链表 将链表中各个结点的数据依次输出。将链表中各个结点的数据依次输出。 首先要知道链表表头首先要知道链表表头head的地的地址，再定义一个指向结点的指针变量址，再定义一个指向结点的指针变量 p ，使，使p先指向第一个结点，输出先指向第一个结点，输出该该 结点的数据，然后让结点的数据，然后让 p 指向下一个结点，再输出，直到表尾为止。指向下一个结点，再输出，直到表尾为止。 例例

18、11.9 编写一个输出链表的函数编写一个输出链表的函数print。void print(struct student *head) struct student *p; printf(n输出输出结点结点数据数据 :n) ; p=head; if(head!=NULL) /* 如果不是空链表，则输出如果不是空链表，则输出 */ do printf(%ld %fn, p-num , p-score) ; p=p-next ; /* 使使 p 指向下一个结点指向下一个结点 */ while( p!=NULL) ;可以在可以在main 函数中调用函数中调用 creat 函数：函数：main( ) cr

19、eat( ); 调用调用creat 函数后建立函数后建立一个单向动态链表一个单向动态链表 从一个动态链表中删除一个结点，并不是真正从内存中把它抹掉，而是从一个动态链表中删除一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离出来，只要改变原来的连接关系即可，即让该结点的前一把它从链表中分离出来，只要改变原来的连接关系即可，即让该结点的前一个结点直接指向该结点的下一个结点。个结点直接指向该结点的下一个结点。注意注意: 如果如果删除的是第一个结点删除的是第一个结点，则要修改表头，则要修改表头 head。 如果链表是空表（无结点）或表中找不到要删除的结点如果链表是空表（无结点）或表中找不到要删

20、除的结点 , 不删除。不删除。p2. . .p1 删除删除headp1 删除一个结点删除一个结点进行操作：进行操作：head = p1-next ;用函数来删除一个指定的结点，方法如下：用函数来删除一个指定的结点，方法如下：1. 用一个指向结点的指针变量，从表头开始用一个指向结点的指针变量，从表头开始查找查找需要删除的结点。需要删除的结点。2. 定义两个指针变量定义两个指针变量 p1 和和 p2 ，其中：，其中： p1 指向要删除的结点，指向要删除的结点，p2 是指向是指向 p1前面的一个结点。前面的一个结点。要删除要删除 p1，使，使p2-next = p1-next ; 就从链表中删除了就

21、从链表中删除了p1 所指的结点。所指的结点。struct student *del (struct student *head, long num) struct student *p1,*p2; if (head = NULL) printf(空链表空链表n) ; goto end; p1=head; while( p1 - num != num & p1-next != NULL) p2=p1; p1=p1-next ; /* 后移一个结点后移一个结点, 继续查找继续查找 */ if( p1 - num = num) /* 找到找到 */ if ( p1 = head) /* 如果删除第一

22、个结点如果删除第一个结点, 则修改表头则修改表头 */ head=p1-next; else p2-next=p1-next; /* 删除结点删除结点(包含删除表尾结点包含删除表尾结点)*/ printf(delete: %ldn, num); n=n-1; else printf ( 没找到没找到!n ); /* 没找到没找到 */ end: return (head) ;例例 写一个函数以删除动态链表中指定的结点。写一个函数以删除动态链表中指定的结点。当没找到而且还不是表尾当没找到而且还不是表尾 对链表的对链表的插入插入是指将一个结点是指将一个结点按某种规律按某种规律 插入到已有的链表中。

23、插入到已有的链表中。 要正确插入结点，必须解决两个问题：要正确插入结点，必须解决两个问题：怎样找到插入的位置；怎样实现插入。怎样找到插入的位置；怎样实现插入。 我们可以用函数来实现插入一个结点，其中：我们可以用函数来实现插入一个结点，其中： 用指针变量用指针变量 p0 指向待插入的结点，用指针变量指向待插入的结点，用指针变量 p1 和和 p2 来找到需来找到需要插入的位置，使得结点要插入的位置，使得结点 p0 插在插在 p1 之前之前 p2 之后。之后。 插入结点插入结点p2. . .p2-nextp1-nextp1p0p2-nextp0-next插入插入进行以下操作进行以下操作： p0-ne

24、xt =p2-next ; p2-next= p0 ; NULLp1p0NULL插在表尾插在表尾headp0p1插在表头插在表头 注意：插入位置在表头和表尾时的情况。注意：插入位置在表头和表尾时的情况。 p1-next=p0; p0-next=NULL; head = p0;p0-next = p1;例例 插入结点的函数插入结点的函数insert。/* 将将stud所指结点插到所指结点插到已排序已排序的链表中的链表中 */struct student *insert(struct student * head, struct student *stud ） struct student *p0

25、,*p1,*p2; p0=stud; p1=head; if(head=NULL) /* 如果是空表如果是空表 ，作为第一个结点插入，作为第一个结点插入 */ head=p0; p0-next=NULL; else /* 不是空表不是空表 ，找找插入位置插入位置 */while (p0-num p1-num) & (p1-next != NULL) ) p2=p1; /* p2 保保留留p1 之前结点的地址之前结点的地址 */ p1=p1-next; if (p0-num num) if (head = p1) head = p0; /* 插在第一个结点之前插在第一个结点之前 , 更新表头更新

26、表头 */ else p2-next = p0; /* p0 插在插在 p1 之前，之前，p2之后之后 */ p0-next = p1; else p1-next=p0; p0-next=NULL; /* p0插在表尾插在表尾*/ n=n+1; return(head); 将以上建立、输出、删除、插入的函数组织在一个将以上建立、输出、删除、插入的函数组织在一个C程序中，可以程序中，可以实现建立链表、删除结点、插入结点、输出结点的操作。实现建立链表、删除结点、插入结点、输出结点的操作。 链表的综合操作链表的综合操作void main( void) struct student *head ,*s

27、tu; long del_num; printf(Input records:n) ; head=creat( ) ; print (head); printf(nInput the deleted number:) ; scanf(%ld” , &del_num) ; head=del (head, del_num) ; print(head); printf(n Input the inserted record:); stu=(struct student *)malloc(sizeof(struct student); scanf(%ld ,%f, stu-num , stu-scor

28、e) ; head=insert (head, &stu) ; print(head);#include #define NULL 0struct student long num; float score; struct student *next; ; int n; /*结点个数结点个数*/ 1. 填空填空 (1)写出建立如图所示的存储结构所需的类型说明和定义语句。写出建立如图所示的存储结构所需的类型说明和定义语句。struct A (1) i d ;(2) data ;(3) ;p i d data 10 A 习习 题题 (2).写出建立如图所示的存储结构所需的动态申请空间的语句和写出建

29、立如图所示的存储结构所需的动态申请空间的语句和赋值语句。赋值语句。p=(4) malloc (5) ;(6)=10 ; (7)= A ; (3).写出输出结果。写出输出结果。printf(%d,%cn , (8) , (9) ;2. 填空填空 (1)写出建立如图所示的存储结构所需的类型说明和定义语句写出建立如图所示的存储结构所需的类型说明和定义语句struct link (1) data ;(2) next ;(3) ; (2)写出建立如图所示的存储结构所需的动态申请空间的语句和赋值语句写出建立如图所示的存储结构所需的动态申请空间的语句和赋值语句head=(4) ;(5)=10 ; (6)=NULL ; (3)写出输出结果写出输出结果printf(%dn , (7) ;head data next 10 NULL3. 写出以下程序运行结果写出以下程序运行结果 （1）struct pen int x ;double y ; ; main( ) struct pen d=3 , 1.23 ; count( &d) ; void count(struct pen *p) double z ; z=p-x * p