中国科学技术大学：《数据结构与数据库》课程教学资源（PPT课件讲稿）第二章 线性表

2.3线性表的链式表示和实现 2.3.1线性链表（单链表和指针) >数据域(data)和指针域(next) >存储表示 typedef struct LNode ElemType data; Struct LNode *next; LNode,*LinkList; ypb@ustc.edu.cn 11 中国科学技术大学

ypb@ustc.edu.cn 11 中国科学技术大学 2.3线性表的链式表示和实现 2.3.1线性链表（单链表和指针） ➢数据域（data）和指针域（next） ➢存储表示 typedef struct LNode{ ElemType data; Struct LNode *next; }LNode, *LinkList;

单链表种类 不带头结点单链表 带头结点单链表 head (a)不带头结点的单链表 … (b)带头结点的单链表 ypb@ustc.edu.cn 12 中国科学技术大学

ypb@ustc.edu.cn 12 中国科学技术大学 单链表种类 不带头结点单链表 带头结点单链表

常见指针操作* p=q p→next=q 0日少正+ a/何 p=q→next 4+ 日日日 a 雨 p→next=q→next p-p→next G日G+ ypb@ustc.edu.cn 13 中国科学技术大学

ypb@ustc.edu.cn 13 中国科学技术大学 q p p=q q p p=q → next p p=p→next q p p→next=q q p p→next=q→next 常见指针操作*

单链表的基本操作 求线性表的长度时间复杂度：On) 2四18-30-5-2-56☑ k ypb@ustc.edu.cn 14 中国科学技木大学

ypb@ustc.edu.cn 14 中国科学技术大学 单链表的基本操作 求线性表的长度 时间复杂度：O(n)

查找元素操作 时间复杂度：0(n) (a)查找成咖（从链头开始后移指针-1次） P=NULL )睿我失败（从链头开始后移指针末到-1次，指针变空） 3 ypb@ustc.edu.cn 15 中国科学技术大学

ypb@ustc.edu.cn 15 中国科学技术大学 查找元素操作 时间复杂度：O(n)