网络软件公司,重庆seo技术博客,网片网格,建设学院网站的通知顺序表#xff1a; 线性表的顺序存储
线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素 在程序设计语言中#xff0c;一维数组在内存中占用的存储空间就是一组连续的存储区域#xff0c;因此#xff0c;用一维数组来表示顺序存储的数据区域是…顺序表 线性表的顺序存储
线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素 在程序设计语言中一维数组在内存中占用的存储空间就是一组连续的存储区域因此用一维数组来表示顺序存储的数据区域是再合适不过的 考虑到线性表的运算有插入和删除等即表的长度是动态可变的 所以数组的容量需设计的足够大 Data[MAXSIZE]其中MAXSIZE是一个根据实际问题定义的足够大的整数 线性表中的数据从Data[0]开始依次顺序存放 因为当前线性表中的实际元素个数可能没达到MAXSIZE多个因此用一个变量Last来记录当前线性表中最后一个元素在数组中的位置 即Last起一个指针的作用实际是数组下标始终指向线性表中的最后一个元素 表空时Last-1 表长为Last1 为了体现数据组织的整体性通常将数组Data和变量Last封装成一个结构作为顺序表的类型
typedef int Position;
typedef struct LNode *PtrToLNode;
struct LNode
{ElementType Data[MAXSIZE];Position Last;
};
typedef PtrToLNode List;由于LNode是一个包含数组的结构当我们实现各种针对顺序表的操作时直接将该结构作为函数参数传递显然不是一个好办法使用结构指针的传递效率更高所以我们把List定义为结构指针。 这样我们可以利用List定义线性表L:List L;
本题要求实现顺序表的操作集。 函数接口定义
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。
裁判测试程序样例
#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; /* 保存线性表中最后一个元素的位置 */
};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);elseprintf(%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;
}/* 你的代码将被嵌在这里 */输入样例
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.代码
List MakeEmpty()
{List L(List)malloc(sizeof(struct LNode));L-Last-1;return L;
}Position Find( List L, ElementType X )
{for(int i0;iL-Last;i)//注意i从0到L-Last {if(L-Data[i]X) return i;}return ERROR;
}bool Insert( List L, ElementType X, Position P )
{if(L-LastMAXSIZE-1)//注意MAXSIZE-1 {printf(FULL);return false;}if(P0||P(L-Last1)) {printf(ILLEGAL POSITION);return false; }int i;for(iL-Last1;iP;i--)//这个是插入所以i从L-Last1开始 {L-Data[i]L-Data[i-1];}L-Data[i]X;L-Last;return true;
}bool Delete( List L, Position P )
{Position j;if(P0||P(L-Last)){printf(POSITION %d EMPTY,P);return false;}for(jP;jL-Last;j)//因为是删除所以j不可能等于L-Last {L-Data[j]L-Data[j1];}L-Last--;return true;
}
