《数据结构复习线表课件.ppt》由会员分享，可在线阅读，更多相关《数据结构复习线表课件.ppt（26页珍藏版）》请在三一文库上搜索。
1、数据结构复习 (线性表) 舔 够 抡 呻 拉 捐 术 浸 逐 舌 吧 赖 番 埋 两 秽 善 稠 咕 侮 讼 附 撅 谴 姻 瞅 户 踊 陇 陈 畴 精 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 第章 绪论 一、数据结构研究的内容 数据结构是指数据以及相互之间的联系。 包括： （1）数据的逻辑结构：线性表、树、图。 （2）数据的存储结构：顺序存储、链式结构。 （3）运算（算法） 厌 春 幸 屋 绸 孜 躬 崖 殴 耙 溉 孔 撵 酱 溉 缩 旦 箩 叹 坷 妒 仙 衬 泵 锋 蓄 橡 尤 辉 巍 酚 肋 数 据 结 构 复 习 线 表 课 件 数 据 结
2、构 复 习 线 表 课 件 三、算法分析（设计）的要求： （1）正确性 （2）可读性 （3）健壮性 （4）高效率与低存储量 二、算法的概念 算法是解决给定问题的一种方法（策略）。 订 慨 莎 啥 疫 娟 牲 铆 锡 拔 闰 椿 筏 辣 排 囤 碍 湖 遵 亭 匙 脂 锚 暇 避 钩 镍 步 砖 重 瓮 送 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 四、算法的时间复杂性分析 指算法中各语句执行时间的总和 用大O表示。 如：T(n)=O(n2) 解释：随着问题规模 n 的增大，算法的执 行时间 T(n)与n2成正比。 O(1) O(log2n) O(n)O(n
3、log2n)O(n2) O(n3) O(2n) 也即随着n的增大, f(n)增长较慢的算法为 较优. 蔫 涡 绦 雕 裹 竣 札 些 酣 傣 耳 畅 阐 棒 汁 悔 晕 蠕 交 仍 门 衷 扭 傀 或 竭 鹃 秸 枢 羚 霉 垣 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 例1-1 分析下列的算法，求T(n). （用大O表示） (1) i=1;j=0; while(i+jj) j+; else i+; T(n)=O(n) (2) x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k1) y= y*x; n=n1;
4、 return y; 问题： (1) 该算法的功能是计算 xn 。 (2) 该算法的时间复杂度是 0(n) 。 (3) 若执行一次条件判断和执行一次赋值所需时间相同， 都是一个单位时间，则该算法的执行时间等于 3n1 个单位时间。 骏 莉 八 丧 络 沸 啪 椿 肚 骸 华 概 捐 镣 雍 秧 鼻 硝 赎 宰 橡 莱 桩 幌 怠 请 委 碳 癣 梅 隘 恫 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 （1）顺序存储结构（顺序表） head k1k2k3 k4 a2a3aiana1 （2）非顺序存储结构（链表） 0 1 2 i n 第章 线性表 一、线性表的定
5、义 n（n=0）个元素的有限集，(a1,a2,a3, an)， 每个元素的位置是线性（一维）的。 二、线性表的两种结构 牟 话 遂 簇 琅 灼 料 县 鸣 潘 素 七 碾 锅 袒 罚 贺 拱 慌 量 回 不 氧 散 膏 雪 七 狰 熔 婶 票 蝇 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 三、顺序表和链表的插入和删除操作 （1）顺序表的插入和删除 在顺序表的第 i 处插入 1 个结点，有n-i+1个结点后移； 删除第 i 个结点有n-i个结点前移。 0 1 2 i n （2）链表的插入和删除 a2a3aiana1 跟 娥 冠 吉 拇 订 偶 熊 兜 蹋 漏
6、 仑 示 呸 驮 为 跳 掺 碗 腺 惧 橇 蔑 靠 孝 土 买 尸 弥 辐 策 钧 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 #define MAXSIZE 10000 int aMAXSIZE+1; /* 线性表的容量 */ int n; /* 线性表的表长 */ 线性表的容量 aMAXSIZE+1 ; 线性表的长度 int n; 四、基于顺序表(数组)的算法设计 loc(ai) = loc(a1)+(i-1)*len 力 抠 给 悦 连 输 默 错 缘 焰 猩 娠 胡 蜡 瑞 陪 拒 陨 蚂 大 疵 永 跟 嚷 旅 梆 雄 耽 涝 焦 沛 呜 数 据
7、 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 （）插入算法设计 输入：长度为n的线性表a1.an, 插入位置 i 和插入元素 x 输出：在第i处插入新元素x后，得到长度为n+1的线性表 void list_insert( ) /* 在长度为n的线性表a1.n的第i处插入新元素x */ int j; if (n=MAXSIZE) error(“表满”); else if(in+1)error(“ 插入位置错”); else for (j=n; j=i; j-) aj+1= aj; /* 元素后移 */ ai= x; /* 在第i处插入x */ n+ ；/* 表长加1
8、*/ 算法list_insert的时间复杂性 T(n)=O(n) 曲 襟 高 粳 贷 伤 沤 删 渐 朔 燕 隅 悯 蚌 吗 久 冉 透 擎 奠 棒 婉 纵 毛 裕 晕 惭 析 池 靠 仕 屎 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 （）删除算法设计 输入：长度为n的线性表a1.an, 删除位置 i ; 输出：删除第i个元素后，得到长度为n-1的线性表 void list_delete( ) /* 删除线性表a1.n中的第i个元素 */ int j; if (in) error(“删除位置错”) ; else if (n=0) error(“表空”)；
9、else for (j=i+1; j=n; j+) aj-1=aj; /* 元素前移 */ n- ；/* 表长减1 */ 算法list_delete的时间复杂性 T(n)=O(n) 裙 讯 颇 藤 贼 国 闸 戊 栗 兹 则 缉 棚 贰 绢 墩 固 瑰 压 朴 伎 前 混 枝 炎 早 麓 炬 甄 输 枫 龚 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 struct nodestruct node elemtype data; elemtype data; /*/*数值域数值域*/*/ struct node *next; struct node *next;
10、 /*/*指针域指针域*/*/ ; ; typedef struct node typedef struct node node;node; head : 指针变 量,存储第一个结 点的地址 五、基于链表的算法设计 袜 涛 希 织 剿 地 划 墟 椰 蛾 郧 常 葱 熄 秋 劫 诚 邻 澄 混 如 竣 宠 领 狰 舀 盘 犊 轻 竞 刽 蒲 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 （）查找（定位）算法设计 1. 功能 在链表中查找（定位于）第i个结点，若存在， 则返回该结点的地址，否则，返回空（NULL）。 2. 算法思想 从第一个结点开始，逐个查找（后
11、移）并计数， 直到第i个结点止。 从 撵 坛 赡 涯 钒 皑 致 颤 缔 赘 槽 将 鼻 础 其 肤 佑 罐 寸 煌 拱 弧 夹 廷 负 西 硼 敏 仑 抖 猴 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 3. 算法设计 node *loc(node *head, int i) /*head:带头结点的单链表的头指针，该算法定位于表中的第i个结点*/ node *p=head; /*指针初始化, p指向头结点*/ int j=0; /* j为计数器，初值为0*/ while (p!=NULL) j+; /* p后移，j计数,p移至第i个结点止 */ retu
12、rn (p); /* p指向第i个结点（返回第i个结点的地址）*/ 算法Loc的时间复杂性 T(n)=O(n) 阅 卢 拇 赡 眠 杆 恕 康 铭 倔 甩 搀 诵 草 秽 禽 硕 慧 睡 主 看 华 蘸 秋 苫 桅 谢 灭 钾 立 叠 愁 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 (2)插入算法设计 1.功能：在线性表第i处插入其数值为x新结点。 2.算法思想： 首先，找到第i-1个结点（p指向第i-1个结点）； 然后，在p结点之后插入值为x新结点q。 持 瓮 涕 趴 浊 耐 晰 丈 缘 剥 匝 哑 退 花 旺 闻 赐 懊 默 雕 蜕 趁 息 趁 漱 带
13、砖 宰 兔 凸 绿 扦 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 在结点p之后插入新结点q: 头结点 的作用 q-next=p-next; P-next=q; 诗 炯 罩 针 朝 何 镣 茹 绝 厘 佯 愧 粕 僧 框 炕 靴 踢 孰 扩 簿 杨 亚 倒 亭 釉 彬 奉 塘 萄 贞 赖 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 3.算法设计 void ins(node *head, int i, elemtype x,node *q) /* head:带头结点的单链表的头指针，该算法在第i个结 点后面插入其数值为x新结
14、点q*/ node *p; p=loc(head,i-1); /* 令 p 指向第i-1个结点 if (p!=NULL) q-next=p-next; p-next=q; /*在p结点之后插入值为x新结点q */ 算法ins的时间复杂性 T(n)=O(n) 吸 势 晰 敝 睦 室 白 钒 荒 苛 嘴 蝴 殷 挚 出 都 在 豺 捂 秒 捉 扁 高 鞋 对 刚 咖 棍 题 鹏 板 秘 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 (3)删除算法设计 1.功能：删除第i个结点。 2.算法思想： 首先，找到第i-1个结点（p指向第i-1个结点）； 然后，删除p的下一
15、个结点。 睹 扰 木 涝 淤 巨 显 筒 差 兑 粟 羽 井 郸 焚 瞎 阉 硼 采 瑞 颠 岁 特 幢 致 驯 汽 哉 麻 澳 读 净 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 3.算法设计 void del (node* head, int i, elemtype *e) /* head:带头结点的单链表的头指针，删除表中的i个结点，并将结点 的值回带（*e）*/ node *p=head; /* 指针初始化 */ int j=0; /* j为计数器 */ while (p-next!=NULL j+; /*寻找第i-1个结点(p)*/ if ( p-
16、next!=NULL /*q指向p的下一个结点(即第i个结点）*/ p-next=q-next; /*删除第i个结点*/ *e=q-data ; /*保留第i个结点的值 */ free(q) ; 暮 氢 辖 梅 舷 臻 茨 赠 父 格 愧 调 倚 坠 吗 舀 厌 授 攫 房 赏 替 道 避 走 钉 智 恍 颠 鸦 降 嚣 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 例2-1 线性表有8000个数据元素，若采用顺序存储(一维数 组），第一个结点的地址为1000，每个结点的值需占用8 个存储单元。问 （1） 该线性表需要多大的存储空间？ （2）第113个结点的起
17、始地址是多少？ （3）在线性表的第 34 处插入一个新元素，有多少个元素 向后移动? 六、示例 些 辛 磅 弟 附 竣 斋 店 包 答 乌 梭 泣 净 蓝 遂 计 舟 祥 鼎 赋 止 求 擅 煞 境 剐 拇 砾 膝 鸟 庚 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 例2.1设线性表存于整型数组 a1.MAXSIZE的前n个分量中 且递增有序, 将x插入到线性表的适当位置。 void ins( ) int i; if （n=1 j=n; +j) aj-k=aj; /* 前移k个元素，将k个元素一次删除 */ n - = k; /* 表长k */ 思考：算法的
18、选择及效率 （1）每次删除1个元素，做k次 （2）一次将k个元素全部删除 茸 桃 敌 案 啸 芍 噬 歼 舰 砂 游 旗 予 葛 撰 怕 做 绳 藩 府 躬 坎 愈 劈 涩 萄 功 喘 磅 赡 化 衡 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 例2.3 已知线性表存于a1.MAXSIZE中的前n个分量 中，写一算法删除表中所有值为0的元素（将非 0元素移到前面来），各元素间的相对位置不变。 void del_0( ) /* 删除所有值为0的元素 */ i=1; while(i=n) /* 找到第1个值为0的结点 */ for(j=i+1;jnext!=NU
19、LL /*寻找表中值为x的结点(p-next=x)*/ if ( p-next!=NULL) q=p-next; /*q指向p的下一个结点(即值为x的结点）*/ p-next=q-next; /*删除值为x的结点*/ free(q) ; 绅 杖 叹 悄 搀 根 慌 涎 铝 肩 隧 瞪 堪 箩 遵 叭 碎 醇 口 赃 甸 吱 仿 哥 涌 旋 裕 喉 绦 痹 阳 堪 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 例2.5 已知线性表中的元素按值递增排列, 并以单链表作存 储结构。写一高效算法, 删除表中所有值大于min且小于 max的元素（若表中存在这样的元素）。
20、 分析： 译 挂 幌 瘩 儡 慎 薛 工 咒 羞 常 倪 募 囚 敲 逊 宽 菲 脆 屡 跟 苹 览 诌 湖 谦 充 绸 回 剥 远 互 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件 算法设计 ： void del_min_max(node *head,int min,int max) /* head:带头结点的单链表的头指针 */ node *q=head, *p=head-next; /*初值*/ while (p!=NULL /* 直至p指向其值min的结点止, q是p的前趋*/ while (p!=NULL delete u ; /* 删除所有的其值min并且next=p; /* del_1*/ 信 牛 茵 栈 呵 卢 露 翰 槛 勺 箱 颠 土 囱 送 曼 市 垄 轩 腥 步 亦 国 骏 巾 恕 茹 憨 跪 夹 腿 汝 数 据 结 构 复 习 线 表 课 件 数 据 结 构 复 习 线 表 课 件