数据结构严蔚敏(c语言版)课后算法题答案-线性表

（ 1 ） 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个
链表的存储空间，不另外占用其它的存储空间。表中不允许有重复的数据。

#include<stdio.h>
typedef struct Lnode
{
int data;
struct Lnode *next;
} Lnode,*Link;
void createlist(Link &L,int n,int z[]);
void listput(Link &L1,Link &L2,Link &L3);
main()
{
Link a1,a2,a3;
int an=5,bn=6;
int a[an]={2,4,7,3,9};
int b[bn]={5,12,13,1,15,2};
createlist(a1,an,a);
createlist(a2,bn,b);
listput(a1,a2,a3);
}
void createlist(Link &L,int n,int z[])
{
Lnode *p,*r,*L1;
L=new Lnode; //分配一个Londe类型的动态内存空间，指针变量L指向这个空间地址。
L->next=NULL;
L1=L;
p=new Lnode;
p->data=z[0];
p->next=NULL;
L->next=p;
for(int i=1;i<n;i++)
{
r=L;
p=new Lnode;
p->data=z[i];
for(int j=0;j<i;j++)
{
if(p->data<r->next->data)
{
p->next=r->next;
r->next=p;
break;
}
else{
r=r->next;
if(!r->next)
{
r->next=p; p->next=NULL;
}
}}
}
printf("序列：");
while(L1->next){L1=L1->next;printf("%d ",L1->data);}
printf("n");
}
void listput(Link &L1,Link &L2,Link &L3)
{
Lnode *s1,*s2,*r1,*q;
s1=L1->next;
s2=L2->next;
L3=L1;
r1=L3;
while(s1&&s2)
{ if(s1->data<s2->data) {
r1->next=s1; r1=s1; s1=s1->next;
}
else if(s1->data>s2->data)
{
r1->next=s2;
r1=s2;
s2=s2->next; }
else
{
r1->next=s1;
r1=s1;
s1=s1->next;
q=s2->next;
delete s2;
s2=q;
}
}
r1->next=s1?s1:s2;/*?:是一个条件运算符,比如P=A?B:C,它表示---若A为真,则用P=B,若A为假,则用P=C.*/
delete L2;
printf("结果：");
while(L3->next)
{ L3=L3->next; printf("%d ",L3->data);}
}

（ 2 ） 将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍用原
两个链表的存储空间， 不另外占用其它的存储空间。表中允许有重复的数据。

int listreverse(Link &L)
//单链表递归倒序输出
{
L=L->next;
Lnode *r;
r=L;
if(!L)
return 0;
else
listreverse(L);
printf("%d ",r->data);
}
void listreverse(Lnode *L)
//前插法倒序输出
{
Lnode *r,*p,*L1;
p=L->next;
L1=L;
L1->next=NULL;
while(p)
{
r=p->next;
p->next=L1->next;
L1->next=p;
p=r;
}
printf("结果：");
while(L1->next)
{
L1=L1->next; printf("%d ",L1->data);
}
}

（ 3 ） 巳知两个链表A 和B 分别表示两个集合， 其元素递增排列。请设计算法求出A 与
B 的交集， 并存放于A 链表中。

void listputmix(Link &L1,Link &L2,Link &L3) //两个单链表的交集
{
Lnode *p1,*p2,*r,*q;
p1=L1->next;
p2=L2->next;
L3=L1;
r=L3;
while(p1&&p2)
{
if(p1->data<p2->data)
{
q=p1; p1=p1->next;
delete q;
}
else if(p1->data>p2->data)
{
q=p2; p2=p2->next;
delete q; }
else if(p1->data==p2->data)
{ r->next=p1;
r=p1;
p1=p1->next;
q=p2;
p2=p2->next;
delete q; }
}
while(p1) { q=p1; p1=p1->next, delete q;
}
while(p2) { q=p2; p2=p2->next, delete q;
}
r->next=NULL;
delete L2;
printf("结果：");
while(L3->next)
{ L3=L3->next; printf("%d ",L3->data);
}
}

（ 4 ） 巳知两个链表A 和B 分别表示两个集合， 其元素递增排列。请设计算法求出两个
集合A 和B 的差集（ 即仅由在A 中出现而不在B 中出现的元素所构成的集合）， 并以同样的
形式存储， 同时返回该集合的元素个数。

int listputdef(Link &L1,Link &L2,Link &L3) //两个单链表的差集（只出现在A中而不在B中出现）
{
Lnode *p1,*p2,*r,*q;
p1=L1->next;
p2=L2->next;
L3=L1;
r=L3;
int n=0;
while(p1&&p2)
{
if(p1->data<p2->data)
{
r->next=p1;
r=p1;
p1=p1->next; n++;}
else if(p1->data>p2->data)
{
q=p2; p2=p2->next; delete q;}
else if(p1->data==p2->data)
{ q=p1;
p1=p1->next;
delete q;
q=p2;
p2=p2->next;
delete q;
}
}
while(p1) {
r->next=p1; r=p1; p1=p1->next; }
while(p2) { q=p2; p2=p2->next, delete q;
}
r->next=NULL;
//一定要把最后一个结点的next指向为NULL，因为它原本的next指向的结点已经删除
delete L2;
printf("结果：");
while(L3->next)
{ L3=L3->next; printf("%d ",L3->data);
}
return n;
}

（ 5 ） 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C ， 其中
B 表的结点为A 表中值小于零的结点， 而C 表的结点为A 表中值于零的结点（ 链表A 中的
元素为非零整数， 要求B 、C 表利用A 表的结点） 。

#include<stdio.h> //创建结点，作为另一条链表的头节点，前插法输出
typedef struct Lnode
{
int data;
struct Lnode *next;
} Lnode,*Link;
void createlist(Link &L,int n,int z[]);
void DifCompose(Link &L);
main()
{
Link a1;
int an=10;
int a[an]={-2,5,-6,7,-1,12,-5,8,-9,10};
createlist(a1,an,a);
DifCompose(a1);
}
void createlist(Link &L,int n,int z[])
{
Lnode *p,*r,*L1;
L=new Lnode;
L->next=NULL;
r=L;
L1=L;
for(int i=0;i<n;i++)
{
p=new Lnode;
p->data=z[i];
p->next=NULL;
r->next=p;
r=p;
}
printf("A：");
while(L1->next) { L1=L1->next;printf("%d ",L1->data);}
printf("n");
}
void DifCompose(Link &L)
{
Lnode *L1,*L2,*p,*r;
L2=new Lnode;
L2->next=NULL;
p=L->next;
L1=L;
L1->next=NULL;
while(p)
{
r=p->next;
if(p->data<0)
{
p->next=L1->next;
L1->next=p;
}
else{
p->next=L2->next;
L2->next=p;
}
p=r;
}
printf("B：");
while(L1->next)
{
L1=L1->next;
printf("%d ",L1->data);
}
printf("n");
printf("C：");
while(L2->next)
{
L2=L2->next;
printf("%d ",L2->data);}
}
void DifCompose(Link &L) //不创建结点，记录另一条链表的首元节点，后插法输出
{
Lnode *p,*r1,*r2,*L1,*L2;
p=L->next;
r1=L;
L1=L;
int n=1;
while(p)
{
if(p->data>0)
{
r1->next=p;
r1=p;
p=p->next;
}
else{
if(n>0){ r2=p; L2=p; p=p->next;n=0;}
else {
r2->next=p;
r2=p;
p=p->next;}
}
}
r1->next=NULL;
r2->next=NULL;
printf("B：");
while(L2)
{
printf("%d ",L2->data);L2=L2->next;}
printf("n");
printf("C：");
while(L1->next)
{
L1=L1->next;
printf("%d ",L1->data);}
}

（ 6 ） 设计一个算法， 通过一趟遍历在单链表中确定值最大的结点。

void listmax(Link &L) //遍历单链表最大值
{
Lnode *p;
int max;
p=L->next;
max=p->data;
while(p->next)
{
p=p->next;
if(p->data>max)
max=p->data;
}
printf("最大值：%d",max);
}

（ 7 ） 设计一个算法， 通过遍历一趟， 将链表中所有结点的链接方向逆转， 仍利用原表的
存储空间。

void listreverse(Lnode *L)
//单链表所有结点的链接方向"原地"逆置
{
Lnode *r,*p,*q;
p=L;
r=q=NULL;
while(p)
//使得原来的每个后一结点指向前一结点，头结点的next指向空
{
q=p->next;
p->next=r;
r=p;
p=q;
}
printf("结果：");
while(r->next)
{
printf("%d ",r->data); r=r->next; }
}

（ 8 ） 设计一个算法， 删除递增有序链表中值大于mink 且小于maxk 的所有元素（ mink
和是给定的两个参数， 其值可以和表中的元素相同， 也可以不同）。

void Diflist(Link &L,int mink,int maxk) //无序单链表删除符合条件的元素
{
Lnode *p,*r,*L1;
L1=L;
p=L->next;
while(p)
{
r=p->next;
if(p->data>mink&&p->data<maxk)
{
delete p;
L1->next=r;
}
else
{
L1->next=p;
L1=p;
}
p=r;
}
while(L->next) { L=L->next;printf("%d ",L->data);}
}
void Diflist(Link &L,int mink,int maxk) //有序单链表删除符合条件的元素
{
Lnode *p,*r,*L1;
L1=L;
p=L->next;
while(p)
{
while(p->data>mink&&p->data<maxk)
{
r=p->next;
delete p;
p=r;
}
L1->next=p;
L1=p;
p=p->next;
}
while(L->next) { L=L->next;printf("%d ",L->data);}
}

（ 9 ） 已知指向双向循环链表中的一个结点， 其结点结构为data 、prior 、next 三个域，
写出算法p 所指向的结点和它的前结点的顺序。

#include<stdio.h>
//在双向循环链表中，第n个结点和前驱结点交换位置
typedef struct Lnode
{
int data;
struct Lnode *prior;
struct Lnode *next;
} Lnode,*Link;
void createlist(Link &L,int n,int z[]);
void change(Link &L,int n);
main()
{
Link a1;
int n=6;
int an=10;
int a[an]={-2,5,-6,7,-1,12,-5,8,-9,10};
createlist(a1,an,a);
change(a1,n);
}
void createlist(Link &L,int n,int z[])
{
Lnode *p,*r,*L1;
L=new Lnode;
r=L;
L1=L;
for(int i=0;i<n;i++)
{
p=new Lnode;
p->data=z[i];
r->next=p;
p->prior=r;
r=p;
}
p->next=L;
L->prior=p;
printf("双向循环链表：");
while(L1->next!=L) { L1=L1->next;printf("%d ",L1->data);}
printf("n");
}
void change(Link &L,int n)
{
Lnode *p,*r,*k1,*k2,*L1;
p=L;
L1=L;
for(int i=0;i<n;i++) { r=p;p=p->next; }
k1=r->prior;
k2=p->next;
k1->next=p;
p->next=r;
r->next=k2;
k2->prior=r;
r->prior=p;
p->prior=k1;
printf("转变之后链表：");
while(L1->next!=L) { L1=L1->next;printf("%d ",L1->data);}
}

最后

以上就是虚心外套为你收集整理的数据结构严蔚敏(c语言版)课后算法题答案-线性表的全部内容，希望文章能够帮你解决数据结构严蔚敏(c语言版)课后算法题答案-线性表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。