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

数据结构答案

的前驱结点。
【答】：
首先定义双链表的数据结构，相关文件
dlink.h，内容如下：
typedef int datatype; /*预定义的数据类型
*/
typedef struct dlink_node{ /*双链表结点定义
*/
datatype data;
struct dlink_node *llink,*rlink;
}dnode;


typedef dnode* dlinklist; /*双链表结点指针类型定义
*/

/*尾插法创建带头结点的双链表
*/
dlinklist creatdlinklist(void)
{ dlinklist head,r,s;

datatype x;
head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点
*/
head->llink=head->rlink=NULL;
printf("\n请输入双链表的内容：（整数序列，以
0结束）\n");
scanf("%d",&x);
while (x) /*输入结点值信息，以
0结束*/
{ s=(dlinklist ) malloc(sizeof(dnode));


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



s->llink=r;
r->rlink=s;
r=s;
scanf("%d",&x);


}

return head;
}
/*输出双链表的内容
*/
void print(dlinklist head)

{ dlinklist p;
p=head->rlink;
printf("\n双链表的内容是：
\n");
while (p)
{ printf("%5d",p->data);
p=p->rlink;
}
}

本题的求解程序如下：


#include <stdio.h>
#include "dlink.h"
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("\n双链表中不存在值为
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;


head=creatdlinklist();

print(head);

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

scanf("%d",&y);

printf("\n请输入要输入的结点值
x:\n");

scanf("%d",&x);

insertxaty(head,y,x);/*在值为
y的结点前插入值为
x的新结点
*/

print(head);/*输出新的双链表
*/

getch();
}
本程序的一组测试情况如下图所示。



3.10设计一个算法，从右向左打印一个双链表中各个结点的值。
【答】：
本题的双链表定义同题
3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实
现如下：


#include <stdio.h>

#include "dlink.h"

void vprint(dlinklist head)

{ /*递归方法从右向左打印双链表的值
*/
if (head->rlink)
{vprint(head->rlink);
printf("%5d",head->rlink->data);
}

}

void main() /*测试函数*/

{
dlinklist head;
head=creatdlinklist();
prin
t(head);
printf("\n从右向左打印的双链表的内容是
:\n");


vprint(head);
getch();


}

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



3.11设计一个算法，将一个双链表改建成

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构(第二版)习题答案第3章(4)在线全文阅读。