2.3线性表的链式表示·单链表和指针>数据域（data）和指针域（next）>存储表示typedef struct Lnode?data;ElemType*next;Struct Lnode}Lnode, *LinkList;11中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 11 中国科学技术大学 2.3线性表的链式表示 • 单链表和指针 ➢数据域（data）和指针域（next） ➢存储表示 typedef struct Lnode{ ElemType data; Struct Lnode *next; }Lnode, *LinkList;
单链表种类>不带头结点单链表为什么设计>带头结点单链表头结点？head（a）不带头结点的单链表+一（b）带头结点的单链表12中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 12 中国科学技术大学 单链表种类 ➢ 不带头结点单链表 ➢ 带头结点单链表 为什么设计 头结点？
常见指针操作p→next=gp=qqpp=g-→next石qp-→next=q→nextp=p-nextp中pP13中国科学技术大学ypb@ustc.edu.cn
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时间复杂度：O(n)211830754256614中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 14 中国科学技术大学 单链表的基本操作 求线性表的长度 算法2.15时间复杂度：O(n)
查找元素操作算法26时间复杂度：0（n）Bf=d+安中一（a)查找成功（从链头开始后移指针1-1次）P-NULL（b）查找失败（以链头开始后移指针未到1-！次，指针变空）15中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 15 中国科学技术大学 查找元素操作 算法2.16时间复杂度：O(n)