3. DS单链表–合并
题目描述
假定两个单链表是递增有序，定义并实现以下函数，完成两个单链表的合并，继续保持递增有序
int LL_merge(ListNode *La, ListNode *Lb)
输入
第1行先输入n表示有n个数据，接着输入n个数据
第2行先输入m表示有M个数据，接着输入m个数据
输出
输出合并后的单链表数据，数据之间用空格隔开
输入样例
3 11 33 55
4 22 44 66 88
输出样例
11 22 33 44 55 66 88
参考代码
#include <bits/stdc++.h> using namespace std; #define ok 0 #define error -1 //链表结点类定义 class ListNode { public: int data; ListNode *next; ListNode() { next = NULL; } }; //带头结点的单链表类定义 class LinkList { public: ListNode *head; int len; //操作定义 LinkList() { head = new ListNode(); len = 0; } //链表回收，要逐个结点回收 ~LinkList() { ListNode *p, *q; p = head; while (p != NULL) { q = p; p = p->next; delete q; } len = 0; head = NULL; } //返回第i个结点的指针，如果不存在返回NULL ListNode *LL_index(int i) { if (i < 0 || i > len) return NULL; int k = 0; ListNode *p = head; while (p && k < i) { p = p->next; k++; } return p; } //获取第i个元素的数据 int LL_get(int i) { ListNode *p = LL_index(i); return p->data; } //把数值item插入第i个位置 int LL_insert(int i, int item) { if (i <= 0 || i > len + 1) return error; ListNode *p = LL_index(i - 1); ListNode *newNode = new ListNode(); newNode->data = item; newNode->next = p->next; p->next = newNode; len++; return ok; } //删除第i个结点 int LL_del(int i) { if (i <= 0 || i > len) return error; ListNode *p = LL_index(i - 1); ListNode *q = p->next; p->next = q->next; delete q; return ok; } //输出单链表的内容 void LL_display() { ListNode *p; p = head->next; while (p) { cout << p->data << " "; p = p->next; } cout << endl; } //结点交换 int swap(int pa, int pb) { ListNode *pa_point = LL_index(pa); ListNode *pb_point = LL_index(pb); if (!pa_point || !pb_point) return error; ListNode *front_pa = LL_index(pa - 1); ListNode *front_pb = LL_index(pb - 1); ListNode *temp = pa_point->next; pa_point->next = pb_point->next; pb_point->next = temp; front_pa->next = pb_point; front_pb->next = pa_point; return ok; } //两个单链表的合并 int LL_merge(ListNode *La, ListNode *Lb) { ListNode *p = head; while (La && Lb) { if (La->data < Lb->data) { ListNode *temp = new ListNode(); temp->data = La->data; temp->next = La->next; p->next = temp; p = p->next; La = La->next; len++; } else { ListNode *temp = new ListNode(); temp->data = Lb->data; temp->next = Lb->next; p->next = temp; p = p->next; Lb = Lb->next; len++; } } while (La) { ListNode *temp = new ListNode(); temp->data = La->data; temp->next = La->next; p->next = temp; p = p->next; La = La->next; len++; } while (Lb) { ListNode *temp = new ListNode(); temp->data = Lb->data; temp->next = Lb->next; p->next = temp; p = p->next; Lb = Lb->next; len++; } return 1; } }; int main() { int n; cin >> n; LinkList ex1, ex2, ex3; //输入数据 for (int i = 0; i < n; i++) { int data; cin >> data; ex1.LL_insert(i + 1, data); } cin >> n; //输入数据 for (int i = 0; i < n; i++) { int data; cin >> data; ex2.LL_insert(i + 1, data); } ex3.LL_merge(ex1.head->next, ex2.head->next); ex3.LL_display(); }
4. DS单链表—删除重复元素
题目描述
给定n个整数，按输入顺序建立单链表，删除其中的重复数字，输出结果链表。（要求不可以构建新结点，不可以定义新链表。在原链表上删除。）
输入
测试次数t
每组测试数据一行：
n（表示有n个整数），后跟n个数字
输出
对每组测试数据，输出删除重复数字后的结果链表表长和每个元素，具体格式见样例。
输入样例
3
10 1 2 3 4 1 2 10 20 30 20
5 1 1 1 1 1
6 20 22 22 22 22 20
输出样例
7: 1 2 3 4 10 20 30
1: 1
2: 20 22
参考代码
#include <bits/stdc++.h> using namespace std; #define ok 0 #define error -1 //链表结点类定义 class ListNode { public: int data; ListNode *next; ListNode() { next = NULL; } }; //带头结点的单链表类定义 class LinkList { public: ListNode *head; int len; //操作定义 LinkList() { head = new ListNode(); len = 0; } //链表回收，要逐个结点回收 ~LinkList() { ListNode *p, *q; p = head; while (p != NULL) { q = p; p = p->next; delete q; } len = 0; head = NULL; } //返回第i个结点的指针，如果不存在返回NULL ListNode *LL_index(int i) { if (i < 0 || i > len) return NULL; int k = 0; ListNode *p = head; while (p && k < i) { p = p->next; k++; } return p; } //获取第i个元素的数据 int LL_get(int i) { ListNode *p = LL_index(i); return p->data; } //把数值item插入第i个位置 int LL_insert(int i, int item) { if (i <= 0 || i > len + 1) return error; ListNode *p = LL_index(i - 1); ListNode *newNode = new ListNode(); newNode->data = item; newNode->next = p->next; p->next = newNode; len++; return ok; } //删除第i个结点 int LL_del(int i) { if (i <= 0 || i > len) return error; ListNode *p = LL_index(i - 1); ListNode *q = p->next; p->next = q->next; delete q; return ok; } //输出单链表的内容 void LL_display() { ListNode *p; p = head->next; cout << len << ": "; while (p->next) { cout << p->data << " "; p = p->next; } cout << p->data << endl; //cout << endl; } void deleteSame() { ListNode *p = head->next; ListNode *q = p->next; while (p) { while (q) { //cout << "2" << endl; if (q->data == p->data) { //cout << "3" << endl; ListNode *temp = head->next; while (temp->next != q) temp = temp->next; temp->next = q->next; delete q; len--; q = temp->next; } else q = q->next; } p = p->next; if (p) q = p->next; else break; } } }; int main() { int t; cin >> t; while (t--) { int n; cin >> n; LinkList list; for (int i = 0; i < n; i++) { int data; cin >> data; list.LL_insert(i + 1, data); } list.deleteSame(); list.LL_display(); } return 0; }
5. DS线性表—多项式相加
题目描述
对于一元多项式p(x)=p0+p1x+p2x2+…+pnxn，每个项都有系数和指数两部分，例如p2x2的系数为p2,指数为2。
编程实现两个多项式的相加。
例如5+x+2x2+3x3，-5-x+6x2+4x4，两者相加结果：8x2+3x3+4x4
其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。
要求用单链表实现。
输入
第1行：输入t表示有t组测试数据
第2行：输入n表示有第1组的第1个多项式包含n个项
第3行：输入第一项的系数和指数，以此类推输入n行
接着输入m表示第1组的第2个多项式包含m项
同理输入第2个多项式的m个项的系数和指数
参考上面输入第2组数据，以此类推输入t组
假设所有数据都是整数
输出
对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况
输出格式参考样本数据，格式要求包括：
1.如果指数或系数是负数，用小括号括起来。
2.如果系数为0，则该项不用输出。
3.如果指数不为0，则用符号^表示，例如x的3次方，表示为x^3。
4.多项式的每个项之间用符号+连接，每个+两边加1个空格隔开。
输入样例
2
4
5 0
1 1
2 2
3 3
4
-5 0
-1 1
6 2
4 4
3
-3 0
-5 1
2 2
4
9 -1
2 0
3 1
-2 2
输出样例
5 + 1x^1 + 2x^2 + 3x^3
(-5) + (-1)x^1 + 6x^2 + 4x^4
8x^2 + 3x^3 + 4x^4
(-3) + (-5)x^1 + 2x^2
9x^(-1) + 2 + 3x^1 + (-2)x^2
9x^(-1) + (-1) + (-2)x^1
参考代码
#include <bits/stdc++.h> using namespace std; class ListNode { public: int data1, data2; ListNode *next; ListNode() { next = NULL; } }; class LinkList { public: ListNode *head; int len; LinkList() { head = new ListNode; len = 0; } ~LinkList() { ListNode *p, *q; p = head; while (p) { q = p; p = p->next; delete q; } len = 0; head = NULL; } void createList(int n) { int i; ListNode *q = head; int d1, d2; for (i = 0; i < n; i++) { cin >> d1 >> d2; ListNode *p = new ListNode; p->data1 = d1; p->data2 = d2; q->next = p; p->next = NULL; q = p; } len = n; } void display() { int i; ListNode *p = head->next; for (i = 0; i < len; i++) { if (p->data1 == 0) { p = p->next; continue; } else if (p->data2 == 0) { if (p->data1 < 0) cout << "(" << p->data1 << ")"; else cout << p->data1; p = p->next; } else { if (p->data1 < 0) cout << "(" << p->data1 << ")x^"; else cout << p->data1 << "x^"; if (p->data2 < 0) cout << "(" << p->data2 << ")"; else cout << p->data2; p = p->next; } if (i != len - 1) cout << " + "; } cout << endl; } void add(LinkList *q) { ListNode *pre = head; ListNode *s = pre->next; ListNode *r = q->head->next; while (s != NULL && r != NULL) { if (s->data2 < r->data2) { s = s->next; pre = pre->next; } else if (s->data2 == r->data2) { s->data1 = s->data1 + r->data1; s = s->next; pre = pre->next; r = r->next; q->len--; } else { ListNode *m = new ListNode; m->data1 = r->data1; m->data2 = r->data2; m->next = s; pre->next = m; r = r->next; pre = pre->next; q->len--; } } if (r) { pre->next = r; len = len + q->len; } } ListNode *index(int i) { int j = 0; ListNode *p = head; while (p && j < i) { p = p->next; j++; } if (!p) return NULL; else return p; } }; int main() { int T, n, m; cin >> T; while (T--) { LinkList *La = new LinkList, *Lb = new LinkList; cin >> n; La->createList(n); cin >> m; Lb->createList(m); La->display(); Lb->display(); La->add(Lb); La->display(); delete La, Lb; } return 0; }
