华中科技大学：《数据结构》课程教学资源（PPT课件讲稿）作业解答3

7感门 20023

数据结构作业 2002 年 第三章 栈和队列

2.37设带表头的双向循环链表表示的线性表为L=(a,a2,an) 试写一复杂度为O(n)的算法,将L改造成 L=(al, a3,..., an,...., a4, a2 L{m十a口a2- an ail ①tail=L> prior

2.37 设带表头的双向循环链表表示的线性表为L=(a1,a2,…an)。 试写一复杂度为O(n)的算法，将L改造成: L= (a1,a3,…,an,….,a4,a2) L /// a1 a2 an tail ① ① tail=L->prior

1ma口a an tail ②2用指针p访问链表的所有结点(不包括an) p=L->next while(p!=tail) p=p->next

L /// a1 a2 an tail ① ② 用指针p访问链表的所有结点（不包括an） p=L->next; while (p!=tail) { ……….. p=p->next; } p ②

Lma凵a2a3 an qp tail ③3当p访问链表的偶序号结点,删除p所指向的结点,不释放单元, p=L->next; 1=1 while (p!=tail) if(%2=0) &a=p; p=p->next; p->prior= -prior, q-prior-next-p else p=p->next +

L /// a1 a2 an tail ① ③ 当p访问链表的偶序号结点,删除p所指向的结点，不释放单元， p=L->next; i=1; while (p!=tail) { if (i%2==0) { q=p; p=p->next; p->prior=q ->prior; q ->prior->next=p; ………. } else p=p->next; i++; } p ③ a3 q

an a2 tail q ④将q所指向结点插入到tai所指向结点之后,tai指向不变。 g->next=tail->next q->prior=tail tall->next ->prior=q tail->next=q

/// a2 L a1 an tail ① p a3 q ④ 将q所指向结点插入到tail所指向结点之后， tail指向不变。 q->next=tail->next; q->prior=tail; tail->next ->prior=q; tail->next=q;

void adjust( dulLinkList *L) i tail==L->prior; p=L->next while (p!=tail) if(9%2=0 i g=p: p=p->next p> prior=q→> prior;q→ prior->next=p;/删除q结点* q->next=tail->next;q→>pior-tail;/*插入q结点* tail->next ->prior=q; tail->next=q else p=p->next +

void adjust(DulLinkList *L) { tail=L->prior; p=L->next; i=1; while (p!=tail) { if (i%2==0) { q=p; p=p->next; p->prior=q ->prior; q ->prior->next=p; /*删除q结点*/ q->next=tail->next; q->prior=tail; /*插入q结点*/ tail->next ->prior=q; tail->next=q; } else p=p->next; i++; } }

3.6试证明,若借助栈由输入序列123.n得到的输出序 列为p1p2…pn(它们是输入的一个排列),则在输出序列 中不可能出现这样的情形:存在<j<k使 pj<pk<pi 证明 根据i<j<k得出栈次序pi、pj、pk 又根据pj<pk<pi,所以pj、pk、pi入栈的次序依此 为:pj、pk、pi,由于pi最先出栈,此时的p、pk必在栈中, 且形式是p在下、pk在上,得出栈次序pi、pk、pj。 所以由<j<k和 pj<pk< pi推导出互相矛盾的结果,故原 命题成立

3.6 试证明，若借助栈由输入序列１２３…n得到的输出序 列为p1p ２ ….p n （它们是输入的一个排列），则在输出序列 中不可能出现这样的情形：存在i < j < k使pj<pk<pi. 证明: 根据 i < j < k 得出栈次序pi、pj、pk。 又根据 pj < pk < pi，所以 pj、pk、pi入栈的次序依此 为：pj、pk、pi，由于pi最先出栈，此时的 pj、pk必在栈中， 且形式是pj在下、pk在上，得出栈次序pi、 pk 、 pj 。 所以由i < j < k和pj<pk<pi推导出互相矛盾的结果，故原 命题成立