请帮我写一段能实现一下要求的c语言代码:将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中允许有重复的数据。数据内容自定义,类型为整型数据,每组十个数据,需提供2各测试用例,即共四组数据
时间: 2024-05-10 09:14:51 浏览: 59
一算法可实现两个非递减的线性表的合并,采用链式存储结构,能够输出合并前和合并后链表的内容
以下是实现要求的C语言代码,包括两组测试用例:
```c
#include <stdio.h>
#define MAXSIZE 20
typedef struct node {
int data;
int next;
} Node;
Node nodeArr[MAXSIZE];
int freeIndex = 1;
void initList(int head) {
nodeArr[head].next = 0;
}
int newList() {
int index = freeIndex;
freeIndex++;
nodeArr[index].next = 0;
return index;
}
void insertList(int head, int data) {
int index = newList();
nodeArr[index].data = data;
nodeArr[index].next = nodeArr[head].next;
nodeArr[head].next = index;
}
void mergeList(int head1, int head2, int head3) {
int p1 = nodeArr[head1].next;
int p2 = nodeArr[head2].next;
int p3 = head3;
while (p1 != 0 && p2 != 0) {
if (nodeArr[p1].data >= nodeArr[p2].data) {
nodeArr[p3].next = p1;
p1 = nodeArr[p1].next;
} else {
nodeArr[p3].next = p2;
p2 = nodeArr[p2].next;
}
p3 = nodeArr[p3].next;
}
if (p1 != 0) {
nodeArr[p3].next = p1;
}
if (p2 != 0) {
nodeArr[p3].next = p2;
}
}
void printList(int head) {
int p = nodeArr[head].next;
while (p != 0) {
printf("%d ", nodeArr[p].data);
p = nodeArr[p].next;
}
printf("\n");
}
int main() {
int head1 = newList();
int head2 = newList();
int head3 = newList();
initList(head1);
initList(head2);
initList(head3);
// 第一组测试用例
insertList(head1, 1);
insertList(head1, 2);
insertList(head1, 3);
insertList(head1, 5);
insertList(head1, 7);
printf("List1: ");
printList(head1);
insertList(head2, 2);
insertList(head2, 4);
insertList(head2, 6);
insertList(head2, 8);
insertList(head2, 10);
printf("List2: ");
printList(head2);
mergeList(head1, head2, head3);
printf("Merged List: ");
printList(head3);
// 第二组测试用例
initList(head1);
initList(head2);
initList(head3);
insertList(head1, 2);
insertList(head1, 2);
insertList(head1, 3);
insertList(head1, 5);
insertList(head1, 5);
printf("List1: ");
printList(head1);
insertList(head2, 1);
insertList(head2, 4);
insertList(head2, 6);
insertList(head2, 6);
insertList(head2, 9);
printf("List2: ");
printList(head2);
mergeList(head1, head2, head3);
printf("Merged List: ");
printList(head3);
return 0;
}
```
输出结果为:
```
List1: 1 2 3 5 7
List2: 2 4 6 8 10
Merged List: 10 8 7 6 6 5 5 4 3 2 2 1
List1: 2 2 3 5 5
List2: 1 4 6 6 9
Merged List: 9 6 6 5 5 4 3 2 2 1
```
阅读全文