第十二章结构体与共用体方案.ppt

12.7.2动态数据结构——单向链表 struct Link { int data; struct Link *next; }; data next head data next data next data NULL 链表（Linked Table）:线性表的链式存储结构 特点：用一组任意的存储单元存储线性表的数据；存储单元可以是连续的，也可是不连续的 12 - * 链表的定义 data next head data next data next data NULL 链表（Linked table）:线性表的链式存储结构 为表示每个元素与后继元素的逻辑关系，除存储元素本身信息外，还要存储其直接后继信息 两部分信息组成一个节点 struct Link { int data; struct Link *next; }; 12 - * 头节点 中间节点 中间节点 末节点 data next head data next data next data NULL 数据域：存储数据元素信息（不局限一个成员数据） 指针域：存储直接后继的节点信息 链表（Linked Table）:线性表的链式存储结构 为表示每个元素与后继元素的逻辑关系，除存储元素本身信息外，还要存储其直接后继信息 struct Link { int data; struct Link *next; }; n个节点链接成一个链表（因为只包含一个指针域，故又称线性链表或单向链表） 12 - * 链表的定义 链表的建立 向链表中添加一个新节点 data = A node data = B node data = C ∧ node head 空指针NULL表示链表结尾 链表的头指针：访问链表的关键 12 - * 链表的建立 若原链表为空表(head == NULL) ，则将新建节点p置为头节点 head (1)head = p data next p 新建节点 (2) pr = p ∧ pr (3) pr-next = NULL 12 - * data next 新建节点 p 链表的建立 若原链表为非空，则将新建节点p添加到表尾 (1) pr-next = p (2) pr = p ∧ pr pr (3) pr-next = NULL next 12 - * 链表的删除操作 若原链表为空表，则退出程序 若待删除节点p是头节点，则将head指向 当前节点的下一个节点即可删除当前节点 data next (1) head = p-next head 待删除节点 data next p 头节点 (2) free(p) 12 - * 链表的删除操作 若待删除节点不是头节点，则将前一节点的指针域指向当前节点的下一节点即可删除当前节点 (1) pr-next = p-next data next data next 待删除节点 data next p 中间节点 data next 若已搜索到表尾（p-next == NULL）仍未找到待删除节点，则显示“未找到” (2) free(p) 12 - * 链表的插入操作 若原链表为空表，则将新节点p作为头节点，让head指向新节点p head 待插入节点 data ∧ p (1) head = p p = (struct link *)malloc(sizeof(struct link)); p-next = NULL; p-data = nodeData; 12 - * 链表的插入操作 若原链表为非空，则按节点值（假设已按升序排序）的大小确定插入新节点的位置 若在头节点前插入新节点，则将新节点的指针域指向原链表的头节点，且让head指向新节点 head 待插入节点 data next p (2) head = p data next data next data ∧ (1) p-next = head 12 - * data next 链表的插入操作 若在链表中间插入新节点，则将新节点的指针域指向下一节点且让前一节点的指针域指向新节点 待插入节点 data next p (2) pr-next = p data next data next data ∧ (1) p-next = pr-next pr 12 - * data next 链表的插入操作 若在表尾插入新节点，则末节点指针域指向新节点 待插入节点 data next p (1) pr-next = p pr data ∧ 原末节点 next ∧ 12 - * 链表的输出 遍历链表的所有节点 head data next data next data ∧ p p p p ∧ 12 - * 链