データ構造——手順表の基本操作

まず問題を見に来ます.
この問題は、順序表要素の増加、削除、検索、および順序表出力の4つの基本的な操作関数を実現することを要求します.Lは順序表で、関数Sttus ListInsert_です.Sq(SqList&L,int pos,ElemType)は、シーケンステーブルのpos位置に要素e(posは1から始まるべき)を挿入し、関数Stuts ListDelete_Sq(SqList&L,int pos,ElemType&e)は、シーケンステーブルのpos位置を削除し、参照型パラメータeで持ち帰って(posは1から)関数int ListLocate_Sq(SqList L,ElemType)は、クエリ要素eがシーケンステーブルの順位で戻ります(複数の最初の位置を取ると、戻りはビットで、1から存在しない場合は0に戻ります)、関数void ListPrint_Sq(SqList L)は、出力順序表要素である.実現にあたっては、表の拡大を考慮する必要がある.
関数インターフェースの定義:

Status ListInsert_Sq(SqList &L, int pos, ElemType e);
Status ListDelete_Sq(SqList &L, int pos, ElemType &e);
int ListLocate_Sq(SqList L, ElemType e);
void ListPrint_Sq(SqList L);

ここでLは順番表です.posは位置ですe元素を表します.挿入と削除操作中のposパラメータが不正な場合、関数はERRORに戻ります.そうでなければOKに戻ります.
審判試験手順の例:

//        
#include
#include
#include


//       
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;

//          
#define LIST_INIT_SIZE  100
#define LISTINCREMENT   10
typedef int ElemType;  //             
typedef struct{
    ElemType* elem;   //       
    int length;       //       
    int listsize;     //     
}SqList;    //       
Status ListInsert_Sq(SqList &L, int pos, ElemType e);
Status ListDelete_Sq(SqList &L, int pos, ElemType &e);
int ListLocate_Sq(SqList L, ElemType e);
void ListPrint_Sq(SqList L);

//          
Status InitList_Sq(SqList &L){
  //   L          
    L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem)exit(OVERFLOW);
    L.listsize=LIST_INIT_SIZE;
    L.length=0;
    return OK;
}


int main() {
    SqList L;

    if(InitList_Sq(L)!= OK) {
        printf("InitList_Sq:      ！！！
");
        return -1;
    }

    for(int i = 1; i <= 10; ++ i)
        ListInsert_Sq(L, i, i);

    int operationNumber;  //    
    scanf("%d", &operationNumber);

    while(operationNumber != 0) {
        int operationType;  //    
        scanf("%d", & operationType);

        if(operationType == 1) {  //    
            int pos, elem;
            scanf("%d%d", &pos, &elem);
            ListInsert_Sq(L, pos, elem);
        } else if(operationType == 2) {  //    
             int pos; ElemType elem;
             scanf("%d", &pos);
             ListDelete_Sq(L, pos, elem);
             printf("%d
", elem);
        } else if(operationType == 3) {  //      
            ElemType elem;
            scanf("%d", &elem);
            int pos = ListLocate_Sq(L, elem);
            if(pos >= 1 && pos <= L.length)
                printf("%d
", pos);
            else
                printf("NOT FIND!
");
        } else if(operationType == 4) {  //    
            ListPrint_Sq(L);
        }
       operationNumber--;
    }
    return 0;
}

/*          */

入力フォーマット:1行目は整数のoperationNumberを入力して、操作数を表します.次にoperation Number行で、1行に1つの操作情報(「操作種類番号操作内容」を含みます.)を表します.番号は1で挿入操作を示し、後の2つのパラメータは挿入の位置と挿入の要素値番号は2で削除操作を示し、後の一つのパラメータは削除の位置番号は3で検索動作を表し、後の一つのパラメータは検索の値番号は4で順序表出力操作を表します. 出力フォーマット:操作2に対して、削除された要素の値を出力します.操作3に対して、その要素の位置を出力します.この要素が存在しない場合は、「NOT FOUND」を出力します.4を操作する場合、順序表全体の要素を順次出力します.二つの要素の間はスペースで区切られています.最後の要素の後ろにはスペースがありません.
入力サンプル:

4
1 1 11
2 2
3 3
4

出力例:

1
3
11 2 3 4 5 6 7 8 9 10

テーマの内容によって、このプログラムの主関数と必要な声明が出されました.私達が自分で充填するのがSttus ListInsert_です.Sq(SqList&L,int pos,ElemType)、Sttus ListDelete_Sq(SqList&L,int pos,ElemType&e)、int ListLocate_Sq(SqList L,ElemType)とvoid ListPrint_Sq(SqList L)の4つの関数の具体的な内容.私たちは一人ずつ見に来ます.
一.Sttus List Insert_Sq(SqList&L,int pos,ElemType)
この関数は、Lのシーケンステーブルのpos位置にデータeを挿入することで実現される.pos位置にデータeを挿入すると、pos位置の後のすべての要素が後ろに移動します.幸い、posというところが空いているので、データeを入れます.そこで私達はまず一つのfor循環を使って、もとのpos位置とその後の元素を後ろに1つ移動させて、その後pos位置にデータeを挿入すればいいという考えを持ち始めました.しかし、私たちも考えたいのですが、シーケンステーブルの要素の個数、つまりL.lengthの数値は最初に設定された上限に達しています.

#define LIST_INIT_SIZE  100

この行で定義されているLIST_INIT_SIZEの個数については、まず拡大してから各データを後ろに移動させる作業が必要です.さもないと境界を超えます.ですから、拡大が必要かどうかを判断します.また、与えられたposが本来L.engthの制限を超えていたら、エラーに戻ります.第pos位がないからです.また、注意しなければならない点は、posは>=1であり、配列は0から始まるので、pos番目の数は配列中の下に「pos-1」と表示されます.
コード実現とは:

Status ListInsert_Sq(SqList &L, int pos, ElemType e) { ElemType *newbase;//          if(pos >= 1&&pos <= L.length + 1)//    pos   L.length      { if(L.length >= L.listsize)//  L.length          ，     { newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT) * sizeof(ElemType));// newbase         LISTINCREMENT     if(!newbase)//            return ERROR; L.elem = newbase;//          L.listsize += LISTINCREMENT;//                          } ElemType *p,*q; p = &(L.elem[pos - 1]);//   pos            p for(q = &(L.elem[L.length - 1]);q >= p;--q) { *(q + 1) = *q; }//                    q，                  *p = e;//   e  pos   ++L.length;//          return OK; } else return OVERFLOW; }

二.Sttus ListDelete_Sq(SqList&L,int pos,ElemType&e)
はい、一番難しい関数はもう解決しました.残りは全部簡単です.
この関数が実現したのは、シーケンステーブルの第posビットの要素を削除します.これは私達に思わず第一の増加の効果を思い付かせて、しかし削除するのは増加するよりずっと簡単で、拡張の問題を考慮する必要はありません.だから、pos位置以降の要素を一つずつ前に移動させるだけでいいです.ただし、参照の形でデータeに戻りますので、eに値を付けてから削除操作を行います.同様に、posは>=1であり、配列は0から始まるので、配列中のpos番目の数は【pos-1】としてマークされます.
コードの実装は以下の通りです.

Status ListDelete_Sq(SqList &L, int pos, ElemType &e) { if(pos >= 1&&pos <= L.length)//  pos            { ElemType *q; e = L.elem[pos - 1];//  e  ，            for(q = &(L.elem[pos - 1]);q <=&(L.elem[L.length - 1]);++q) { *q = *(q + 1); }// pos                L.length = L.length - 1;//L       } else return OVERFLOW; }

三.int ListLocate_Sq(SqList L,ElemType)
この関数は検索機能であり、このデータがあると戻りがいくつか目になり、複数があると最初のこの数の位置数に戻ります.存在しないなら、NOT FOUNDに戻ります.まず数aを定義して、位置の数を表します.なお、位置数は1から始まり、順序表は0から始まります.2番目の数は、順序表の下に1として表示されます.したがって、戻る時はaを＋1操作します.また、見つけられない場合がありますので、先にaを初値にしてもいいです.aの値が初値でない場合、存在を説明します.aがまだ初値であるなら、この数が存在すると説明します.
コードの実装は以下の通りです.

int ListLocate_Sq(SqList L, ElemType e) { int a = -1;// a   ，           ，      -1 ，    -1 for(int i = 0;i <= L.length -1;i++) { if(L.elem[i] == e) { a = i; break; } }//for       if(a >= 0&&a <= L.length -1) return a + 1;//  a      ，   a else return ERROR;//  a   ，     。 }

四.void ListPrint_Sq(SqList L)
この関数が実装されるのはシーケンステーブルの出力です.最後の数だけ注意してください.後ろにスペースがないだけでいいです.
コードの実装:

void ListPrint_Sq(SqList L) { for(int i = 0;i <= L.length - 2;i++) { printf("%d ",L.elem[i]); } printf("%d",L.elem[L.length -1]); }