第二章线性表.

《第二章线性表.》由会员分享，可在线阅读，更多相关《第二章线性表.（65页珍藏版）》请在金锄头文库上搜索。

1、第二章第四章 线性结构,线性结构特点：在数据元素的非空有限集中： 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继,第二章 线性表（6学时）,第一讲 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 第二讲 2.3 线性表的链式表示和实现,一、线性表的定义,线性表(Linear List) ：由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。 其中：数据元素的个数n定义为表的长度。 当n=0时称为空表。 常将非空的线性表(n0)记作： (a

2、1，a2，an) 说明 ：数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 例1、26个英文字母组成的字母表 （ A，B，C、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况： （6，17，28，50，92，188）,例3、学生健康情况登记表如下：,在此例中，一个数据元素由若干数据项组成，常把这样的数据元素称为记录，含有大量记录的线性表，又称为文件。,线性表的基本要求：,从以上三个例子可以看出，线性表中的数据元素可以是各种各样，但同一线性表中的数据元素必须具有相同的特性，即属于同一数据对象，相邻的元素之间存在着序偶关系。 通常将线性表记为：

3、(a1,ai-1,ai,ai+1,an) ai为第i个元素，i为元素ai在线性表中的位序。,线性表的逻辑特征：,在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构，长度可增减，对元素可进行访问，插入、删除等操作。,二、线性表的抽象数据类型定义,ADT List 数据对象：D=ai|aiElemSet,i=1,2,3.,n,n0 数据关系：R1=| ai-1, aiD,i=

4、2,3.,n 基本操作： InitList(&L) 操作结果：构建一个空的线性表。 DestroyList(&L) 初始条件：线性表已存在(已初始化) 操作结果：销毁线性表 ClearList(&L) 初始条件：线性表已存在(已初始化) 操作结果：将线性表重置为空表 ListEmpty(L) 初始条件：线性表已存在(已初始化) 操作结果：若线性表为空表则返回TRUE,否则返回FALSE,ListLength(L) 初始条件：线性表已存在(已初始化) 操作结果：返回线性表中元素个数 GetElem(L,i,否则操作失败。 NextElem(L,cur_e,&next_e) 初始条件：线性表已存在

5、(已初始化) 操作结果：若cur_e是线性表中的数据元素,且不是最后一个元素，则用next_e返回它的的后继，否则操作失败，next_e无定义。,ListInsert( 在上述基本操作定义的基础上，还可以进行更复杂的操作。,例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。,void union(List 分析算法复杂度：O(ListLength(La)ListLength(Lb),例2-2 已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。,void mergelist

6、(list la，list lb，list ,while(i=la_len) getelem(la，i+，ai); istinsert(lc， +k，ai); while(j=lb_len) getelem(lb，j+，bj); listinsert(lc，+k，bi); 分析算法复杂度： O(ListLength(La)+ListLength(Lb),返回,一、线性表的顺序表示,把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。 则线性表中第i+1个数据

7、元素的存储位置 LOC( a i+1)和第i个数据元素的存储位置LOC(a i)之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)l,a1,a2,ai,b,b+l,b+l*(i-1),1,2,i,内存,元素序号,b+l(n-1),an,n,b+l(maxlen-1),用结构进行表示和实现： #define LIST_INIT_SIZE 100 /线性表初始空间， 是单位空间的倍数 #define LISTINCREMENT 10 /分配空间增量 typedef struct Sqlist elem

8、type *elem; /数组指针 /存储空间起始地址 int length; /当前长度 int listsize; /当前分配空间 Sqlist; 例如： Sqlist *L;,二、顺序表上的基本操作,1、初始化：构造一个空表。算法如下： Status InitList_Sq(Sqlist 2、插入：在表的第i (1in+1)个位置上，插入一个新结点e，使长度为n的线性表： (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，e，ai，an),e,Status ListInsert_Sq(Sqlist ,q= 分析： 这里的问题规模是表的长度，设它的值为n。该算

9、法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。 当i=n时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）； 当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。,计算算法平均时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为： 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当

10、低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。,3、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，an) 变成长度为n-1的线性表 (a1，a i-1，a i+1，an),Status Deletelist(sqlist ,分析： 该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。 若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点； 若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算

11、法的时间复杂度分别为O(1)和O(n)。 删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 式中，Qi表示删除表中第i个结点的概率。,在等概率的假设下， Q1=Q2=Q3=Qn=1/n 由此可得： 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n) 结论：在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低,4、 按值查找 线性表中的按值查找是指在线性表中查找与给定值e相等的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素 a1

12、起依次和e比较，直到找到一个与e相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 e 相等的元素，返回-1或0。 int Location_SeqList(SeqList L, ElemType e ) int i=0; /此题与书不同 ElemType *p; p=L.elem; while(iL.length) return -1; else return i; /*返回的是存储位置*/ ,5、线性表应用举例线性表合并 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。 算法思路

13、：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。,void mergelist_sq(sqlist la,sqlist lb,sqlist ,三、顺序存储结构的优缺点,优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分,练习与作业,练习：分析线性表按值查找和合并的时间复杂度。 作业：习题二 2、11,返回,2.11 设顺序表va中的数据元素递增有序。试写一算法，将

14、x插入到顺序表的适当位置上，以保持该表的有序性。,解： Status InsertOrderList(SqList ,解： Status InsertOrderList(SqList ,一、线性链表,1、链表： 链表是用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的，因此，对于每个数据元素ai，除了要存储本身的数据信息外，还要存储其直接后继的信息，即地址。 节点 data域是数据域，用来存放结点的值。 next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。 特点：链表正是通过每个结点的链域将线性表的n

15、个结点按其逻辑次序链接在一起的。,“指针”回顾,内存的两种访问形式： 直接访问：根据所声明变量和地址之间的一一对应关系进行访问。如：int i=3; printf(“%d”,i); 间接访问：将变量i的地址存放于另外一个内存单元中，如： i_pointer=,2、线性链表： 1）、定义：结点中只含一个指针域的链表叫线性链表，也叫单链表。 2）、实现：借助于C语言的结构指针 typedef struct LNode ElemType data; struct LNode *next; LNode *LinkList; 例如： LinkList p;,为增强程序的可读性，通常设置一个链表的头指针，单链表可以用头指针的名字来命名。如：下面链表可称为表head: 将标识链表的头指针说明为LinkList类型的变量，如： LinkList head ; 当head = NULL，则表示一个空表； 当head = 第一个结点的地址，即链表的头指针； 将指向某结点的指针变量说明为LNode *类型，如: LNode *p；,头结点：在单链表第一个结点前附设一个结点，在其数据域存发附加信息，如链表的长度等。 线性表为空：头结点指针域为空 。,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,52,头指针,110