各依次输入递增有序若干个不超过100的整数,分别建立两个递增有序单链表,分别表示集合A和集合B。设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并存放于A链表中。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。然后输出求的差集的单链表。测试数据保证结果链表至少存在一个元素。
输入格式:
首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据先在第一行输入数据个数n及n个依次递增有序的不超过100的整数,再在第二行输入数据个数m及m个依次递增有序的不超过100的整数。
输出格式:
对于每组测试,输出A与B的差集的单链表,每两个数据之间留一个空格。
输入样例:
1 2 3 4 5
| 2 11 10 14 23 25 26 31 34 42 51 65 90 10 10 41 42 46 51 58 59 60 68 97 5 1 2 3 4 5 3 3 4 5
|
输出样例:
1 2
| 14 23 25 26 31 34 65 90 1 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 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
| #include<stdio.h> #include<malloc.h> using namespace std;
typedef struct LNode { int data; struct LNode *next; } LNode;
void CreatelistR(LNode *&head,int arr[],int n); void ShowList(LNode *head);
void Difference(LNode *A,LNode *B);
int main() { int n; scanf("%d",&n); for(int i = 0; i < n; i++) { int tmp;
LNode *head = nullptr; int arr[100] = {0}; int n1; scanf("%d",&n1); for(int i = 0; i < n1; i++) { scanf("%d",&tmp); arr[i] = tmp; }
CreatelistR(head,arr,n1);
LNode *head_2 = nullptr; int arr_2[100] = {0}; int n2; scanf("%d",&n2); for(int i = 0; i < n2; i++) { scanf("%d",&tmp); arr_2[i] = tmp; }
CreatelistR(head_2,arr_2,n2);
Difference(head,head_2); ShowList(head); } return 0; }
void CreatelistR(LNode *&head,int arr[],int n) { if(arr == nullptr || n < 0) return; head = (LNode *)malloc(sizeof(LNode)); head->next = nullptr;
LNode *temp = head; for(int i=0; i<n; i++) { LNode *node = (LNode *)malloc(sizeof(LNode)); node->data = arr[i]; node->next = nullptr;
temp->next = node; temp = temp->next; } }
void ShowList(LNode *head) { if(head == nullptr) return; while(head->next != nullptr) { if(head->next->next == nullptr) printf("%d",head->next->data); else printf("%d ",head->next->data); head = head->next; } printf("\n"); }
void Difference(LNode *A,LNode *B) { if(A == nullptr || B == nullptr) return ; LNode *p = A->next,*q = B->next; LNode *r = A;
while(p != nullptr && q != nullptr) { if(p->data < q->data) { r = p; p = p->next; } else if(p->data > q->data) { q = q->next; } else { LNode *s = p; r->next = p->next;
p = p->next; free(s); } } }
|