[SCU 2016年問題]並べ替えられた2つの単一チェーンテーブルがあり、問題を統合
2056 ワード
2016年の試験問題を思い出した.
2つの単一チェーンテーブルがあり、すでに非減算でソートされており、2つのチェーンテーブルのマージを完了する必要があり、非減算でソートされ、現在の2つのチェーンテーブル以外のストレージスペースは使用できません.
ここでは、重複する要素の存在を許可します.
たとえば、ha->(1)->(3)->(8);hb->(1) -> (7) -> (9) .
マージ後、ha->(1)->(1)->(3)->(7)->(8)->(9)を得るべきです.
タイトルには余分なストレージスペースの使用が許されないことが要求されているため、2つのチェーンテーブルの要素を3番目のチェーンテーブルに直接書き込むサボりは通用しません.
解決策:2番目のチェーンテーブルの要素を順番に1番目のチェーンテーブルの現在位置に挿入するかどうかを判断する.s 1,s 2はそれぞれ第1のチェーンテーブルを指し、t 1,t 2はそれぞれ第2のチェーンテーブルを指す.
t 1の値がs 2の値より大きい場合、s 1とs 2は順次後方に移動し、サイクル後に判断する.
t 1の値がs 2より小さい場合、t 1がs 1とs 2の間に挿入されることを示す.t 1はt 2となり、t 2はt 1の後続をプログラミングする.
ループの終了条件は、s 2またはt 2のいずれかがNULLになることであり、チェーンテーブルの1つが終了したことを示す.
コードは次のとおりです.テストに合格しました.
帰ってきてまたこの問題を考えて、もう一つの良い方法があることを発見して、直接2つのチェーンテーブルを合併して、それから全体の大きいチェーンテーブルに対して並べ替えて、泡が出ても、急速に並べ替えてもいいです.
これにより、問題の要件にも合致し、他の追加のストレージスペースは使用されません.
汗ですね~その時は緊張しすぎて反応しませんでした...
2つの単一チェーンテーブルがあり、すでに非減算でソートされており、2つのチェーンテーブルのマージを完了する必要があり、非減算でソートされ、現在の2つのチェーンテーブル以外のストレージスペースは使用できません.
ここでは、重複する要素の存在を許可します.
たとえば、ha->(1)->(3)->(8);hb->(1) -> (7) -> (9) .
マージ後、ha->(1)->(1)->(3)->(7)->(8)->(9)を得るべきです.
タイトルには余分なストレージスペースの使用が許されないことが要求されているため、2つのチェーンテーブルの要素を3番目のチェーンテーブルに直接書き込むサボりは通用しません.
解決策:2番目のチェーンテーブルの要素を順番に1番目のチェーンテーブルの現在位置に挿入するかどうかを判断する.s 1,s 2はそれぞれ第1のチェーンテーブルを指し、t 1,t 2はそれぞれ第2のチェーンテーブルを指す.
t 1の値がs 2の値より大きい場合、s 1とs 2は順次後方に移動し、サイクル後に判断する.
t 1の値がs 2より小さい場合、t 1がs 1とs 2の間に挿入されることを示す.t 1はt 2となり、t 2はt 1の後続をプログラミングする.
ループの終了条件は、s 2またはt 2のいずれかがNULLになることであり、チェーンテーブルの1つが終了したことを示す.
コードは次のとおりです.テストに合格しました.
typedef struct header
{
int V;
struct header * pnext;
} Node;
Node * link_merg(Node * p1, Node *p2)
{
Node *s1=p1, *s2, *t1=p2, *t2;
if(s1->V > t1->V)
{
Node * tmp = t1;
t1 = s1;
s1 = tmp;
}
s2 = s1->pnext;
t2 = t1->pnext;
while((s2!=NULL)&&(t2!=NULL))
{
if(s2->V > t1->V)
{
s1->pnext = t1;
t1->pnext = s2; // t1
s1= t1;
s2 = s1->pnext;
t1 = t2;
t2 = t1->pnext;
}
else
{
s1 = s2;
s2 = s1->pnext;
}
}
if(s2==NULL)
{ s1->pnext = t1;}
else
{s2->pnext = t1;}
return(s1);
}
帰ってきてまたこの問題を考えて、もう一つの良い方法があることを発見して、直接2つのチェーンテーブルを合併して、それから全体の大きいチェーンテーブルに対して並べ替えて、泡が出ても、急速に並べ替えてもいいです.
これにより、問題の要件にも合致し、他の追加のストレージスペースは使用されません.
汗ですね~その時は緊張しすぎて反応しませんでした...