您的位置: 首页  >  IT文章  >  【PTA】6-2 顺序表操作集 (20分)

【PTA】6-2 顺序表操作集 (20分)

分类: IT文章 • 2022-05-07 11:19:09

【PTA】6-2 顺序表操作集 (20分)

函数接口定义：

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

其中  List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

各个操作函数的定义为：

List MakeEmpty()：创建并返回一个空的线性表；

Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；

bool Insert( List L, ElementType X, Position P )：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；

bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。

裁判测试程序样例：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define MAXSIZE 5
 5 #define ERROR -1
 6 typedef enum {false, true} bool;
 7 typedef int ElementType;
 8 typedef int Position;
 9 typedef struct LNode *List;
10 struct LNode {
11     ElementType Data[MAXSIZE];
12     Position Last; /* 保存线性表中最后一个元素的位置 */
13 };
14 
15 List MakeEmpty(); 
16 Position Find( List L, ElementType X );
17 bool Insert( List L, ElementType X, Position P );
18 bool Delete( List L, Position P );
19 
20 int main()
21 {
22     List L;
23     ElementType X;
24     Position P;
25     int N;
26 
27     L = MakeEmpty();
28     scanf("%d", &N);
29     while ( N-- ) {
30         scanf("%d", &X);
31         if ( Insert(L, X, 0)==false )
32             printf(" Insertion Error: %d is not in.
", X);
33     }
34     scanf("%d", &N);
35     while ( N-- ) {
36         scanf("%d", &X);
37         P = Find(L, X);
38         if ( P == ERROR )
39             printf("Finding Error: %d is not in.
", X);
40         else
41             printf("%d is at position %d.
", X, P);
42     }
43     scanf("%d", &N);
44     while ( N-- ) {
45         scanf("%d", &P);
46         if ( Delete(L, P)==false )
47             printf(" Deletion Error.
");
48         if ( Insert(L, 0, P)==false )
49             printf(" Insertion Error: 0 is not in.
");
50     }
51     return 0;
52 }
53 
54 /* 你的代码将被嵌在这里 */

输入样例：

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

输出样例：

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.

函数实现细节：

 1 List MakeEmpty(){
 2     List L=(List)malloc(sizeof(struct LNode));
 3     int n=MAXSIZE-1;
 4     while(n>=0) L->Data[n--]=0;
 5     L->Last=-1;
 6     return L; 
 7 }
 8 Position Find(List L,ElementType X){
 9     if(L==NULL)return ERROR;
10     int i=0;
11     for(;i<=L->Last;i++){
12         if(L->Data[i]==X)return i;
13     }
14     return ERROR;
15 }
16 bool Insert(List L,ElementType X,Position P){
17     if(L==NULL)return false;
18     if(L->Last==MAXSIZE-1){
19         printf("FULL");
20         return false;
21     }
22     if(P>L->Last+1||P<0){
23         printf("ILLEGAL POSITION");
24         return false;
25     }
26     for(int i=L->Last;i>=P;i--){
27         L->Data[i+1]=L->Data[i];
28     }
29     L->Last++;
30     L->Data[P]=X;
31     return true;
32 }
33 bool Delete( List L, Position P ){
34     if(L==NULL)return false;
35     if(P>L->Last||P<0){
36         printf("POSITION %d EMPTY",P);
37         return false;
38     }
39     int i;
40     for(i=P;i<=MAXSIZE-1;i++){
41         if(i==L->Last){
42             L->Data[i]=0;
43         }else{
44             L->Data[i]=L->Data[i+1];
45         }
46     }
47     L->Last--;
48     return true;
49 }

相关推荐