数据结构-合并链表算法

数据结构算法题

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

int MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递增链表,用原有的空间，不能有重复的数据
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){
        if(pa->data<pb->data){//比较较小的节点插入Lc中
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else if(pa->data>pb->data){
                pc->next=pb;
                pc=pb;
                pb=pb->next;
        }
        else{//有相同节点时选择其中一个链入Lc中，另一个则释放掉
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    pc->next=pa?pa:pb;
    return OK;
}
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

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

int Union(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递减的链表,用原有的空间，可有重复的数据（用头插法，完成逆序）
    LinkList pa,pb,p;
    pa=La->next;
    pb=Lb->next;
    Lc=La;
    Lc->next=NULL;
    while(pa||pb){
        if(!pa){
            p=pb;
            pb=pb->next;
        }
        else if(!pb){
            p=pa;
            pa=pa->next;
        }
        else if(pa->data<=pb->data){
            p=pa;
            pa=pa->next;
        }
        else{
            p=pb;
            pb=pb->next;
        }
        p->next=Lc->next;
        Lc->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

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

int Mix(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表求交集,用原有La的空间
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){//有一个表结束，就可以全部结束了
        if(pa->data==pb->data){
            pc->next=pa;//相交并入表
            pc=pa;
            pa=pa->next;
            u=pb->next;//释放空间
            free(pb);
            pb=u;
        }
        else if(pa->data<pb->data){//较小节点前移，等待比较
                u=pa->next;
                free(pa);
                pa=u;
        }
        else {
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    while(pa){
        u=pa->next;
        free(pa);
        pa=u;
    }
    while(pb){
        u=pb->next;
        free(pb);
        pb=u;
    }
    pc->next=NULL;//结尾标志
    free(Lb);
    return OK;
}
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

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

int Difference(LinkList &La,LinkList &Lb,int &n){//两个递增链表求A-B的差集,用原有La的空间
    LinkList pa,pb,pre;//从La表中修改将不是差集中的删除
    pa=La->next;
    pb=Lb->next;
    pre=La;//用pre作pa的头节点
    while(pa&&pb){
        if(pa->data<pb->data){
            pre=pa;
            pa=pa->next;
            n++;//计数
        }
        else if(pa->data>pb->data){
            pb=pb->next;
        }
        else {
            pre->next=pa->next;//删除不是差集中的结点
            free(pa);
            pa=pre->next;
        }
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

int Divide(LinkList &La,LinkList &Lb,LinkList &Lc){//将La分成两个分别大于零和小于零的Lb和Lc
    LinkList p,pc,pb;
    p=La->next;
    Lb=La;
    pb=Lb;
    Lc=(LinkList)malloc(sizeof(Lnode));
    pc=Lc;
    while(p){
        if(p->data>0){
            pb->next=p;
            pb=p;
            p=p->next;
        }
        else if(p->data<0){
            pc->next=p;
            pc=p;
            p=p->next;
        }
    }
    pb->next=NULL;//结束标记
    pc->next=NULL;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

全部代码：

#include <iostream>
#define OK 1
#define ERROR 0
#include <stdio.h>
#include<stdlib.h>
#include<malloc.h>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode *next;
}Lnode,*LinkList;
int Initlist_L(LinkList &L);//建立一个空表，并将表头返回
int Create(LinkList &L);//将空表传入，为表中输入元素，在返回表头
int MergeList(LinkList &La,LinkList &Lb,LinkList &Lc);//两个递增链表合并为一个递增链表,用原有的空间，不能有重复的数据
int Union(LinkList &La,LinkList &Lb,LinkList &Lc);//两个递增链表合并为一个递减的链表,用原有的空间，可有重复的数据
int Mix(LinkList &La,LinkList &Lb,LinkList &Lc);//两个递增链表求交集,用原有La的空间
int Difference(LinkList &La,LinkList &Lb,int &n);//两个递增链表求A-B的差集,用原有La的空间
int Divide(LinkList &La,LinkList &Lb,LinkList &Lc);//将La分成两个分别大于零和小于零的Lb和Lc
int OperateMenu();//建立菜单，提示操作代码
void printfs(LinkList L);//将线性表L中的元素依次打印
int main(){
    LinkList La=NULL;
    LinkList Lb=NULL;
    LinkList Lc=NULL;
    int i=1,n=0;
    while(i){
    switch(OperateMenu()){
        case 1:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            MergeList(La,Lb,Lc);
            printf("合并完的链表为：");
            printfs(Lc);
            break;
        case 2:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            Union(La,Lb,Lc);
            printf("合并完的链表为：");
            printfs(Lc);
            break;
        case 3:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            Mix(La,Lb,Lc);
            printf("合并完的链表为：");
            printfs(Lc);
            break;
        case 4:
            printf("La:");
            Create(La);
            printf("Lb:");
            Create(Lb);
            Difference(La,Lb,n);
            printf("合并完长度%d的链表为：",n);
            printfs(La);
            break;
        case 5:
            printf("La:");
            Create(La);
            Divide(La,Lb,Lc);
            printf("大于零链表为：");
            printfs(Lb);
            printf("小于零链表为：");
            printfs(Lc);
            break;
        case 0:
           i=0;
           break;
    }
    }
}

int Initlist_L(LinkList &L){//建立一个空表，并将表头返回
    L=(LinkList)malloc(sizeof(Lnode));
    L->data=0;
    L->next=NULL;
    return OK;
}
int Create(LinkList &L){//将空表传入，为表中输入元素，在返回表头
    Initlist_L(L);//先建立一个带头节点的链表
    LinkList p,s;
    int e;
    p=L;
    scanf("%d",&e);
    while(e!=0)
    {
        s = (LinkList)malloc(sizeof(Lnode));
        s->data=e;
        p->next=s;
        p=s;//插入到表尾
        L->data++;
        scanf("%d",&e);
    }
    p->next=NULL;
    return OK;
}

int OperateMenu(){//建立菜单，提示操作代码
    int num;
    printf("                             *-----------------------------------------------------------------*\n");
    printf("                                               1.两个递增链表合并为一个递增链表\n");
    printf("                                               2.两个递增链表合并为一个逆序链表\n");
    printf("                                               3.两个递增链表合并两个链表的交集\n");
    printf("                                               4.两个递增链表合并为一个A-B的差集\n");
    printf("                                               5.将一个链表分成以零为界限的两个表\n");
    printf("                                               0.结束\n");
    printf("                             *-----------------------------------------------------------------*\n");
    scanf("%d",&num);
    for(int i=0;;i++){
        if(num<0||num>5){printf("选择错误！");return -1;}
        else if(num==1){return num;break;}
        else if(num==2){return num;break;}
        else if(num==3){return num;break;}
        else if(num==4){return num;break;}
        else if(num==5){return num;break;}
    }
}
int MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递增链表,用原有的空间，不能有重复的数据
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){
        if(pa->data<pb->data){//比较较小的节点插入Lc中
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else if(pa->data>pb->data){
                pc->next=pb;
                pc=pb;
                pb=pb->next;
        }
        else{//有相同节点时选择其中一个链入Lc中，另一个则释放掉
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    pc->next=pa?pa:pb;
    return OK;
}
int Union(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表合并为一个递减的链表,用原有的空间，可有重复的数据（用头插法，完成逆序）
    LinkList pa,pb,p;
    pa=La->next;
    pb=Lb->next;
    Lc=La;
    Lc->next=NULL;
    while(pa||pb){
        if(!pa){
            p=pb;
            pb=pb->next;
        }
        else if(!pb){
            p=pa;
            pa=pa->next;
        }
        else if(pa->data<=pb->data){
            p=pa;
            pa=pa->next;
        }
        else{
            p=pb;
            pb=pb->next;
        }
        p->next=Lc->next;
        Lc->next=p;//插入
    }
}
int Mix(LinkList &La,LinkList &Lb,LinkList &Lc){//两个递增链表求交集,用原有La的空间
    LinkList pa,pb,pc,u;
    pa=La->next;
    pb=Lb->next;
    Lc=pc=La;//用La作Lc的头节点
    while(pa&&pb){//有一个表结束，就可以全部结束了
        if(pa->data==pb->data){
            pc->next=pa;//相交并入表
            pc=pa;
            pa=pa->next;
            u=pb->next;//释放空间
            free(pb);
            pb=u;
        }
        else if(pa->data<pb->data){//较小节点前移，等待比较
                u=pa->next;
                free(pa);
                pa=u;
        }
        else {
            u=pb->next;
            free(pb);
            pb=u;
        }
    }
    while(pa){
        u=pa->next;
        free(pa);
        pa=u;
    }
    while(pb){
        u=pb->next;
        free(pb);
        pb=u;
    }
    pc->next=NULL;//结尾标志
    free(Lb);
    return OK;
}
int Difference(LinkList &La,LinkList &Lb,int &n){//两个递增链表求A-B的差集,用原有La的空间
    LinkList pa,pb,pre;//从La表中修改将不是差集中的删除
    pa=La->next;
    pb=Lb->next;
    pre=La;//用pre作pa的头节点
    while(pa&&pb){
        if(pa->data<pb->data){
            pre=pa;
            pa=pa->next;
            n++;//计数
        }
        else if(pa->data>pb->data){
            pb=pb->next;
        }
        else {
            pre->next=pa->next;//删除不是差集中的结点
            free(pa);
            pa=pre->next;
        }
    }
    return OK;
}
int Divide(LinkList &La,LinkList &Lb,LinkList &Lc){//将La分成两个分别大于零和小于零的Lb和Lc
    LinkList p,pc,pb;
    p=La->next;
    Lb=La;
    pb=Lb;
    Lc=(LinkList)malloc(sizeof(Lnode));
    pc=Lc;
    while(p){
        if(p->data>0){
            pb->next=p;
            pb=p;
            p=p->next;
        }
        else if(p->data<0){
            pc->next=p;
            pc=p;
            p=p->next;
        }
    }
    pb->next=NULL;//结束标记
    pc->next=NULL;
    return OK;
}
void printfs(LinkList L){//将线性表L中的元素依次打印
    LinkList p=L->next;
    if(p!=NULL){
    for(int j=0;;j++){
        printf("%d ",p->data);
        p=p->next;
        if(p==NULL)break;
    }
    }
    else printf("该链表为空！\n");
    printf("\n");
}

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276