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

#define LIST_INIT_SIZE 100 	// 线性表存储空间的初始分配量
#define LISTINCREMENT 10	// 线性表存储空间的分配增量
typedef int Status;			// 定义返回值状态类型
#define OK 1
#define ERROR 0

typedef struct{		// 定义数据类型，存放的是一个名字，所以只有字符数组
	char name[100];
}ElemType;

typedef struct{
	ElemType * elem;	// 存储空间基址
	int length;			// 当前长度
	int listsize;		// 当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;

Status InitList_Sq(SqList &L) { // 算法2.3
	// 构造一个空的线性表L。
	L.elem = (ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if (!L.elem)
		return OK; // 存储分配失败
	L.length = 0; // 空表长度为0
	L.listsize = LIST_INIT_SIZE; // 初始存储容量
	return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 算法2.4
	// 在顺序线性表L的第i个元素之前插入新的元素e，
	// i的合法值为1≤i≤ListLength_Sq(L)+1
	ElemType *p;
	if (i < 1 || i > L.length + 1)
		return ERROR; // i值不合法
	if (L.length >= L.listsize) { // 当前存储空间已满，增加容量
		ElemType *newbase = (ElemType *) realloc(L.elem, (L.listsize
				+ LISTINCREMENT) * sizeof(ElemType));
		if (!newbase)
			return ERROR; // 存储分配失败
		L.elem = newbase; // 新基址
		L.listsize += LISTINCREMENT; // 增加存储容量
	}
	ElemType *q = &(L.elem[i - 1]); // q为插入位置
	for (p = &(L.elem[L.length - 1]); p >= q; --p)
		*(p + 1) = *p;
	// 插入位置及之后的元素右移
	*q = e; // 插入e
	++L.length; // 表长增1
	return OK;
} // ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { // 算法2.5
	// 在顺序线性表L中删除第i个元素，并用e返回其值。
	// i的合法值为1≤i≤ListLength_Sq(L)。
	ElemType *p, *q;
	if (i < 1 || i > L.length)
		return ERROR; // i值不合法
	p = &(L.elem[i - 1]); // p为被删除元素的位置
	e = *p; // 被删除元素的值赋给e
	q = L.elem + L.length - 1; // 表尾元素的位置
	for (++p; p <= q; ++p)
		*(p - 1) = *p; // 被删除元素之后的元素左移
	--L.length; // 表长减1
	return OK;
} // ListDelete_Sq

int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 算法2.6
	// 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。
	// 若找到，则返回其在L中的位序，否则返回0。
	int i;
	ElemType *p;
	i = 1; // i的初值为第1个元素的位序
	p = L.elem; // p的初值为第1个元素的存储位置
	while (i <= L.length && !(*compare)(*p++, e))
		++i;
	if (i <= L.length)
		return i;
	else
		return 0;
} // LocateElem_Sq

void ListShow(SqList L){
	// 将顺序表中的所有元素都显示出来，每个姓名之间用空格分开
	int i;
	for(i=0;i<L.length;i++){
		if(i){		// 用来判断是否需要输出空格
			putchar(' ');
		}
		printf("%s", L.elem[i].name);	// 输出姓名
	}
	putchar('\n');	// 注意最后需要换行
}

Status cmp(ElemType e1, ElemType e2){
	// 用来比较两个ElemType元素是否相等
	return (Status)!strcmp(e1.name, e2.name);
}

int main(){

	SqList namelist;		// 定义姓名列表
	InitList_Sq(namelist);	// 初始化姓名列表

	char strInstruct[10];	// 用来保存每行开头的指令
	int pos;				// 用来保存插入或者搜索的位置
	ElemType e;				// 用来保存姓名的节点
	while(scanf("%s", strInstruct) != EOF){
		if(strcmp(strInstruct, "insert") == 0){	// 插入姓名
			scanf("%d%s" ,&pos, e.name);		// 读取待插入的位置与姓名
			ListInsert_Sq(namelist, pos, e);	// 将姓名插入到pos之前
		}else if(strcmp(strInstruct, "show") == 0){	// 显示列表中所有的元素
			ListShow(namelist);
		}else if(strcmp(strInstruct, "delete") == 0){	// 删除某个姓名
			scanf("%s", e.name);		// 读取需要删除的元素
			// 先查找这个姓名在列表中的位置
			// 然后调用 ListDelete_Sq 删除该元素
			pos = LocateElem_Sq(namelist, e, cmp);
			ListDelete_Sq(namelist, pos, e);
		}else if(strcmp(strInstruct, "search") == 0){	// 查找某个姓名的位置
			scanf("%s", e.name);		// 读取需要查找的元素
			printf("%d\n", LocateElem_Sq(namelist, e, cmp));
		}
	}

	return 0;
}

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