問題1.9順序配列の挿入
本題では、任意の所与の要素を大から小までの配列の中の適切な位置に挿入し、結果が依然として秩序化されていることを維持する必要があります.
関数インターフェースの定義:
審判試験手順の例:
関数インターフェースの定義:
bool Insert( List L, ElementType X );
List
の構造定義は以下の通りである.typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* */
};
L
は、ElementType
要素が、==、Insertを通してX
をData[]
に適切な位置に挿入し、結果が依然として規則化されていることを維持するための線形表である.X
がすでにData[]
にあるなら、挿入しないでください.失敗したタグfalse
を返します.挿入が成功するとtrue
に戻る.また、Data[]
には最大MAXSIZE
個の要素しか保存できないので、新しい要素を挿入する前にすでに満杯になっていたら、挿入するのではなく、失敗したタグfalse
を返します.審判試験手順の例:
#include
#include
#define MAXSIZE 10
typedef enum {false, true} bool;
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* */
};
List ReadInput(); /* , 。 0 */
void PrintList( List L ); /* , */
bool Insert( List L, ElementType X );
int main()
{
List L;
ElementType X;
L = ReadInput();
scanf("%d", &X);
if ( Insert( L, X ) == false )
printf("Insertion failed.
");
PrintList( L );
return 0;
}
/* */
入力例1:5
35 12 8 7 3
10
出力例1:35 12 10 8 7 3
Last = 5
入力例2:6
35 12 10 8 7 3
8
出力例2:Insertion failed.
35 12 10 8 7 3
Last = 5
/*c */
bool Insert( List L, ElementType X )
{
if(L->Last+1==MAXSIZE)
return false;
for(int i=0;i<=L->Last;i++)
{
if(L->Data[i]==X)
return false;
else if(L->Data[i]Last;j>=i;j--)
{
L->Data[j+1]=L->Data[j];
}
L->Data[i]=X;
L->Last=L->Last+1;
break;
}
else if(L->Data[i]>X&&i==L->Last)
{
L->Data[L->Last+1]=X;
L->Last=L->Last+1;
break;
}
}
return true;
}