数据结构ppt课件2线性表.ppt

2. 1 线性表的类型定义 2. 1 线性表的类型定义 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.3 线性表的链式存储和实现 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2.3.1 线性链表 2.3.1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2．3 线性表的链式存储和实现 2. 3. 2 循环链表 2. 3. 3 双向链表 双向链表的存储类型描述 typedef struct DulNode{ ElemType data; struct DulNode *prior; struct DulNode *next; } DulNode , *DuLinkList; 2.3.3 双向链表 2.3.3 双向链表 a b p c data next … … b 步骤1：用循环找到被删除节点i的前驱 即：p=p-next; a b p c data next … … b 步骤2：将b的地址记录下来 即：q=p-next; q a b p c data next … … b 步骤3：让p-next指向b后第一个结点 即：p-next=q-next; q a b p c data next … … b q 步骤4：释放b结点 即：free(q) 单线性链表的缺点之一，是无法从指定的某结点到达该结点的前趋结点，这可能会给某些应用带来一些不便，下面介绍线性表的另外两种链式存储结构—— 循环链表和双向链表。 1 循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是将线性 链表的最后一个结点的指针指向链表的第一个结点（头节点） 2 循环链表图示 (a)非空表 （b）空表 H H a1 an 1 双向链表的概念 (a)结点图示 数据域 指针域 指针域 结点 存储数据元素 存储后继结点 的地址 存储前趋结点 的地址 双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。 ^ L A B C ^ 2 双向循环链表图示 L （c）非空的双向循环链表 (b)空的双向循环链表 L a b * 第二章 线性表 线性表是n 个类型相同数据元素的有限序列， 通常记作（a1, a2, a3, …, an ）。 姓名 电话号码 蔡颖 陈红 刘建平 王小林 张力 ... 例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A, B, C, D, E? Z ）。例3、某单位的电话号码簿。 一 线性表的逻辑结构 电话号码簿是数据元素（记 录）的有限序列，每一数据 元素包括两个数据项，一个 是用户姓名，一个是对应的 电话号码。大量记录的线性 表为文件 说明：设 A=（a1, a2, ... , ai -1, ai , ai+1, …, an ）是一线性表 1） 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须 是同一类型的； 2） 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的直接前趋，ai+1 是ai 的直接后继； 3） 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，