数据结构作业
2002 年第三章 栈和队列
2.37 设带表头的双向循环链表表示的线性表为 L=(a1,a2,…an) 。
试写一复杂度为 O(n)的算法，将 L改造成,
L= (a1,a3,…,an,….,a4,a2)
/// a2 ana1L
tail
①
① tail=L->prior
/// a2 ana1L
tail
①
② 用指针 p访问链表的所有结点（不包括 an）
p=L->next;
while (p!=tail)
{
………..
p=p->next;
}
p
②
/// a2 ana1L
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
///
a2
ana1L
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)
{ 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 试证明，若借助栈由输入序列１２３ …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推导出互相矛盾的结果，故原命题成立。