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

100 阅读 0 评论 66 点赞

我是靠谱客的博主虚心外套，这篇文章主要介绍数据结构严蔚敏(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);}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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 ）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍用原
两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 链表中。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 中出现的元素所构成的集合），并以同样的
形式存储，同时返回该集合的元素个数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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);}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#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 ）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 ）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的
存储空间。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
和是给定的两个参数，其值可以和表中的元素相同，也可以不同）。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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 所指向的结点和它的前结点的顺序。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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);}
}