《作业解答3-C语言课件.ppt》由会员分享，可在线阅读，更多相关《作业解答3-C语言课件.ppt（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构作业2002 年第三章 栈和队列2.37 设带表头的双向循环链表表示的线性表为L=(a1,a2,an)。试写一复杂度为O(n)的算法，将L 改造成:L=(a1,a3,an,.,a4,a2)/a2 ana1Ltail tail=L-prior/a2 ana1Ltail 用指针p访问链表的所有结点（不包括an）p=L-next;while(p!=tail).p=p-next;p/a2 ana1Ltail 当p访问链表的偶序号结点,删除p所指向的结点，不释放单元，p=L-next;i=1;while(p!=tail)if(i%2=0)q=p;p=p-next;p-prior=q-prior;
2、q-prior-next=p;.else p=p-next;i+;pa3 qvoid 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 使pjpkpi.证明:根据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 和pjpkpi 推导出互相矛盾的结果，故原命题成立。