(x6,y6)
(x7,y7)
为了表示这种既有数据又有指针的情况， 引入结构这种数据类型。
精选课件
3
11.7 用指针处理链表
链表是程序设计中一种重要的动态数据结构， 它是动态地进行存储分配的一种结构。
动态性体现为：
链表中的元素个数可以根据需要增加和减少，不 像数组，在声明之后就固定不变；
元素的位置可以变化，即可以从某个位置删除， 然后再插入到一个新的地方；
精选课件
7
（4）删除操作是指，删除结点ki，使线性表的长度 减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变 化：
删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1 成为ki+1的前驱，ki+1成为ki-1的后继.
(5)打印输出
精选课件
8
一个指针类型的成员既可指向其它类型的结构体 数据，也可以指向自己所在的结构体类型的数据
10
11.7.3 处理动态链表所需的函数
C 语言使用系统函数动态开辟和释放存储单元
1.malloc 函数
函数原形：void *malloc(unsigned int size); 作用：在内存的动态存储区中分配 一个 长度为size 的连续空间。 返回值：是一个指向分配域起始地址的指针（基本 类型void）。 执行失败：返回NULL
精选课件
4
结点里的指针是存放下一个结点的地址
Head
1249
1249
A 1356
1356
B 1475
1475
C 1021
1021
D Null
1、链表中的元素称为“结点”，每个结点包括两 个域：数据域和指针域；
2、单向链表通常由一个头指针（head)，用于指向 链表头；
3、单向链表有一个尾结点，该结点的指针部分指
第二步：该结点被头结点、尾结点同时指向。 P1=p2=(struct student*)m使a用llmoacl(lLocE(NL)E;N头) 指针部分为 空，head=NULL;
第三步：重复申请待插入结点空间，对该结点的数据部 分赋值（或输入值），将该结点插入在最前面，或者最 后面（书上在尾部插入）.
{ long num; float score;
建
struct student *next; };
立
main()
和
{ struct student a, b, c, *head, *p;
输
ab..nnuumm==9999110013;;ab.s.sccoorree==8990.5;;各 始结终点占在有程内序容中不定放义，，这不种是链临表时称开为辟“的静，出 一
精选课件
11
2. calloc 函数
函数原形:void *calloc(unsigned n,unsigned size); 作用：在内存动态区中分配 n个 长度为size的
连续空间。 函数返回值：指向分配域起始地址的指针 执行失败：返回null 主要用途：为一维数组开辟动态存储空间。n 为
数组元素个数，每个元素长度为size
（2）检索操作是指，按给定的结点索引号或检索 条件，查找某个结点。如果找到指定的结点， 则称为检索成功；否则，称为检索失败。
（新3）的插结入点操k作’，是使指线，性在表结的点长k度i-1增与1k，i之且间k插i-1入与一ki个的 逻辑关系发生如下变化：
插新入插前入，的ki-结1是点kki的’成前为驱ki，-1的ki后是继ki-、1的ki后的继前；驱插. 入后，
13
结点的动态分配
ANSI C 的三个函数(头文件 malloc.h) void *malloc(unsigned int size)
void *calloc(unsigned n, unsigned size)
void free(void *p) C++ 的两个函数
new 类型（初值） delete [ ] 指针变量
第十一章 链表
精选课件
1
结构的概念与应用
例：跳马。依下图将每一步跳马之后的位置(x,y)放 到一个“结点”里，再用“链子穿起来”，形成 一条链，相邻两结点间用一个指针将两者连到一 起。
3 4
5 7
3
2
4
2
6
1
结 点 1 0 1 2 3 精选课4件 5
678
2
依上图有7个结点
(x1,y1) (x2,y2)
精选课件
12
3. free 函数
函数原形： void free(void *p);
作用：释放由 p 指向的内存区。
P:是最近一次调用 calloc 或 malloc 函数 时返回的值。
free 函数无返回值
动态分配的存储单元在用完后一定要释放， 否则内存会因申请空间过多引起资源不足 而出现故障。
精选课件
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); 精}选课件
/*[ ] 表示释放数组，可有可无）*/ 使用 new 的优点：
可以通过对象的大小直接分配，而不管对象 的具体长度是多少（p340 例14.10）
精选课件
14
11.7.4 建立动态链表
基本方法:
三个结点（头结点head、尾结点 NULL 和待插入结点 P）
第一步：定义头结点hea*dh、ea尾d,结*p1点,*pp22 和待插入结点p1， 待插入的结点数据部分初始化；
num Score next
99101 89.5
99103 90
99107 85
next是struct student类型中的一个成员， 它又指向struct student类型的数据。
换名话说：next存放下一个结点的地址
精选课件
9
11.7.2 简单链表
例11.7
#define NULL 0
struct student
向一个空结点(NULL) 。 精选课件
5
链表中结点的定义
链表是由结点构义打破了先定义再使用的限制, 即可以用自己定义自己；
递归函数的定义也违反了先定义再使用；
这是C语言程序设计上的两大特例
精选课件
6
链表的基本操作
对链表的基本操作有：
（1）创建链表是指，从无到有地建立起一个链表， 即往空链表中依次插入若干结点，并保持结点 之间的前驱和后继关系。