2.3线性表的链式表示和实现2.3.1线性链表（单链表和指针）>数据域（data）和指针域（next）>存储表示typedef struct LNode!data;ElemType*next;Struct LNodeLNode, *LinkList;11中国科学技术大学ypb@ustc.edu.cn
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）带头结点的单链表12中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 12 中国科学技术大学 单链表种类 不带头结点单链表 带头结点单链表
常见指针操作p-→next=qp=qqpp=q -→ nextH向p-*next=q-nextqp=p-nextpPP13中国科学技术大学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 常见指针操作*
单链表的基本操作求线性表的长度时间复杂度：O(n)21181301-7542156P6K3214中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 14 中国科学技术大学 单链表的基本操作 求线性表的长度 时间复杂度：O(n)
查找元素操作时间复杂度：0（n）Bf=d+（a)）查找成功（从链头开始后移指针1-1次）P=NULL（b）查找失败（以链头开始后移指针未到1-！次，指针变空）15中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 15 中国科学技术大学 查找元素操作 时间复杂度：O(n)