数据结构_第一章绪论_第二章_第三章栈与队列.ppt

如果在单链表查找直接前驱，需从表头指针出发。如果希望查找前驱的时间复杂度达到O(1)，可以用空间换时间的方法,每个结点再加一个指向前驱的指针域，使链表可以进行双方向查找。用这种结点结构组成的链表称为双向链表。 三、双向链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： typedef struct DulNode { ElemType data; struct DulNode *prior; struct DulNode *next; }DulNode,*DuLinkList; 和单链表类似，双链表一般也是由头指针唯一确定的，增加头结点也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。 ? ? ? ? ? ? 设指针p指向某一结点，则双向链表结构的对称性可用下式描述： p-next-prior=p-prior-next=p 即结点*p的存储位置既存放在其前趋结点*(p—prior)的直接后继指针域中，也存放 在它的后继结点* (p-next)的直接前趋指针域中。 插入、删除操作 ? ? ? ? ? ? a b x 双向循环链表的插入算法： status ListInsert_Dul(DuLinkList L, int i, ElemType e) {//在带头结点的双向循环链表中的第i个位置之前插入元素 e If (!(p=GetElemP_Dul(L,i))) return ERROR; //表的长度未达i s = (DuLinkList)malloc(sizeof(DuLNode)); if (!s) return (ERROR) //空间不够，溢出 s-data = e; s-prior = p-prior; p-prior-next=s; s-next= p; p-prior = s; return OK; } ? ? ? ? ? ? 思考 插入部分的语句顺序可以修改吗？ 如果找第i-1个元素的位置，则插入语句部分如何修改？ Status ListDelete_Dul(DuLinkList L,int i,ElemType e) { if (!(p=GetElemP_Dul(L,i))) return ERROR; e=p-data; p–prior–next=p–next; p–next–prior=p–prior; free(p);return OK; } 课本p37 算法2.19 删除语句的顺序可以修改吗？ 注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。 a b x 2.4 一元多项式的表示和相加 一、一般一元多项式的表示 符号多项式的操作，已经成为表处理的典型用例。在数学上，一个一元多项式Pn(X) 可以写成： Pn(X) ＝ p0十 p1X十p2x2十…十 pnXn 它由n＋1个系数唯一确定。因此，在计算机里，它可用一个线性表P来表示： P=(p0 , p1 , p2 , …, pn) 每一项的指数i隐含在其系数pi 的序号里。 假设Qm(x)是一元m次多项式，同样可用线性表Q来表示 Q＝(q0 , q1 , q2 , …, qm) ? ? ? ? ? ? 不失一般性，设 m＜n，则两个多项式相加的结果 Rn(x)＝Pn(x) ＋Qm(x)可用线性表 R R＝( p0 + q0 , p1 +q1 , p2 +q2 , …, pm +qm , pm+1 ,, …, pn) 二、 稀疏多项式的表示 显然，我们可以对P、Q和R采用顺序存储结构，使得多项式相加的算法定义十分简洁。至此，一元多项式的表示及相加问题似乎已经解决了。然而，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。特别是在处理形如 S(x)=1＋3x10000＋2x20000 ? ? ? ? ? ? 的多项式时，就要用一长度为20001的线性表来表示，表中仅有三个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项则显然必