NWPU 数据结构 NOJ 005 单链表的删除

题目

已知 $A,B$ 和 $C$ 为三个非递减有序的线性表,均以单链表作为存储结构。现要求对 $A$ 表作如下操作:删去那些既在 $B$ 表中出现又在 $C$ 表中出现的元素。试对单链表编写实现上述操作的算法,并释放 $A$ 表中的无用结点空间。

输入

第一行输入 3 个正整数 $m,n,p\,\,\,(m,n,p\leq 100)$,用空格分开,表示三个线性表中的元素个数,其后 3 行依次输入 $A,B,C$ 表中的元素。

解法

以第一个链表元素为基准,依次把后两个拉到不超过第一个当前枚举的元素的位置,如果三个相等则删除。

#include <cstdio> #include <iostream> #include <algorithm> #include <cassert> using namespace std; class pNode { public: int x; pNode* nxt; }; int n, m; void print(pNode* s) { pNode *p3 = s; while(p3 != NULL) { printf("%d ", p3->x); p3 = p3->nxt; } puts(""); } int n1, n2, n3; void clean(pNode* s) { if(s == NULL) return; clean(s->nxt); free(s); } int main() { // freopen("005.in", "r", stdin); cin >> n1 >> n2 >> n3; pNode* h1 = (pNode*)malloc(sizeof(pNode)); pNode* r = h1; h1->x = -1; h1->nxt = NULL; while(n1--) { int y; cin >> y; pNode* o = (pNode*)malloc(sizeof(pNode)); o->x = y; o->nxt = NULL; r->nxt = o; r = o; } pNode* h2 = (pNode*)malloc(sizeof(pNode)); r = h2; h2->x = -1; h2->nxt = NULL; while(n2--) { int y; cin >> y; pNode* o = (pNode*)malloc(sizeof(pNode)); o->x = y; o->nxt = NULL; r->nxt = o; r = o; } pNode* h3 = (pNode*)malloc(sizeof(pNode)); r = h3; h3->x = -1; h3->nxt = NULL; while(n3--) { int y; cin >> y; pNode* o = (pNode*)malloc(sizeof(pNode)); o->x = y; o->nxt = NULL; r->nxt = o; r = o; } pNode *p1, *p2, *p3; p1 = h1->nxt; p2 = h2; p3 = h3; pNode* pp1 = h1; while(p1 != NULL) { int ref = p1->x; while(p2->nxt != NULL && p2->nxt->x <= ref) { p2 = p2->nxt; } while(p3->nxt != NULL && p3->nxt->x <= ref) { p3 = p3->nxt; } if(ref == p2->x && ref == p3->x) { pp1->nxt = p1->nxt; pNode* dn = p1; p1 = p1->nxt; free(dn); } else { pp1 = p1; p1 = p1->nxt; } } print(h1->nxt); clean(h1); clean(h2); clean(h3); return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注