6-2 sequence table operation set

6-2 Sequence table operation set

This problem requires the implementation of the operation set of the sequence table .

Function interface definition ：

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

among List The structure is defined as follows ：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    
    ElementType Data[MAXSIZE];
    Position Last; /*  Save the position of the last element in the linear table  */
};

Each operation function is defined as ：

List MakeEmpty()： Create and return an empty linear table ;

Position Find( List L, ElementType X )： Return to the linear table X The location of . If not, return ERROR;

bool Insert( List L, ElementType X, Position P )： take X Insert in position P And back to true. If the space is full , Then print “FULL” And back to false; If parameters P Point to an illegal location , Then print “ILLEGAL POSITION” And back to false;

bool Delete( List L, Position P )： Place P Delete the element and return true. If parameter P Point to an illegal location , Then print “POSITION P EMPTY”（ among P Is the parameter value ） And back to false.

Sample referee test procedure ：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5
#define ERROR -1
typedef enum {
    false, true} bool;
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
    
    ElementType Data[MAXSIZE];
    Position Last; /*  Save the position of the last element in the linear table  */
};

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

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

    L = MakeEmpty();
    scanf("%d", &N);
    while ( N-- ) {
    
        scanf("%d", &X);
        if ( Insert(L, X, 0)==false )
            printf(" Insertion Error: %d is not in.\n", X);
    }
    scanf("%d", &N);
    while ( N-- ) {
    
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.\n", X);
        else
            printf("%d is at position %d.\n", X, P);
    }
    scanf("%d", &N);
    while ( N-- ) {
    
        scanf("%d", &P);
        if ( Delete(L, P)==false )
            printf(" Deletion Error.\n");
        if ( Insert(L, 0, P)==false )
            printf(" Insertion Error: 0 is not in.\n");
    }
    return 0;
}

/*  Your code will be embedded here  */

sample input ：

6
1 2 3 4 5 6
3
6 5 1
2
-1 6

sample output ：

FULL Insertion Error: 6 is not in.
Finding Error: 6 is not in.
5 is at position 0.
1 is at position 4.
POSITION -1 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
POSITION 6 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.

Code ：

//List MakeEmpty()： Create and return an empty linear table ;
List MakeEmpty()
{
    
    List L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
    return L;
}


//Position Find( List L, ElementType X )： Return to the linear table X The location of .
// If not, return ERROR;
Position Find( List L, ElementType X )
{
    
    int i = 0;
    for(i = 0; i <= L->Last; i++)
    {
    
        if(L->Data[i] == X)
            return i;
    }
    return ERROR;
}

//bool Insert( List L, ElementType X, Position P )：
// take X Insert in position P And back to true.
// If the space is full , Then print “FULL” And back to false;
// If parameters P Point to an illegal location , Then print “ILLEGAL POSITION” And back to false;
bool Insert( List L, ElementType X, Position P )
{
    
    // Space full 
    if(L->Last == MAXSIZE-1)
    {
    
        printf("FULL");
        return false;
    }
    //P Point to an illegal location ,P The range pointed :[0, L->Last],P Insert range of ：[0, L->Last+1]
    if(P < 0 || P > (L->Last+1))
    {
    
        printf("ILLEGAL POSITION");
        return false;
    }
    // Insert ,P The following elements are collectively shifted to the right 
    int end = L->Last;
    while(end >= P)
    {
    
        L->Data[end+1] = L->Data[end];
        end--;
    }
    L->Data[P] = X;
    L->Last++;
    return true;
}

//bool Delete( List L, Position P )：
// Place P Delete the element and return true.
// If parameter P Point to an illegal location , Then print “POSITION P EMPTY”（ among P Is the parameter value ）
// And back to false.
bool Delete( List L, Position P )
{
    
	//P Scope of deletion ：[0, L->Last]
    if(P < 0 || P > L->Last)
    {
    
        printf("POSITION %d EMPTY", P);
        return false;
    }
    // Delete 
    int start = P;
    while(P < L->Last)
    {
    
        L->Data[start] = L->Data[start+1];
        start++;
    }
    L->Last--;
    return true;
}