#11930: 想法


nkavengertree (LaG)

School : No School
ID : 62501
IP address : [49.216.191.28]
Last Login :
2021-11-21 03:06:49
d166. 反轉表 -- w11123 | From: [163.30.20.150] | Post Date : 2017-04-20 12:48

這題主要是在計算  某個數字的前方有幾個數字是比他大的

藉此來排出數列的順序。

 

分析字串的方式建議使用:  string  與  stringstream  來做分割,

比較不會有問題!

 

我是以最大的數字為中心點(因為最大的數字必定為0)

使用linked list的方式,可以很方便的隨時插入,

最後只要判斷插入的點是哪一個地方,

結果就會直接出來!

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

const int MSIZE=55;
unsigned int m[MSIZE],mindex;
struct Node{
    unsigned int number;
    Node* next;
};
Node* head;

//利用stringstream來切割字串
void readin_m(string str1){
string tmp1;//拿來當作暫時存檔的字串
stringstream ss1;
ss1.str("");
ss1.clear();
ss1 << str1;//把字串放入
mindex = 0;//紀錄有幾個切割字串
while(getline(ss1,tmp1,' ')){//利用' '來分割字串
stringstream ss2;
ss2.str("");
ss2.clear();
ss2 << tmp1;
ss2 >> m[++mindex];//string 轉 int
}
}
//尋找符合的位置,並利用linked list新增資料
void linkNode(int nb){
Node* newNode=new Node();//新增的資料點
newNode->number = nb;

Node* find = head;//尋找用的指標
while(m[nb]>0){
find = find->next;
if (find->number > nb)
m[nb]--;
}

newNode->next = find->next;//新增
find->next = newNode;

newNode=0;//釋放
delete newNode;
}
//輸出所有的資料
void show_node(){
Node* run;
run = head->next;
bool first=true;
while(run != 0){
if (!first)cout << " ";
cout << run->number;
run = run->next;
first=false;
}
delete run;
cout << endl;
}
int main()
{
string input1;
//直接讀取整行,當遇到"-1"的時候結束
while(getline(cin,input1) && input1 != "-1"){
readin_m(input1);//分析字串

head = new Node();
head->number = 0;
head->next = 0;

//倒著的順序方式來調整每一個的位置
for (mindex=mindex; mindex>0; mindex--){
linkNode(mindex);
}
//輸出結果
show_node();
}
return 0;
}



 
ZeroJudge Forum