文档详情

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

发布:2017-12-29约4.59千字共31页下载文档
文本预览下载声明
链表的典型形态 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
显示全部
相似文档