数据结构02-线性表.ppt

线性链表 2.3 用指针实现线性表（链表） 头指针、头结点和首元结点 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 单链表可由一个头指针唯一确定。 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息; 首元结点是指链表中存储线性表第一个数据元素a1的结点 线性链表 上例链表的逻辑结构示意图有以下两种形式： ① ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H ② ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H 区别：① 无头结点 ② 有头结点 线性链表 2.3 用指针实现线性表（链表） 查找链表中某个元素 2.3 用指针实现线性表（链表） 在链表中插入元素 2.3 用指针实现线性表（链表） 在第一个结点前插入 newnode-next = first ; first = newnode; （插入前） （插入后） newnode newnode first first 在链表中插入元素 2.3 用指针实现线性表（链表） 在链表中间插入 Newnode-next=current-next current-next = newnode； (插入前) (插入后) newnode current newnode current 在链表中插入元素 2.3 用指针实现线性表（链表） 在链表中插入元素 2.3 用指针实现线性表（链表） 在链表末尾插入 current-next = newnode； Newnode-next=null (插入前) (插入后) newnode newnode current current ? ? 在链表中删除k处的元素x 2.3 用指针实现线性表（链表） 在链表中删除k处的元素x 2.3 用指针实现线性表（链表） 单链表的特点 2.3 用指针实现线性表（链表） 单循环链表 2.4 循环链表(Circular List) 循环链表：首尾相接的链表 单循环链表：在单链表中，将终点的指针域NULL改为指向第一个结点，也可以设置一个头结点 单循环链表的各种算法与单链表基本一样，只是循环条件不同 双向链表 2.5 用双链表示线性表（双向链表） 双向循环链表 2.5 用双链表示线性表（双向链表） 双向链表运算：删除 2.5 用双链表示线性表（双向链表） 双向链表运算：插入 2.5 用双链表示线性表（双向链表） 一元多项式 2.6 线性表的应用：一元多项式的表示与相加 一元多项式 2.6 线性表的应用：一元多项式的表示与相加 一元多项式 2.6 线性表的应用：一元多项式的表示与相加 一元多项式 2.6 线性表的应用：一元多项式的表示与相加 本章小结 理解线性表的概念：同一类型的元素组成的有限系列 熟悉定义在线性表上的基本运算：查找、插入、删除 掌握实现线性表的一般步骤 掌握用数组实现线性表的步骤和方法 掌握用指针实现线性表的步骤和方法 掌握单循环链表的实现方法 掌握双向链表的实现方法 作业1 小娜和小丽喜欢游戏，准备开始一个新游戏。在一条直线上放置了n个巧克力棒，小娜从左到右吃，小丽从右到左吃。两个人同时开始吃，且吃的速度是一样的。当玩家吃饭一根巧克力棒后，立即吃下一根。一根巧克力棒只能给一个人吃，当两个人要开始同时吃同一根的时候，小丽会让给小娜吃。 现有n根巧克力棒，从左到右给出巧克力棒的长度，请给出算法计算出每个人吃的根数。 输入第一行包括一个正整数N(1=N=500000)，表示巧克力棒数。接下来一行有n个整数，t1,t2,…,tn(1=ti=100),表示从左到右的每个巧克力棒的长度 实验任务 数据输入 输出两个数，小娜和小丽各自吃掉的巧克力棒数 数据输出 作业2：有序链表的插入 中国地质大学（北京）* 数 据 结 构 Data Structures 安海忠 博士 中国地质大学（北京）人文经管学院 院长 教授 博士生导师 国土资源部资源环境承载力评价重点实验室 主任 电话：01082323793（办）电邮：ahz369@163.com 教学内容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第六章 树和二叉树 第七章 图 第九章 查找 第十章 内部排序 第二章 线性表 2.1 线性表的定义 2.2 用数组实现线性表（顺序表） 2.3 用指针实现线性表（链表） 2.4 循环链表 2.5 用双链表示线性表（双向链表） 2.6 线性表的应用：一元多项式的表示及相加 第二章 线性表 学习重点 线性结构