简化 sax第二章线性表[章节讲课]

1、第2章 线性表 本章主要介绍下列内容 l线性表的类型定义 l线性表的顺序存储结构 l线性表的链式存储结构 l线性表的应用举例 1章节课件 2.1 线性表的类型定义 1、线性表的定义 线性表是由n（n0）个类型相同的数据元素组成 的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度 当n=0时，线性表为空，又称为空线性表。表中相 邻元素之间存在着前后次序关系将ai-1称为ai的直接 前驱，将ai1,称为ai的直接后继。 2章

2、节课件 线性表举例：线性表举例： La=(34,89,765,12,90,-34,22)/La=(34,89,765,12,90,-34,22)/数据元素类型为数据元素类型为intint。 Ls=(Ls=( H H , , W W , , C C ) ) / /数据元素类型为字符型。数据元素类型为字符型。 Lb=(bookLb=(book1 1,book,book2 2,.,book,.,book100 100) ) / /数据元素类型为下列所示的结构类型：数据元素类型为下列所示的结构类型： struct bookinfostruct bookinfo int No; / int No; /*

3、 *图书编号图书编号* */ / char char * *name; /name; /* *图书名称图书名称* */ / char char * *auther; /auther; /* *作者名称作者名称* */ / .; .; ; ; 3章节课件 L=( a1, a2,.,ai-1,ai,ai+1,.,an) 2、线性表的四个特点： 1）存在唯一的一个被称作“第一个”的数据 元素。 2）存在唯一的一个被称作“最后一个”的数 据元素。 3）除第一个之外，集合中的每个数据元素均 只有一个前驱。 4）除最后一个外，集合中的每个数据元素均 只有一个后继。 4章节课件 3、线性表的抽象数据类型定义

4、 ADT List 数据对象：D=ai|aiElemSet,i=1,2,，n,n0 数据关系：R=|ai-1,aiD,i=2,3,n 基本操作： InitList( 操作结果：构造一个空的线性表L。 DestroyList( 初始条件：线性表L已存在。 操作结果：销毁线性表L。 5章节课件 ClearList( 初始条件：线性表L已存在。 操作结果：将L重置为空表。 ListEmpty(L); 初始条件：线性表L已存在。 操作结果：若L空表，则返回TRUE,否则返回FALSE ListLength(L); 初始条件：线性表L已存在。 操作结果：返回L中数据元素的个数。 GetElem(L,i,

5、 初始条件：线性表L已存在，1iListLength(L)。 操作结果：用e返回L中第i数据元素的值。 6章节课件 LocateElem(L,e,equal);LocateElem(L,e,equal); 初始条件：线性表初始条件：线性表L L已存在。已存在。 操作结果：返回操作结果：返回L L中第中第1 1个与个与e e相等数据元素的位序。若相等数据元素的位序。若 这样的数据元素不存在，则返回值为这样的数据元素不存在，则返回值为0 0。 PriorElem(L,cur_e,PriorElem(L,cur_e, 初始条件：线性表初始条件：线性表L L已存在。已存在。 操作结果：若操作结果：若c

6、ur_ecur_e是是L L的数据元素，且不是第一个，的数据元素，且不是第一个， 则用则用pre_epre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_epre_e无意无意 义。义。 NextElem(L,cur_e,NextElem(L,cur_e, 初始条件：线性表初始条件：线性表L L已存在。已存在。 操作结果：若操作结果：若cur_ecur_e是是L L的数据元素，且不是第一个，的数据元素，且不是第一个， 则用则用next_e next_e 返回他的后继，否则操作失败，返回他的后继，否则操作失败，next_enext_e无无 意义意义。 7章节课件 ListIns

7、ert(ListInsert( 初始条件：线性表初始条件：线性表L L已存在，已存在， 1iListLength(L)+11iListLength(L)+1。 操作结果：在操作结果：在L L中第中第i i个位置之前插入新的数据元素个位置之前插入新的数据元素e e， L L的长度加的长度加1 1。 ListDelete(ListDelete( 初始条件：线性表初始条件：线性表L L已存在且非空，已存在且非空， 1iListLength(L)1iListLength(L)。 操作结果：删除操作结果：删除L L的第的第i i个数据元素，并用个数据元素，并用e e返回其值，返回其值， L L的长度减的

8、长度减1 1。 ADT ListADT List 8章节课件 例例2-1：归并两个线性表：归并两个线性表LA和和 LB ，使，使LA包含包含 LA 中的全部元素和中的全部元素和LB的不包含在的不包含在 LA 中的元素。中的元素。 归并运算说明：归并运算说明： 1) LB 中与中与 LA 中相同的元素不归并到中相同的元素不归并到LA 中；中； 2) 不另建新线性表，需要扩大表不另建新线性表，需要扩大表 LA ，将，将 LB 中需要并入的元素插入到中需要并入的元素插入到 LA 中；中； 3) LB 中需要并入的元素作为中需要并入的元素作为 LA 的尾元素插的尾元素插 入。入。 9章节课件 伪码表示

9、的算法：伪码表示的算法： void union(List Lb_len=ListLength(lb); /求线性表的长度求线性表的长度 for(i=1; i=Lb_len; i+) GetElem(Lb,i,/ 取取LB中的第中的第i 个数据元素赋值给个数据元素赋值给e if(!LocateElem(La,e,equal) ListInsert(La,+La_len,e); / LA 中不存在和中不存在和e相同的数据元素，则插入之。相同的数据元素，则插入之。 /for /union 10章节课件 2.2线性表的顺序存储及操作实现 2.2.1 顺序存储 线性表的顺序存储是把线性表的数 据元素放在

10、一组地址连续的存储单元 中。（以元素在计算机内存储器内的物理位（以元素在计算机内存储器内的物理位 置来体现互为前驱和后继的逻辑关系，线性表置来体现互为前驱和后继的逻辑关系，线性表 中相邻的元素在内存储器内也相邻中相邻的元素在内存储器内也相邻） 假设每个元素占用l( 小写L)个存储 单元，线性表中第一个元素的存储地址 LOC(a1)=b，那麽线性表中第i个元素的 存储地址是多少？ 11章节课件 12章节课件 i a0 a1 a2 a6 a5 a4 a3 a0 a1 a2 a6 i a5 a4 a3 a0 a1 a2 a6 i a5 a4 a3 e n+1n+1 n+1 2.2.2顺序存储结构下基

11、本操作的分析顺序存储结构下基本操作的分析 1、插入操作、插入操作ListInsert ( /假设数组元素类型是int型 4、用结构体类型表示线性表用结构体类型表示线性表 struct SQ elemtype* elem; /数组的首地址 int listsize; /数组长度 int length; /线性表长度 ; 16章节课件 5、定义一个新的类型SqList typedef struct SQ elemtype* elem; /数组的首地址 int listsize; /数组长度 int length; /线性表长度 SqList; 此语句定义了一个新的类型此语句定义了一个新的类型SqL

12、ist，它等价于，它等价于 结构体型结构体型SQ SqList La，Lb；什麽含义？；什麽含义？ 17章节课件 n1、初始化线性表、初始化线性表 nStatus InitList(SqList n n if (L.elem=NULL) /建立动态数组失败，返回失败信建立动态数组失败，返回失败信 息息 n return OVERFLOW; n n else n L.listsize = LIST_INIT_SIZE; /动态数组初始长度动态数组初始长度 n L.length = 0; /线性表长度为线性表长度为0 n return OK; /返回成功信息返回成功信息 n /InitList 1

13、8章节课件 n2、删除操作、删除操作 nStatus ListDelete(SqList / L.elem=NULL 表示表不存在，返回错误信息表示表不存在，返回错误信息 if (i L.length) return ERROR; /i值不合法值不合法 ，返回错误信息，返回错误信息 n e = L.elemi-1; n /用用e返回动态数组返回动态数组i位置的元素的值位置的元素的值 ，为什麽下标是，为什麽下标是i-1 n 把第把第i位置后的元素依次向前移一位位置后的元素依次向前移一位/（自己实现）（自己实现） n L.length -; /L的长度减的长度减1 n return OK; /返回

14、成功信息返回成功信息 n/ListDelete 19章节课件 3、插入操作、插入操作 Status ListInsert(SqList /L.elem=NULL,表不存在表不存在,返回出错返回出错 信息信息 if (i L.length+1 | i 1) return ERROR; /i值不合法，返回出错信息值不合法，返回出错信息 if (L.length = L.listsize) /如果动态数组的长度等于线性表的长度，插入的元如果动态数组的长度等于线性表的长度，插入的元 素没有空间存放，需要改变动态数组的长度素没有空间存放，需要改变动态数组的长度 elemtype * newbase =

15、(elemtype *)realloc(L.elem,sizeof(elemtype) * (LISTINCREMENT + L.listsize); /把动态数组把动态数组L.elem的长度由的长度由L.listsize改为改为LISTINCREMENT + L.listsize ， ， 因为改变数组长度不一定成功，暂时把改变长度以后的数组的首地址赋值给因为改变数组长度不一定成功，暂时把改变长度以后的数组的首地址赋值给new base n if (newbase =NULL) return OVERFLOW; /改变动态数组长度失败，改变动态数组长度失败， 返回出错信息，因没有空间，无法进行

16、插入返回出错信息，因没有空间，无法进行插入 n else n L .elem = newbase; / 成功，改变长度后的动态数组的首地址重新赋值给改变长度后的动态数组的首地址重新赋值给 L.elem n L.listsize += LISTINCREMENT; /动态数组的新长度的等于原先的长度加动态数组的新长度的等于原先的长度加 上长度增量上长度增量 n 从动态数组的第从动态数组的第length个元素开始直至插入位置元素，依次后移一位个元素开始直至插入位置元素，依次后移一位 L.elem i-1=e /在动态数组的第在动态数组的第i个位置插入个位置插入e，因下标从，因下标从0开始，所以动态

17、开始，所以动态 数组的第数组的第i个位置元素是个位置元素是L.elem i-1 n +L.length; /别忘了线性表的长度加别忘了线性表的长度加1 n return OK; / n/ListInsert 20章节课件 n4、销毁线性表 nStatus DestroyList(SqList n n else n free(L.elem); /释放动态数组占用的内存 n return OK; /返回成功信息 n/DestroyList 21章节课件 上机作业上机作业： n顺序存储方式下，建立线性表（顺序存储方式下，建立线性表（12，13，24， 28，30，42，77）并输出，在线性表的第五）

18、并输出，在线性表的第五 个位置插入数据元素个位置插入数据元素25，然后删除线性表中的，然后删除线性表中的 第四个数据元素，输出变化后的线性表第四个数据元素，输出变化后的线性表,最后最后 销毁线性表。销毁线性表。 22章节课件 线性表采用顺序存储方式时线性表采用顺序存储方式时,缺点：缺点： 1）占用一组编号连续的存储单元。）占用一组编号连续的存储单元。 23章节课件 2）删除、插入操作需大量移动数据元素。）删除、插入操作需大量移动数据元素。 为什麽说占用一组编号连续的存储单元是缺点？ 某一时刻计算机内存状态某一时刻计算机内存状态 24章节课件 25章节课件 一、基本概念 1、线性表的链式存储 线

19、性表的链式存储是指用一组任意的存 储单元（可以不连续）存储线性表中的数 据元素。 26章节课件 CB A L B A C 864 128 L=(A,B,C)的顺序存储结构： L=(A,B,C)的链式存储结构： 27章节课件 8 B 128 A NULL C 864 128 ABC NULL 28章节课件 2、结点：数据和指针的组合。上图中一个蓝 色的方块就代表一个结点。 ABC null 3、链表：线性表的链式存储结构。上图三个 方块加两个箭头就是一个链表。 Data next next 数据部分命名为data：用来存放线性表中数据元素。：用来存放线性表中数据元素。 指针部分命名为指针部分命名

20、为next：存放下一个结点的地址。：存放下一个结点的地址。 29章节课件 L= 的链表（的链表（ 同学们自画）同学们自画） a1a2an head a1a2an head a1a2an 带头结点的链表带头结点的链表 )a,.,a ,a ( n21 30章节课件 二、基本操作分析二、基本操作分析 1、删除线性表的第、删除线性表的第i个数据元素个数据元素 n1）找到第i-1个结点q和第i个结点p n2）令i-1个结点q的指针域指向第i+1个结点 n3）释放结点p即第i个结点所占用的内存空间 q p ai-1aiai+1 31章节课件 2、插入操作、插入操作 在线性表的第在线性表的第i个位置插入数据

21、元素个位置插入数据元素x 1）建立新结点s,令s的数据域等于x 2）找到第i-1个结点q和第i个结点p 3）令第i-1个结点q的指针域指向新结点s 令新结点s的指针域指向新结点的指针域指向新结点p ai-1ai q x s p 32章节课件 三、源码实现 1、几点说明：、几点说明： 1）用类型定义函数声明线性表的数据类型是）用类型定义函数声明线性表的数据类型是elemtype typedef int elemtype; 2）结点的表示）结点的表示 数据和指针的组合。因为是两项的组合，所以我们用数据和指针的组合。因为是两项的组合，所以我们用 一个结构体来表示：结构体中包含一个结构体来表示：结构体

22、中包含data和和next两项。两项。 struct LNode ElemType data; /数据部分，存放线性表的某一个数据元素数据部分，存放线性表的某一个数据元素 ？ *next; / 指针部分，指示下一个结点的地址指针部分，指示下一个结点的地址 ; 33章节课件 3）线性表的表示）线性表的表示 a1a2an typedef LinkNode *LinkList ; LinkList la,lb; 34章节课件 2、基本操作的实现、基本操作的实现 1）初始化线性表初始化线性表 nStatus initlist(LinkList /开辟结点不成功，返回失败信息开辟结点不成功，返回失败信息

23、 nelse n L.data=0; /线性表的长度是线性表的长度是0 n L.next=null; /头结点的指针为空头结点的指针为空 n return ok; /返回成功信息返回成功信息 n n L 0null 35章节课件 q p ai-1aiai+1 2、删除操作、删除操作 Status ListDelete(linkList /表示表不存在，返回一个出错信息表示表不存在，返回一个出错信息 if (i L. data) return ERROR; /i值不合法，返回一个出错信息。值不合法，返回一个出错信息。 找到第找到第i-1个结点个结点q和第和第i个结点个结点p 令令i-1个结点个结

24、点q的指针域指向第的指针域指向第i+1个结点个结点 e=p.data; /用用e返回第返回第i个位置的元素的值个位置的元素的值 free(p); / 释放结点释放结点p即第即第i个结点所占用的内存空间个结点所占用的内存空间 L.data -; /因为删除了一个元素，别忘了因为删除了一个元素，别忘了L的长度减的长度减1 return OK; /返回成功信息返回成功信息 /ListDelete 36章节课件 3、插入操作、插入操作 Status ListInsert(linkList / 即即L =NULL，表示链表，表示链表L不存在，返回一个出错信息不存在，返回一个出错信息 if (i L. d

25、ata+1 | i 1) return ERROR; /i值不合法，返回出错信息值不合法，返回出错信息 s=(linknode*)malloc(sizeof(linknode); /建立新结点建立新结点s s.data=e;/令新结点的数据值等于令新结点的数据值等于e 找到第找到第i-1个结点个结点q和第和第i个结点个结点p; 令令s 的后继指针指向第的后继指针指向第i个结点个结点p 令令i-1个结点个结点q后继指针指向后继指针指向s L. data +; /别忘了线性表的长度加别忘了线性表的长度加1 return OK; /返回成功信息返回成功信息 /ListInsert ai-1ai q

26、e s 2 p 1 37章节课件 4）销毁线性表 Status DestroyList(linkList / L =null表示链表不存在，返回一个错误的信息。表示链表不存在，返回一个错误的信息。 else 释放链表中的所有结点释放链表中的所有结点 return OK; /返回一个成功的信息返回一个成功的信息 /DestroyList 38章节课件 n线性表采用顺序存储方式时线性表采用顺序存储方式时,缺点：缺点： n 1）需要一组编号连续的存储单元，零碎空间）需要一组编号连续的存储单元，零碎空间 得不到充分利用。得不到充分利用。 n 2）删除、插入操作需大量移动数据元素。）删除、插入操作需大量

27、移动数据元素。 n线性表采用链式存储时，上述两个缺点都得到线性表采用链式存储时，上述两个缺点都得到 了克服。了克服。 n1）不需要编号连续的存储单元，零碎空间得）不需要编号连续的存储单元，零碎空间得 到了充分利用。到了充分利用。 n2）删除、插入操作仅需修改指针。）删除、插入操作仅需修改指针。 39章节课件 head a1a2an 已知线性表首地址，取第i个数据元素。 40章节课件 顺序存储优点： 1）可随机存取 2）存储密度大 链式存储缺点： 1）不可随机存取，只能顺序存取 2）存储密度小 41章节课件 顺序表和链表的比较 顺序表顺序表 链表链表 一整块连续的存储 空间 零碎的存储空间零碎的

28、存储空间 插入、删除操作时 需大量移动数据 插入、删除操作时插入、删除操作时 仅需修改指针仅需修改指针 随机存取顺序存取顺序存取 存储密度大存储密度小存储密度小 42章节课件 上机作业：上机作业： 1)链式存储结构下，建立线性表（链式存储结构下，建立线性表（12，13，24， 28，30，42，77）并输出，在线性表的第五）并输出，在线性表的第五 个位置插入数据元素个位置插入数据元素25，然后删除线性表中的，然后删除线性表中的 第四个数据元素，输出变化后的线性表。第四个数据元素，输出变化后的线性表。 43章节课件 2.4其他形式的链表其他形式的链表 （1 1）循环链表）循环链表 把链表最后一个结点的指针改为指向头结点，链把链表最后一个结点的指针改为指向头结点