6-5チェーンシート操作集(20分)本題はチェーンテーブルの操作集を実現することを要求します.

＊＊
6-5チェーンシート操作集(20分)
＊＊本題はチェーンシートの操作集を実現することを要求します.関数インターフェースの定義:

Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );

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

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

各操作関数の定義は以下の通りです.
Position Find(List L,ElemenntType X):線形表で初めてXが発生する位置を返します.見つけられないならERRORに戻ります.
List Insert(List L,ElementType X,Position P):位置Pが指す結点にXを挿入する前に、チェーンの表の先頭に戻ります.パラメータPが不正な位置を指すと、「Wrong Position for Insertion」を印刷し、ERRORに戻ります.
List Delete(List L,Position P):位置Pの要素を削除し、チェーンテーブルのヘッダに戻ります.パラメータPが不正な位置を指すと、「Wrong Position for Deletion」を印刷してERRORに戻ります.
審判試験手順の例:

#include 
#include 

#define ERROR NULL
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P, tmp;
    int N;

    L = NULL;
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        L = Insert(L, X, L);
        if ( L==ERROR ) printf("Wrong Answer
");
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.
", X);
        else {
            L = Delete(L, P);
            printf("%d is found and deleted.
", X);
            if ( L==ERROR )
                printf("Wrong Answer or Empty List.
");
        }
    }
    L = Insert(L, X, NULL);
    if ( L==ERROR ) printf("Wrong Answer
");
    else
        printf("%d is inserted as the last element.
", X);
    P = (Position)malloc(sizeof(struct LNode));
    tmp = Insert(L, X, P);
    if ( tmp!=ERROR ) printf("Wrong Answer
");
    tmp = Delete(L, P);
    if ( tmp!=ERROR ) printf("Wrong Answer
");
    for ( P=L; P; P = P->Next ) printf("%d ", P->Data);
    return 0;
}

/*            */

入力例:6 12 2 4 7 10 2 12 12 12 12 2 2 12 87出力例:

2 is found and deleted.
12 is found and deleted.
87 is found and deleted.
Finding Error: 5 is not in.
5 is inserted as the last element.
Wrong Position for Insertion
Wrong Position for Deletion
10 4 2 5 

まず、本題には順序表との違いがあります.順序表はすでに申請済みで十分な空間があります.挿入する時は空間が十分であれば直接に挿入できます.チェーンテーブルは単独で一つの結点を申請して値を入れて挿入します.
＊＊
本題の答え
＊＊

Position Find(List L, ElementType X)//                 
{
    while(L)
    {
        if (L->Data == X)
            return L;
        L = L->Next;
    }
    return ERROR;
}

List Insert(List L, ElementType X, Position P)//       ，                     
{   
    List m = (List)malloc(sizeof(List));//          ，         
    m->Next = NULL;//         “   ”，         ，   
    m->Data = X;
    List head = L;//           
   
    if (P == L) //                 
    {
        m->Next = L;
        return m;
    }
    while (L)//    
    {
		if (L->Next == P)//           
		{
			m->Next = L->Next;
			L->Next = m;
			return head;
		}
		L = L->Next;//     ，    
    }
   
        printf("Wrong Position for Insertion
");//            
        return ERROR;

}

List Delete(List L, Position P)//         
{
    List m, head;

    //           
    if (P == L)
    {
        L = L->Next;
        return L;
    }
    head = L;
  
    while (L)
    {
        if (L->Next == P )//       
        {
           
            L->Next = P->Next;
            return head;
        }

        L = L->Next;
    }
  printf("Wrong Position for Deletion
");

    return ERROR;
 
}

以上のように、***のチェーンブロックの削除と挿入は二つの状況に分けられます.1:要求位置はヘッドノード2:中間結点はヘッドノード付きのシングルチェーン表であれば、一つの状況しかありません.例えば、先頭ノードのシングルチェーン表の挿入などです.

        bool Insert(List L, ElementType X, Position P)
{
    List m = (List)malloc(sizeof(struct LNode));
    m->Next = NULL;
    m->Data = X;
    while (L)
    {
        if (P == L->Next)
        {
            m->Next = L->Next;
            L->Next = m;
            return true;
        }
        L = L->Next;
    }
    printf("Wrong Position for Insertion");
    return false;
}

ヘッドノードがあるので、直接挿入できます.各位置は同じです.