1 鏈表的基本操作
我做鏈表題比較習慣于給鏈表設(shè)置哨兵（sentinel），這樣可以減少邊界極端情況的判斷搂抒，避免沒有考慮周全導致出錯。如下圖中尿扯，深灰色部分就是哨兵結(jié)點求晶。
image.png
1.1 順序創(chuàng)建鏈表
輸入樣例：
1 2 3 4 5 6 7 -1
輸出樣例
1 2 3 4 5 6 7
讀入結(jié)點，遇到-1就不讀了姜胖，那么借助哨兵結(jié)點（head）創(chuàng)建鏈表的寫法如下誉帅，最后返回的鏈表又去掉了哨兵：
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *readlist(); // 最后不返回哨兵結(jié)點
void printlist( struct ListNode *L )
{
struct ListNode *p = L;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *L, *Odd;
L = readlist();
printlist(L);
return 0;
}
struct ListNode *readlist(){
int curr = 0;
scanf("%d", &curr);
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->data = NULL;
head->next = NULL;
struct ListNode* p = head;
while (curr != -1){
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->data = curr;
temp->next = NULL;
p->next = temp;
p = p->next;
scanf("%d", &curr);
}
return head->next;
}
改成不使用哨兵，就需要加入對頭節(jié)點是否為NULL的判斷右莱。
struct ListNode *readlist(){
int curr = 0;
scanf("%d", &curr);
struct ListNode* head = NULL;
struct ListNode* p = head;
while (curr != -1){
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->data = curr;
temp->next = NULL;
if (head == NULL){
head = temp;
p = head;
} else {
p->next = temp;
p = p->next;
}
scanf("%d", &curr);
}
return head;
}
1.2 逆序創(chuàng)建鏈表
逆序創(chuàng)建鏈表蚜锨，其實就是把新讀入的結(jié)點，插到現(xiàn)有鏈表的頭部慢蜓。這個時候就沒有哨兵節(jié)點了亚再。
輸入樣例：
1 2 3 4 5 6 7 -1
輸出樣例
7 6 5 4 3 2 1
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist(); // 這個時候就沒有哨兵節(jié)點了
int main()
{
struct ListNode *p, *head = NULL;
head = createlist();
for ( p = head; p != NULL; p = p->next )
printf("%d ", p->data);
printf("\n");
return 0;
}
struct ListNode *createlist(){
int curr = 0;
scanf("%d", &curr);
struct ListNode *head = NULL;
while (curr != -1){
struct ListNode *newNode = (struct ListNode *) malloc(sizeof(struct ListNode));
newNode->data = curr;
newNode->next = head;
head = newNode;
scanf("%d", &curr);
}
return head;
};
1.3 插入元素
將x插入到以head為頭節(jié)點的鏈表指針的第pos位置上
輸入樣例：
1 2 3 4 5 6 8 9 -1
7 7
輸出樣例
1 2 3 4 5 6 7 8 9
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist(); // 帶哨兵結(jié)點的創(chuàng)建鏈表
void insert(struct ListNode *head, int pos, int X); // 帶哨兵結(jié)點的插入
void printlist( struct ListNode *head )
{
struct ListNode *p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *head = NULL;
int pos=0,X=0;
head = createlist();
scanf("%d %d", &pos, &X);
insert(head, pos, X);
printlist(head);
return 0;
}
struct ListNode *createlist(){
int curr = 0;
scanf("%d", &curr);
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->data = NULL;
head->next = NULL;
struct ListNode* p = head;
while (curr != -1){
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->data = curr;
temp->next = NULL;
p->next = temp;
p = p->next;
scanf("%d", &curr);
}
return head;
};
void insert(struct ListNode *head, int pos, int X){
struct ListNode *pre = head;
for (int i=0;i<pos-1;i++){
pre = pre->next;
}
struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->data = X;
newNode->next = pre->next;
pre->next = newNode;
}
1.4 查找和刪除元素
刪除以head為頭節(jié)點的鏈表指針上，所有數(shù)值為X的結(jié)點晨抡。其實是先查找然后刪除氛悬。
輸入樣例：
10 11 10 12 10 -1
10
輸出樣例
11 12
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist(); // 帶哨兵結(jié)點的創(chuàng)建鏈表
void deleteItem(struct ListNode *head, int X); // 帶哨兵結(jié)點的刪除
void printlist( struct ListNode *head )
{
struct ListNode *p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *head = NULL;
int pos=0,X=0;
head = createlist();
scanf("%d", &X);
deleteItem(head, X);
printlist(head);
return 0;
}
struct ListNode *createlist(){
int curr = 0;
scanf("%d", &curr);
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->data = NULL;
head->next = NULL;
struct ListNode* p = head;
while (curr != -1){
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->data = curr;
temp->next = NULL;
p->next = temp;
p = p->next;
scanf("%d", &curr);
}
return head;
};
void deleteItem(struct ListNode *head, int X){
struct ListNode *pre = head;
struct ListNode *p = pre->next;
while (p){
if (p->data == X){
pre->next = pre->next->next;
free(p);
p = pre->next;
} else {
pre = pre->next;
p = p->next;
}
}
}
1.5 單鏈表的反轉(zhuǎn)
原始單鏈表.png
循環(huán)結(jié)束.png
1結(jié)點的next指向oldn結(jié)點.png
頭結(jié)點指向newn結(jié)點.png
鏈表反轉(zhuǎn)是個常考的操作耘柱，上圖中展示了讓單鏈表1->2->3->4->5->6->null反轉(zhuǎn)前4個結(jié)點如捅，變成4->3->2->1->5->6->null的過程。
其實就是使用三個指針newn, oldn, temp進行以下循環(huán)操作调煎，直到反轉(zhuǎn)完題目要求的結(jié)點個數(shù)
- temp記錄old的下一個結(jié)點位置
- 然后讓oldn結(jié)點往回指向newn
- 然后依次將newn,oldn向右移動一個結(jié)點镜遣，返回第1步
循環(huán)結(jié)束后，要處理head->next->next和head->next 指向正確的位置
輸入樣例：
1 2 3 4 5 6 6 7 -1
輸出樣例
1 2 3 4 5 6 6 7
7 6 6 5 4 3 2 1
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist();
struct ListNode *reverse( struct ListNode *head );
void printlist( struct ListNode *head )
{
struct ListNode *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *p, *head = NULL,*reHead=NULL;
head = createlist();
printlist(head);
reHead = reverse(head);
printlist(reHead);
return 0;
}
struct ListNode *createlist(){
int curr = 0;
scanf("%d", &curr);
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->data = NULL;
head->next = NULL;
struct ListNode* p = head;
while (curr != -1){
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->data = curr;
temp->next = NULL;
p->next = temp;
p = p->next;
scanf("%d", &curr);
}
return head->next;
};
struct ListNode *reverse( struct ListNode *head ){
if (head==NULL){
return NULL;
}
struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
phead->data = NULL;
phead->next = head;
struct ListNode* newn = phead->next;
struct ListNode* oldn = newn->next;
while (oldn){
struct ListNode* temp = oldn->next;
oldn->next = newn;
newn = oldn;
oldn = temp;
}
phead->next->next = oldn;
phead->next = newn;
return phead->next;
}
1.6 鏈表的合并
鏈表的合并操作很容易讓人想到歸并排序里的merge操作士袄，本質(zhì)上都一樣悲关，只不過這里是用指針進行操作谎僻，歸并排序一般用數(shù)組進行操作。
L1和L2是給定的帶頭結(jié)點的單鏈表寓辱。要注意最后L1和L2要指向NULL艘绍。
輸入樣例
3
1 3 5
5
2 4 6 8 10
輸出樣例
1 2 3 4 5 6 8 10
NULL
NULL
List Merge(List L1, List L2){
List L = (List)malloc(sizeof(struct Node));
L->Next = NULL;
List p = L,p1=L1,p2=L2;
p1 = p1->Next;
p2 = p2->Next;
while (p1 && p2){
if (p1->Data <=p2->Data){
p->Next = p1;
p1 = p1->Next;
p = p->Next;
} else {
p->Next = p2;
p2 = p2->Next;
p = p->Next;
}
}
if (p1){
p->Next = p1;
}
if (p2){
p->Next = p2;
}
L1->Next = NULL;
L2->Next = NULL;
return L;
}
1.7 快慢指針
1.7.1 快慢指針解決單鏈表回文問題
leetcode-234:回文鏈表
請判斷一個鏈表是否為回文鏈表。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *createlist(); // 不帶頭結(jié)點的創(chuàng)建鏈表
bool isPalindrome(struct ListNode* head); // 判斷是否是回文單鏈表
void printlist( struct ListNode *head )
{
struct ListNode *p = head;
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *head = NULL;
head = createlist();
bool ans = isPalindrome(head);
if (ans){
printf("true");
} else {
printf("false");
}
return 0;
}
struct ListNode *createlist(){
int curr = 0;
scanf("%d", &curr);
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = NULL;
head->next = NULL;
struct ListNode* p = head;
while (curr != -1){
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = curr;
temp->next = NULL;
p->next = temp;
p = p->next;
scanf("%d", &curr);
}
return head->next;
};
bool isPalindrome(struct ListNode* head){
struct ListNode* fast = head, *slow = head;
// fast ==NULL 偶數(shù),slow指向鏈表1->2->2->1->NULL的第二個2
// fast != NULL 奇數(shù),slow指向鏈表1->2->3->2->1->NULL的3
while (fast !=NULL && fast->next!=NULL){
fast = fast->next->next;
slow = slow->next;
}
if(fast!=NULL){ // 奇數(shù)時slow再向右一步
slow = slow->next;
}
// 反轉(zhuǎn)slow后面的鏈表
struct ListNode* newn = NULL;
struct ListNode* oldn = slow;
while (oldn){
struct ListNode* temp = oldn->next;
oldn->next = newn;
newn = oldn;
oldn = temp;
}
// 比較
struct ListNode* left = head;
struct ListNode* right = newn;
while (right){
if (left->val != right->val){
return false;
}
left = left->next;
right = right->next;
}
return true;
}
1.7.2 快慢指針解決環(huán)形鏈表問題
判斷是否有環(huán)
leetcode-141:環(huán)形鏈表
給定一個鏈表秫筏，判斷鏈表中是否有環(huán)诱鞠。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *fast = head, *slow = head;
while (fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if (fast == slow){
return true;
}
}
return false;
}
找到鏈表開始入環(huán)的第一個節(jié)點
leetcode-142: 環(huán)形鏈表 II
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點这敬。 如果鏈表無環(huán)般甲，則返回 null。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast = head, *slow = head;
while (fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if (fast == slow){
break;
}
}
if (fast == NULL || fast->next == NULL){
return NULL;
}
slow = head;
while (slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
找到鏈表倒數(shù)第k個元素
leetcode:返回倒數(shù)第 k 個節(jié)點
leetcode:面試題22. 鏈表中倒數(shù)第k個節(jié)點
leetcode-19:刪除鏈表的倒數(shù)第N個節(jié)點
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int kthToLast(struct ListNode* head, int k){
struct ListNode* fast = head, *slow = head;
while (k>0){
fast = fast->next;
k--;
}
while (fast){
fast = fast->next;
slow = slow->next;
}
return slow->val;
}
2 靜態(tài)鏈表
動態(tài)鏈表使用指針來建立結(jié)點之間的關(guān)聯(lián)關(guān)系鹅颊，而當題目告訴你結(jié)點地址在5位數(shù)及以內(nèi)時敷存，可以使用靜態(tài)鏈表。
靜態(tài)鏈表其實就是使用結(jié)構(gòu)體數(shù)組堪伍，數(shù)組中每個元素是一個包含數(shù)據(jù)锚烦、下一個地址的結(jié)構(gòu)體。使用數(shù)組的方便之處在于帝雇，可以直接使用下標表示結(jié)點的地址涮俄，查詢也快速。
02-線性結(jié)構(gòu)3 Reversing Linked List (25分)
給定整數(shù) K 和單鏈表 L, 你需要每K個元素把鏈表反轉(zhuǎn)一次尸闸。
- 例如給定鏈表 1→2→3→4→5→6, K=3,那么反轉(zhuǎn)后的結(jié)果是3→2→1→6→5→4;
- 如果 K=4, 輸出結(jié)果是 4→3→2→1→5→6.
- 要注意這道題會有多余結(jié)點不在鏈表上
樣例輸入
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
樣例輸出
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
這道題我用了兩種方法彻亲。第一種方法偷懶，直接使用了c++的reverse() 方法吮廉，但是當時寫完仍然不知道對單鏈表到底怎么反轉(zhuǎn)苞尝。于是嘗試用c寫了第二種方法。
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MaxLen 100001
struct node{
int Addr;
int num;
int NextAddr;
};
typedef struct node Node;
Node nodes[MaxLen];
vector<Node> nodeList;
int main(){
int firstAdd, N, K;
scanf("%d %d %d", &firstAdd, &N,&K);
while (N--){
Node n;
scanf("%d %d %d", &n.Addr, &n.num,&n.NextAddr);
nodes[n.Addr] = n;
}
int address = firstAdd;
while(address!=-1){
nodeList.push_back(nodes[address]);
address = nodes[address].NextAddr;
}
int len = nodeList.size();
int period = len/K;
for (int i=1;i<=period;i++){
int head = (i-1)*K;
int end = i*K;
reverse(nodeList.begin()+head,nodeList.begin()+end);
}
for (int i=0;i<len-1;i++){
nodeList[i].NextAddr = nodeList[i+1].Addr;
printf("%05d %d %05d\n", nodeList[i].Addr,nodeList[i].num,nodeList[i].NextAddr);
}
nodeList[len-1].NextAddr =-1;
printf("%05d %d %d", nodeList[len-1].Addr,nodeList[len-1].num,nodeList[len-1].NextAddr);
}
c語言宦芦，手寫反轉(zhuǎn)鏈表
#include <stdlib.h>
#include <stdio.h>
struct node{
int Addr;
int num;
int NextAddr;
};
typedef struct node Node;
Node nodes[100001];
int main(){
// 讀入
int firstAdd, N, K;
scanf("%d %d %d", &firstAdd, &N,&K);
for (int i=0;i<N;i++){
Node currNode;
scanf("%d %d %d", &currNode.Addr, &currNode.num,&currNode.NextAddr);
nodes[currNode.Addr] = currNode;
}
Node head;
head.Addr = NULL;
head.num = NULL;
head.NextAddr = firstAdd;
Node *currHead = &head; // 指向頭節(jié)點宙址，作為每次翻轉(zhuǎn)的頭指針
// 獲取真實結(jié)點個數(shù),因為會有多余結(jié)點不在鏈表上
Node *q = &head;
int realN = 0;
while (q && q->NextAddr!=-1){
q = &nodes[q->NextAddr];
realN++;
}
// 逆序
int period = realN/K;
while (period > 0 && K>1){ // 如果K=1就不需要做逆序
Node *newn = &nodes[currHead->NextAddr];
Node *oldn = &nodes[newn->NextAddr];
int len = K;
while (len>1){ // 4個結(jié)點翻轉(zhuǎn)時，會有3個結(jié)點指向前一個結(jié)點
Node *temp; // 依次3個相鄰指針 newn,oldn,temp
if (oldn->NextAddr!=-1){
temp = &nodes[oldn->NextAddr];
} else {
temp = NULL;
}
oldn->NextAddr = newn->Addr;
newn = oldn;
oldn = temp;
len--;
}
Node *temp2 = &nodes[currHead->NextAddr]; // 指向下一批要翻轉(zhuǎn)結(jié)點的頭節(jié)點
if (oldn){
nodes[currHead->NextAddr].NextAddr = oldn->Addr;
} else {
nodes[currHead->NextAddr].NextAddr = -1;
}
currHead->NextAddr = newn->Addr;
if(period == realN/K){
head.NextAddr = newn->Addr;
}
currHead = temp2;
period--;
}
// 輸出
Node p = nodes[head.NextAddr];
while(p.NextAddr != -1){
printf("%05d %d %05d\n", p.Addr, p.num,p.NextAddr);
p = nodes[p.NextAddr];
}
printf("%05d %d %d\n", p.Addr, p.num,p.NextAddr);
}
3 線性結(jié)構(gòu)練習題
02-線性結(jié)構(gòu)2 一元多項式的乘法與加法運算 (20分)
設(shè)計函數(shù)分別求兩個一元多項式的乘積與和调卑。
輸入格式:
輸入分2行抡砂，每行分別先給出多項式非零項的個數(shù)，再以指數(shù)遞降方式輸入一個多項式非零項系數(shù)和指數(shù)（絕對值均為不超過1000的整數(shù)）恬涧。數(shù)字間以空格分隔注益。
輸出格式:
輸出分2行，分別以指數(shù)遞降方式輸出乘積多項式以及和多項式非零項的系數(shù)和指數(shù)溯捆。數(shù)字間以空格分隔丑搔，但結(jié)尾不能有多余空格。零多項式應(yīng)輸出0 0。
輸入樣例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
輸出樣例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
最開始我是用鏈表做的低匙。鏈表的注意點有
- head節(jié)點是沒有數(shù)據(jù)的，真正的第一個數(shù)據(jù)在head->Next節(jié)點里碳锈，這樣寫的目的是利用哨兵簡化實現(xiàn)難度
- 指針指向一個不存在的地址時就會出現(xiàn)段錯誤
- 理解題意顽冶，題目說的是head->Next為NULL時，只需要輸出
0 0 - 當相加時倆系數(shù)相互抵消售碳，那么這個節(jié)點也就不存在了
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode *List;
struct LNode{
int co;
int exp;
List Next;
};
List PtrL;
List read(int n1){
List pL1 = (List) malloc(sizeof(struct LNode));
pL1->Next = NULL;
List t = pL1;
for (int i=0;i<n1;i++){
List a = (List) malloc(sizeof(struct LNode));
a->Next = NULL;
scanf("%d", &(a->co));
scanf("%d", &(a->exp));
t->Next = a;
t = t->Next;
}
t->Next = NULL;
return pL1;
}
void attach(int c, int e, List rear){
List t = (List) malloc(sizeof(struct LNode));
t->co = c;
t->exp = e;
t->Next = NULL;
rear->Next = t;
rear = t;
}
List Addp2(List L1,List L2){
List r = (List) malloc(sizeof(struct LNode));
r->Next = NULL;
List curr = r;
List p1 = L1->Next, p2=L2->Next;
if (!p1 && !p2){
return NULL;
}
while (p1 && p2){
if (p1->exp > p2->exp){
attach(p1->co, p1->exp, curr);
p1 = p1->Next;
curr = curr->Next;
}
else if (p1->exp < p2->exp){
attach(p2->co, p2->exp, curr);
p2 = p2->Next;
curr = curr->Next;
}
else {
int sum = 0;
sum = p1->co+p2->co;
if (sum){
attach(sum, p2->exp, curr);
curr = curr->Next;
}
p1 = p1->Next;
p2 = p2->Next;
}
}
while (p1){
attach(p1->co, p1->exp, curr);
p1 = p1->Next;
curr = curr->Next;
}
while (p2){
attach(p2->co, p2->exp, curr);
p2 = p2->Next;
curr = curr->Next;
}
return r;
}
List Multiply(List pL1,List pL2){
List p1 = pL1->Next, p2=pL2->Next;
List sumHead = (List) malloc(sizeof(struct LNode));
if (!p1 && !p2){
return NULL;
}
List t = sumHead;
while (p1){
attach(p2->co * p1->co, p2->exp + p1->exp, t);
p1 = p1->Next;
t= t->Next;
}
p2 = p2->Next;
while (p2){ // 當p2為NULL時退出循環(huán)
p1 = pL1->Next;// p1重新回到起點
t = sumHead;
while (p1){
int c = p2->co * p1->co;
int e = p2->exp + p1->exp;
while (t->Next && t->Next->exp > e){
t = t->Next;
}
if ((t->Next) && (t->Next->exp==e)){
if (t->Next->co + c !=0){
t->Next->co+=c;
} else {
List dis = t->Next;
t->Next = dis->Next;
free(dis);
}
}
else {
List insert = (List) malloc(sizeof(struct LNode));
insert->co = c;
insert->exp = e;
insert->Next = t->Next;
t->Next = insert;
t = t->Next;
}
p1 = p1->Next;
}
p2 = p2->Next;
}
return sumHead;
}
void Display(List L){
List p = L;
p = p->Next;
if (p==NULL){
printf("0 0");
}
int flag = 0;
while (p){
if (flag==0){
printf("%d %d", p->co, p->exp);
flag = 1;
} else {
printf(" %d %d", p->co, p->exp);
}
p = p->Next;
}
}
int main(){
int n1=0,n2=0;
scanf("%d", &n1);
List pL1 = read(n1);
scanf("%d", &n2);
List pL2 = read(n2);
List M = Multiply(pL1,pL2);
Display(M);
printf("\n");
List A = Addp2(pL1,pL2);
Display(A);
return 0;
}
然后參考網(wǎng)上的方法使用結(jié)構(gòu)數(shù)組和連續(xù)數(shù)組强重，其中連續(xù)數(shù)組的下標是指數(shù)exp，值是系數(shù)co
#include <stdio.h>
struct Poly{
int ex;
int co;
}Poly[1001];
int main(){
int n1,n2,M[2005]={0},A[1001]={0};
scanf("%d", &n1);
for (int i=0;i<n1;i++){
scanf("%d %d", &Poly[i].co,&Poly[i].ex);
A[Poly[i].ex] += Poly[i].co;
}
int temp1,temp2;
scanf("%d", &n2);
for (int i=0;i<n2;i++){
scanf("%d %d", &temp1,&temp2);
A[temp2]+=temp1;
for (int j=0;j<n1;j++){
M[temp2+Poly[j].ex] += (temp1*Poly[j].co);
}
}
int isFirst =1;// 1-是第一個輸出
int haveOutput = 0; // 0 不是零多項式
for (int i=2001;i>=0;i--){
if (M[i]!=0){
if (!isFirst){
printf(" %d %d", M[i],i);
} else {
isFirst = 0;
printf("%d %d", M[i],i);
}
haveOutput = 1;
}
}
if (!haveOutput){
printf("0 0");
}
isFirst =1;
haveOutput = 0;
printf("\n");
for (int i=1001;i>=0;i--){
if (A[i]!=0){
if (!isFirst){
printf(" %d %d", A[i],i);
} else {
isFirst = 0;
printf("%d %d", A[i],i);
}
haveOutput = 1;
}
}
if (!haveOutput){
printf("0 0");
}
}
