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

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

vprint(head); getch(); }

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

3.11 设计一个算法，将一个双链表改建成一个循环双链表。 【答】：

#include #include \

/*将一个双链表改成循环双链表*/ void dlinktocdlink(dlinklist head) { dlinklist r; r=head;

while (r->rlink) /*寻找尾结点*/ r=r->rlink;

head->llink=r; r->rlink=head; }

void printcdlink(dlinklist head) { /*打印双链表*/ dlinklist p; p=head->rlink; while (p!=head)

{printf(\ p=p->rlink;

}

}

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

head=creatdlinklist(); dlinktocdlink(head);

printf(\循环双链表的容是：\\n\ printcdlink(head); }

21