浙大版「データ構造(第2版)」テーマ集-練習問題1.9順序配列の挿入(20点)

本題では、任意の所与の要素を大から小までの配列の中の適切な位置に挿入し、結果が依然として秩序化されていることを維持する必要があります.
関数インターフェースの定義:

bool Insert( List L, ElementType X );

List構造の定義は以下の通りである.

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /*                 */
};

Lは、ElementType要素が、==、
審判試験手順の例:

#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 8 3 10
出力例1:
35 12 10 8 8 Last=5
入力例2:
6 35 12 10 8 8 3 8
出力例2:
Insertion failed.35 10 8 7 Last=5
参照コード

bool Insert( List L, ElementType X )
{
    if(L->Last==MAXSIZE-1)
    {
        return false;
    }
    int i;
    for(i=0;i<=L->Last;i++)
    {
        if(X==L->Data[i])
        {
            return false;
        }
        else if(X>L->Data[i])
        {
            int j;
            for(j=L->Last;j>=i;j--)
            {
                L->Data[j+1]=L->Data[j];
            }
            L->Data[i]=X;
            L->Last++;
            break;
        }
        else if(i==L->Last)
        {
            L->Data[L->Last+1]=X;
            L->Last++;
            break;
        }
    }
    return true;
}

他の2つの関数参照コード

List ReadInput()
{
    List L;
    L=(List)malloc(sizeof(struct LNode));
    int x;
    scanf("%d",&x);
    L->Last=x-1;
    int i;
    for(i=0;i<=L->Last;i++)
    {
        scanf("%d",&L->Data[i]);
    }
    return L;
}

void PrintList( List L )
{
    int i;
    for(i=0;i<=L->Last;i++)
    {
        printf("%d",L->Data[i]);
        if(i==L->Last)
        {
            printf("
");
        }
        else
        {
            printf(" ");
        }
    }
    printf("Last = %d",L->Last);
}

考え方:
まず、線形表配列の要素がいっぱいかどうかを判断します.次に、線形表配列の各要素を巡回し、挿入する要素が既に存在する場合は、falseを返します.そうでなければ、挿入する要素は配列の要素と比較されます.配列の要素は減少しています.配列の中の要素は挿入する要素より小さい値だけを見つける必要があります.挿入要素はこの位置に入れます.位置の後の要素は統一された後に1桁移動します.最後の要素を巡回した場合、挿入する要素よりも小さい値がまだ見つからない場合、挿入する要素は最小要素です.配列の最後の要素に挿入します.