主頁 >  其他 > 程式語言與編程實踐4-> 藍橋杯C/C++備賽記錄2 | 第二周學習訓練

程式語言與編程實踐4-> 藍橋杯C/C++備賽記錄2 | 第二周學習訓練

2022-03-24 07:57:34 其他

0323，又是一周星期三，按道理該總結了，這周前幾天寫題比較多，后面事情多了起來，就沒怎么寫了，主要方向是洛谷的基本語法熟悉，PTA平臺資料結構的一些題目，

0323附上: 題目比較多，所以文章可能有點長，

00 0317

00-1 P1116 車廂重組

00-1-1 題目描述

在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉，

一個車站的職工發現橋的長度最多能容納兩節車廂，如果將橋旋轉180度，則可以把相鄰兩節車廂的位置交換，

用這種方法可以重新排列車廂的順序，于是他就負責用這座橋將進站的車廂按車廂號從小到大排列，

他退休后，火車站決定將這一作業自動化，其中一項重要的作業是編一個程式，

輸入初始的車廂順序，計算最少用多少步就能將車廂排序，

輸入格式

共兩行，

第一行是車廂總數N (N≤10000)，

第二行是 N 個不同的數表示初始的車廂順序，

輸出格式

一個整數，最少的旋轉次數，

00-1-2 輸入輸出樣例

輸入

4
4 3 2 1

輸出

6

00-1-3 解決代碼

這道題，有一點意思，因為題目中沒有告訴我們排序的操作程序，因此我們會去想示例的排序次數是怎么得出來的，所以我們寫的程式就會是冒泡排序或者其他，再在冒泡排序中計數，

但我正要手寫排序的時候，突然想起來實際上根本用不著，只輸出移動次數意味著什么？意味著只需要統計一個數字前面有幾個比它大，所以我們統計序列里每個數字前的count就可以啦，

題解最高贊也是我這個想法!-_-!

#include<iostream>
using namespace std;

int main(){
    int N,count = 0;
    cin >> N;
    int train[N] = {0};
    for(int i = 0; i < N; i++){
        cin >> train[i];
    }
    //查一個數前面有幾個比他大
    for(int i  = 0; i < N; i++){
        for(int j = 0; j < i; j++){
            if(train[j] > train[i]){
                count++;
            }
        }
    }
    cout << count;
    return 0;
}

00-2 P1146 硬幣翻轉

00-2-1 題目描述

在桌面上有一排硬幣，共N枚，每一枚硬幣均為正面朝上，

現在要把所有的硬幣翻轉成反面朝上，規則是每次可翻轉任意N-1枚硬幣

（正面向上的被翻轉為反面向上，反之亦然），

求一個最短的操作序列（將每次翻轉N-1枚硬幣成為一次操作），

輸入格式

一個自然數N（N為不大于100的偶數），

輸出格式

第一行包含一個整數S，表示最少需要的操作次數，接下來的S行每行分別表示每次操作后桌上硬幣的狀態

（一行包含N個整數（0或1），表示每個硬幣的狀態：

0――正面向上，和1――反面向上，不允許出現多余空格），

對于有多種操作方案的情況，則只需操作的字典序最小輸出一種，

注：操作的字典序：對于一次操作，1表示翻轉，0表示不反轉，

但是需要你輸出的是每一次操作完的狀態，0表示正面朝上，1表示反面朝上，

00-2-2 輸入輸出樣例

輸入

4

輸出

4
0111
1100
0001
1111

00-2-3 解決代碼

這是個很簡單的題，但是需要會讀題......每次反轉n-1等價于每次翻一個，再把n個全翻一次，

  • 如果n是偶數，執行n次以上的操作第二步就被抵消了，只執行第一步，所以輸入n就可以輸出n作為答案；
  • 如果n是奇數，相當于執行n次第一步，然后把所有的硬幣翻一次面，這樣就無法實作翻面，這種情況不可能，

接著就是每一組翻動都輸出01序列就好了，

參考題解

#include<iostream>
using namespace std;

int main(){
    int n;
    int coin[105] = {0};
    cin >> n;
    cout << n << endl; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(j!=i){
                coin[j] = 1 - coin[j];
            }  
            cout << coin[j];
        }
        cout <<endl;
    }
    return 0;
}

01 0318

01-1 P1150Peter 的煙

01-1-1 題目描述

Peter 有 n 根煙，他每吸完一根煙就把煙蒂保存起來，

k（k>1）個煙蒂可以換一個新的煙，那么 Peter 最終能吸到多少根煙呢？

輸入格式

每組測驗資料一行包括兩個整數 n, k（1 < n, k <= 10^8），

輸出格式

對于每組測驗資料，輸出一行包括一個整數表示最終煙的根數，

01-1-2 輸入輸出樣例

輸入 1

4 3

輸出1

5

輸入2

10 3

輸出2

14

01-1-3 解決代碼

這道題我想了一會兒，發現這件事情并不難，只需要一個回圈就可以實作，只不過需要不斷更新香煙的總數n，有一點剩余定理無限逼近的味道，但是題目是整數，所以總會到達， 可以舉一個具體的迭代程序來看： 以4 3 為例：

i=1 <4, i%3!=0，繼續；

i=2 <4，i%3!=0，繼續;

i=3 <4, i%3==0, n++;

i=4 <5, i%3!=0, 繼續；

i=5 =5, i%3!=0,繼續；

i=6 >6,結束

#include<iostream>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    int count =  n ;
    int sum = k;
    for(int i = 1; i <= n; i++){
        
        if(i%k==0)n++;
    }
    cout << n;
}

01-2 P1151 子數整數

01-2-1 題目描述

123

01-2-2 輸入輸出樣例

輸入(0<k<1000)

15

輸出

22555
25555
28555
30000

01-2-3 解決代碼

這道題不是很難，也讓我意識到該復習一些演算法和資料結構了，對于10000到30000的這些整數，每一個都求出它的三個子數，進行判斷即可，

這道題提交了兩次，原因是沒有把題目看完全，題目中說若沒有符合條件的，則輸出"No"，我沒有考慮到，所以就有測驗用例出錯了，

#include<iostream>
using namespace std;

int main(){
    int k;
    cin >> k;
    int sub1,sub2,sub3;
    int flag = 0;//得設計一個標志位，
    for(int i = 10000; i <= 30000; i++){
        sub1 = i/100;
        sub2 = (i-i/10000*10000)/10;
        sub3 = i%1000;
        if(sub3%k==0&&sub2%k==0&&sub1%k==0){
            flag = 1;
            cout<<i <<endl;
        }
    }
    if(!flag)cout << "No"<<endl;
    return 0;
}

01-3 P1152 歡樂的跳

01-3-1 題目描述 & 輸入輸出樣例

1231

01-3-3 解決代碼

這道題其實也沒啥好說的，新建一個陣列來記錄兩相鄰元素的差，再取個絕對值，進行逐項判斷，不過自己對于while的語法有些忘了，題目的要求也沒有看清楚，

取絕對值的函式：

#include<stdlib.h>內，有abs()函式，可以對整型變數求絕對值；
#include<math.h>內，有fabs()函式，可以對浮點型變數求絕對值；

#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int jolly[n]= {0};
    int jump[n-1] = {0};
    for(int i = 0; i < n; i++){
        cin >> jolly[i];
    }//第一次是忘了輸入陣列》，，
    int t = 0,j=1,i=0;
    while(j!=n){
        jump[t++]=jolly[j++]-jolly[i++];
    }//3 2 -1
    //第二次是把回圈條件寫成了j==n,屬于是太久不用while了
    int flag=0;
    for(int i = 0; i < n-1; i++){
        if(abs(jump[i])<n&&abs(jump[i])>0){
            flag ++;
        }
    }
    if(flag==n-1)cout<<"Jolly"<<endl;
    else{
        cout << "Not jolly"<<endl;
    }
    //第三次是Not Jolly報錯，Jd
    return 0;
}
//屬實是麻了，Not jolly要小寫，麻了，

01-4 01-復雜度3 二分查找

01-4-1 題目描述

函式介面定義：

Position BinarySearch( List L, ElementType X );

其中List結構定義如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存線性表中最后一個元素的位置 */
};

L是用戶傳入的一個線性表，其中ElementType元素可以通過>、==、<進行比較，并且題目保證傳入的資料是遞增有序的，函式BinarySearch要查找X在Data中的位置，即陣列下標（注意：元素從下標1開始存盤），找到則回傳下標，否則回傳一個特殊的失敗標記NotFound，

裁判測驗程式樣例：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存線性表中最后一個元素的位置 */
};

List ReadInput(); /* 裁判實作，細節不表，元素從下標1開始存盤 */
Position BinarySearch( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    Position P;

    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d\n", P);

    return 0;
}

/* 你的代碼將被嵌在這里 */

01-4-2 輸入輸出

輸入樣例1：

5
12 31 55 89 101
31

輸出樣例1：

2

輸入樣例2：

3
26 78 233
31

輸出樣例2：

0

01-4-3 解決代碼

在mooc上用浙大的資料結構mooc來溫習資料結構的知識，提供了一個高質量的題測平臺PTA，當然要用起來，同時洛谷的入門題刷著也有點沒意思了，每次只檢查一些語法的問題以及思考的角度，對于高階的結構和演算法都不怎么涉及，是時候更進一步了，所以來了一道PTA的資料結構題...

雖然是二分查找但還是有一點折磨（雖然思路很簡單但是做法很難一遍過）...平臺的測驗用例有一些刁鉆，我拿當時學資料結構時已經通過的代碼來提交也會報錯，推薦一個二分查找講的很好的視頻.講解的模板考慮很全面，

//01二分查找
Position BinarySearch( List L, ElementType X ){
    int head = 0, tail = L->Last+1;
    
    while(head+1!=tail){
        int mid = head+(tail-head)/2;
        if(L->Data[mid]==X){
            return mid;
        }
        if(L->Data[mid]>X){
            tail = mid;
        }
        if(L->Data[mid]<X){
            head = mid;
        }
    }
    return NotFound;
}

01-5 02-線性結構1 兩個有序鏈表序列的合并

01-5-1 題目描述

題要求實作一個函式，將兩個鏈表表示的遞增整數序列合并為一個非遞減的整數序列，

函式介面定義：

List Merge( List L1, List L2 );

其中List結構定義如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存盤結點資料 */
    PtrToNode   Next; /* 指向下一個結點的指標 */
};
typedef PtrToNode List; /* 定義單鏈表型別 */

L1和L2是給定的帶頭結點的單鏈表，其結點存盤的資料是遞增有序的；函式Merge要將L1和L2合并為一個非遞減的整數序列，應直接使用原序列中的結點，回傳歸并后的帶頭結點的鏈表頭指標，

裁判測驗程式樣例：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 細節在此不表 */
void Print( List L ); /* 細節在此不表；空鏈表將輸出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代碼將被嵌在這里 */

01-5-2 輸入輸出

輸入樣例：

3
1 3 5
5
2 4 6 8 10

輸出樣例：

1 2 3 4 5 6 8 10 
NULL
NULL

01-5-3 解決代碼

寫一個二分已經有點難了，寫有序鏈表合并確實也有點困難，不過這種困難來自于手法上的生疏，想法上有力了很多（也有可能是學習了后續課程演算法設計的緣故，演算法講授的更宏觀），

這個問題很簡單，分別遍歷AB兩個鏈表，逐結點比較，如果符合插入條件，則執行插入操作，如果不滿足，指標繼續向后移動，直到兩者中的一者到達鏈表邊界（空）；然后將后續未比較內容直接鏈過來，

List Merge(List L1,List L2){
    List L3,p,q,l0;
    L3 = (List)malloc(sizeof(List));
    l0=L3;
    p = L1->Next;
    q = L2->Next;
    //演算法編程里這種變數更容易敲，雖然專案里不喜歡
    L3->Next = NULL;
    while(p&&q)
    {
        if(p->Data<=q->Data)
        {
            l0->Next = p;
            l0 = l0->Next;
            p=p->Next;
        }
        else{
            l0->Next = q;
            l0 = l0->Next;
            q=q->Next;
        }      
    }
    l0->Next = p?p:q;
//     if(p)
//     {
//         l0->Next=p;
//     }
//     if(q)
//     {
//        l0->Next = q;
//     }
    L1->Next=NULL;
    L2->Next=NULL;
    //合并完成兩鏈表置空，題目要求的事情一定要做
    return L3;
}

02 0319

02-1 01-復雜度1 最大子列和問題

02-1-1 題目描述

給定K個整陣列成的序列{ N1, N2, ..., Nk }，“連續子列”被定義為{ Ni, Ni+1, ..., Nj }，其中 1≤ i ≤ j ≤ K，“最大子列和”則被定義為所有連續子列元素的和中最大者，例如給定序列{ -2, 11, -4, 13, -5, -2 }，其連續子列{ 11, -4, 13 }有最大的和20，現要求你撰寫程式，計算給定整數序列的最大子列和，

本題旨在測驗各種不同的演算法在各種資料情況下的表現，各組測驗資料特點如下：

  • 資料1：與樣例等價，測驗基本正確性；
  • 資料2：102個隨機整數；
  • 資料3：103個隨機整數；
  • 資料4：104個隨機整數；
  • 資料5：105個隨機整數；

輸入格式:

輸入第1行給出正整數*K* (≤100000)；第2行給出*K*個整數，其間以空格分隔，

輸出格式:

在一行中輸出最大子列和，如果序列中所有整數皆為負數，則輸出0，

02-1-2 輸入輸出

輸入樣例:

6
-2 11 -4 13 -5 -2

輸出樣例:

20

01-1-3 解決代碼

這道題半年前可能不太會，現在是有一定思路的，可以規定兩個指標，一個指標負責從頭到尾的主遍歷確定頭元素，第二個指標負責通過遍歷改變尾元素，一首一尾就能確定一個子列，這道題還沒有讓輸出最大子列和對應的那個子列，所以只需要設定一個max，不斷更新即可，

所以很簡單：

不過寫的時候還是犯了低級錯誤，即輸入輸出陣列的時候不是A[i]，而是A[k]，所以一直得不到正確結果，

//0319最大子列和
#include<iostream>
using namespace std;

int main(){
    int K;
    cin >> K;
    int A[K]={0};
    for(int i = 0; i < K; i++){
        cin >> A[i];
    }
    //輸入完成
    //計算
    // for(int i = 0; i < K; i++){
    //     cout << A[i];
    // }
    int sum = 0, tag = 0, count = 0;
    for(int i = 0; i < K; i++){
        count = A[i];
        if(count>=sum)sum = A[i];
        if(A[i]<0)tag++;
        //cout << count<<endl;
        for(int j = i+1; j < K;j++){
            //cout << j << " ";
            count+=A[j];
            //cout << count<<endl;
            if(count >= sum){
                sum = count;
            }
        }
    }
    if(tag < K){
        cout << sum;
    }
    else{
        cout <<0;
    }
    return 0;
}
//思路沒問題，陣列的輸入輸出寫錯了，我麻了呀，

02-2 01-復雜度2 Maximum Subsequence Sum

02-2-1 題目描述

給定一個序列K整數 {N1,N2, ...,NK}.連續子序列定義為 {Ni,Ni+1, ...,Nj} 其中1≤ i ≤ j ≤ K.最大子序列是具有其元素最大和的連續子序列，例如，給定序列 { -2， 11， -4， 13， -5， -2 }，其最大子序列為 { 11， -4， 13 }，最大和為 20，

現在，您應該找到最大總和，以及最大子序列的第一個和最后一個數字，

輸入規格：

每個輸入檔案包含一個測驗用例，每個案例占用兩行，第一行包含正整數K (≤10000).第二行包含K數字，以空格分隔，

輸出規格：

對于每個測驗用例，在一行中輸出最大和，以及最大子序列的第一個和最后一個數字，數字必須用一個空格分隔，但行尾不得有多余的空格，如果最大子序列不是唯一的，請輸出索引最小的子序列我和j（如示例案例所示），如果所有K數字為負數，然后其最大和定義為 0，并且您應該輸出整個序列的第一個和最后一個數字，

02-2-2 輸入輸出

示例輸入：

10
-10 1 2 3 4 -5 -23 3 7 -21

示例輸出：

10 1 4

02-2-3 解決代碼

這道題是上一道題的加強版，要求在輸出最大子列和的同時輸出這個子列的頭尾元素，

就我上道題的思路，實作這一個升級是很簡單的，增加兩個標記位即可，遇到最大值就把頭尾存下來，同時它強調輸出下標較小的，所以要把上道題中的 ">=" 改成 ">" ，

第一次提交，感覺已經很周全了，出現了部分正確：

sdfs

一個正數的情況出錯，稍加檢查發現我用來甄別在一個數出取得最大子列和的地方出錯，寫成了：

  for(int i = 0; i < K; i++){
        count = A[i];
        if(count>sum){
            sum = A[i];
            left = i;
            right = i;
            //應當是left = A[i],left和right都應該是，
        }

代碼如下：

//0319加強版的最大子列
//需要在輸出最大子列和的同時輸出首尾元素，用我的思路來講，只需要增加兩個標記位罷了，
#include<iostream>
using namespace std;

int main(){
    int K;
    cin >> K;
    int A[K]={0};
    for(int i = 0; i < K; i++){
        cin >> A[i];
    }
    //輸入完成
    //計算
    // for(int i = 0; i < K; i++){
    //     cout << A[i];
    // }
    int sum = 0, tag = 0, count = 0;
    int left = 0, right = 0;//增加兩個標記位
    for(int i = 0; i < K; i++){
        count = A[i];
        if(count>sum){
            sum = A[i];
            left = A[i];
            right = A[i];
        }
        if(A[i]<0)tag++;
        //cout << count<<endl;
        for(int j = i+1; j < K;j++){
            //cout << j << " ";
            count+=A[j];
            //cout << count<<endl;
            if(count > sum){
                sum = count;
                left = A[i];
                right = A[j];
                //cout << sum<<" "<< left << " "<<right<<endl;
            }
        }
    }
    if(tag < K){
        cout << sum<<" "<< left << " "<<right<<endl;
    }
    else{
        cout << 0 <<" " << A[0] << " " << A[K-1];
    }
    return 0;
}

03 0320 / 0322

0320開了這個題，但是沒寫，去寫計組的一個實驗測驗題了，有些難度，寫了半天，所以就沒有刷題，

0321打開又想了一會，覺得加法有點思路，乘法實作起來還是有點陌生，去寫計組作業和微機介面mooc去了，

0322晚上終于得空，把實作了一下，參照了一下別的博主的思路，

03-1 線性結構2 一元多項式的乘法與加法運算

03-1-1 題目描述

設計函式分別求兩個一元多項式的乘積與和，

輸入格式:

輸入分2行，每行分別先給出多項式非零項的個數，再以指數遞降方式輸入一個多項式非零項系數和指數（絕對值均為不超過1000的整數）， 數字間以空格分隔，

輸出格式:

輸出分2行，分別以指數遞降方式輸出乘積多項式以及和多項式非零項的系數和指數， 數字間以空格分隔，但結尾不能有多余空格， 零多項式應輸出，0 0

03-1-2 輸入輸出

設計函式分別求兩個一元多項式的乘積與和，

輸入格式:

輸入分2行，每行分別先給出多項式非零項的個數，再以指數遞降方式輸入一個多項式非零項系數和指數（絕對值均為不超過1000的整數）， 數字間以空格分隔，

輸出格式:（！這里最重要！）

輸出分2行，分別以指數遞降方式輸出乘積多項式以及和多項式非零項的系數和指數， 數字間以空格分隔，但結尾不能有多余空格， 零多項式應輸出，0 0

03-1-3 解決思路以及細節問題

感覺用陣列可以硬做，但是用鏈表其實更好，本來在回憶鏈表的一些操作，突然想起來自己明明報了浙大的mooc，打開一看，以上的題目居然都有實作程序，不禁感嘆這個mooc質量之高，

參考思路

敲出來當然覺得很高興，因為去年同期，這是很難的事情，但高興早了，提交上去之后報錯，全錯，格式錯誤，仔細檢查發現是自己的輸出函式不對（下面代碼輸出函式的注釋部分），

又審了一遍題，發現沒有認真理解題目關于輸出格式的要求，要求 和多項式 和 積多項式 輸出之間有一個換行，并且每一行最后不能有空字符，每一個結點的兩個數之間有空格，結點和結點之間也有空格，我的代碼是實作不了這些的，我只好應用了putchar().

改進之后其實還是錯的(20分拿了16分）,是細節之錯，我覺得很有記錄的必要，見這段代碼下方，先來看看近乎正確代碼：

//0319兩個一元多次多項式的相加
//感覺有陣列可以硬做，但是用鏈表其實更好
#include<iostream>
using namespace std;

typedef struct LNode{
    int coef,exp;
    LNode *next;
}LNode;
LNode *creatList(){//創建鏈表
    int n ;
    cin >> n;
    LNode *head = new LNode;
    head->next = NULL;
    LNode *p = head;

    while(n--){
        LNode *q = new LNode;
        q->next = NULL;
        cin >> q->coef >> q->exp;
        p = p->next = q;
        //相當于p->next = q; p = p->next;
    }
    return head;
}
LNode *polyAdd(LNode* L1, LNode* L2){
    L1 = L1->next;
    L2 = L2->next;

    //創建 和鏈表
    LNode* head = new LNode;
    head->next = NULL;

    //尾插法
    LNode* p = head;
    while(L1 && L2){
        LNode *q = new LNode;
        q -> next = NULL;

        if(L1->exp > L2->exp){
            q->exp = L1->exp;
            q->coef = L1->coef;
            p = p->next = q;
            L1 = L1->next;
        }
        else if(L1->exp < L2->exp){
            q->exp = L2->exp;
            q->coef = L2->coef;
            p= p->next = q;
            L2 = L2->next;
        }
        else{
            q->exp = L1->exp;
            q->coef = L1->coef+L2->coef;
            //到這里很特別，因為等零我們是不能放進求和鏈表的，所以判斷后刪去節點q
            if(q->coef == 0){
                delete q;
            }
            else{
                p= p ->next = q;
            }
            L1 = L1->next;
            L2 = L2 ->next;
        }
    }
    LNode* L = L1?L1:L2;
    while(L){
        p = p->next = L;
        L = L -> next;
    }
    return head;//別忘了回傳
}
LNode *polyMult(LNode* L1,LNode* L2){
    L1 = L1->next;
    L2 = L2->next;

    LNode *head = new LNode;
    head->next = NULL;
    //說是求積，其實也不復雜，定住一條鏈，遍歷另一條
    while(L1){
        LNode* headofL2 = L2;
        //先保存一下L2頭結點
        while(L2){
            LNode* p = new LNode;
            p->next = NULL;
            p->coef = L1->coef*L2->coef;
            p->exp = L1->exp+L2->exp;
            //放入求積鏈表需要一個操作，即找到這個結點該放入的位置
            LNode* pr = head;
            //移動pr,當pr的下一節點次數比當前結果小，那就把當前節點插入pr之后
            while(pr->next && pr->next->exp > p->exp){
                pr = pr->next;
            }
            //回圈結束有幾種情況，一種pr->next = NULL或者滿足比當前結果小，就插入
            //另一種相等，則相加
            if(pr->next == NULL || pr ->next ->exp < p->exp){
                p -> next = pr->next;
                pr ->next = p;
            }//插入
            else{
                pr->next->coef += p->coef;
                //只要兩結點相加，就要考慮為零的情況
                if(pr->next->coef==0){
                    LNode* tmp = pr->next;
                    pr->next = tmp->next;
                    delete(tmp);
                }
                delete p;
            }
            L2 = L2->next;
        } 
        //一次內回圈后把L2歸位
        L2 = headofL2;
        L1 = L1->next;   
    }
    return head;
    
}
//下面需要輸出函式
void printList(LNode* L){
    //由于空鏈表需要輸出 0 0，所以空時需要特別處理一下
    if(L->next == NULL){//剛手敲掉了一個=
        LNode *p = new LNode;
        p->next = NULL;
        p->coef = 0;
        p->exp = 0;
    }
    L = L->next;
    // while(L){
    //     //這里面還需要注意，需要呼叫兩次這個，所以記得最后輸出換行
    //     //cout << L->coef << " " << L-> exp<<" ";
    //     //L = L->next;
    //     //
    // }
    // cout<<endl;
    //按照上面的寫法跟題目輸出的格式并不同
    while(L){
        cout << L->coef <<" "<< L->exp;
        if(L->next)putchar(' ');
        else putchar('\n');
        L= L ->next;
    }
}

int main(){
    LNode *L1 = creatList();
    LNode *L2 = creatList();
    //初始化兩個鏈表，包括輸入
    printList(polyMult(L1,L2));
    printList(polyAdd(L1,L2));
    //可以直接輸出兩個運算的結果
    return 0;
}

但是，這一版代碼提交還是有問題的，截圖如下：

hjklh

出錯原因也很簡單：在進行例外處理即輸出0 0 的時候，自己準備用來輸出0 0 的結點沒有掛上去，來看看輸出函式printlist是怎么漏掉的

void printList(LNode* L){
    //由于空鏈表需要輸出 0 0，所以空時需要特別處理一下
    if(L->next == NULL){//剛手敲掉了一個=
        LNode *p = new LNode;
        p->next = NULL;
        p->coef = 0;
        p->exp = 0;
    }
    ...
}

可以看到我的想法很好，如果是空鏈表，我新建一個結點，里面放兩個0，然后把這個結點掛上去，再進行下面輸出操作，就執行了，但是問題在于，if陳述句的最后我沒有把L->nex = p;，所以產生了上面的錯誤，

void printList(LNode* L){
    //由于空鏈表需要輸出 0 0，所以空時需要特別處理一下
    if(L->next == NULL){//剛手敲掉了一個=
        LNode *p = new LNode;
        p->next = NULL;
        p->coef = 0;
        p->exp = 0;
        L->next = p;
    }
    ...
}

03-1-4 最終代碼

所以完整代碼是：

//0319兩個一元多次多項式的相加
//感覺有陣列可以硬做，但是用鏈表其實更好
#include<iostream>
using namespace std;

typedef struct LNode{
    int coef,exp;
    LNode *next;
}LNode;
LNode *creatList(){//創建鏈表
    int n ;
    cin >> n;
    LNode *head = new LNode;
    head->next = NULL;
    LNode *p = head;

    while(n--){
        LNode *q = new LNode;
        q->next = NULL;
        cin >> q->coef >> q->exp;
        p = p->next = q;
        //相當于p->next = q; p = p->next;
    }
    return head;
}
LNode *polyAdd(LNode* L1, LNode* L2){
    L1 = L1->next;
    L2 = L2->next;

    //創建 和鏈表
    LNode* head = new LNode;
    head->next = NULL;

    //尾插法
    LNode* p = head;
    while(L1 && L2){
        LNode *q = new LNode;
        q -> next = NULL;

        if(L1->exp > L2->exp){
            q->exp = L1->exp;
            q->coef = L1->coef;
            p = p->next = q;
            L1 = L1->next;
        }
        else if(L1->exp < L2->exp){
            q->exp = L2->exp;
            q->coef = L2->coef;
            p= p->next = q;
            L2 = L2->next;
        }
        else{
            q->exp = L1->exp;
            q->coef = L1->coef+L2->coef;
            //到這里很特別，因為等零我們是不能放進求和鏈表的，所以判斷后刪去節點q
            if(q->coef == 0){
                delete q;
            }
            else{
                p= p ->next = q;
            }
            L1 = L1->next;
            L2 = L2 ->next;
        }
    }
    LNode* L = L1?L1:L2;
    while(L){
        p = p->next = L;
        L = L -> next;
    }
    return head;//別忘了回傳
}
LNode *polyMult(LNode* L1,LNode* L2){
    L1 = L1->next;
    L2 = L2->next;

    LNode *head = new LNode;
    head->next = NULL;
    //說是求積，其實也不復雜，定住一條鏈，遍歷另一條
    while(L1){
        LNode* headofL2 = L2;
        //先保存一下L2頭結點
        while(L2){
            LNode* p = new LNode;
            p->next = NULL;
            p->coef = L1->coef*L2->coef;
            p->exp = L1->exp+L2->exp;
            //放入求積鏈表需要一個操作，即找到這個結點該放入的位置
            LNode* pr = head;
            //移動pr,當pr的下一節點次數比當前結果小，那就把當前節點插入pr之后
            while(pr->next && pr->next->exp > p->exp){
                pr = pr->next;
            }
            //回圈結束有幾種情況，一種pr->next = NULL或者滿足比當前結果小，就插入
            //另一種相等，則相加
            if(pr->next == NULL || pr ->next ->exp < p->exp){
                p -> next = pr->next;
                pr ->next = p;
            }//插入
            else{
                pr->next->coef += p->coef;
                //只要兩結點相加，就要考慮為零的情況
                if(pr->next->coef==0){
                    LNode* tmp = pr->next;
                    pr->next = tmp->next;
                    delete tmp;
                }
                delete p;
            }
            L2 = L2->next;
        } 
        //一次內回圈后把L2歸位
        L2 = headofL2;
        L1 = L1->next;   
    }
    return head;
    
}
//下面需要輸出函式
void printList(LNode* L){
    //由于空鏈表需要輸出 0 0，所以空時需要特別處理一下
    if(L->next == NULL){//剛手敲掉了一個=
        LNode *p = new LNode;
        p->next = NULL;
        p->coef = 0;
        p->exp = 0;
        L->next = p;
    }
    L = L->next;
    // while(L){
    //     //這里面還需要注意，需要呼叫兩次這個，所以記得最后輸出換行
    //     //cout << L->coef << " " << L-> exp<<" ";
    //     //L = L->next;
    //     //
    // }
    // cout<<endl;
    //按照上面的寫法跟題目輸出的格式并不同
    while(L){
        cout << L->coef <<" "<< L->exp;
        if(L->next)putchar(' ');
        else putchar('\n');
        L= L ->next;
    }
}

int main(){
    LNode *L1 = creatList();
    LNode *L2 = creatList();
    //初始化兩個鏈表，包括輸入
    printList(polyMult(L1,L2));
    printList(polyAdd(L1,L2));
    //可以直接輸出兩個運算的結果
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/448132.html

標籤：其他

上一篇：Java基礎——Calendar類

下一篇：Java基礎——例外

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂