算法3： Status ReverseList_L-3(LinkList&L) p-L->next: L->next=Null; ∥L->next:此结点域保存当前结点*s的net值 while(p) s=p: 小指示当前结点，P指示*s的后继，不断链 p-p->next: s->next=L->next: L->next=s, return OK: //ReverseList L-3 1算法 可理 算法4： Status ReverseList_L-4(LinkList&L) p=L->next while(p->next)p=p->next. 仰指向最后结点 while(L->next!=p){ ∥L>next=p表示己别除掉an之前的所有结点 q=L->next: g指向当前结点 L->next-q->next /刚除q,并借助头结点的next域找到下一结点，不断链 q->next-p->next: *q插入p之后 p->next=q: return OK; ∥ReverseList L-4
5 算法 3： Status ReverseList_L-3(LinkList &L){ p=L->next; L->next= Null; // L->next：此结点域保存当前结点*s 的 next 值 while(p){ s=p; //s 指示当前结点，p 指示*s 的后继，不断链 p=p->next ; s->next=L->next ; L->next=s; } return OK; }// ReverseList_L-3 //算法 3 也可理解为从表头进行的表头插入法。 //算法 4 可理解为从表尾进行的表头插入法。 算法 4： Status ReverseList_L-4(LinkList &L){ p=L->next; while(p->next) p= p->next; //p 指向最后结点 while(L->next!=p){ // L->next=p 表示已删除掉 an 之前的所有结点 q=L->next ; //q 指向当前结点 L->next=q->next； //删除*q，并借助头结点的 next 域找到下一结点，不断链 q->next=p->next； //*q 插入*p 之后 p->next=q； } return OK; }// ReverseList_L-4
作业4： 己知两个具有相同结点个数的集合A、B:A={ala2,an,B=b1b2.,bn。集合用 带头结点的单链表表示，设集合A、B的头指针分别为La和Lb。写一算法将A、B合并成 集合C={al,bl,a2,b2,.,an,bn,且集合C的头指针仍为La。 要求：不再另分配空间。 参考答案4： 北工中平西 地工中四平。 Status MergeList L(LinkList&La,LinkList Lb) a=La->next b=Lb->next t=b->next; a、b分别指向单链表La和Lb的当前结点，t指向6的后继结点 while (t){ b->next=a->next; a->next=b: 插入结点b a=a->next->next b=t t=t->next; 后移a、b、t指针 a->next=b; 插入Lb中最后结点 return OK: MergeList_I
6 作业 4： 已知两个具有相同结点个数的集合 A、B：A={a1a2.,an}，B={b1b2.,bn}。集合用 带头结点的单链表表示, 设集合 A、B 的头指针分别为 La 和 Lb。写一算法将 A、B 合并成 集合 C={a1,b1,a2,b2,.,an,bn }，且集合 C 的头指针仍为 La。 要求：不再另分配空间。 参考答案 4： Status MergeList_L(LinkList &La，LinkList Lb){ a = La->next; b = Lb->next; t = b->next; //a、b 分别指向单链表 La 和 Lb 的当前结点，t 指向*b 的后继结点 while (t) { b->next = a->next; a->next = b; //插入结点*b a = a->next->next; b = t； t = t->next; //后移 a、b、t 指针 } a->next = b; //插入 Lb 中最后结点 return OK; }// MergeList_L
作业5： 在双向链表（带头结点）中实现第一个结点与第二个结点的位置互换。仅限修改指针域， 假设该双向链表含3个以上结点。 参考答案5： 算法1： Status Exchange _DuL(DuLinkList&L){ ∥使用2个辅助指针p,q:先删除首结点*p,再将其插入合适位置。 p=L->next; g=p->next>next,/辅助指针p、q L->next=p->next p->next->next-p p->next=q; 对正向链 q->prior p; p->prior=L->next: L->next>prior=L对逆向链 //Exchange1_DuL 算法2 /父 Aa1a2a3子= Status Exchange2_DuL(DuLinkList&L) 使用1个辅助指针P:分别对各结点相应指针调整 p=L->next->next 辅助指针p L->next->next=p->next; L->next->prior=p 对a1所在结占 p->ncxt->prior=L>next对a3所在结点 p->next L->next p->prior =L: ∥对a2所在结点 L->next=p 对头结点 ∥Exchange2_DuL >
7 作业 5： 在双向链表(带头结点)中实现第一个结点与第二个结点的位置互换。仅限修改指针域， 假设该双向链表含 3 个以上结点。 参考答案 5： 算法 1： Status Exchange1_DuL(DuLinkList &L){ //使用 2 个辅助指针 p,q：先删除首结点*p,再将其插入合适位置。 p = L->next; q = p->next->next; //辅助指针 p、q L->next = p->next; p->next->next=p; p->next=q; //对正向链 q->prior = p; p->prior = L->next; L->next->prior = L; //对逆向链 }// Exchange1_DuL 算法 2： Status Exchange2_DuL(DuLinkList &L){ //使用 1 个辅助指针 p:分别对各结点相应指针调整 p = L->next->next; //辅助指针 p L->next->next = p->next; L->next->prior = p; //对 a1 所在结点 p->next->prior = L->next; //对 a3 所在结点 p->next = L->next; p->prior = L; //对 a2 所在结点 L->next = p //对头结点 }// Exchange2_DuL
算法3： a23 Status Exchange3 DuL(DuLinkList &L) 不使用辅助指针：可以实现，但表述教复杂 L->next->next=L >next->next->next L->next->next->prior->next =L->next: L->next=L->next->next->prior; L->next->next->next->prior=L->next->next: L->next->next->prior=L->next: Lnext->prior-L ∥Exchange3_Dul
8 算法 3： Status Exchange3_DuL(DuLinkList &L){ //不使用辅助指针：可以实现，但表述教复杂 L->next->next= L->next->next->next; L->next->next ->prior->next = L->next； L->next=L->next-> next-> prior; L->next->next -> next ->prior=L->next->next; L->next->next ->prior=L-> next； L->next-> prior=L； }// Exchange3_DuL
作业6： 在一个至少含有三个元素的循环链表L中，既无头指针，也无头结点P为指向某结点的 指针，别除该结点的前驱结点。 参考答案6： q p 分析：算法关健是找到p前驱的前驱* 算法1 Status DelPrel_CirL(CirLinkList&L,LNode*p){ g=p: while (q->nextl =p)q=q->next; 找*p的前驱*g r=q while (r->next!=q)r=r->next; 找*q的前驱*r r->next =p; 删除结点 free(q): return OK: /DelPre1_CirL 算法2： Status DelPre2_CirL(CirLinkList&LLNode*p) I=D: while(r->next.>net=p）【=r->net, /找*D前驱的前服◆灯 q =r->next 记录要删除的结点位置，以释放空间 r->next=p; 除结点 free(q). return OK //DelPre2_CirL
9 作业 6： 在一个至少含有三个元素的循环链表 L 中,既无头指针,也无头结点, p 为指向某结点的 指针,删除该结点的前驱结点。 参考答案 6： 分析：算法关键是找到*p 前驱的前驱*r. 算法 1: Status DelPre1_CirL(CirLinkList &L,LNode *p){ q = p; while ( q->next! = p ) q = q->next; //找*p 的前驱*q r = q; while ( r->next! = q ) r = r->next; //找*q 的前驱*r r->next = p; //删除结点 free(q); return OK; }// DelPre1_CirL 算法 2: Status DelPre2_CirL(CirLinkList &L,LNode *p){ r = p; while ( r->next->next! = p ) r = r->next; //找*p 前驱的前驱*r q = r->next; //记录要删除的结点位置，以释放空间 r->next = p; //删除结点 free(q); return OK; }// DelPre2_CirL