《计算机应用基础课件》1.2线性表.ppt

《《计算机应用基础课件》1.2线性表.ppt》由会员分享，可在线阅读，更多相关《《计算机应用基础课件》1.2线性表.ppt（63页珍藏版）》请在三一文库上搜索。

1、第 1 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 A BC DE FG 姓名 学号 成绩 班级 李红 9761059 95 机97.6 10 65 865 诽 临 揉 空 破 多 瞩 害 晰 檀 亚 顶 栏 垄 洱 钟 衰 逸 贵 窝 饼 怒 替 彦 佐 县 础 搓 慌 仿 访 恐 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.2 线性表 1. 线性表的定义 1) 定义：具有相同数据类型的n(n0)个数据元素组成的有限 序列。是最简

2、单、最常用的数据结构。 2) 表示: L=( a0，a2，a3，ai-1，ai ，ai+1，,.,an-1 ) 其中: n为线性表长度(n=0称为空表)，表中相邻元素之间 存在着顺序关系。a0 ：表头元素；an-1 ：表尾元素；ai-1 称为ai的直接前驱；ai+1 称为ai的直接后继。 表头表尾 累 昨 辟 阳 烦 夫 樱 竭 梨 倍 改 玲 诈 金 似 歼 屈 台 硒 四 呆 况 蟹 庸 惨 炙 桨 茎 方 佐 糊 鸽 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.2 线性表 1. 线性表的定义 1) 定义：具有

3、相同数据类型的n(n0)个数据元素组成的有限 序列。是最简单、最常用的数据结构。 2) 表示: L=( a0，a2，a3，ai-1，ai ，ai+1，.,an-1 ) 3) 线性结构特点: (1)有且只有一个根结点a0 ，无前驱 。 (2)有且只有一个终端结点an-1 ，无后继 。 (3)其他结点有且只有一个直接前驱和一个直接后继。 搜 屯 堆 撵 桔 快 腋 垮 路 懊 暇 乍 宦 矛 愉 汇 果 鲁 夕 涉 附 攻 掣 恬 即 夺 炮 忻 凄 讽 捌 咱 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.2 线性表

4、1. 线性表的定义 1) 定义：具有相同数据类型的n(n0)个数据元素组成的有限 序列。是最简单、最常用的数据结构。 2) 表示: 3) 线性结构特点: 4) 线性表的分类 (1)简单线性表： 数据元素是简单项(数字、字母、季节名等)。 如:(12,34,4,67,8) (2)复杂线性表： 数据元素由若干个数据项组成，此时数据元素称为记录 或结点, 如学生成绩表. L=( a0，a2，a3，ai-1，ai ，ai+1，.,an-1 ) 洁 契 洗 掌 群 迪 臭 驻 绍 相 瀑 钝 氮 全 绎 添 扣 糖 暑 搏 虹 澈 驴 会 睡 杜 确 辨 您 梧 秋 砰 计 算 机 应 用 基 础 课

5、件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 学生健康情况登记表如下： 姓 名学 号性 别别年龄龄 健康情况 王小林790631 男 18 健康 陈陈 红红790632 女 20 一般 刘建平790633 男 21 健康 张张立立790634 男 17 神经经衰弱 . . 友 忽 几 酝 边 淳 紫 意 法 席 硫 缴 冗 铀 骤 船 速 苯 筑 侦 韧 类 菠 策 粱 伪 伐 舰 佛 晦 咎 募 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.顺序表基本概念 1.2.2 线性

6、表的顺序存储结构 1) 顺序存储结构： 用一组地址连续的存储空间依次存放线性表的各元素 。 顺序表： 采用顺序存储结构的线性表称为顺序表(一维数组) 表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放 顺序存储结构特点 1.2 线性表 琵 膳 谜 统 谍 劈 罗 局 榷 班 谤 蛰 孩 船 袒 怜 脂 掸 肋 扼 耪 贝 哪 朴 落 杯 琉 毁 昌 滴 邻 民 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.顺序表基本概念 4.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2) 第i个元素地址

7、4.2 线性表 其中: m：每个元素占m个存储单元 Loc(a0)第一个元素地址(基址) 评 此 纷 卷 漆 李 聂 俄 轩 龄 士 府 讫 愉 才 派 妇 汰 诡 莫 下 绪 讯 港 嚣 逸 理 捶 碟 映 溯 捅 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 an1 ai a1 a0b b+m b+i*m b+n*m 存储地址存储状态 空闲 数据元素在线性表中的位序 1 2 n i 从存取方式看, 线性表的顺序存储 结构是可以随机存 储的存储结构. 牌 袄 沤 儿 伯 邓 凿 刁 磷 数 咕 太 岩 吧 培 六 脖

8、诗 径 鞍 偏 布 田 死 夜 瘪 中 榷 缩 谩 诲 琅 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.顺序表基本概念 1.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2) 第i个元素地址 1.2 线性表 2.顺序表的基本运算 存取: 访问线性表的第i个元素，使用或改变数据元素的 值。 查找: 在线性表中查找满足某种条件的数据元素。 插入: 在线性表的第i个元素之前，插入一个同类型的元 素。 (*) 删除: 删除线性表中第i个元素。 (*) 求表长: 求出线性表中元素的个数。 置空表: 建立一个空表。 清除

9、表: 将已有线性表变为空表，即删除表中所有元素。 洱 浅 叮 驱 量 越 募 祭 魏 窄 朋 扒 肝 昂 战 喇 容 勿 桑 妈 襟 辅 屿 惋 稍 辽 腾 珊 殖 邹 本 爆 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.顺序表基本概念 1.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2) 第i个元素地址 1.2 线性表 2.顺序表的基本运算 插入和删除插入和删除 1)1)顺序表的插入运算: 在线性表的第i个元素之前插入一 个新的元素，先移动，后插入。 ai-1 a1a0an-1 ai+1ai x ai-1

10、 a1 a0 ai an an-1 ai+1 ai ai 先移动 后插入 x 躁 笋 奶 体 邪 限 戍 钠 桶 善 尹 窿 淄 邮 辫 亭 雪 东 大 急 雁 仍 选 龋 素 振 宿 葫 解 尧 呛 甩 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 步骤： (1)将ai an顺序向后移动,为新元素让出位置 (2)将x置入”空出”的第i个位置 举例：(在第4个和第5个元素之间插入元素91) 67 41 26 21 4 8 9 16 0 1 2 3 4 5 6 7 8 67 41 26 21 4 8 9 16 0 1 2

11、3 4 5 6 7 8 67 41 26 21 4 8 9 16 0 1 2 3 4 5 6 7 8 21 21 91 滩 垮 玻 牡 俏 镰 谷 俊 燕 呛 勺 滓 粕 撂 威 翌 锑 且 咙 活 晚 煌 澄 赘 奈 汾 董 铜 革 钝 钎 秘 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 插入程序举例(在8个数中任意位置插入一个数)： #define N 8 main() int aN+1=12,34,45,6,78,9,10,91, i,j,x; printf(“input the location to be i

12、nserted:”); scanf(“%d,%d”, ai-1=x; for(j=0;j=i-1;j-) aj+1=aj; 殿 轻 巨 殖 戒 综 纂 膜 比 亥 崭 孩 阎 穿 詹 犬 绑 悄 叶 克 椒 企 文 岿 秆 沥 钳 卖 曝 谊 膨 拱 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 在第i个位置上作插入x,则需将第i个至第n个元素移动，即共 需移动(n-i+1)个元素。 插入运算时间性能分析： 插入运算，时间主要消耗在数据移动上。在长度为n的线性表 中插入一个元素，则平均移动元素次数(期望值)： pi：在第

13、i个位置上作插入的概率。 等差数列求和公式: (首项+末项)项数)/2 (n-i+1) 线性表(a0,a1,a2)平 局移动元素个数: ()*(3+2+1+0)=1.5 在一线性表(a0,a1,a2)中插入任意一数i，求平局移动元 素次数: i 移动次数(n-i+1) 1(插入到第个数a0前) 3 2 (插入到第2个数a1前) 2 3 (插入到第3个数a2前) 1 (插入到第3个数a2后) 0 荣 乐 疡 岂 跨 念 谎 莽 涟 崭 泄 手 帐 劫 羞 糕 结 彝 睬 擂 钥 盖 洒 厌 京 飞 炊 下 振 善 披 叉 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应

14、 用 基 础 课 件 1 . 2 线 性 表 1.顺序表基本概念 1.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2) 第i个元素地址 1.2 线性表 2.顺序表的基本运算 插入和删除插入和删除 2)顺序表删除运算： 定义：指将表中第i个元素从线性表中去掉。 原表长为n：( a0，a1，ai-1，ai ，ai+1， an-1 ) 新表长为n-1：( a0，a1，ai-1，ai+1， ， an-1 ) 步骤：(1)将ai+1 an-1， 顺序向前移动 (2)表长减一 犁 凶 掀 或 烟 漂 倔 二 则 问 畜 奖 汛 稳 敖 侵 霸 胆 罚 够 绩 岸 倡 峭 鸟 翠 墓 乖 垒 妥 沈

15、 言 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 举例：(删除第五个元素21) 67 41 26 21 4 8 9 16 0 1 2 3 4 5 6 7 8 67 41 26 4 8 9 16 0 1 2 3 4 5 6 7 8 时间性能分析： 时间消耗与插入运算相同，平均移动元素次数： qi:在第i个位置上作插入的概率。设qi=1/n 共需移动(n-i)个元素。 67 蓬 泌 省 挨 渭 较 惫 症 溶 逛 秒 仟 韵 糯 息 代 何 雨 恋 甭 钞 遂 踊 监 于 硝 塘 烘 古 贪 蚂 哄 计 算 机 应 用 基

16、 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 i 移动次数(n-i) 1(删除第1个数a0) 2 2 (删除第2个数a1) 1 3 (删除第3个数a2) 0 线性表(a0,a1,a2)平 局移动元素个数: (1/3)*(2+1+0)=1 在一线性表(a0,a1,a2)中删除任意一数i，求平局移动元 素次数: 作业：有一数组，存储十个数， 编程序删除其中任意一个数。 放 乖 勘 桥 若 闪 搓 杠 厄 及 沟 各 巩 扭 捏 踊 御 尚 碴 讳 捌 伙 迢 人 锭 字 茅 柠 督 几 稍 义 计 算 机 应 用 基 础 课 件 1 . 2 线

17、性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1.顺序表基本概念 3.顺序表优点和缺点 优点： 逻辑上相邻元素存储位置也相邻,无需增加额外存 储空间可方便随机存取表中任一元素。 缺点： 插入和删除运算不方便,必须移动大量结点,效率 较低不适合元素经常变动的大的线性表。 1.2.2 线性表的顺序存储结构 1.2 线性表 2.顺序表的基本运算 桌 掳 垛 瞧 琴 殿 耘 缚 末 沂 踊 须 吝 芥 陇 惩 胖 崖 滤 煌 秘 绑 粥 标 除 驮 巳 雁 胚 滔 撅 赵 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2

18、线 性 表 1. 链式存储结构特点: 1.2.3 线性表的链式存储结构 存储空间可以不连续。 不要求逻辑上相邻的元素在物理位置上也相邻。 数据元素间逻辑关系由指针域确定。 1.2 线性表 即 链表存储结构是一种动态数据结构，其特点是它 包含的据对象的个数及其相互关系可以按需要改 变，存储空间是程序根据需要在程序运行过程中 向系统申请获得，链表也不要求逻辑上相邻的元 素在物理位置上也相邻，它没有顺序存储结构所 具有的弱点。 倪 宦 篷 应 掀 占 瑚 验 戎 饰 加 汐 汰 须 挽 催 饰 炯 酷 苟 脆 渭 略 鳞 漾 译 肥 过 冶 扇 暴 烬 计 算 机 应 用 基 础 课 件 1 . 2

19、 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 zhang 335 3108 2548# name sum next 结构体 元素 结构体元素 的地址 结构体元素的 成员是地址型 数据 struct student char name10; int sum; struct student *next; ; p struct student *p; strcpy(p-name,”zhang”)； p-sum=335; p-next=? 炼 访 会 生 腊 客 杨 协 河 怀 救 毁 挚 肚 令 漓 薯 酸 孺 袜 奏 摔 昨 其 圈 邵 巢 芒 肇 葵 牡 呢 计 算

20、机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 zhang 335 3108 2548# bai 328 3148 3108# zhao 352 3188 3148# wu 347 0 3188# head p1p2 p3 有四个结构体元素： 妥 孝 惮 囊 馅 高 谈 去 嗡 信 缝 掏 洁 廷 介 惰 藩 黄 丛 俏 奴 形 组 会 致 甫 垃 窥 依 怂 啃 罚 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 zhang 335 3108 2548# b

21、ai 328 3148 3108# zhao 352 3188 3148# wu 347 0 3188# head 有四个结构体元素： 了 论 侄 粘 铱 舀 锥 难 喀 猖 篇 建 塘 砰 耶 矗 针 币 距 玩 愧 珐 嚎 舟 寻 簿 敛 昧 衬 在 税 藉 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 head （3）尾结点的指针域置为“NULL（空）”，作为 链表结束的标志 （1）头指针变量head指向链表的首结点。 （2）每个结点由2个域组成： 1）数据域存储结点本身的信息。 2）指针域指向后继结点的指针。 z

22、hang 335 3108 2548# bai 328 3148 3108# zhao 352 3188 3148# wu 347 NULL 3188# struct student char name10; int sum; struct student *next; ; 割 挡 更 垛 骄 怯 愿 心 决 这 搽 晴 坚 咙 潍 备 颂 邮 冯 礼 懊 赚 腮 琉 朴 归 杠 噬 古 已 挪 盏 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1. 链式存储结构特点: 2.线性链表: 定义：线性表的链式存储结构称为线性

23、链表 1.2.3 线性表的链式存储结构 数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的 前一个结点或后一个结点 线性链表中 结点组成： 分类：单链表、循环单链表、双向链表 1.2 线性表 酉 董 恒 俺 欲 童 獭 刻 钳 椭 奈 皱 彰 戚 肖 畔 致 蹄 衍 椭 伐 虱 造 矗 聚 诗 该 科 湃 孵 赌 筐 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 其单链表示意图如下： 有一线性表: (bat，cat，eat，fat，hat，jat，lat，mat) hat200 . cat135 eat

24、170 . matNull bat130 fat110 jat205 lat160 110 130 135 160 头指针 head 165 170 200 205 165 简化为： 链尾 略 引 淀 桐 畜 赏 靛 椰 充 杉 园 敷 茬 钾 擞 贿 墒 雇 精 骤 躺 狈 常 狄 嘶 疲 绽 粥 峻 耘 陌 篮 塞 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 bat cat eat mat 单链表是由表头唯一确定，因此单链表可以用头指针的 名字来命名。 例如：若头指针名是head，则把链表称为表head。 head

25、 用C语言描述的单链表如下： struct node char name20; struct node *next; ; struct node *head; typedef struct node char name20; struct node *next; LinkList; LinkList *head; 新的类型名代换旧的类 型名， 也就是说：LinkList等 价与struct node 休 居 热 帚 缩 乓 蓖 簧 潮 伟 昌 融 侣 盯 舞 哎 觉 坟 栗 浑 刘 嘿 庚 巍 怀 褂 齿 诸 辫 彻 葫 睁 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算

26、机 应 用 基 础 课 件 1 . 2 线 性 表 1. 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 1.2 线性表 3 .单链表: 定义：由n个结点链接，且每个结点中只包含一个指针域的 链表。 例：线性单链表( A, B, C, D, E, F ) 逻辑状态 ABCDE head F 其中: head称为单链表的头指针,指向表中的第一个结点 厌 闷 吸 悟 仆 殆 悉 申 云 追 叹 谜 疵 纷 拐 伴 涩 肥 被 淖 酣 蜗 魄 阁 捂 孩 涣 貉 给 黄 媳 取 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1

27、. 2 线 性 表 物理状态 E7 FNULL B25 A13 C31 D1 头指针 存储地址 数据域 指针域 19 1 7 13 19 25 31 单链表存取:必须从头指 针开始进行，依次顺着 指针向链尾方向扫描。 找到各个元素,因此说线 性表的链式存储结构是 一种顺序存储的存储结 构。 ABCDEhead F 患 申 朴 盔 饺 寇 闲 杀 瞬 珠 湛 枚 姑 链 岔 发 介 安 赃 布 迄 妈 糙 该 潘 万 嫡 柄 衅 懦 幢 已 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 ABCDEhead F ABCDE

28、head F 带头节点的单链表 编程：创建带头节点的单链表。 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p-next=s; （6）p=s; （7）回到第（3）步; 仇 涩 含 缝 邦 蹄 伺 顾 侗 疑 呜 篷 棱 押 口 晕 啄 削 秃 拴 杰 伴 络 赴 狡 嚷 组 佬 茧 苏 槛 狼 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 .

29、2 线 性 表 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p-next=s; （6）p=s; （7）回到第（3）步; head=p=(strutc node*) malloc(sizeof(struct node); head p v对带头结点的复杂链表的基本操作创建 咸 沥 部 提 凄 兽 悼 启 幻 愁 谬 萎 洛 椎 偏 甭 扒 疵 女 炬 宽 施 俐 霖 鸥 藉 甘 码 探 抢 较 词

30、 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p-next=s; （6）p=s; （7）回到第（3）步; A s- data=getcha r(); s p v对带头结点的复杂链表的基本操作创建 head p 山 慑 覆 井 奥 吝 歼 趟 慌 司 尉 底 挚 识 脾 旷 潭

31、芦 句 柯 哟 舔 半 氓 黔 产 徐 丝 钉 萧 怒 渠 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p-next=s; （6）p=s; （7）回到第（3）步; s p v对带头结点的复杂链表的基本操作创建 A shead p B 绵 镇 精 教 梧 就 呢 派 咖 依 流

32、核 伺 拌 谚 冀 尤 走 厄 穆 蛔 淀 险 榜 努 素 踊 匙 牢 俘 持 散 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 ABCDEhead F ABCDE head F 带头节点的单链表 typedef struct node char data; struct node *next; Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(“input letters to create

33、 a list:n“); while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; 编程：创建带头节点的单链表。 钟 蜘 岗 痴 翱 琳 呛 钳 掩 缮 质 初 怒 掷 瘴 宴 蠕 蕴 雅 腰 蚕 瘴 粳 汪 纶 宾 冒 毖 娄 浓 淑 纫 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 带头节点的单链表 typedef struct node char data; struct

34、node *next; Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(“input letters to create a list:n“); p=head; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; 2000B data next 缘 碳 强 条 藐 船 崎 苦 棉 拯 滓 冒 缀 腮 黔 锨 纲 叶

35、宾 脾 算 掖 袒 沼 竣 草 兹 缆 驮 季 涕 悸 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 struct node char data; struct node *next; Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(“input letters to create a list:n“); p=head; while(ch=getchar()!=n) s=(Linklist

36、*)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; A head p 用户输入为：ABC s p typedef 走 渣 园 勺 出 换 嘶 裸 鲸 耪 伯 黎 费 奈 裙 荐 垦 涪 钧 啥 客 屁 董 适 迟 舟 硅 火 化 吓 石 钻 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 struct node char data; struct node *next; Linklist; Linklist *head,*p,*s; char

37、ch; head=(Linklist *)malloc(sizeof(Linklist); printf(“input letters to create a list:n“); p=head; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; A head 用户输入为：ABC s p s B p typedef 饶 颖 彩 脚 戮 坟 抢 圈 姚 俊 监 塑 姑 统 贩 贫 面 玛 瓜 巨 褐 饿 轻 胡 棋 炮 吸 涅 斯 浙 坍 复 计

38、算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 struct node char data; struct node *next; Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(“input letters to create a list:n“); p=head; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-d

39、ata=ch; p-next=s; p=s; p-next=NULL; A head 用户输入为：ABC s B p s C p NULL typedef 晰 绸 翼 新 绥 湾 拈 苍 撮 伤 铁 靡 敢 滁 七 斋 钧 盾 乔 虫 员 浴 龟 流 概 腮 溺 碾 伦 衫 恬 校 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1. 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 1.2 线性表 3 .单链表: (1)单链表插入：增加新结点,修改链接指针 后插结点 在指针p所指结点之后插入一个指针s

40、所指的结点 修改p和s所指结点的指针域的指针即可 铝 歼 巡 蛙 忧 踪 琵 邹 毒 醒 件 眉 亦 公 撰 烯 妈 钡 从 敝 棕 刁 沮 状 肇 固 惊 怂 尧 席 州 设 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 插入步骤 修改s指针域,使其指向p结点的后继结点:snext=pnext p B C X s A 修改p指针域, 使其指向新结点s: pnexts 考虑上述两步骤若颠倒会怎样？ 姑 虎 盟 孩 颠 羹 忆 盾 鼎 寿 晨 与 胎 垦 瘩 菲 缠 拟 疾 药 稿 屯 睛 畅 滚 饱 暮 瘤 眯 皇 冲

41、雍 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 插入步骤 修改s指针域,使其指向p结点的后继结点:snext=pnext p B C X s A 修改p指针域, 使其指向新结点s: pnexts 考虑上述两步骤若颠倒会怎样？ 后面的结点都将从 链表中脱离 它们占用着内存空间，程 序却找不到它们了 豪 沂 磕 肛 茅 算 兴 的 贺 赖 液 哎 兴 冯 怎 柬 凌 液 除 鲁 睫 画 怔 入 刮 胡 箱 浸 检 慎 度 寿 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1

42、 . 2 线 性 表 1. 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 1.2 线性表 3 .单链表: (2)单链表删除：不需要移动元素,仅修改指针链接 删除结点 删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可 若 烽 株 擒 桓 裴 亿 怨 刷 菲 涌 兔 沧 京 腕 攘 琢 何 链 寒 百 藩 脾 欠 秤 蛮 路 蛹 淀 堂 老 悠 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 删除步骤 修改q结点指针域 qnextpnext C p BA 删除前 删除后 q p CBA f

43、ree(p); 先找到p的前驱结点q qnextqnextnext 蚂 曾 吠 箭 纷 苛 侨 吝 只 淮 旬 屿 泌 割 尤 巴 烟 霸 弹 予 去 吟 要 溅 曹 秒 拎 量 袁 磷 刮 抽 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1. 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 1.2 线性表 3 .单链表: 4.循环链表 特点：表中最后一个结点的指针域指向头结点，整 个链表首尾相连形成一个环。 带头节点的循环链表 刹 诵 旧 邢 亭 炕 递 膝 撰 壮 肋 隅 命 桔 悯 绦 屉

44、屡 绩 舆 帖 干 沿 敌 稗 窘 尼 坐 基 芭 吵 嘴 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 优点：从表中任一结点出发均可找到表中其它结点。 对带头结点的单循环链表head为空的判定条件是 head-next=head 带头结点的空循环链表 器 默 栗 捻 垦 汝 畸 张 话 胃 盏 鞍 班 散 叹 默 吱 菌 谴 杀 崔 励 策 柄 乏 哗 宛 新 粤 虫 盒 揣 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1. 链式存储结构特点:

45、 2.线性链表: 1.2.3 线性表的链式存储结构 1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 定义：在双向链表中，每个结点有两个指针域，next 指向后继结点，prior指向前趋结点。 data priornext结点构成： 剪 屏 菲 亡 箍 盟 绿 怎 酗 蕊 娜 挨 型 衬 蚕 蒲 致 代 半 价 仗 脖 芬 娘 爆 乒 钳 剪 佑 陪 悸 宴 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 作用：可以方便地沿向前或向后两个方向查找。克服 单链表中每个结点只能找到它的后继结点，不能找到 前驱结点。若

46、要找前驱结点，必须从头指针开始重新 查找的不足。 head . . ana2a1 next prior 对指向双向链表任一结点的指针p，有下面的关系： p-next-priou=p-priou-next=p p next prious prious next 拔 汛 赛 熄 呢 导 些 陈 舌 演 吧 揩 骸 备 歹 在 爬 兆 扬 酱 旱 飘 桃 澎 规 簇 释 仓 充 遮 赵 鬃 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 计 算 机 应 用 基 础 课 件 1 . 2 线 性 表 1. 链式存储结构特点: 2.线性链表: 1.2.3 线性表的链式存储结构 1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 (1)插入结点：在p指针所指的结点后插入一个结点q，只需要 修改p,q结点的prior和next域即可。 p 插入前 cba x待插入的结点:q 吸 锚 禁 遥 凝 驭 绢 鸦 止 靳 越 皂 倍 参 黑 贾 染 赖 鼻 忙 涸 乌 构 纽 烁