清华大学：《实用数据结构》课程教学资源（PPT课件）第三章 线性链表

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第3章线性链表 3.1线性链表的基本概念 3.2线性链表的基本运算 3.3循环链表 3.4多项式的表示与运算

第3章 线 性 链 表 3.1 线性链表的基本概念 3.2 线性链表的基本运算 3.3 循环链表 3.4 多项式的表示与运算

清华大学出版社 TSINGHUA UNIVERSITY PRESS 3.1线性链表的基本概念 3.1.1线性表顺序存储的问题 3.1.2线性链表 3.1.3带链的栈 3.1.4带链的队列

3.1 线性链表的基本概念 3.1.1 线性表顺序存储的问题 3.1.2 线性链表 3.1.3 带链的栈 3.1.4 带链的队列

清华大学出版社 TSINGHUA UNIVERSITY PRESS 3.1.1线性表顺序存储的问题 3.1.2线性链表 线性表的链式存储结构称为线性链表

3.1.1 线性表顺序存储的问题 3.1.2 线性链表 线性表的链式存储结构称为线性链表

清华大学出版社 TSINGHUA UNIVERSITY PRESS 存储序号 教据域 指针域 端性链表的存储空

清华大学出版社 TSINGHUA UNIVERSITY PRESS 存储序号数据域指针域 V〔i〕 HEIT ( 线性链表的一个存储结点

清华大学出版社 TSINGHUA UNIVERSITY PRESS 线性链表的逻结构 配→数:一→数 +数据n|IL

清华大学出版社 TSINGHUA UNIVERSITY PRESS (i) NexT(i) HEAD 123 10 56789 线性链表的物理状态 3 1 9 aa3→a子叶 线性链表的逻辑状态

清华大学出版社 TSINGHUA UNIVERSITY PRESS 依次输出线性链表中的各结点值 输入:线性链表的存储空间V(1:m)、NEXT(1:m); 线性链表的头指针HEAD 输出:依次输出线性链表中各结点的值。 PROCEDURE PRTLL (HEAD) HEAD WHILE(j≠0)DO I OUTPUT V(j; j=NEXT(j) RETURN

依次输出线性链表中的各结点值 输入：线性链表的存储空间V(1：m)、NEXT(1：m)； 线性链表的头指针HEAD。 输出：依次输出线性链表中各结点的值。 PROCEDURE PRTLL(HEAD) j＝HEAD WHILE (j≠0) DO { OUTPUT V(j) ； j＝NEXT(j) } RETURN

清华大学出版社 TSINGHUA UNIVERSITY PRESS struct结构体名 数据成员表 struct结构体名*指针变量名; 例如 struct node i char name [10] /*数据域*/ char sex: /*数据域*/ struct node *next /*指针域*/

struct 结构体名 { 数据成员表； struct 结构体名 *指针变量名； } 例如 struct node { char name[10]； /*数据域*/ char sex； /*数据域*/ struct node *next； /*指针域*/ }

清华大学出版社 TSINGHUA UNIVERSITY PRESS # include" stdlib.h"/米 malloc函数需要包含头文件 stdlib.h* struct node /*定义结点类型 i int d /*数据域*/ struct node next /*指针域* main struct node*p;/*定义该类型的指针变量p* p=(struct node *)malloc (sizeof (struct node)) /*申请分配结点存储空间*/ free(p);/*释放结点存储空间*

#include "stdlib.h"/* malloc 函数需要包含头文件stdlib.h*/ struct node /*定义结点类型*/ { int d； /*数据域*/ struct node *next； /*指针域*/ } main() { struct node *p； /*定义该类型的指针变量p*/ … p=(struct node *)malloc(sizeof(struct node))； /*申请分配结点存储空间*/ … free(p)； /*释放结点存储空间*/ }