1025 反轉連結清單 (25 分)+測試點6
題目
給定一個常數 K 以及一個單連結清單 L，請編寫程式将 L 中每 K 個結點反轉。例如：給定 L 為 1→2→3→4→5→6，K 為 3，則輸出應該為 3→2→1→6→5→4；如果 K 為 4，則輸出應該為 4→3→2→1→5→6，即最後不到 K 個元素不反轉。
輸入格式
每個輸入包含 1 個測試用例。每個測試用例第 1 行給出第 1 個結點的位址、結點總個數正整數 N (≤105)、以及正整數 K (≤N)，即要求反轉的子鍊結點的個數。結點的位址是 5 位非負整數，NULL 位址用 −1 表示。
接下來有 N 行，每行格式為：
Address Data Next
其中 Address 是結點位址，Data 是該結點儲存的整數資料，Next 是下一結點的位址。
輸出格式：
對每個測試用例，順序輸出反轉後的連結清單，其上每個結點占一行，格式與輸入相同。
輸入樣例：
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
題目連結
解題思路
- 一行資訊包含節點位址，資料以及下一結點位址，通過一個結構體才存放每一行資訊。
- 通過閱讀題目可以看出輸入的資訊是無序的，是以在進行反轉連結清單操作之前，就是将輸入的無序資訊轉化成有序資訊。
- 有了以上思路，我們開始讀資料，第一行通過三個變量擷取首位址，結點數和步長，對于結點資訊使用一個結構體數組進行讀取，已經得到節點個數是以通過一個for循環讀取每一行的資料，關于結點存儲的的問題，最簡單的是按順序将每行資訊存到數組中，但是帶來的問題是，在對結點進行排序時，每次尋找下一節點時都需要周遊整個數組，是以為了簡化工作量，我們開一個1w的數組，按照每一個結點的位址來決定存放在數組中的位置，這樣當我們尋找下一節點的時候可以直接通過索引。
for (int i = 0; i < num; i++) //讀資料
{
cin>>ID>>Date>>NEXT;
p[ID].date=Date;
p[ID].next=NEXT;
p[ID].id=ID;
}
-
讀完資料之後，我們開始對資料進行排序，定義一個成員指針的數組，用指針數組主要是考慮到空間的問題，我們可以對指針數組進行排序。這個比再賦一遍值要好得多。
這裡排序的過程中會涉及的測試點6過不了的問題，我們在後面單獨分析
int tk=0;
for(int i=first;i!=-1;i=p[i].next)//将資料按順序存放到指針數組q中
{
q[tk++]=&p[i];
}
-
最後我們對已經排好序的數組進行反轉操作
這裡使用了一個reverse（）的函數
逆序（反轉）無論是在C或是C++中用的都特别多，常用于數組，字元串，容器等，其本身的函數參數也不複雜。
标準C中是沒有recerse()函數的，這是C++的一個新增函數，使用需要包含頭檔案
#include < algorithm >
reverse函數用于反轉在[first,last)範圍内的順序（包括first指向的元素，不包括last指向的元素），reverse函數沒有傳回值。
例如，交換vector容器中元素的順序
vector v = {5,4,3,2,1};
reverse(v.begin(),v.end());//v的值為1,2,3,4,5
還有string類的字元串
string str=“www.mathor.top”;
reverse(str.begin(),str.end());//str結果為pot.rohtam.wwww
最後給出函數原型，該函數等價于通過調用iter_swap來交換元素位置
template < class BidirectionalIterator >
void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
while ((first!=last)&&(first!=–last))
{
std::iter_swap (first,last);
++first;
}
}
按照題意，我們通過取餘的方式劃分出每一塊需要反轉的結點，for循環結束的判定條件則是當剩餘結點不夠進行一次反轉：
for(int i=tk,j=0;i/ty!=0;i-=ty,j+=ty)
{
reverse(q+j,q+j+ty);//逆序指針數組 原來數組存放的連結清單位址進行逆序
}
- 最後一步将最終結果列印出來：
for( int i=0;i<tk-1;i++)
{
printf("%05d %d %05d\n",q[i]->id,q[i]->date,q[i+1]->id);
}
printf("%05d %d -1",q[tk-1]->id,q[tk-1]->date);
- 關于測試點6的問題，這題一直卡在測試點6過不去，參考了别人的代碼，一行一行的對比最後才找出問題，吐血~，這題在題目中挖了一個坑 “結點的位址是 5 位非負整數，NULL 位址用 −1 表示。”這句話其實暗示-1也可以作為位址，而我們可能會先入為主，把 -1當作最後一個空位址，然而在輸入的資訊中可能會存在這樣或這樣一行資訊
-1 1 -1
-1 3 12309
-
這就需要我們在對結點進行排序的時候，就需要将這些無效結點剔除出去，也就是判斷它的位址是不是 -1
這是我之前的代碼！！！！！(錯誤的）
for (int i = 0; i < num; i++) //讀資料
{
cin>>ID>>Date>>NEXT;
p[ID].date=Date;
p[ID].next=NEXT;
p[ID].id=ID;
}
- 哈哈腦補一個測試樣例：
00100 7 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
-1 7 -1
- 我之前的代碼運作結果是
1025 反轉連結清單 (25 分)+測試點61025 反轉連結清單 (25 分)+測試點6 - 正确結果是：
AC代碼：
#include<iostream>
#include<algorithm>
using namespace std;
struct List
{
int id;
int date;
int next;
};
int main()
{
struct List p[100000+10];//連結清單結構體
struct List *q[100000+10];//存放連結清單結構體位址的數組
int first,num,ty;
cin>>first>>num>>ty;
int ID,Date,NEXT;//暫時存放
for (int i = 0; i < num; i++) //讀資料
{
cin>>ID>>Date>>NEXT;
p[ID].date=Date;
p[ID].next=NEXT;
p[ID].id=ID;
}
int tk=0;
for(int i=first;i!=-1;i=p[i].next)//将資料按順序存放到指針數組q中
{
q[tk++]=&p[i];
}
for(int i=tk,j=0;i/ty!=0;i-=ty,j+=ty)
{
reverse(q+j,q+j+ty);//逆序指針數組 原來數組存放的連結清單位址進行逆序
}
for( int i=0;i<tk-1;i++)
{
printf("%05d %d %05d\n",q[i]->id,q[i]->date,q[i+1]->id);
}
printf("%05d %d -1",q[tk-1]->id,q[tk-1]->date);
return 0;
}
哈哈~這是自己第一次寫部落格，立個小小的flag，能堅持一個月發兩篇。