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

}
int main() /*测试函数*/
{linklist head,L;


head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
*/
L=sprit(head); /*分裂单链表
head*/
printf("\n原单链表为
:\n");
print(head); /*输出倒置后的单链表
*/
printf("\n分裂所得奇数单链表为
:\n");
print(L);


}

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



3.8设计一个算法，对一个有序的单链表，删除所有值大于
x而不大于
y的结点。
【答】：
#include "linklist.h"
void deletedata(linklist head,datatype x,datatype y)
{ /*删除带头结点单链表中所有结点值大于
x而不大于
y的结点*/


linklist pre=head,p,q;
p=head->next; /*初始化*/
while (p && p->data<=x) /*找第
1处大于
x的结点位置
*/


{ pre=p;
p=p->next;
}
while (p && p->data<=y) /*找第
1处小于
y的位置*/


p=p->next;
q=pre->next; /*删除大于
x而小于
y的结点*/
pre->next=p;
pre=q->next;



while (pre!=p) /*释放被删除结点所占用的空间
*/

{free(q);
q=pre;
pre=pre->next;


}
}
void main() /*测试函数*/
{ linklist head,L;

datatype x,y;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
*/
printf("\n请输入要删除的数据区间
:\n");
scanf("%d%d",&x
,&y);
deletedata(head,x,y);
print(head); /*输出删除后的单链表
*/


}

3.9设计一个算法，在双链表中值为
y的结点前面插入一个值为
x的新结点。即使值为
x的新
结点成为值为
y的结点

数据结构答案

的前驱结点。
【答】：
首先定义双链表的数据结构，相关文件
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设计一个算法，将一个双链表改建成

数据结构答案

一个循环双链表。
【答】：
#include <stdio.h>
#include "dlink.h"
/*将一个双链表改成循环双链表
*/
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)
…… 此处隐藏：1323字，全部文档内容请下载后查看。喜欢就下载吧 ……