《数据结构第二章 线性表part5》由会员分享，可在线阅读，更多相关《数据结构第二章 线性表part5（56页珍藏版）》请在文档大全上搜索。
1、用上述定义的单链表实现线性表的操作用上述定义的单链表实现线性表的操作时，存在的问题时，存在的问题：改进链表的设置：改进链表的设置：1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前位置的指当前位置的指针针” 三个数据域；三个数据域； 2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i ”改变为改变为“指针指针 p
2、 ”。四、改进的线性链表类型四、改进的线性链表类型typedef struct LNode / 结点类型结点类型 ElemType data; struct LNode *next; *Link, *Position;typedef struct / 链表类型链表类型 Link head, tail; / 分别指向头结点和最后分别指向头结点和最后 一个结点的指针一个结点的指针 int len; / 指示链表长度指示链表长度 Link current; / 指向当前被访问的结点的指针，指向当前被访问的结点的指针， / 初始位置指向头结点初始位置指向头结点 LinkList; a1 ai . an
3、 头结点头结点headcurrenttailStatus MakeNode( Link &p, ElemType e ); / 分配由分配由 p 指向的值为指向的值为e的结点，并返回的结点，并返回OK， / 若分配失败，则返回若分配失败，则返回 ERRORvoid FreeNode( Link &p ); / 释放释放 p 所指结点所指结点链表的基本操作链表的基本操作: : 结构初始化和销毁结构结构初始化和销毁结构 Status InitList( LinkList &L ); / 构造一个空的线性链表构造一个空的线性链表 L，其头指针、，其头指针、 / 尾指针和当前指
4、针均指向头结点，表长尾指针和当前指针均指向头结点，表长 / 为零。为零。 Status DestroyList( LinkList &L ); / 销毁线性链表销毁线性链表 L L，L L不再存在。不再存在。 O(1) O(n) 引用型操作引用型操作 Status ListEmpty ( LinkList L ); /判表空判表空int ListLength( LinkList L ); /求表长求表长Status Prior( LinkList L ); /改变当前指针指向其前驱改变当前指针指向其前驱Status Next ( LinkList L ); /改变当前指针指向其后继改变
5、当前指针指向其后继ElemType GetCurElem ( LinkList L ); /返回当前指针所指数据元素返回当前指针所指数据元素O(1)O(1)O(n)O(1)O(1) Status LocatePos( LinkList L, int i ); /改变当前指针指向第改变当前指针指向第i i个结点个结点Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType); /若存在与若存在与e e 满足函数满足函数compare( )compare( )判定关系的判定关系的 /元素，则移动当
6、前指针指向第元素，则移动当前指针指向第1 1个满足条件的个满足条件的 /元素的前驱，并返回元素的前驱，并返回OK; OK; 否则返回否则返回ERRORERRORStatus ListTraverse(LinkList L, Status(*visit)() ); /依次对依次对L L的每个元素调用函数的每个元素调用函数visit()visit()O(n)O(n)O(n) 加工型操作加工型操作 Status ClearList ( LinkList &L ); /重置重置 L L 为空表为空表Status SetCurElem(LinkList &L, ElemType e );
7、 /更新当前指针所指数据元素更新当前指针所指数据元素Status Append ( LinkList &L, Link s ); /在表尾结点之后链接一串结点在表尾结点之后链接一串结点Status InsAfter ( LinkList &L, Elemtype e ); /将元素将元素 e e 插入在当前指针之后插入在当前指针之后Status DelAfter ( LinkList &L, ElemType& e ); /删除当前指针之后的结点删除当前指针之后的结点 O(1)O(n) O(s) O(1) O(1)Status InsAfter( LinkLis
8、t& L, ElemType e ) /若当前指针在链表中，则将数据元素若当前指针在链表中，则将数据元素e e插入在线性插入在线性 /链表链表L L中当前指针所指结点之后中当前指针所指结点之后, ,并返回并返回OK;OK; /否则返回否则返回ERRORERROR。 / InsAfter if ( ! 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;
9、L.current = s; return OK;Status DelAfter( LinkList& L, ElemType& e ) /若当前指针及其后继在链表中，则删除线性链表若当前指针及其后继在链表中，则删除线性链表L L中当前中当前 /指针所指结点之后的结点，并返回指针所指结点之后的结点，并返回OK; OK; 否则返回否则返回ERRORERROR。 /DelAfterif ( !(L.current & L.current-next ) ) return ERROR;q = L.current-next;L.current-next = q-next;if (
10、L.tail = q) L.tail = L.current;e=q-data; FreeNode(q);return OK;例一例一Status ListInsert_L(LinkList L, int i, ElemType e) /在带头结点的单链线性表在带头结点的单链线性表L L的第的第i i个元素之前插入元素个元素之前插入元素e e / ListInsert_L 利用上述定义的线性链表如何完利用上述定义的线性链表如何完成线性表的其它操作成线性表的其它操作 ？if (!LocatePos (L, i-1) return ERROR; /i i值不合法，第值不合法，第i-1i-1个结点不
11、存在个结点不存在if (InsAfter (L, e) return OK; /完成插入完成插入else return ERROR;Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ， int (*compare) (ElemType,ElemType) /归并有序表归并有序表 La La 和和 Lb ,Lb ,生成新的有序表生成新的有序表 LcLc, , /并在归并之后销毁并在归并之后销毁La La 和和 Lb,Lb, /compare compare 为指定的元素大小判定函数为指定的元素大小判定函
12、数 / MergeList_L例二例二if ( !InitList(Lc) return ERROR; /存储空间分配失败存储空间分配失败while (!( a=MAXC & b=MAXC) / LaLa或或LbLb非空非空 LocatePos (La, 0); LocatePos (Lb, 0 ) ; /当前指针指向头结点当前指针指向头结点if ( DelAfter( La, e) a = e; / 取得取得LaLa表中第一个元素表中第一个元素a a else a = MAXC; / MAXCMAXC为常量最大值为常量最大值if ( DelAfter( Lb, e) b = e; /
13、 取得取得LbLb表中第一个元素表中第一个元素b b else b = MAXC; / a a和和b b为两表中当前比较元素为两表中当前比较元素DestroyList(La); DestroyList(Lb); / 销毁链表销毁链表 La La 和和 LbLbreturn OK; if (*compare)(a, b) next= =LpL3.双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . and结构特性：结构特性：d-next-prior=d- prior - next=d双向链表的操作特点：双向链表的操作特点： 有些操作如：有些操作如：ListLength、GetElem、和
14、、和LocateElem等仅需涉及一个方向的指针，所等仅需涉及一个方向的指针，所以以和单链表相同。和单链表相同。 “插入插入”和和“删除删除”时需要同时修改时需要同时修改两个方向上的指针。两个方向上的指针。ai-1aies-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) /
15、在带头结点的双向循环链表在带头结点的双向循环链表L中第中第i 个结点之前个结点之前 / 插入新的元素插入新的元素 e，1i 表长表长+1。 / ListInsert_DuL算法的算法的时间复杂度时间复杂度为为:O(ListLength(L)if (!(p=GetElem_DuL(L,i) / 第第i 个元素的位置指针个元素的位置指针p return ERROR; / p=NULL，即第，即第i个元素不存在个元素不存在if (!(s=(DuLinkList)malloc(sizeof(DuLNode) return ERROR; / 存储空间分配失败存储空间分配失败S-data=e;s- pri
16、or = p- prior; p- prior -next = s;s-next= s; p-prior = s;return OK; Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) / 删除带头结点的双向循环链表删除带头结点的双向循环链表L中第中第i 个元素个元素 / i的合法值为的合法值为 1i 表长表长+1。 / ListDelete_DuL算法的算法的时间复杂度时间复杂度为为:O(ListLength(L)if (!(p=GetElem_DuL(L,i) / 第第i 个元素的位置指针个元素的位置指针p r
17、eturn ERROR; / p=NULL，即第，即第i个元素不存在个元素不存在E=p-data; / 存储空间分配失败存储空间分配失败p- prior -next = p-next;p-next-prior= p-prior;free(p);Return OK;4.静态链表静态链表 借用一维数组来描述线性链表，称静态链表。借用一维数组来描述线性链表，称静态链表。这种描述方法便于在不设这种描述方法便于在不设“指针指针”类型的高级程序类型的高级程序语言中使用链表结构。语言中使用链表结构。 其类型说明如下：其类型说明如下：#define MAXSIZE 1000 / 链表的最大长度链表的最大长度T
18、ypedef struct elemtype data; int cur; component, SlinkListMAXSIZE;1ZHAO2QIAN3SUN4LI5ZHOU6WU7ZHENG8WANG0静态链表示例静态链表示例0123456789101ZHAO2QIAN3SUN4LI9ZHOU6WU8ZHENG8WANG0SHI5012345678910原始状态插入“SHI”和删除“ZHENG”之后的状态 如上描述的链表中，数组的一个分量表示一如上描述的链表中，数组的一个分量表示一个结点，同时用游标（指示器个结点，同时用游标（指示器cur）代替指针指示）代替指针指示结点在数组中的位置。数组
19、的第零分量可看成头结点在数组中的位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点。结点，其指针域指示链表的第一个结点。 这种存储结构仍需要预先分配一个较大的存这种存储结构仍需要预先分配一个较大的存储空间，但在作线性表的插入和删除操作时不需储空间，但在作线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。构的主要优点。 为了和指针型描述的线性链表相区别，我们为了和指针型描述的线性链表相区别，我们给这种用数组描述的链表起名为给这种用数组描述的链表起名为静态链表静态链表。 假设S为SLinkList型的变量，则S
20、0.cur指示第一个结点在数组中的位置。 若设i=S0.cur，则Si.data存储线性表的第一个元素，且Si.cur指示第二个结点在数组中的位置。 一般情况，若第i个分量表示链表的第k个结点，则Si.cur指示第k+1个结点的位置。 因此，在静态链表中实现线性表的操作和动态链表相似，以整型游标i代替动态指针p，i= Si.cur的操作为指针后移（类似于p=p-next）。静态链表中定位函数静态链表中定位函数LocateElem的实现的实现int LocateElem_SL(SLinkList S,ElemType e) /在静态单链线性表在静态单链线性表L L中查找第中查找第1 1个值为个值
21、为e e的元素。的元素。 /若找到，则返回它在若找到，则返回它在L L中的位序中的位序; ; 否则返回否则返回0 0。 i=S0.cur; / i 指示表中第一个结点指示表中第一个结点 while (i&Si.data!=e) i=Si.cur; /在表中顺链查找在表中顺链查找 return i; / LocateElem_SL 类似地可写出在静态链表中实现插入和删除操类似地可写出在静态链表中实现插入和删除操作的算法。作的算法。 由上述图例可见，静态链表中指针修改的操作由上述图例可见，静态链表中指针修改的操作和单链表基本相同，所不同的是，需由用户自己实和单链表基本相同，所不同的是，需由
22、用户自己实现现malloc和和free这两个函数。为了辩明数组中哪些这两个函数。为了辩明数组中哪些分量未被使用，解决的办法是将所有未被使用过的分量未被使用，解决的办法是将所有未被使用过的以及被删除的分量用游标链成一个备用的链表，每以及被删除的分量用游标链成一个备用的链表，每当进行插入时便可从备用链表上取得第一个结点作当进行插入时便可从备用链表上取得第一个结点作为待插入的新结点；反之，在删除时将从链表中删为待插入的新结点；反之，在删除时将从链表中删除下来的结点链接到备用链表上。除下来的结点链接到备用链表上。六、有序表类型六、有序表类型ADT Ordered_List 数据对象数据对象: S =
23、xi|xi OrderedSet ， i=1,2,n, n0 集合中集合中任意两个任意两个元素之间元素之间均可以均可以进行比较进行比较数据关系数据关系: :R = | xi-1, xi S, xi-1 xi, i=2,3,n LocateElem( L, e, &q, int(*compare)(ElemType,ElemType) ) 初始条件初始条件：有序表有序表L已存在。已存在。 操作结果操作结果：若有序表若有序表L中存在元素中存在元素e e，则，则q指示指示L中中 第一个值为第一个值为e 的元素的位置的元素的位置，并返回函，并返回函 数值数值TRUE；否则；否则q 指示第一个大
24、于指示第一个大于e 的元素的前驱的位置的元素的前驱的位置，并返回函数值，并返回函数值 FALSE。 基本操作：基本操作： Compare是一个是一个有序判定函数有序判定函数( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 )例如例如:若若 e = 45, 则则 q 指向指向 若若 e = 88, 则则 q 指向指向表示值为表示值为 88 的元素应插入的元素应插入在该指针所指结点之后。在该指针所指结点之后。回顾例回顾例2-2中中的算法的算法void purge(List &La, List Lb) / Lb为有序表为有序表 InitList(LA); La
25、_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) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之算法时间复杂度：算法时间复杂度：O(n)链式存储结构的优缺点：链式存储结构的优缺点：
26、 插入和删除运算时，无须移动表中元素的位插入和删除运算时，无须移动表中元素的位置，只需修改有关结点的指针内容；置，只需修改有关结点的指针内容； 不能随机访问表中元素，访问时间与元素在不能随机访问表中元素，访问时间与元素在表中的位置有关；表中的位置有关； 不需要一块连续的存储空间，只要能存放一不需要一块连续的存储空间，只要能存放一个数据元素的空闲结点就可以被利用；个数据元素的空闲结点就可以被利用； 表的规模易扩充。表的规模易扩充。在实际应用中采用哪一种存储结构更合适？在实际应用中采用哪一种存储结构更合适？ 对这个问题不能一概而论，这涉及到不同实现方法的选对这个问题不能一概而论，这涉及到不同实现方
27、法的选择问题。一般而言，对存储结构的选择应从以下几条区别：择问题。一般而言，对存储结构的选择应从以下几条区别： 应有利于基本运算的实现。因为运算的具体实现以存应有利于基本运算的实现。因为运算的具体实现以存储结构的确定为前提，存储结构在一定程度上、一定范围内储结构的确定为前提，存储结构在一定程度上、一定范围内决定了运算的实现是否方便、高效；决定了运算的实现是否方便、高效； 应有利于数据的特性。除了数据的逻辑性外，其他的应有利于数据的特性。除了数据的逻辑性外，其他的诸如数据规模也应在选择存储结构时加以考虑；诸如数据规模也应在选择存储结构时加以考虑； 应有利于软件环境。数据的存放方式对存储结构有不应
28、有利于软件环境。数据的存放方式对存储结构有不同的要求，所以应依据情况适当选择存储结构。具体而言，同的要求，所以应依据情况适当选择存储结构。具体而言，即应主要从存储空间、运算时间、程序设计语言三方面考虑。即应主要从存储空间、运算时间、程序设计语言三方面考虑。即即 存储空间存储空间 顺序表要求预先分配存储空间，一般在程序执行之前顺序表要求预先分配存储空间，一般在程序执行之前是难以估计存储空间大小，估计过大会造成浪费，估计过是难以估计存储空间大小，估计过大会造成浪费，估计过小又会产生空间溢出。而链式存储结构的存储空间是动态小又会产生空间溢出。而链式存储结构的存储空间是动态分配，只要内存空间有空间，就
29、可动态申请内存空间，不分配，只要内存空间有空间，就可动态申请内存空间，不会产生溢出。对于存储空间的考虑也可以存储密度的大小会产生溢出。对于存储空间的考虑也可以存储密度的大小来衡量。其中存储密度的大小定义为一个结点数据本身所来衡量。其中存储密度的大小定义为一个结点数据本身所占用的存储量与结点结构所占用的存储量的比值。一般地，占用的存储量与结点结构所占用的存储量的比值。一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为的存储密度为1，而链式存储结构的存储密度则小于，而链式存储结构的存储密度则小于1。 运算时间运算时间 顺序存储结
30、构是一种随机存取的结构，便于元素的随机顺序存储结构是一种随机存取的结构，便于元素的随机访问。即表中任一元素都可在访问。即表中任一元素都可在O(1)时间复杂度情况下迅速而时间复杂度情况下迅速而直接地存取。而链式存储结构，必须从头指针开始顺着链扫直接地存取。而链式存储结构，必须从头指针开始顺着链扫描才能取得，一般情况下其时间复杂度为描才能取得，一般情况下其时间复杂度为O(n)，所以对于那，所以对于那些只进行查找运算而很少做插入和删除等的运算，宜采用顺些只进行查找运算而很少做插入和删除等的运算，宜采用顺序存储结构。但在顺序表中进行元素的插入和删除运算时，序存储结构。但在顺序表中进行元素的插入和删除运
31、算时，需移动大量元素，平均要移动约半数的元素。尤其是当表中需移动大量元素，平均要移动约半数的元素。尤其是当表中每个元素的信息量较复杂时所花费的时间就更为可观。而采每个元素的信息量较复杂时所花费的时间就更为可观。而采用链式存储结构，由于进行元素的插入或删除，只需修改指用链式存储结构，由于进行元素的插入或删除，只需修改指针并结合一定的查找。所以，对于那些需要经常频繁地进行针并结合一定的查找。所以，对于那些需要经常频繁地进行元素的插入和删除运算的线性表，其存储结构应采用链式存元素的插入和删除运算的线性表，其存储结构应采用链式存储结构。储结构。 程序设计语言程序设计语言 这主要是指依据某种高级语言是否
32、提供指针类型或者这主要是指依据某种高级语言是否提供指针类型或者依据实际需要决定存储结构是选用静态链表还是动态链表。依据实际需要决定存储结构是选用静态链表还是动态链表。 总之，线性表的顺序实现和链式实现各有优缺点，是总之，线性表的顺序实现和链式实现各有优缺点，是无法笼统地认定哪种优，哪种劣。只能根据实际问题的具无法笼统地认定哪种优，哪种劣。只能根据实际问题的具体实现需要，对各方面的优缺点加以综合平衡来确定适宜体实现需要，对各方面的优缺点加以综合平衡来确定适宜的存储结构。的存储结构。 在数学上，一元在数学上，一元n n次多项式次多项式 Pn ( x)= p0 + p1 x+ p2 x2 + + p
33、n xn由由n+1n+1个系数唯一确定，可用线性表个系数唯一确定，可用线性表P P来表示来表示 P =（p0 ,p1 , p2 , pn ）每一项的指数每一项的指数 i 隐含在其系数隐含在其系数Pi的序号里。的序号里。 假设假设Q Qm m(x)(x)是一元是一元m m次多项式次多项式, ,同样可用线性表同样可用线性表Q Q来表示来表示 Q =（q0 ,q1 , q2 , qm ） 设设mnmn，则两个多项式相加的结果，则两个多项式相加的结果 Rn ( x)= Pn ( x)+ Q Qm m(x) (x) 可用线性表可用线性表R R表示表示 R=( p0+q0 , p1+q1, p2+q2 ,
34、 , pm+qm, pm+1, , pn) 在通常应用中，多项式的次数很高且变化很大，在通常应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在使得顺序存储结构的最大长度很难确定，特别是在处理形如处理形如 S(x) = 1 + 3x10000 2x20000的一元稀疏多项式时，就要用一长度为的一元稀疏多项式时，就要用一长度为20001的线的线性表来表示，表中仅有三个非零元素，这种对内存性表来表示，表中仅有三个非零元素，这种对内存空间的浪费是应该避免的。空间的浪费是应该避免的。 如果只存储非零系数项，则显然必须同时存储如果只存储非零系数项，则显然必须同时存储相应的指数
35、。相应的指数。 一般情况下的一般情况下的一元稀疏多项式一元稀疏多项式可写成可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指数为是指数为ei 的项的非零系数的项的非零系数， 0 e1 e2 em = n可用一个长度为可用一个长度为m且每个元素有两个数据项且每个元素有两个数据项（系数项和指数项）的线性表表示：（系数项和指数项）的线性表表示：（p1, e1）, (p2, e2), , (pm,em) ） P999(x) = 7x3 - 2x12 - 8x999例如例如:可用线性表可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示
36、表示 在最坏情况下，在最坏情况下，n+1(=m)个系数都不为零，个系数都不为零，则比只存储每项系数的方案要多存储一倍的则比只存储每项系数的方案要多存储一倍的数据。但对于数据。但对于S(x)类的多项式，这种表示将类的多项式，这种表示将大大节省空间。大大节省空间。对于象对于象 (p1， e1), （p2， e2), （pm， em)的线性表，有两种存储结构：顺序存储结构的线性表，有两种存储结构：顺序存储结构和链式存储结构。在实际的应用程序中取用和链式存储结构。在实际的应用程序中取用哪一种，则要视多项式作何种运算而定。哪一种，则要视多项式作何种运算而定。 若只求多项式的值，运算中无须修改若只求多项式
37、的值，运算中无须修改多项式的系数和指数值，采用顺序存储结构多项式的系数和指数值，采用顺序存储结构为宜。为宜。 若求两个多项式之和，采用链式存储若求两个多项式之和，采用链式存储结构为宜。结构为宜。多项式选择顺序存储结构：多项式选择顺序存储结构： #define maxlen maxsize; typedef struct / 定义结点类型定义结点类型 float coef; / 系数域系数域 int exp; / 指数域指数域 elemtp; typedef struct elemtp vecmaxlen; / 定义线性表为向量定义线性表为向量 int len; / 线性表长度线性表长度 seq
38、uenlist; / 类型定义类型定义p1e1p2pme2emcoef exp多项式选择链式存储结构：多项式选择链式存储结构： typedef struct node / 定义结点类型定义结点类型 float coef; / 系数域系数域 int exp; / 指数域指数域 struct node *next; / 指针域指针域 polynode; ploynode *p,*q;ADT Polynomial 数据对象数据对象： 数据关系数据关系：抽象数据类型一元多项式的定义如下：D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的中的每个元素包含一个每个元素包
39、含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1 |ai-1 ,aiD, i=2,.,n 且且ai-1中的指数值中的指数值ai中的指数值中的指数值 CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ) 基本操作：操作结果操作结果：输入输入 m 项的系数和指数，项的系数和指数， 建立一元多项式建立一元多项式 P。初始条件初始条件：一元多项式一元多项式 P 已存在已存在。操作结果操作结果：销毁一元多项式销毁一元多项式 P。初始条件初始条件：一元多项式一元多项式 P 已存在已存在。操作结
40、果操作结果：打印输出一元多项式打印输出一元多项式 P。 PolynLength( P ) AddPolyn ( &Pa, &Pb ) 初始条件初始条件：一元多项式一元多项式 P P 已存在。已存在。操作结果操作结果：返回一元多项式返回一元多项式 P P 中的项数。中的项数。初始条件初始条件：一元多项式一元多项式 Pa 和和 Pb 已存在。已存在。操作结果操作结果：完成多项式相加运算，即：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式并销毁一元多项式 Pb。 SubtractPolyn ( &Pa, &Pb ) MultiplyPolyn ( &a
41、mp;Pa, &Pb ) ADT Polynomial初始条件初始条件：一元多项式一元多项式 Pa 和和 Pb 已存在。已存在。操作结果操作结果：完成多项式相减运算，即：完成多项式相减运算，即： Pa = Pa - Pb，并销毁一元多项式并销毁一元多项式 Pb。初始条件初始条件：一元多项式一元多项式 Pa 和和 Pb 已存在。已存在。操作结果操作结果：完成多项式相减运算，即：完成多项式相减运算，即： Pa = Pa - Pb，并销毁一元多项式并销毁一元多项式 Pb。Status CreatPolyn ( polynomail &P, int m ) / 输入输入m项的系数和指数
42、，建立表示一元多项式的有序链表项的系数和指数，建立表示一元多项式的有序链表P / CreatPolynInitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 设置头结点的数据元素设置头结点的数据元素for ( i=1; i=m; +i ) / 依次输入依次输入 m 个非零项个非零项return OK;scanf (e.coef, e.expn);if (!LocateElem ( P, e, (*cmp)() ) / 当前链表中不存当前链表中不存 在该指数项在该指数项 if ( MakeNode(s,e) InsFirst(q
43、,s); / 生成结点并插入生成结点并插入 注意注意: : 1. .输入次序不限输入次序不限; ;2. .指数相同的项只能输入一次。指数相同的项只能输入一次。例：设例：设An ( x)和和Bm ( x)都是形如都是形如 Pn ( x)= p1 xe1+ p2 xe2 + + pm xem 的一元多项式，现求两多项式之和的一元多项式，现求两多项式之和 Cn ( x)= An ( x)+Bm ( x) (mn) 显然，应采用链式存储结构。用两个线性链表显然，应采用链式存储结构。用两个线性链表分别表示两个一元多项式，链表中的每个结点表示分别表示两个一元多项式，链表中的每个结点表示多项式中的一项。多项
44、式中的一项。两个一元多项式的运算规则：两个一元多项式的运算规则： 指数相同的项，对应系数相加，若和不为零，则生成和指数相同的项，对应系数相加，若和不为零，则生成和多项式的一项；指数不相同的项，则复制到和多项式中。多项式的一项；指数不相同的项，则复制到和多项式中。实现方法：实现方法： 设两个指针设两个指针p,qp,q分别指向两个多项式中的某一个结点，分别指向两个多项式中的某一个结点，则可以比较结点的指数项，则可以比较结点的指数项， 若若p pexpqexp, *q结点是多项式中的一项，结点是多项式中的一项，*q结结点应插在点应插在*p结点之前，且结点之前，且q q指针在原来的链表上后移；指针在原
45、来的链表上后移；-17 03 19 8517-18 122 7-98papb多项式表的单链存储结构多项式表的单链存储结构-17 011 1 51722 7pc相加得到的和多项式相加得到的和多项式pqprepolyadd(polynode &pa, polynode &pb, polynode &pc) /多项式加法：多项式加法：pc=pa+pbpc=pa+pb, , / 利用两个多项式的结点构成和多项式利用两个多项式的结点构成和多项式 pc=pa;p=panext; q=pbnext; pre=pa; while (p!=nil)&(q!=nil) if (pe
46、xpqexp) pre=p;p=pnext; / p p指针后移指针后移 else if (pexp=qexp) x=pcoef+qcoef; if (x!=0) pcoef=x; pre=p; / 修改修改p p结点结点 else prenext=pnext; free(p); / 删除删除p p结点结点 p=prenext; r=q; q=qnext; free( r ); else r=qnext; qnext=p; prenext=q; pre=q; q=r; / q q结点插入在结点插入在p p结点之前结点之前 if (q!=nil) prenext=q; free(pb); / p
47、olyadd本本 章章 学学 习习 要要 点点 1. 1.了解线性表的逻辑结构特性是数据元素了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。表，用后者表示的线性表简称为链表。 2. 2.熟练掌握这两类存储结构的描述方法，熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。以及线性表的各种基本操作的实现。 3. 3.能够从时间和空间复杂度的角度综合比较能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及适用场合。线性表两种存储结构的不同特点及适用场合。
