数据结构(C)第2章线性表.ppt

第2章 线性表 第1章介绍了几种基本逻辑结构：线性结构、树形结构和图结构。线性结构是最简单、最基本的数据结构，本章讨论线性表的基本概念、存储结构以及相关运算。 主要内容： ? 线性表的基本概念 ? 线性表的顺序存储结构及实现 ? 线性表的链表存储结构及实现 ? 线性表的应用 2.1 线性表的基本概念 现实中存在大量线性表的实例。例如： 大写英文字母表：(A,B,C,…,Y,Z)； 一周中7天(星期一，星期二，…，星期日)； MP3播放器中的若干个歌曲的目录。怎样查找自己喜欢的歌曲？怎样输入新的曲目？删除过时曲目？这就是本节所研究的内容：线性表及其运算。 2.1.1 线性表的定义 线性表（Linear List）是n(n≥0)个数据元素的有限序列。记作：(a1，a2，…，an) ai(1≤i≤n)属于同一数据对象，具有相同的数据类型。 n代表表长，即线性表中数据元素的个数。 当n=0时，线性表为空表。 对于ai: 当1＜i≤n时，它有一个直接前驱ai?1 ； 当1≤i＜n时，它有一个直接后继ai+1 。 2.1.2 线性表的抽象数据类型 ADT Linear_list { 数据对象：D={ai | ai∈ ElemSet , i=1,2,…,n, n≥0 ；} 数据关系：R={ai-1 ,ai | ai-1 ,ai∈D, i=2,3, …,n } 基本操作：初始化空线性表; 求线性表表长; 取线性表的第i个元素; 在线性表的第i个位置插入元素x; 删除线性表的第i个元素; 修改线性表中的第i个元素; 按某种要求重排线性表中各元素的顺序; 按某个特定值查找线性表中的元素; 等等; } ADT Linear_list; 2.2 线性表的顺序存储结构及实现 为了用计算机解决线性表问题，需要考虑数据信息如何在计算机内存储。计算机可以用多种不同的方法来存储数据信息，常用的方法是顺序存储结构和链式存储结构。 2.2.1 线性表的顺序存储结构 2.2.2 顺序表类定义 2.2.3 顺序表的插入和删除 顺序表的插入 顺序表的插入算法--算法2.1 2．顺序表的删除 顺序表的删除 顺序表的删除算法--算法2.1 用顺序表的类对象，调用线性表的插入和删除算法 3．插入和删除算法的时间复杂度分析 插入算法的平均移动次数分析 插入算法的平均移动次数分析 删除算法的平均移动次数分析 删除算法的平均移动次数分析 插入和删除算法的时间复杂度分析 2.2.4 线性表的其他运算 除前面两种基本运算外，还有一些较复杂的运算。 class SqList {　　 //……代码与前文类Sqlist的定义完全同前； public: //以下是增加的两个公有函数成员 void Insertdz( ElemType x); //有序表插入 void Deletaz(ElemType x); //有序表删除 }; 1．在非递减有序表中插入一个数据元素x，使线性表仍保持非递减有序。 　　　前提是线性表中数据元素已经有序。已知条件是将要插入的数据x，插入的位置需要程序来查找。 已知有线性表：（14，21，21，38，46，80） 若x=30，结果：（14，21，21，30，38，46，80） 若x=10，结果：（10，14，21，21，38，46，80） 若x=99，结果：（14，21，21，38，46，80，99） 　　　因插入的数据元素x值不同其插入位置也不同。插入位置怎样确定？ 1．在非递减有序表中插入一个数据元素x，使线性表仍保持非递减有序。 算法2.3 void SqList::Insertdz( ElemType x) { int i=length-1; while(i=0 elem[i]x) { elem[i+1]=elem[i]; i--;} elem[i+1]=x; //插入数据元素 length++; /