数据结构(第二版)习题答案第3章(4)

s->rlink=r->rlink; /*将新结点 s 插入到双链表链尾*/

18

s->llink=r;

r->rlink=s;

r=s;

scanf(\

}

return head; }

/*输出双链表的内容*/ void print(dlinklist head) { dlinklist p; p=head->rlink;

printf(\双链表的内容是：\\n\ while (p)

{ printf(\ p=p->rlink;

}

}

本题的求解程序如下： #include #include \

void insertxaty(dlinklist head,datatype y,datatype x) { dlinklist s,p;

/*首先在双链表中找 y 所在的结点，然后在 y 前面插入新结点*/ p=head->rlink;

while (p && p->data!=y) p=p->rlink;

if (!p) printf(\双链表中不存在值为 y 的结点,无法插入新结点!\\n\ else /*插入值为 x 的新结点*/ { s=(dlinklist)malloc(sizeof(dnode)); s->data=x; s->rlink=p;

s->llink=p->llink; p->llink->rlink=s; p->llink=s;

}

}

void main() /*测试函数*/ { dlinklist head; datatype x,y;

19

head=creatdlinklist(); print(head);

printf(\请输入要输入的位置结点值 y:\\n\ scanf(\

printf(\请输入要输入的结点值 x:\\n\ scanf(\

insertxaty(head,y,x);/*在值为 y 的结点前插入值为 x 的新结点*/ print(head);/*输出新的双链表*/ getch(); }

本程序的一组测试情况如下图所示。

3.10 设计一个算法，从右向左打印一个双链表中各个结点的值。 【答】：

本题的双链表定义同题 3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实 现如下：

#include #include \

void vprint(dlinklist head)

{ /*递归方法从右向左打印双链表的值*/ if (head->rlink)

{vprint(head->rlink);

printf(\

}

}

void main() /*测试函数*/ { dlinklist head;

head=creatdlinklist(); print(head);

printf(\从右向左打印的双链表的内容是:\\n\

20