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

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

ypb@ustc.edu.cn 11 中国科学技术大学 2.3线性表的链式表示 • 单链表和指针 ➢数据域（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 a/何 p=q→next 4H 日正正 a 冠 p→next=q→next p=p→next 日GG+ q 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 常见指针操作

单链表的基本操作 求线性表的长度算法2.15时间复杂度：On) +21-18-30--42-56☑ ypb@ustc.edu.cn 14 中国科学技术大学

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

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

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