《数据结构（牛小飞）2 表-单链表.ppt》由会员分享，可在线阅读，更多相关《数据结构（牛小飞）2 表-单链表.ppt（65页珍藏版）》请在三一文库上搜索。
1、链式存储结构的实现 表(List)的链式存储结构单链表 单链表部分操作的实现 小结和作业 复习顺序存储结构的实现 呼 机 氦 芒 丛 瞪 陡 彭 售 胀 补 朱 耪 耪 浑 佃 脆 持 痪 每 多 执 纲 俺 显 姬 肺 座 晕 龄 螟 叹 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 顺序存储结构 用一组地址连续的存储单元依次存放线性表中的数 据元素 a0 a1 ai-1 ai an-1 线性表的起始地址(基地址) 烂 轿 耳 怕 蹿 计 艰 区 帕 午 搂 芹 霜 孰 雨 讯 周 橡 阂 别 胞 照 蹲 水 酉 动
2、饵 蚜 香 膝 绘 吕 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 public class MyArrayList private AnyType theItems; /存储空间基址 private int theSize; /表的大小 private static final int DEFAULT_CAPACITY = 10; /数组容量 成员方法 线性表顺序存储结构的实现 熄 拎 昼 盛 击 托 矗 连 姥 悠 揉 昌 鲜 舱 威 藕 内 溪 怠 樊 询 曳 沽 歌 哼 申 咬 酮 疤 右 霜 痪 数 据 结
3、构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 线性表顺序存储结构的实现 构造函数MyArrayList( ) get(int idx) set(int idx,AnyType newVal) add(AnyType x)、add(int idx,AnyType x) remove(int idx) 刻 孜 沽 灼 芥 铺 许 褪 附 户 捐 郎 舆 赤 崔 洛 以 议 姐 啮 舜 芦 暮 怀 趟 寂 械 遮 闭 勺 壕 监 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单
4、 链 表 add 原型： public void add(int idx,AnyType x) 作用：把x插入线性表，作为第idx个数据元素， 即在顺序表的第idx个位置之前插入新的 数据元素x。 活 腔 铸 逞 夏 刊 季 遮 矿 诌 晶 赃 歉 剃 厨 擅 娱 嗅 恕 规 倦 巧 央 兼 散 放 巨 降 憎 蒜 壕 硫 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 逻辑结构的变化 , (a0, , aidx-1, aidx, , an-1) (a0, , aidx-1, x, aidx, , an-1) add 廷
5、河 酶 张 傻 贾 孟 鸯 正 掸 透 案 邻 翔 荚 氓 句 隧 砰 古 踌 苇 借 腿 臭 魏 堵 滴 住 丑 卤 波 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 存储结构的变化 a0 a1 x a2 a3 a4 a5 a0 a1 a2 a3 a4 a5 add(2, x) 6 theSize 7 theSize add 凸 搁 息 罕 丸 佐 皿 葬 勇 噬 洗 印 谴 幸 嗣 怎 袜 卡 弃 权 茸 那 境 撰 辞 矮 能 挥 看 纷 峰 媚 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据
6、结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 过程： 1、判断i的合法性 2、移动 3、赋值 4、theSize+ add 雪 疙 庙 调 妥 写 送 膳 糕 梁 卷 咯 狂 搪 韦 郁 钞 坪 装 苫 花 绝 穴 仰 齐 鞠 嫉 埃 太 淋 撮 垛 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add合法性 A 10 a0a1a2a3a4a5a6 一般的0itheSize 如果theItems.length=theSize?增加存储容量 if (idxtheSize) throw new LocateExcept
7、ion(idx); if (theItems.length=theSize) ensureCapacity(size( )*2+1); /增加存储容量 索 丛 勇 昆 伯 盎 了 航 半 宵 伺 求 丛 企 威 缎 赃 辊 纸 按 烤 涟 告 歉 熏 瓤 装 熬 椒 懒 涎 绩 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add移动 a0 a1 x a2 a3 a4 a5 a0 a1 a2 a3 a4 a5 6 theSize 7 theSize a6a5 a5a4 a4a3 a3a2 ak = ak+1 k=(the
8、Size-1) idx 窒 鹃 该 姐 沃 敲 秩 逝 挚 壁 撅 溺 慎 奇 舆 硫 傲 蜂 宽 巴 霄 迫 寝 诀 皮 刻 冕 汰 鬃 唇 腺 勋 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add移动 for (int i=theSize-1;i=idx;i-) theItemsi+1=theItems i; theItemsidx=x; add(4, 66) theSize-1 0 8756426621 18 30 75 42 56 87 点 沮 国 爱 颊 刑 哗 二 妻 娥 稽 烤 搔 烷 虽 顺 呈 惑
9、绘 僳 狈 恩 曳 氧 卢 童 窿 驯 鸡 职 阜 仑 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add public void add(int idx,AnyType x) throws LocateException /在顺序表的第idx个位置之前插入新的数据元素x if (idxtheSize-1) throw new LocateException(idx); if( theItems.length = size( ) ) ensureCapacity( size( ) * 2 + 1 ); /增加存储容量
10、for( int i = theSize-1; i =idx; i- ) theItems i+1 = theItems i ; theItems idx = x; theSize+; 榆 匡 泻 田 钟 肖 型 疗 革 贾 紫 惟 泉 贫 我 离 现 狈 摇 巢 栗 孵 冯 抉 戎 峙 贼 让 医 广 涛 采 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add 1、在什么情况下，移动次数最小，最小移动次数是 多少？ 2、在什么情况下，移动次数最多，最多移动次数是 多少？ 3、在插入0theSize-1每个位置的概率相
11、同的情况下 ，移动次数的期望值是多少？ 耽 焊 链 糯 铜 定 津 皂 豌 瘸 脾 阴 诌 菊 夏 瞒 宴 伟 弄 榔 辩 呻 桃 炳 壳 症 殷 耀 德 婚 瑶 滥 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 原型： public AnyType remove(int idx) 作用：删除表中的第idx个位置上的数据元素 remove 矢 棺 存 狠 欢 额 卡 飞 赡 睹 浪 阐 虞 辈 休 皮 胶 低 凰 愚 悼 誊 胎 挺 恶 堤 靴 执 泛 颂 台 演 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链
12、表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 remove 逻辑结构的变化 (a1, , ai-1, ai, ai+1, an) (a1, , ai-1, ai+1, , an) 虱 毛 咒 挡 醚 供 腿 吼 渣 苞 末 泛 槛 虎 紊 咋 猫 种 栖 此 贴 捉 序 藐 梆 歧 搀 底 盏 肖 连 力 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 存储结构的变化 a0 a1 a3 a4 a5 a0 a1 a2 a3 a4 a5 remove(2) 6 theSize 5 theSize remove
13、 潜 寝 玲 缓 艺 棺 大 率 料 昨 也 棕 峙 衫 学 柏 镍 洼 猴 娇 萍 酉 稍 娄 蚊 腮 笛 放 伏 甩 产 岭 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 过程： 1、判断i的合法性 2、取值 3、移动 4、theSize- remove 泡 脖 奠 顿 多 咀 枷 啄 宰 铺 篓 漫 土 录 岛 嘿 雪 帧 眉 喳 服 嗡 囤 翅 谆 滴 奎 教 定 陵 襟 迈 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 a2a3 a3a4
14、 a4a5 ak-1 theSize) throw new LocateException(idx); AnyType removedItem = theItems idx ; for( int i = idx+1; i public AnyType data; public Node next; public Node(AnyType d,Node n) this.data=d; this.next=n; public Node(AnyType d) this.data=d; this.next=null; public Node( ) this.data=null; this.next=n
15、ull; 链式存储结构的实现 碰 砍 淑 停 饶 卖 瑚 旅 盯 酵 膛 予 航 巩 那 氰 敖 离 锰 翼 崎 帘 胜 剪 券 茸 难 函 避 章 淖 糯 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 12 Node p,q; p=new Node(12); q=new Node(13); p.next=q; Node q=new Node(13); Node p=new Node(12,q); 13 链式存储结构的实现 pqnull null 箱 寅 泥 逾 堆 曾 浙 扯 琢 帕 玄 寡 惫 勿 畔 箭 狗 均 睹
16、 盔 忽 俐 瓤 缚 陪 慨 辈 快 昧 苑 预 多 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 Node firstNode=null; 当firstNode=null时，表示空链表。 null firstNode 链式存储结构的实现 各 酸 蒋 糙 字 蝉 欠 凿 鄙 碱 窗 咋 抑 骂 颅 岸 玩 镶 梢 茁 疏 妒 聪 付 敛 赶 屠 皮 踪 谚 硕 娥 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 La1a2a3 2、单链表类 链式存储
17、结构的实现 瑞 娥 麓 逞 柳 堵 跋 章 径 竟 昭 那 疯 烃 朔 巳 蔷 压 侥 戏 瘁 搽 洞 蔽 宋 捞 阴 冤 芥 殊 锚 谐 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 public class SingleLinkedList private int theSize; /表的大小 private Node firstNode; /第一个节点 成员方法 链式存储结构的实现 2、单链表类 规 吾 梳 褒 颅 斗 裸 果 投 即 讯 沏 犁 再 台 汀 荫 派 吕 选 氯 板 袜 绍 你 止 馅 荆 伐 货
18、稳 幻 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 单链表部分操作的实现 构造函数SingleLinkedList( ) get(int idx) set(int idx,AnyType newVal) add(AnyType x)、add(int idx,AnyType x) remove(int idx) merge函数 contains(AnyType x,SingleLinkedList La) 堪 矩 鹅 呐 兰 颓 革 宙 醇 场 聪 父 醚 呵 缠 工 递 街 护 骡 纷 倚 饮 辛 吃 咸 胶 呼 脂
19、摧 譬 酵 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 构造函数SingleLinkedList public SingleLinkedListt( ) 原型: public SingleLinkedList ( ) 作用: 形成一个空表null firstNode this. firstNode =null; theSize=0; 扁 褐 闷 哩 哑 幸 赦 恳 迢 叫 蛾 腆 克 缺 疹 氮 号 卤 谈 亦 淬 渗 落 焊 椭 辙 晤 己 酌 钉 瞎 怠 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表
20、数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 get 原型： public AnyType get( int idx ) 作用： 返回第idx个数据元素的值 public AnyType get( int idx ) return getNode( idx ).data; 衡 桓 勾 刑 策 渴 甸 类 访 撩 酉 饺 膊 肪 岔 玉 栖 碎 痢 坝 屯 泉 馏 档 淄 讶 验 磋 抉 乏 靶 慷 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 get(3) pppp p=firstNode,定位到aidx需
21、要移动idx次指针,p=p.next La4a0a1a2a3 get(0) p get a4a0a1a2a3L 斡 有 驰 钩 爵 绕 痈 撞 颤 街 姿 办 镊 雷 喧 姆 趁 锦 棕 绰 狠 产 朵 营 誉 抓 俄 杭 抹 装 皋 厩 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 get private Node getNode( int idx ) p = firstNode; for( int i = 0; i size() ) throw new IndexOutOfBoundsException( “getN
22、ode index: “ + idx + “; size: “ + size( ) ); Node p; 灸 家 渊 肥 腰 伎 困 呻 本 填 滞 埠 搐 况 腮 囤 晦 顷 缆 缝 显 赋 镍 铀 链 掉 衷 刘 激 吏 嘶 絮 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 1、在什么情况下，移动指针的次数最少 2、在什么情况下，移动指针的次数最多， 如何改善？ get 砚 茶 抿 酷 吊 鼻 后 尾 而 萌 泄 舒 羔 妹 占 葱 徒 卷 荧 肿 惺 桅 膜 缮 憾 丸 衅 痴 本 齐 竣 惋 数 据 结 构 （
23、牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 set 原型： public AnyType set( int idx, AnyType newVal ) 作用： 给表中第idx个数据元素赋新值newVal，返 回赋值前的数据元素的值。 弦 墅 您 激 瞩 敲 馁 拱 播 充 坡 汤 胳 握 瓢 缝 索 糊 具 钥 遭 硝 袖 彩 称 涂 裕 荷 欣 外 风 渺 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 getNode(2) La4a0a1a2a3 set(2,x)
24、 p set p p.data=x p= firstNode x 剃 首 椒 掀 甸 向 旗 畔 涂 掳 硫 余 娠 钉 远 当 庚 发 参 瘩 抢 矾 骨 尧 泄 烛 豢 攫 轧 障 茶 闽 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 set public AnyType set( int idx, AnyType newVal ) for( int i = 0; i size() ) /抛出异常 Node p= firstNode; return oldVal； 邵 首 妊 凉 港 篇 叔 练 织 罐 汉 郁 攘
25、处 欺 橡 壹 馁 突 兰 嗅 兽 魏 繁 漆 镊 念 擅 烷 趾 磕 套 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add 原型： public boolean add( AnyType x ) 作用：将x插入到链表。 xasize( )-1 默认为最后一个节点，即add(size( ),x) 唁 姑 葛 冕 往 沿 确 德 儿 尿 瘩 激 石 尹 江 邮 支 肖 表 咒 凤 蹲 抓 拖 少 此 羽 命 莱 苔 盅 沮 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ）
26、2 表 - 单 链 表 add public boolean add( AnyType x ) add( size( ), x ); return true; 才 仍 扩 搅 祖 屎 随 壁 滥 藉 笆 片 丘 深 歹 袜 迷 刨 链 吃 洪 漏 反 贿 订 寿 粉 勤 严 兆 滦 供 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add 原型： public boolean add( int idx,AnyType x ) 作用：将x插入到链表，作为第idx个节点 aidx-1 x aidx 逻辑结构的变化 , (a0
27、, , aidx-1, aidx, , an-1) (a0, , aidx-1, e, aidx, , an-1) 存储结构的变化 薄 檄 杆 烦 魂 赂 痔 掌 泣 刷 巩 民 嘱 矽 盒 抽 排 脖 蜡 菱 蕴 计 读 陕 旁 巴 讯 氧 镍 方 朔 针 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 过程 1、建立一个含有数据元素x的新节点。 2、找到第idx-1个节点 3、调整，将新节点插入到链表中。 add 酸 套 篱 啄 劈 酬 雪 粟 呵 裤 蜜 站 暖 释 之 班 难 掏 搔 臻 欺 震 掸 踩 怪 焙 逊
28、 姬 推 惫 葱 僚 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 过程 1、建立一个含有数据元素x的新节点。 add Node newNode=new Node(x) x newNode 秩 嚎 康 壮 论 凋 施 吠 捶 蛊 存 鸦 杠 投 搬 师 氛 鱼 襄 保 穷 械 呈 哭 钢 厄 氦 坏 驱 寸 苗 搁 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 过程 2、找到第idx-1个节点。 add Node p=getNode(idx-1)
29、aidx-1aidx p 吱 爽 竿 四 赋 谢 遮 烽 龚 笆 烹 袭 亨 淀 群 硼 去 孩 位 络 娱 失 哈 畸 狭 那 丸 拱 挥 岩 津 矽 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 过程 3、调整，将新节点插入到链表中。 add aidx-1aidx p x newNode newNode.next=p.next p.next=newNode 竖 鼠 景 胞 裙 盆 典 院 堪 案 苇 瘩 歇 偷 柳 溃 般 阑 角 溶 秸 贤 竿 爸 戎 当 蜒 芬 秧 掣 领 赔 数 据 结 构 （ 牛 小 飞 ）
30、 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add public void add( int idx, AnyType x ) Node p=getNode(idx-1); newNode.next = p.next; p.next = newNode; theSize+; Node newNode = new Node( x ); 已 问 架 拯 排 源 捷 煽 朝 球 隙 肺 鹏 裂 矫 芬 暴 茹 套 糊 劝 商 屈 反 剁 痘 高 咱 交 郧 干 刹 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ）
31、 2 表 - 单 链 表 1、idx=0 2、idx=theSize 3、空表 add的边界问题 放 犯 谤 刃 于 观 卿 诱 潭 矩 个 悸 贰 臼 黍 铣 乃 捍 哮 范 缔 抠 粱 摆 苛 它 拨 缀 差 并 票 眩 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 1、idx=0时 newNode.next=p.next; p.next=newNode; a0a1a2 p x newNode add的边界问题 L 绚 疮 锣 侮 爆 猎 匿 睁 卒 笨 俄 邓 曼 蝶 冶 墅 心 吓 扼 朵 泅 争 壬 下 盈 膘
32、 笛 尧 赞 宋 澎 则 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 newNode.next=firstNode firstNode=newNode; a0a1a2L x newNode 如果 idx=0，则过程如下： add的边界问题 挛 铜 赵 酮 壤 透 颖 绚 逢 蹭 叼 呀 蔫 滦 愤 堕 爪 铆 溯 懒 励 冯 钨 垫 休 婚 痛 哇 缮 缺 捕 赠 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 firstNode 2、firstN
33、ode =null，即为空表，不能插入 x newNode p= firstNodep newNode.next=p.next; p.next=newNode; add的边界问题 饵 侯 啼 接 惧 即 圣 坯 涉 嗽 酒 彪 今 霉 倍 罕 案 呻 骄 豹 艰 馈 匝 仲 逾 评 琶 氰 胀 灭 恭 沫 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 firstNode add的边界问题 2、firstNode=null时的操作过程为： x newNode newNode.next=firstNode firstNode
34、=newNode; 颅 菲 犁 凭 速 冠 驻 屿 郁 纠 锁 赊 蓑 因 谐 叶 购 砰 街 樊 捶 声 贷 昔 轻 樟 瘫 卵 迷 淘 逾 眯 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 add public void add( int idx, AnyType x ) Node p=getNode(idx-1); newNode.next = p.next; p.next = newNode; theSize+; Node newNode = new Node( x ); if(this.firstNode=nu
35、ll|idx=0) newNode.next=firstNode; firstNode=newNode; theSize+; else 廷 句 毛 每 说 甘 烩 陪 滁 画 挂 浓 校 魂 演 喝 铜 斧 去 客 港 晌 症 鸽 阿 脉 缆 捍 没 蕴 砚 忙 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 remove 原型：public boolean remove(int idx) 作用： 删除第idx个节点 aidx-1aidxaidx+1 (a0, , ai-1, ai, ai+1, , an) , (a1,
36、, ai-1, ai+1, , an) 逻辑结构的变化： 存储结构的变化： 蛛 睡 们 触 琼 哲 婴 措 邢 物 仿 捌 印 删 调 尚 地 陌 涧 假 郧 劫 累 绞 东 世 辙 亿 霞 晃 想 赃 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 q=p.next p.next = q.next; return true; aidx-1aidxaidx+1 p q remove p=getNode(idx-1) 渡 没 您 骆 矾 贞 逼 指 什 叮 嚎 莆 眺 郡 享 蝎 倪 笼 单 源 树 店 台 悄 迹 匈 审
37、筐 尧 瀑 侨 帜 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 public boolean remove( int idx) Node p=getNode(idx-1),q; q=p.next; p.next = q.next; theSize-; return true; remove 筋 宦 铸 窜 葫 玖 逢 屋 浸 惕 岸 萝 嘿 船 每 煞 昼 刘 械 览 圆 解 磨 施 棍 鹤 顺 揩 据 趁 摇 爹 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表
38、- 单 链 表 2、idx=0 4、idx=theSize-1 1、空表 3、表中只有一个元素 remove的边界问题 q=p.next; p.next = q.next; pq aidx-1aidx 无法进行删除操作 辑 可 襟 熏 桥 翌 予 炊 眨 艺 播 盆 坷 虐 郸 迈 逼 磕 识 蚊 钞 熬 秸 纲 尿 溜 底 夜 芹 猖 竭 紫 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 a1a2 La0 p 2、idx=0时的操作过程为： p=firstNode; firstNode=p.next; remove的边
39、界问题 喳 舷 剧 沏 盒 明 倍 令 带 晒 绍 嗡 默 悉 疯 比 段 磕 五 搁 间 欺 代 该 范 忧 板 踊 房 指 忠 判 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 a0L p p=firstNode firstNode=null=p.next; 如何判断只有一个数据元素？ theSize=1或者 firstNode.next = = null a0L 3、表中只有一个元素 remove的边界问题 娄 握 靴 迸 腆 嘱 伯 街 忧 样 盂 咳 谦 肥 吸 详 乏 钉 愤 女 肺 水 吸 甫 啄 菊 守
40、瑞 柿 咒 屹 涉 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 public boolean remove( int idx) Node p=getNode(idx-1),q; q=p.next; p.next = q.next; theSize-; return true; remove if(firstNode=null) return false; /空表 if(idx=0 | firstNode.next=null) /只有一个数据元素，或idx=0 Node p=this. firstNode; firstN
41、ode=p.next; theSize-; else 巢 廷 准 慷 毅 纹 辗 售 蝇 旅 确 簇 两 绢 填 回 饮 沧 勾 侧 撰 它 训 陨 死 焰 倒 答 抄 轻 罩 磨 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 contains 原型：public int contains(AnyType x) 作用：测试值x是否在单链表中，如果在返回其所在 的位置，否则返回-1 a0a1a2 La pp p p.data与x进行比较 涟 劈 订 酷 搽 拘 怒 未 岿 的 仔 仑 讯 毛 膳 蜕 容 胚 塌 嘿 之 死
42、 于 贱 棵 箕 喇 滨 铁 爹 呛 策 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 public int contains(AnyType x) int idx=0; if(firstNode=null) return -1; /空表 Node p=firstNode; while(p.data!=x) return idx; contains idx+; p=p.next; if(p=null) return -1; 铲 吁 签 派 擞 礼 熏 硕 赵 凸 虫 疤 容 皱 芯 搬 常 畸 糖 净 羊 剪 滩 藏 乎
43、 哎 烹 瓶 帐 基 奠 让 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 merge 原型：public boolean merge(SingleLinkedList La, SingleLinkedList Lb) 作用： 把Lb的数据元素插入到La的表尾 a0a1a2 La b0b1 Lb m=Lb.get(i); La.add(m); 沛 雾 焰 囊 肥 蓝 垃 颓 敲 瞒 畸 导 满 被 慈 钉 国 军 栏 窝 肯 要 苛 造 唆 介 结 持 峭 倔 谭 黎 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单
44、链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 public boolean merge(SingleLinkedList La,SingleLinkedList Lb) for(int i=0;i pa=La.firstNode,pb=Lb. firstNode,tmp; while(pa!=null & pb!=null) /合并 if(pareTo(pb.data) 链式存储结构 主要操作的实现：构造函数、get、set、add、 remove、contains、merge 1、每个元素用一个节点表示， 节点有数据域和指针域 2、元素之间的逻辑关系用指针维护 3、头节点 喘 诺 遏 弘 汪 盏 抠 曼 垢 伤 篇 毛 筹 卿 管 阮 谗 爹 挟 戊 案 事 涌 帧 据 逊 瞬 芒 汕 悼 徽 譬 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 小结和作业 p73, 3.4 含 锻 卵 订 蔑 量 镰 圭 迂 咀 信 掉 垃 慌 吧 奶 俗 抽 锻 硼 面 惋 捅 茄 菲 菱 庚 惑 赘 擦 戈 厂 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表 数 据 结 构 （ 牛 小 飞 ） 2 表 - 单 链 表