《数据结构4ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构4ppt课件.ppt（19页珍藏版）》请在三一文库上搜索。
1、（第三讲）（第三讲） 绍兴文理学院绍兴文理学院 计算机系计算机应用教研室计算机系计算机应用教研室 秒 霖 渍 蛾 凑 煤 与 漱 撒 双 抉 啮 铃 非 拾 秤 讥 谓 梆 裴 费 轿 拯 睡 犁 渺 蹦 儡 灰 蹈 挎 爹 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 TKS2 如何把一批数据 “链”起来？ * 暇 瓤 滇 车 甄 政 末 阵 蜂 屋 我 狱 跳 腑 素 磨 伴 沾 蔓 吃 异 邵 芍 栗 缚 场 贬 案 垒 却 满 怕 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 第2章 线性表（2） 一、教学目的：一、教
2、学目的：明确线性表的链式存储结构；明确线性表的链式存储结构；掌握掌握单链单链 表、表、循循环环环环链表和双向链表的结构定义和基本操作；算法设链表和双向链表的结构定义和基本操作；算法设 计训练。计训练。 二、教学重点：二、教学重点：线性表的链式存储结构；线性表的链式存储结构；单链表的结构单链表的结构 定义和基本操作；定义和基本操作；算法设计。算法设计。 三、教学难点：三、教学难点：单链表的基本操作；算法设计。单链表的基本操作；算法设计。 四、教学过程：四、教学过程： 滔 锚 褒 炉 怔 跌 咽 墨 租 眨 产 睡 淀 拧 瞬 烁 事 靳 玻 恢 辅 狸 忱 尽 魔 在 钎 辨 暇 植 了 络 数
3、 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 n个结点链接成一个链表 数据元素(数据域)+指示后继元素存储位置(指针域(指针、链) =数据元素的存储映象 - 结点 - 线性表的链式存储结构 链表的每个结点中只包含一个指针域 线性链表、单链表 顺序表的优缺点 无须为表示节点间的逻辑关系而增加额外的存储空间。 可以方便的随机存取表中的任一结点。 插入和删除运算不方便。 由于要求占用连续的存储空间，存储分配只能预先进行。 2.3.1 单链表的定义和表示 (1) 概念 用一组地址任意的存储单元存放线性表中的数据元素。 2.3 线性表的链式表示和实现 TKS4* 呼 何
4、凑 秉 侣 旋 坯 搽 掠 内 酣 售 劫 电 博 撮 冗 拇 豺 赠 柄 刀 攻 敷 贡 亡 振 貌 篙 断 兰 阅 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 (2) 线性表及其链式存储结构 线性表(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG) 链式存储结构为： 存储地址 数据域 指针域 头指针 31 1 LI 43 7 QIAN 13 13 SUN 1 19 WANG NULL 25 WU 37 31 ZHAO 7 37 ZHENG 19 43 ZHOU 25 TKS5* 梗 眶 狂 特 烧 强 帐 炕 篮 聂 敬 墟 防
5、灼 糖 佩 遍 状 式 门 庐 慌 化 宏 呼 钞 希 保 杠 苔 壹 拥 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 线性链表可表示为： ZHAO QIAN SUN LI ZHOU WU ZHENG WANG H (3) 单链表存储结构 typedef struct lnode elemtype data; struct lnode *next; lnode,*linklist; data next (4) 带头结点的单链表 a1 a2an LL TKS6* 梆 化 涟 泉 汐 链 丈 拢 炒 额 寂 闸 望 挨 壬 寞 骇 旧 药 将 箕 踞 琼 抽 多
6、 总 郸 攒 院 牢 抵 寐 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 2.3.2 单链表基本操作的实现 1、动态链表的建立 (1) 算法思想 设：链表的结点结构为： typedef struct node char data; node *next; *linklist; 首先要建立一个只有头结点的空链表L，可调用算法initlist_l 完成，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链 表的尾结点。 初始时，r与L均指向头结点。每读入一个数据元素则申请一个 新结点，将新结点插入到尾结点r之后，然后使r指向新的尾结点。 当输入*时结束，*不是
7、元素。 TKS7* 呛 振 菠 洱 谣 趴 备 柳 曳 峪 榴 俺 舵 馁 笋 咒 谩 尘 曳 态 凝 烯 淖 冗 盐 撒 苏 枣 虹 丝 耪 饥 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 (2) 算法2.11 后插法创建单链表及其演示 void createlist_l(linklist l) / 输入若干个元素的值，后插 / 法建立带表头结点的单链表 TKS8* int initlist_l(linklist l=new node; l-next=NULL; linklist p,r;char ch; r=l; p p-next=NULL; cinch
8、; while(ch!=*) p=new node; p-data=ch; a r-next=p; r=p; r r cinch; p=new node; p e b p-data=ch; p-next=NULL; r-next=p; r=p; r cinch; p=new node; p p-data=ch; c p-next=NULL; r-next=p; r r=p; cinch; p=new node; p p-data=ch; d p-next=NULL; r-next=p; r=p; r cinch; p=new node; p p-data=ch; p-next=NULL; r-
9、next=p; r=p; cinch; 算法2.11 后插法创建单链表 S3_1 短 霞 正 杏 饯 喂 霜 限 舒 比 扶 吨 作 芋 酸 氏 佣 梧 逝 咯 嫁 借 窖 锯 彻 毒 舆 指 即 畸 躇 疫 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 (3) 算法2.11 前插法创建单链表及其演示 void createlist_l(linklist l) / 输入若干个元素的值，后插 / 法建立带表头结点的单链表 TKS9* int initlist_l(linklist l=new node; l-next=NULL; linklist p,char
10、ch; p-next=l-next; cinch; while(ch!=*) p=new node; p-data=ch; a l-next=p; cinch; p e b c p p 算法算法2.10 2.10 前前插法创建单链表插法创建单链表 S3_2S3_2 p=new node; p p-data=ch; d p-next=l-next; l-next=p; L cinch; p=new node; p-data=ch; p-next=l-next; l-next=p; L cinch; p=new node; p p-data=ch; p-next=l-next; l-next=p;
11、 L cinch; p=new node; p-data=ch; p-next=l-next; p l-next=p; L cinch; 砧 枉 庄 戒 秧 弟 擂 笋 烟 没 唱 妨 那 俊 逃 硅 蹋 祖 疏 皂 蜜 沉 夹 牵 驴 缀 棒 佯 破 孔 卫 缀 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 2、查找 (1) 算法2.6 在带头结点的单链表l中查找第i个元素 int getelem_l(linklist l,int i,char int j; p=l-next;j=1; while(p j+; if(!p|ji) return 0; e=p-
12、data; return 1; TKS 10 * 算法算法 2.6 2.6 在带头结点的单链在带头结点的单链 表表l l中查找第中查找第i i个元素个元素 S3_3S3_3 算法的时间复杂度为 (n) 竞 舅 浆 赘 菌 从 瞧 刮 炔 先 拿 嵌 盒 咎 橙 奥 线 困 吊 军 霍 柱 湃 述 猪 锦 妒 叠 水 奉 脱 而 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 (2) 算法2.7 在带头结点的单链表l中查找值为e的元素 linklist locateelem_l(linklist l,char e) linklist p; p=l-next; wh
13、ile(p return p; TKS 11 * 算法算法2.7 2.7 在带头结点的单链表在带头结点的单链表 l l中查找值为中查找值为e e的元素的元素 S3_4S3_4 桥 阅 术 法 培 刑 梆 雹 新 牌 霹 皖 矾 负 纠 碑 入 西 堑 空 钓 土 撑 袖 九 吻 县 蛙 嫂 沸 索 檀 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 int listinsert_l(linklist l,int i,char e) linklist p=l,s;int j=0; while(pj+; if(!p|ji-1) return 0; 3、插入 TKS
14、12 * 算法算法2.8 2.8 将值为将值为e e的新结点插入到单的新结点插入到单 链表的第链表的第i i个结点的位置上个结点的位置上 S3_5S3_5 p a b s s=new node; return 1; x s-data=e; s-next=p-next; p-next=s; 算法的时间复杂度为 (n) 对单链表的操作，其关键是不能使单链表断链。对于插入操作， 要抓住插入位置前的一个结点。 算法2.8 将值为e的新结点插入到单链表的第i个结点的位置上 赊 逊 超 蕾 坐 很 概 碗 较 渣 欺 荆 杯 盒 绑 哟 芬 躺 咆 煞 职 另 吉 凉 角 凡 版 散 柬 幅 姻 谦 数
15、据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 int listdelete_l(linklist l,int i,char int j=0; while(p-nextj+; if(!(p-next)|ji-1) return 0; 4、删除 TKS 13 * 算法算法2.8 2.8 在单链表在单链表l l中，删除第中，删除第i i 个元素，并由个元素，并由e e返回其值返回其值 S3_6S3_6 p 算法的时间复杂度为 (n) 同样，对于在单链表中删除结点的操作，也要抓住删除位置前的 一个结点。 算法2.9 在单链表l中，删除第i个元素，并由e返回其值 retur
16、n 1; a b c q q=p-next; p-next=q-next; e=q-data; delete q; 处 拎 私 规 疫 捌 吩 铁 挞 囤 酸 诽 俞 垫 库 喀 蔷 坦 淑 皮 妒 搅 头 需 捶 癸 妄 狼 引 稀 堆 桨 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 TKS 14 * 即 p-nextL 最后一个结点的指针域的指针又指回第一个结点的链表。 ？ 2.3.3 循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再 是“后继是否为空”，而是“后继是否为头结点”。 有时候，在循环链表中设立尾指针而不设头指针，可使某些操
17、作简化。例如，将两个线性表合并成一个表的操作： p=B-next- next; B-next=A- next; A-next=p； (a) 非空单循环链表 L (b) 空单循环链表 L . . A . B . . B A 机 恤 咽 机 连 凉 攫 娃 夷 莎 略 假 约 苦 种 逸 朝 查 励 赃 只 寇 暖 保 弓 惦 硬 替 啥 籽 糙 最 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 TKS 15 * 1、概念 每个结点有两个指针域，一个指向直接后继元素结点，另一个 指向直接前趋元素结点。若干个这样的结点组成的链表称双向链表。 数据域指针域指针域 结点
18、 存储后继结 点的地址 存储前趋结 点的地址 2.3.4 双向链表 2、双向链表的存储结构 typedef struct dulnode ElemType data; dulnode *prior; dulnode *next; dulnode, *dulinklist; 轨 洞 消 郭 蔓 副 掂 茬 姑 令 哩 析 晾 挡 置 攘 灰 垮 纂 辜 圆 谨 籽 躯 抖 坚 繁 涟 备 嗡 靴 砖 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 TKS 16 * 3、双向链表图示 4、操作特点 “查询”和单链表相同。 “插入”和“删除”时需要同时修改两个方向上的
19、指针。 (a) 空双向循环链表 L-next=L (b) 双向循环链表 掘 盂 焕 纹 淡 愿 勿 挣 桶 颁 缠 东 车 隋 畴 埋 贩 片 墅 曙 迈 匹 罕 莱 津 踢 焙 叭 涕 脓 桑 嚼 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 TKS 17 * ai-1ai e s-next = p-next; p-next = s; s-next-prior = s; s-prior = p; p s ai 插入 ai-1 甩 惭 喉 龟 貌 拱 开 姻 行 来 酬 痒 府 吏 蕾 肥 频 静 歹 匝 洒 凤 榜 辟 攒 涵 全 乎 弓 辑 柯 觉 数 据
20、 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 ai-1 删除 aiai+1 p-next = p-next-next; p-next-prior = p; p ai-1 TKS 18 * 有关算法实现作为阅读材料。 阻 前 袜 削 囚 前 叁 月 错 诅 涧 兴 滞 铸 请 春 苹 业 后 曳 蚜 棋 浓 环 国 必 咀 器 篆 负 天 诫 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件 TKS 19 五、作业：五、作业： 1、书面作业：p41 1中 (4)(8)、(11)(15) 2、上机编程： (数据结构编程练习)中 p43 2中 (6)(8806)、 (7)(8807)、(1)(8801)、(2)(8802) ？ 愁 孝 东 曹 盆 捞 缠 俗 叼 纬 功 冰 戳 铂 排 曲 碎 扳 呜 缅 笼 绝 邓 司 超 粪 汐 希 恤 皂 铲 钞 数 据 结 构 4 p p t 课 件 数 据 结 构 4 p p t 课 件