どっかの過去問2

typedef struct node{
int value;
struct node *next;
} node, *list;

こういう構造体があって

kako2_1.jpg

図のように循環リストで数列を表現して、リストの末尾へのポインタでリストにアクセスするみたい。

問1、数列p1,p2を順番に連結したものを返す関数を作れ、ということで図で表すとこんな感じですか。

kako2_2.jpg

コードだとこんなかんじ。

list catenate(list p1, list p2){
if(p1==0){
return p2;
}
else if(p2==0){
return p1;
}

node *tmp;

tmp = p2->next;
p2->next = p1->next;
p1->next = tmp;

return p2;
}

問2、非負整数列pと位を表す数d(1の位、10の位とか)を与えて、dの位だけで小さい順に並べた整数列を返す関数を定義するそうで(番号のところを穴埋め)。

list sort1(list p,int d){
list pp[10], q; int i, k;
for(i=0;i<10;i++) pp[i] = 0;
while(p!=0){
q = p->next;//(1)
k = q->value/d%10;
if(p == p->next) p = 0;//(2)ここから4行
else p->next = p->next->next;
q->next = q;
pp[k] = catenate(q,pp[k]);
}
for(i=0;i<10;i++) p = catenate(p,pp[i]);//(3)
return p;
}

こんな感じかな。

問3、いま作った関数を使って小さい順にソートする関数を作るそうで。ちなみに、こういう方法でソートする方法を基数整列法という。

手順的には最大値の桁を求めて、その桁まで上のsort1を回せばよさそう。

list sort(list p){
list q; int max, d;
max = p->value;
q = p->next;
while(q!=p){
if(max<q->value) max = q->value;
q = q->next;
}
for(d=1;max;d*=10,max/=10) p = sort1(p,d);
return p;
}

こうかな?確認してないからよくわからん。


posted by 右京 | c言語
blog comments powered by Disqus
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。