1、 程序设计数据结构 第 0 页第二章 线性表基本概念、线性表的应用第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页第 0 页2002-8-22002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-250 页2002-8-22002-8-252002-8-252002-8-252002-
2、8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8 修改时间修改修改时间修改时间修改时间修改时间修改时间修改时间修改时间修改时间时间修改时间修改时间修改时间修改时间修改时间修改时间-252002-8-2518 页文档编号完 成 人 张 昱完成时间完成时间修改时间修改时间2003-9-10目 录2.1 线性表的类型定义 .12.1.1 抽象数据类型线性表的定义 .12.1.2 基于 ADT List 的算法设计 .22.2 线性表的顺序表示和实现 .42.2.1
3、顺序表定义 .42.2.2 基本操作实现 .42.3 线性表的链式表示和实现 .62.3.1 线性链表 .62.3.2 静态链表 .112.3.3 循环链表 .122.3.4 双向链表 .122.3.5 其它 .132.4 线性表的应用 .142.4.1 链表的合并和分解 .142.4.2 线性表的合并(例 2-1) .152.4.3 有序表的合并(例 2-2) .172.4.4 简单的单表分解释放 .172.4.5 双向循环链表的自身变换 .18程序设计数据结构 第 1 页第二章 线性表基本概念、线性表的应用第 1 页第 1 页第 1 页第 1 页第 1 页第 1 页第 1 页第 1 页第
4、1 页第 1 页第 1 页第 1 页第 1 页第 1 页第 1 页第 1 页2002-8-22002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-251 页2002-8-22002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-
5、252002-8-252002-8 修改时间修改修改时间修改时间修改时间修改时间修改时间修改时间修改时间修改时间时间修改时间修改时间修改时间修改时间修改时间修改时间-252002-8-2518 页文档编号完 成 人 张 昱完成时间完成时间修改时间修改时间2003-9-10第 2 章 线性表2.1 线性表的类型定义2.1.1 抽象数据类型线性表的定义抽象数据类型指一个数学模型和定义在该模型上的一组操作的接口和语义说明。 不研究具体的实现，反映其逻辑特征，而其在计算机的内部表示和实现对用户是透明的。 包含各种处理器（包括计算机硬件系统、操作系统、高级语言、数据库等）中已定义并实现的数据类型（固有数
6、据类型）和用户自定义的数据类型。分类：原子类型、固定聚合类型、可变聚合类型、多形数据类型抽象数据类型定义：(D,S,P) D-数据对象，S-数据关系，P-基本操作线性表的抽象数据类型定义：ADT List数据对象：D=a i | aiElemSet, i=1,2,n, n0数据关系：R=R1,R1=|ai-1,aiD, i=2,3,n 基本操作：InitList( 2依值在线性表 LA 中进行查访 ; 3若不存在，则插入之。【算法 2.1】void union(List Lb_len = ListLength(Lb); / 求线性表的长度for (i = 1; i = i; j-) L.ele
7、mj = L.elemj-1; / 后移L.elemi -1 = e; /第 i 个元素存放在 L.elemi-1中，数组下标的起始为 0L.length = L.length+1;合法的位置：i:1.L.length+1上溢及处理：上溢发生的条件：L.lengthL.listsize，此时要先申请一个有一定增量的空间：申请成功则原空间的元素复制到新空间，修改 L.listsize，再进行插入工作；否则报错退出。算法Status ListInsert_Sq( SqList / 上溢时增加空间的分配if( L.length = L.listsize)newbase = (ElemType *)
8、realloc(L.elem,(L.listsize+ LISTINCREMENT)*sizeof(ElemType);if ( newbase = NULL ) exit(OVERFLOW);L.elem = newbase;L.listsize += LISTINCREMENT;/ 插入元素for ( j = L.length; j = i; j-) L.elemj = L.elemj-1;L.elemi-1 = e;L.length+;return OK;2) 算法分析时间频次最高的操作：移动元素。另外，上溢时的空间的再分配与复制(realloc 操作)的时间复杂度与 realloc 的
9、算法以及当前的表长相关，至少为 O(n)；但它仅在插入元素会引起上溢时才执行。若线性表的长度为 n，则： 最好情况 ：插入位置 i 为 n+1，此时无须移动元素，时间复杂度为 O(1); 最坏情况 ：插入位置 i 为 1，此时须移动 n 个元素，时间复杂度为 O(n); 平均情况 ：假设 pi 为在第 i 个元素之前插入一个元素的概率，则：程序设计数据结构 第 6 页第二章 线性表基本概念、线性表的应用第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页第 6 页2002-8-22002-8-25
10、2002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-256 页2002-8-22002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8 修改时间修改修改时间修改时间修改时间修改时间修改时间修改时间修改时间修改时
11、间时间修改时间修改时间修改时间修改时间修改时间修改时间-252002-8-2518 页文档编号完 成 人 张 昱完成时间完成时间修改时间修改时间2003-9-10插入时移动次数的期望值： 1)(niisipE等概率时，即 ，1npi 211niis T(n) = O(n)3、删除操作 ListDelete_Sq1) 算法设计参数：顺序表前移的顺序为 for ( j = i; j L.length ) return ERROR;/ 删除for ( j = i; j next；表示方法的不同，会造成对结点的操作处理的不同。2) 有头结点的单链表空表时，L 指向一结点(称为 头结点) ，该结点的数据
12、域可以不存储信息，也可存储如表长等的附加信息，结点的指针域存放 NULL，即 L-next = NULL。第一个结点和其余结点均可统一表示为其直接前驱结点的 next 域所指向的结点，即-next。4、取第 i 个元素 GetElem_L(LinkList L, int i, ElemType j = 1; / j 表示当前 p 所指向的元素在线性表中的位序while ( j next; j+; / 后移指针并计数 jif ( p = NULL | j i) return ERROR; / 第 i 个元素不存在e = p-data; / 取第 i 个元素return OK; 【性能分析】频度最
13、高的操作：寻找下一个结点，指针后移(next)执行次数：当 1i表长 n 时，频度为 i-1；否则为 n T(n) = O(n)5、插入 ListInsert_L(LinkList 链表结点的指针域是指向该结点的直接后继当 p 指向 ai-1 时，a i 可用*(p-next)表示关键步骤：（如右图所示）a1 a2L an a1 an Lai-1 aies1p2345程序设计数据结构 第 8 页第二章 线性表基本概念、线性表的应用第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页第 8 页200
14、2-8-22002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-258 页2002-8-22002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8 修改时间修改修改时间修改时间修改时间修改时间修
15、改时间修改时间修改时间修改时间时间修改时间修改时间修改时间修改时间修改时间修改时间-252002-8-2518 页文档编号完 成 人 张 昱完成时间完成时间修改时间修改时间2003-9-10找到 ai-1 的位置，即使 p 指向 ai-1 结点，可参考 GetElem_L( )的处理pNULL，则 s = (LinkList)malloc(sizeof(LNode) s-data = e s-next = p-next p-next = s注意：和不能交换，否则会导致 ai 的位置无法获取。【性能分析】其时间消耗主要在,其他为 O(1) T(n) = O(n)【有头结点的算法】算法见教科书 P
16、30 页。算法 1 有头结点的单链表中的插入算法Status ListInsert(LinkList j = 0; / 对 p,j 初始化; *p 为 L 的第 j 个结点while( p != NULL j+; / 寻找第 i-1 个结点的位置if( p = NULL | ji-1) return ERROR;/ i 小于 1 或大于表长s = (LinkList )malloc(sizeof(LNode); / 生成新结点if ( s = NULL ) exit(OVERFLOW);/ 空间分配不成功，报错返回s-data = e; s-next = p-next; / 插入 L 中p-n
17、ext = s; return OK; 【无头结点的算法】算法 2 无头结点的单链表中的插入算法Status ListInsert(LinkList / 生成新结点if ( s = NULL ) exit(OVERFLOW);/ 空间分配不成功，报错返回s-data = e; s-next = L; / 插入到链表 L 中L = s; / 修改链头指针 Lelsep = L; j = 1; / 对 p,j 初始化; *p 为链表的第 j 个结点while( p != NULL j+; / 寻找第 i-1 个结点的位置if( p = NULL | ji-1) return ERROR;/ i 小
18、于 1 或大于表长s = (LinkList )malloc(sizeof(LNode); / 生成新结点*sif ( s = NULL ) exit(OVERFLOW);/ 空间分配不成功，报错返回s-data = e; s-next = p-next; / 插入到链表 L 中p-next = s; return OK; 程序设计数据结构 第 9 页第二章 线性表基本概念、线性表的应用第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页第 9 页2002-8-22002-8-252002-8-2
19、52002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-259 页2002-8-22002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-252002-8-2552002-8-252002-8-252002-8-252002-8-252002-8-252002-8 修改时间修改修改时间修改时间修改时间修改时间修改时间修改时间修改时间修改时间时间修改时间修
20、改时间修改时间修改时间修改时间修改时间-252002-8-2518 页文档编号完 成 人 张 昱完成时间完成时间修改时间修改时间2003-9-10【思考】对比无头结点和有头结点在插入算法上的不同，分析其中的原因。6、删除 ListDelete_L(LinkList 链表结点的指针域指向该结点的直接后继当 p 指向 ai-1 时，a i 可用*(p-next)表示，ai+1 可用 *(p-next-next)表示关键步骤：（如右图所示）找到 ai-1 的位置，即使 p 指向 ai-1 结点, 可参考 GetElem_L( )的处理p-nextNULL（有待删除的结点） ，则 q = p-next
21、 (记录待释放结点的位置 ) p-next = p-next-next free(q)注意：必须在前增加步，否则在执行了后要释放的结点无法标识。【性能分析】其时间消耗主要在,其它为 O(1) T(n) = O(n)7、创建单链表（带头结点）CreateList_L(LinkList / 生成头结点if ( L = NULL ) exit(OVERFLOW);L-next = NULL; / 构造空表/ 若是循环链表，则仅将上一语句改为：L-next = L；其余不变bCycleFlag = 1; / 控制是否继续循环插入新结点/ 循环插入新结点到头结点*L 之后while(bCycleFlag)scanf( / 输入待插的元素if ( e != END_DATA) / END_DATA 为标记元素输入结束的宏名/ 非结束元素，则插入到*L 之后s = (LinkList )malloc(sizeof(LNode); ai-1 ai1pai+1234存储池qa1esL12
