软件技术与基础课件6.ppt

链表的典型形态 1.2.5 链表的典型形态 1、单链表 如前所述 2、带头节点的单链表 头节点：是一个特殊的链点， 数据内容无效 链点指针指向链表头 链表的典型形态 带头节点的单链表 几个容易混淆的概念 第一个元素节点\头指针、头节点、链表头 第一个元素节点是线性表关系中第一个元素——a1 链表头是第一个链点，一般在链表的头部。 头指针是指向第一个元素所在链点的指针 头节点：是一个特殊的链点，数据内容无效，链点指针指向链表头 链表的典型形态 带头节点的单链表 几个容易混淆的概念 第一个元素节点、头指针、头节点、链表头 链表的典型形态 带头节点单链表的操作特点 插入和删除算法不必考虑在表首进行时，需要更改头指针的特殊处理 为什么教材中使用**而教案中没有使用？ 教材中仅定义了链点，没有定义链表结构 程序中调用的上下文不同 为什么教材中使用**而教案中没有使用？ 为什么教材中使用**而教案中没有使用？ 本质是一样的：要在函数调用中改变头指针的指向 改变指针的指向，即改变指针变量的内容 要改变指针的内容，必须将指针变量的地址传入 教材中是将指针的地址传入－－指针的指针 教案中将地址所在的结构的地址传入 双向链表 1.3双向链表 特点：每一个链点包含两个指针， 前趋指针 后继指针 双向链表 1.3.1双向链表的定义 双向链表插入 1.3.2 双向链表的插入操作 双向链表插入 1.3.2 双向链表的插入操作 双向链表插入 1.3.2 双向链表的插入操作 双向链表插入 算法实现（略） 找到ai 执行插入操作 体会 插入操作有多种方式实现，步骤比较复杂 双向链表的使用灵活，可进可退 思考：前面的四个步骤的组合顺序里，哪些是正确的，哪些是错误的？ 双向链表删除 1.3.3 双向链表的删除操作 问题描述：删除第i个元素 双向链表删除 1.3.3 双向链表的删除操作 问题描述：删除第i个元素 循环链表 1.4循环链表 上机练习题 上机练习题 上机练习题 上机练习题 上机练习题 上机练习题 上机练习题 上机练习题 体会 last指针的作用 思考 如果是双向链表还是否需要last指针？ 上机练习题 上机练习题 上机练习题 段景山 * * 段景山 软件技术基础 制作 主讲 段景山 段景山 线性结构 ///// a1 ... 头节点 ai an ... a1 an ... ... ai 头指针 a1 ai+1 an head tail ai-1 ... ... ai ///// a1 ... ai an ... 第一个元素节点、链表头 第一个元素节点 头指针 头节点 head ///// a1 ... ai an ... head p ＝ head； p-next = p-next-next; while(location 1 p != NULL ){ … } 如果location为1, 表首节点将被删除 p typedef struct list_type{ node_type *head; node_type *tail; int length; }list_type; head tail length a1 a2 教材 void main（） { node *head; createsl( head ); …… } void createsl( node **h) { *h = first node; …… } 教案 void main（） { list_type list; create_l( list ); …… } void create_l( list_type *l) { l-head = first node; …… } head head head tail length head tail length a1 a1 …… head tail N a2 N P an P a1 N P P：prior N：next typedef struct double_link_node_type{ struct double_link_node_type * prior; struct double_link_node_type * next; elemtype data; }dl_node_type ; typedef struct double_link_list_type{ dl_node_type *head; dl_node_type *tail; int length; }dl_list_type; 链点的定义 链表的定义 ai-1 N P ai N P 问题描述：在第i个元素前插入新元素 anew N P