数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第二章线性表
46页1、数据结构,第二章 线性表,第二章 线性表,线性表,知 识 点 线性数据结构的基本特征和基本运算 顺序表的插入与删除运算 链表的插入与删除运算 难 点 顺序表的溢出的判断 利用本章的基本知识设计有效的算法解决与线性相关的应用问题,第二章 线性表,要 求 熟练掌握以下内容: 线性表的基本运算 了解以下内容: 线性表运算时间复杂性分析,第二章 线性表,目录,2.1 线性表及其运算 2.2 顺序存储结构 2.3 链表存储结构 2.4 应用实例及分析 小 结 习题与练习,第二章 线性表,2.1.1 线性表(Linear List),线性表是由有限数目的相同类型元素组成的序列。 表中的数据元素,除了第一个和最后一个以外,都有一个且只有一个前驱元素,同时也都有一个且只有一个后继元素; 第一个元素只有一个后继元素而无前驱元素;最后一个元素只有一个前驱元素而无后继元素。 线性表的元素个数n称为这个表的长度,当n=0时,这个表叫做空表。,第二章 线性表,线性表在计算机内存中采用各元素顺序存储的方式,这种存储结构叫做向量。 每个线性表元素叫做这个向量的一个分量。 如果已知线性表第一个元素的地址和每个元素占用
2、的存储单元数,由任一元素的序号就可以计算出该元素在内存中的地址。 在编程时以一维数组表示线性表最简单,用的也最普遍。,第二章 线性表,2.1.2 线性表的运算,对于给定的线性表,可进行如下的基本运算: 1. 求线性表的长度n; 2. 在第i个数据元素前面插入一个新的数据元素; 3. 删除第i个数据元素; 4. 存取或更新线性表第i个元素; 5. 将两个或两个以上的线性表合并成一个线性表; 6. 将一个线性表拆成多个线性表; 7. 将线性表中各数据元素按某个域值(如关键字)递增或递减的顺序重新排列; 8. 在线性表中查找满足某种条件的数据元素;,第二章 线性表,1. 数据元素的插入(insert),设用一个一维数组An表示此线性表,原来有m个元素(mn),元素值已给定。 规定数组的下标从1开始,即这里数据元素对应的数组下标从1到n。 要求在第i个元素前插入一个新数据元素,值为G,因原线性表的数据元素是连续排列的,中间没有空单元,所以第i个元素及其后面的各元素均需向后移动一个单元位置,这样才能将G插入到i位置,且元素总数由m增加为(m+1)。,第二章 线性表,插入函数,void inser
3、t(A, int n, m, i, G) int j; if (in+1) printf(“i值错!n”); else for (j=m;j=i;j-) Aj+1=Aj; /*将第i个元素及其后面的元素后移*/ Ai=G; m+; /*线性表长度加1*/ ,第二章 线性表,插入函数分析,在循环语句中,当i=1时,须循环m次,表示元素插入线性表头的前面,则原线性表中m个元素均须向后移动一个单元,这是最不利的情况。 当i=m+1时,则循环一次也不进行,这时元素直接插入到线性表尾的后面,所以线性表的所有m个元素均不移动,这是最好的情况。,第二章 线性表,2. 数据元素的删除(Delete),设用一个一维数组An表示此线性表,原来有n个元素,元素值已给定。 要求删除第i个数据元素,由于线性表元素在数组中必须连续排列,中间不能有空单元,故将此元素删除后,它后面的所有元素都需要向前移动一个单元,且数据元素总数由原来的n减少到n-1.,第二章 线性表,删除函数,void delete(A,int n,i) int j; if (in) printf(“i值错!n”); else for (j=i;j
4、=n;j+) Aj=Aj+1; n-; ,第二章 线性表,删除函数分析,在循环语句中,当i=1时,需循环(n-1)次,这是要删除线性表表头元素,是最不利的情况; 当i=n时,则循环一次也不执行,只是将元素数目n比原来减少一个,而第n个数据元素不必再考虑,其余的各单元的元素均维持不变,这是最好的情况。,第二章 线性表,2.3.1 链表及其运算,知 识 点 单链表的结点形式、组织方法和特点 单链表的基本运算和相应的算法 循环链表的组织方法和基本运算算法 双链表的结点形式、组织方法和特点 双链表的基本运算和相应的算法 顺序表与链表比较,各自的优、缺点 链表的应用,第二章 线性表,难 点 双链表插入、删除运算的算法 利用链接结构的特点设计有效算法,解决与链表结构相关的应用问题 要 求 熟练掌握以下内容: 单链表的结构特点、基本运算并能设计简单算法 循环链表的结构特点、基本运算并能设计简单算法 双链表的结构特点、基本运算并能设计简单算法,第二章 线性表,链表及其应用目录,3.1 单链表及其运算 3.2 循环链表与双向链表 3.3 链表应用举例 3.5 应用举例及分析 小 结 习题与练习,第二章
《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第二章线性表》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第二章线性表》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页