#include <stdio.h>
#include <string.h>

#define MAXSIZE 11			// 静态链表的长度
typedef char ElemType[8];	// 元素的类型，规定姓氏不超过7个字符

typedef struct{
	ElemType data;			// 节点中的数据
	int cur;				// 下一个节点的下标（相当于指针）
}NodeType;					// 节点类型

NodeType space[MAXSIZE];	// 用来存储节点的数组，相当于一般链表中的内存，
							// 只是那个内存是系统分配的，我们看不到

typedef struct{
	int elem;				// 静态链表存储空间基址（起始元素的下标）
	int length;				// 静态链表中的元素数目
	int listSize;			// 静态链表当前的长度，可容纳元素数目
}SLinkList;					// 静态链表类型的定义，和一般的链表类似

int LocateElem_SL(SLinkList& S, ElemType e) { // 算法2.13
	// 在静态单链线性表L中查找第1个值为e的元素。
	// 若找到，则返回它在L中的位序，否则返回0。
	int i;
	i = S.elem; // i指示表中第一个结点
	while (i && strcmp(space[i].data, e))
		i = space[i].cur; // 在表中顺链查找
	return i;
} // LocateElem_SL

void InitSpace_SL() { // 算法2.14
	// 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，
	// "0"表示空指针
	memset(space, 0 ,sizeof(space));
	for (int i = 0; i < MAXSIZE - 1; ++i)
		space[i].cur = i + 1;
	space[MAXSIZE - 1].cur = 0;
} // InitSpace_SL

int Malloc_SL() { // 算法2.15
	// 若备用空间链表非空，则返回分配的结点下标，否则返回0
	int i = space[0].cur;
	if (space[0].cur)
		space[0].cur = space[space[0].cur].cur;
	return i;
} // Malloc_SL

void Free_SL(int k) { // 算法2.16
	// 将下标为k的空闲结点回收到备用链表
	space[k].cur = space[0].cur;
	space[0].cur = k;
} // Free_SL

void Insert_SL(SLinkList& S, int i, ElemType e){
	// 往静态链表S中的第 i 个位置前插入e
	int cur = S.elem;		// 指向静态链表中的第一个节点
	int j=0;
	int newNodeIndex;		// 存储新分配的节点下标
	while(j < i-1){			// 寻找第 i-1 个节点
		cur = space[cur].cur;
		++j;
	}
	newNodeIndex = Malloc_SL();	// 分配新的节点
	strcpy(space[newNodeIndex].data,e);	// 在新的节点中存入数据
	space[newNodeIndex].cur = 0;		// 指针为空，这一点很重要
	space[newNodeIndex].cur = space[cur].cur;	// 插入静态链表中
	space[cur].cur = newNodeIndex;
	S.length++;			// 插入后静态链表长度加1
}

void Delete_SL(SLinkList& S, int i){
	// 删除静态链表中的第 i 个节点
	int cur = S.elem;		// 指向静态链表中的第一个节点
	int j=0;
	int delCur;				// 存储待删除节点的下标
	while(j < i-1){			// 寻找第 i-1 个节点
		cur = space[cur].cur;
		++j;
	}
	delCur = space[cur].cur;		// 找到待删除节点的下标
	space[cur].cur = space[delCur].cur;	// 删除节点
	Free_SL(delCur);			// 释放节点
	S.length--;			// 删除后静态链表长度减1
}

void CreateList_SL(SLinkList& S){	// 创建静态链表
	S.elem = Malloc_SL();			// 分配头结点的指针
	space[S.elem].cur = 0;
	S.length = 0;
	S.listSize = 9;
}

void Show_space(){
	// 将静态链表中所有的节点显示出来
	int i;
	for(i=0;i<MAXSIZE;i++){
		printf("%-8s%2d\n", space[i].data, space[i].cur);
	}
}

int main(){

	SLinkList S;		// 定义静态链表
	char str[10];		// 用来获得指令
	int a;				// 存储位置
	ElemType e;			// 存储元素
	InitSpace_SL();		// 初始化备用链表
	CreateList_SL(S);	// 创建静态链表
	while(scanf("%s", str) != EOF){
		if(strcmp(str, "insert") == 0){			// 插入元素
			scanf("%d%s", &a, e);
			Insert_SL(S, a, e);
		}else if(strcmp(str, "delete") == 0){	// 删除元素
			scanf("%d", &a);
			Delete_SL(S, a);
		}else if(strcmp(str, "search") == 0){	// 搜索元素
			scanf("%s", e);
			printf("%2d\n********************\n", LocateElem_SL(S, e));
		}else if(strcmp(str, "show") == 0){		// 显示静态链表状态
			Show_space();
			puts("********************");						// 注意空一行
		}
	}

	return 0;
}

/**************************************************************
	Problem: 2139
	User: admin
	Language: C++
	Result: Accepted
	Time:17 ms
	Memory:1148 kb
****************************************************************/