数据结构性表

《数据结构性表》由会员分享，可在线阅读，更多相关《数据结构性表（115页珍藏版）》请在金锄头文库上搜索。

1、数据结构-线性表齐恒大黑楼 B0912什么是云计算?云计算定义云计算（CloudComputing）：是分布式处理(DistributedComputing)、并行处理(ParallelComputing)和网格计算(GridComputing)的发展，或者说是这些计算机科学概念的商业实现。是指基于互联网的超级计算模式-即把存储于个人电脑、移动电话和其他设备上的大量信息和处理器资源集中在一起，协同工作。在极大规模上可扩展的信息技术能力向外部客户作为服务来提供的一种计算方式。40多多亿的移的移动电话一一 2010年 数据来源: Nokia个人个人电脑和和笔笔记本本电脑企企业电脑和服和服务器器PD

2、A云计算综述n数据在云端：不怕丢失,不必备份,可以任意点的恢复 ；n软件在云端：不必下载自动升级 ；n无所不在的计算：在任何时间，任意地点，任何设备登录后就可以进行计算服务；n无限强大的计算：具有无限空间的，无限速度。硬件为中心硬件为中心软件为中心软件为中心 服务为中心服务为中心 PCC/S云计算云计算发展路线并行计算集群计算网格计算云计算云计算体系特点n通过Internet接入n不需要自身具有IT技术来实施n第三方提供n资源共享n无多余功能开发n无多余费用n系统延续性好Cloud Applications(“Software-as-a-Service”)Cloud Platforms(“Pl

3、atform-as-a-Service”)Cloud StorageCloud Servers(“Infrastructure-as-a-Service”)云计算三种服务方式nSAAS（SoftwareasaService）nPAAS（PlatformasaService）nIAAS（InfrastructureasaService）1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 算法的描述和算法分析算法的描述和算法分析第一章回顾什么是数据结构什么是数据结构描述描述非数值计算问题非数值计算问题的数学模型不是

4、数学的数学模型不是数学方程，而是方程，而是树、表和图树、表和图之类的之类的数据结构数据结构。数据结构描述现实世界实体的数据结构描述现实世界实体的数学模型数学模型及及其上的其上的操作操作在计算机中的在计算机中的表示和实现表示和实现。基本概念和术语基本概念和术语数据数据（Data)Data)数据元素数据元素（Data elementData element）数据项数据项（Data itemData item）数据对象数据对象（Data ObjectData Object）数据结构数据结构（Data Structure）-带带结构结构的数据的数据元素的集合。包括数据的逻辑结构和数据的存元素的集合。包

5、括数据的逻辑结构和数据的存储结构。储结构。 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：抽象数据类型抽象数据类型(Abstract Data Type (Abstract Data Type 简称简称ADT)ADT) 是指一个数学模型数学模型以及定义在此数学模型上的一组操作操作。e.g. 矩阵（求转置、加、乘、逆、特征值）算法的

6、描述和算法分析算法的描述和算法分析一、算法（一、算法（algorithm） 解决某一特定问题的解决某一特定问题的具体步骤的描具体步骤的描述述， 是是指令的有限序列指令的有限序列。有穷性、确定性、可行性、有输入、有输出有穷性、确定性、可行性、有输入、有输出 二、算法设计的原则二、算法设计的原则设计算法时，通常应考虑达到以下目标：1 正确性正确性2. . 可读性可读性3 健壮性健壮性4 高效率与低存储量需求高效率与低存储量需求三、算法分析三、算法分析算法算法 = = 控制结构控制结构 + + 原操作原操作 （固有数据类型的操作）算法的执行时间算法的执行时间 =原操作原操作(i)(i)的执行次数的执

7、行次数原操作原操作(i)(i)的执行时间的执行时间第二章第二章线性表线性表线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。是一个数据元素的是一个数据元素的有序（次序）集有序（次序）集2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2

8、 线性表类型的实现线性表类型的实现 顺序映象顺序映象2.1线性表的类型定义线性表的类型定义抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空表。数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n / 设线性表为 (a1，a2, . . . ，ai，. . . ，an), / 称 i 为 ai 在线性表中的位序位序。 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 A

9、DT List InitList( &L )操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操作 结构销毁操作结构销毁操作DestroyList( &L )初始条件：操作结果：线性表 L 已存在。销毁线性表 L。ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraverse(L, visit( )引用型操作引用型操作: : ListEmpty( L )

10、初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（判断线性表是否为空）ListLength( L )初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度） PriorElem( L, cur_e, &pre_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）NextElem( L, cur_e, &next_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，n

11、ext_e无定义。（求数据元素的后继）GetElem( L, i, &e ) 初始条件： 操作结果：线性表L已存在，且 1iLengthList(L)。用e返回L中第i个元素的值。（求线性表中某个数据元素）LocateElem( L, e, compare( ) )初始条件：操作结果：线性表L已存在，e为给定值，compare( )是元素判定函数。返回L中第1个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。（定位函数） ListTraverse(L, visit( )初始条件：操作结果：线性表L已存在，Visit() 为某个访问函数。依次对L的每个元素调用函数

12、visit( )。一旦visit( )失败，则操作失败。（遍历线性表）加工型操作加工型操作 ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e) ClearList( &L )初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）PutElem( &L, i, &e )初始条件：操作结果：线性表L已存在，且 1iLengthList(L) 。L中第i个元素赋值为e的值。（改变数据元素的值） ListInsert( &L, i, e )初始条件：操作结果：线性表L已存在，且 1iL

13、engthList(L)+1 。在L的第i个元素之前插入新的元素e，L的长度增1。（插入数据元素）ListDelete(&L, i, &e)初始条件：操作结果：线性表L已存在且非空， 1iLengthList(L) 。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）利用上述定义的线性表操作线性表操作 可以实现其它更复杂的操作 假设:有两个集合集合 A 和和 B ，分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合现要求一个新的集合AA B。例例 2-1 要求对线性表作如下操作：扩大线性表 LA，将存在于存在于LB 中中

14、而不存在于不存在于LA 中中的数据元素逐个插插入入到到LA 中中去。上述问题可演绎为：1从线性表从线性表LB中依次察看每个数据元素中依次察看每个数据元素;2依值在线性表依值在线性表LA中进行查访中进行查访; 3若不存在，则插入之。若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步骤：操作步骤： GetElem(Lb, i, &e); / 取取Lb中第中第i个元素赋给个元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len

15、, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List &La, List Lb) La_len = ListLength(La); / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union 已知已知一个允许包含重复元素的集合包含重复元素的集合 B，试构造构造一个不允许包含重复元素的不允许包含重复元素的集合集合 A，使使 A中只包含中只包含 B 中所有值各中所有值各不相不相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。

16、例例 2-2从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相同相同上述问题可演绎为：void union(List &La, List Lb) / union GetElem(Lb, i, &e); / 取取Lb中第中第 i 个元素赋给个元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i = Lb_len; i+

17、) InitList(La); / 构造(空的)线性表LALa_len=ListLength(La); Lb_len=ListLength(Lb); 若线性表中的数据元素相互之间可以比较比较，并且数据元素在线性表中依值依值非递减或非递增有序非递减或非递增有序排列排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表有序表(Ordered List)(Ordered List)。试改变结构，以有序表有序表表示集合。例如例如：（2，3，3，5，6，6，6，8，12）对集合 B 而言， 值相同的数据元素必定相邻；值相同的数据元素必定相邻；对集合 A 而言， 数据元素依

18、值从小至大的顺序插入。数据元素依值从小至大的顺序插入。因此，数据结构改变了，数据结构改变了， 解决问题的策略也相应要改变。解决问题的策略也相应要改变。void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, &e); / 取取Lb中第中第i个元素赋给个元素赋给 eIf (ListEmpty(La) | !equal (en, e) L

19、istInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之例2-3将将A、B两个有序表合并成有序表两个有序表合并成有序表C仍采用线性表表示void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 若 La 不空 while (j=Lb_len) / 若

20、Lb 不空 InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb); / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; while (i = La_len) / 当La不

21、空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素2.2线性表类型的实现线性表类型的实现顺序映像最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令 y y 的存储位置和的存储位置和 x x 的存储位置相邻的存储位置相邻。顺序映象顺序映象 以以 x 的存储位置和的存储位置和 y 的存储位置之的存储位置之间某

22、种关系表示逻辑关系间某种关系表示逻辑关系。 用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C C为一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址顺序映像的顺序映像的 C 语言描述语言描述typedef struct SqL

23、ist; / 俗称 顺序表顺序表#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位)线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) /

24、 插入元素插入元素ListDelete(&L, i) / 删除元素删除元素Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem = (ElemType*) malloc (LIST_INIT_SIZE sizeof (ElemType);If (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK; int LocateElem_Sq(SqList L, ElemType e, Status

25、(*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的时间复杂度时间复杂度为：为：i = 1; / i i 的初值为第的初值为第1 1个元素的位序个元素的位序p = L.elem; / p p 的初值为第的初值为第1 1个元素的存储位置个元素的存储位置while (i = L.length & !(*compare)(*p+, e) +i

26、;if (i = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+L.length; / 表长增1return OK;if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCRE

27、MENT; / 增加存储容量if (i L.length+1) return ERROR; / 插入位置不合法 21 18 30 75 42 56 87 21 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length1pppq87564266q = &(L.elemi); / q 指示插入位置for (p = &(L.elemL.length); p = q; -p) *(p+1) = *p;p考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移

28、动元素次数的期望值为： 若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：线性表操作 ListDelete(&L, i, &e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减1a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 Status ListDelete_Sq (SqList &L, int i) / ListDelete_Sqfor (p= &(L.ele

29、mi+1; p = q; +p) *(p-1) = *p; /被删除元素之后的元素左移被删除元素之后的元素左移-L.length; / 表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为: : O( ListLength(L)q = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 删除位置不合法删除位置不合法21 18 30 75 42 56 87 21 18 30 75L.length1pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for

30、(+p; p next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入L 线性表的操作 GetElem(L, i, &e)在单链表中的实现例:211830754256 pppj1 2 3 因此，查找第因此，查找第 i 个数据元素的基本个数据元素的基本操作为：操作为：移动指针移动指针p，比较，比较 j 和和 i 。 单链表是一种顺序存取的结构，为找第单链表是一种顺序

31、存取的结构，为找第 i 个个数据元素，必须先找到其前趋结点数据元素，必须先找到其前趋结点-第第 i-1 个数据元素。个数据元素。 编程实现时，令指针编程实现时，令指针 p p 始终始终指向指向线性表中第线性表中第 j j 个数据元素。个数据元素。 Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素 / GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p = L-next; j = 1; / p p指向第一个结点，指向

32、第一个结点，j j为计数器为计数器while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空if ( !p | ji ) return ERROR; / 第第 i i 个元素不存在个元素不存在e = p-data; / 取得第取得第 i i 个元素的值个元素的值return OK;ai-1 线性表操作 ListInsert(&L, i, e) 在单链表中的实现： 有序对有序对 改变为改变为 和和 eaiai-1 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作

33、为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。 可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但若要在第指针。但若要在第 i 个结点之前插入元个结点之前插入元素，修改的是第素，修改的是第 i-1 个结点的指针。个结点的指针。 Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点个结点之前之前插入新的元素插入新的元素 e / L

34、instInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; p-next = s; / 插入return OK; eai-1aiai-1sp线性表的操作ListDelete (&L, i, &e)在链表中

35、的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点个结点p p，修，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 / ListDelete_L算法的算法的时间复杂度时间复杂

36、度为: O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / 寻找第 i 个结点，并令 p 指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);return OK;操作 ClearList(&L) 在链表中的实现:void ClearList(&L) / 将单链表重新置为一个空表 while (L-next) p=L-next; L-next=p-next; / Cle

37、arListfree(p);算法时间复杂度：O(ListLength(L)四、一个带头结点的线性链表类型四、一个带头结点的线性链表类型typedef struct LNode / 结点类型结点类型 ElemType data; struct LNode *next; *Link, *Position;Status MakeNode( Link &p, ElemType e ); / 分配由 p 指向的值为e的结点，并返回OK， / 若分配失败，则返回 ERRORvoid FreeNode( Link &p ); / 释放 p 所指结点typedef struct / 链表类型链表类型 Link

38、 head, tail, current; / 分别指向链表头结点、 最后一个结点和当前 / 访问结点的指针 int len; / 指示链表长度 LinkList;链表的基本操作链表的基本操作: : 结构初始化和销毁结构初始化和销毁 Status InitList( LinkList &L ); / 构造一个空的线性链表 L，其头指针、 / 尾指针和当前指针均指向头结点， / 表长为零。Status DestroyList( LinkList &L ); / 销毁线性链表 L，L不再存在。 O(1) O(n) 引用型操作引用型操作 Status ListEmpty ( LinkList L )

39、; /判表空判表空int ListLength( LinkList L ); / 求表长求表长Status Prior( LinkList L ); / 改变当前指针，指向其前驱改变当前指针，指向其前驱Status Next ( LinkList L ); / 改变当前指针，指向其后继改变当前指针，指向其后继ElemType GetCurElem ( LinkList L ); / 返回当前指针所指数据元素返回当前指针所指数据元素O(1)O(1)O(n)O(1)O(1) Status LocatePos( LinkList L, int i ); / 改变当前指针，指向第i个结点Status

40、LocateElem (LinkList L, ElemType e, ); / 若存在与e 相同的元素，则移动当前指针 /指向满足条件的元素的前驱， /并返回OK; 否则返回ERRORStatus ListTraverse(LinkList L, Status(*visit)() ); / 依次对L的每个元素调用函数visit()O(n)O(n)O(n) 加工型操作加工型操作Status ClearList ( LinkList &L ); / 重置 L 为空表Status SetCurElem(LinkList &L, ElemType e ); / 更新当前指针所指数据元素Status

41、Append ( LinkList &L, Link s ); / 将表S链接在表L之后Status InsAfter ( LinkList &L, Elemtype e ); /在当前指针所指结点之后链接一个新结点Status DelAfter ( LinkList &L, ElemType& e ); / 删除当前指针之后的结点 O(1)O(n) O(s) O(1) O(1)Status InsAfter( LinkList& L, ElemType e ) / 将数据元素e插入在线性链表L中当前指针所指结点 / 之后,并返回OK; 否则返回ERROR。 / InsAfter if ( !

42、 L.current ) return ERROR; if (! MakeNode( s, e) ) return ERROR; s-next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; return OK;Status DelAfter( LinkList& L, ElemType& e ) / 若当前指针及其后继在链表中，则删除线性链表L中当前 / 指针所指结点之后的结点，并返回OK; 否则返回ERROR。 /DelAfterif ( !(L.current

43、 & L.current-next ) ) return ERROR;q = L.current-next; e=q-data; L.current-next = q-next;if (L.tail = q) L.tail = L.current;FreeNode(q);return OK; 1. 双向链表双向链表五、其它形式的链表五、其它形式的链表typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuL

44、inkList; 最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 . an 2. 循环链表循环链表 和单链表的差别仅在于，判别判别链表中最后一个结点的条件条件不再是“后继是否后继是否为空为空”，而是“后继是否为头结点后继是否为头结点”。双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . an双向链表的操作特点：双向链表的操作特点：“查询查询” 和单链表相同。和单链表相同。“插入插入” 和和“删除删除”时需要同时修时需要同时修改改两个方向上两个方向上的指针。的指针。ai-1aies-next = p-next; p-next = s;s-next-prior = s; s

45、-prior = p;psai-1ai插入插入ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1六、有序表类型六、有序表类型ADT Ordered_List 数据对象数据对象: S = xi|xi OrderedSet ， i=1,2,n, n0 集合中任意两个元素之间均可以进行比较数据关系数据关系: :R = | xi-1, xi S, xi-1 xi, i=2,3,n 2.4 2.4 一元多项式的表示和相加一元多项式的表示和相加在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p1, ，

46、pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？ 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指数为ei 的项的非零系数，且 0 e1 e2 em = n可用下列线性表表示：（p1, e1）, (p2, e2), , (pm,em) ） P999(x) = 7x3 - 2x12 - 8x999例如例如:可用线性表 ( (7, 3), (-2, 12), (-8, 999) )表示ADT Pol

47、ynomial 数据对象数据对象： 数据关系数据关系：抽象数据类型一元多项式的定义如下：D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个每个元素包含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值中的指数值ai中的指数值中的指数值 CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ) 基本操作基本操作：操作结果操作结果：输入 m 项的系数和指数， 建立一元多项式 P。初始条件初始条件：一元多项

48、式 P 已存在。操作结果操作结果：销毁一元多项式 P。初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：打印输出一元多项式 P。 PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) ADT Polynomial初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：返回一元多项式 P 中的项数。初始条件初始条件：一元多项式 Pa 和 Pb 已存在。操作结果操作结果：完成多项式相加/相减运算，即： Pa = PaPb 或Pa = Pa-Pb 一元多项式的实现：链式结构一元多项式的实现：链式结构typed

49、ef struct / 项项的表示 float coef; / 系数系数 int expn; / 指数指数 term, ElemType; typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式用带表头结点的有序链表表示多项式结点的数据元素类型定义为:Status CreatPolyn ( polynomail &P, int m ) / 输入输入m项的系数和指数，建立表示一元多项式的有序链表项的系数和指数，建立表示一元多项式的有序链表P / CreatPolynInitList (P); e.coef = 0.0; e.expn = -1

50、; SetCurElem (h, e); / 设置头结点的数据元素for ( i=1; i=m; +i ) / 依次输入 m 个非零项return OK;scanf (e.coef, e.expn);if (!LocateElem ( P, e, (*cmp)() ) if ( !InsAfter ( P, e ) ) return ERROR; 注意注意: : 1. .输入次序不限输入次序不限; ;2. .指数相同的项只能输入一次。指数相同的项只能输入一次。本章小结本章小结1.1.了了解解线线性性表表的的逻逻辑辑结结构构特特性性是是：数数据据元元素素之之间间存存在在着着线线性性关关系系，在在计计算算机机中中表表示示这这种种关关系系的的两两类类不不同同的的存存储储结结构构是是顺顺序序存存储储结结构构和和链链式式存存储储结结构构。用用前前者者表表示示的的线线性性表表简简称称为为顺顺序序表表，用用后后者者表表示的线性表简称为示的线性表简称为链表链表。本章小结本章小结2.2.熟练掌握这两类存储结构的描述方法，熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。以及线性表的各种基本操作的实现。3.3.能够从时间和空间复杂度的角度综合比能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其较线性表两种存储结构的不同特点及其适用场合。适用场合。