解题思路:
数组也可以模拟链表:用e[N]记当前数组元素的值,相当于数据域;ne[N]指向下一个元素,相当于指域;idx用于给每次添加元素时做独一无二标记。
注意事项:
1.这题在输入字符串的时候不能用cin,应该用sancf("%s",s)来读取,因为这题的测试点会给很多数据,如果用cin来读取,那么就很容易超时。

2.注意锁定链表位置的时候,看下标从什么时候开始的。

参考代码:

#include<bits/stdc++.h>//万能头文件
using namespace std;

const int N=100010;
int e[N],ne[N],idx;//e[N]为当前数组元素的值,ne[N]指向下一个元素,相当于指域,idx用于给每次添加元素时做标记 
int head;//定义头指针,用于指向数组的第一个位置 

int lenn()//求表长 
{
	int i;
	int k;
	for(i=head,k=1;i!=-1;i=ne[i],k++);
	k--;
	return k;
}

void initial()//初始化 
{
	idx=0;
	head=-1;//(-1为结束的标志 )
}

void inn(int n)
{
	int x;
	while(n--)//前插法 
	{
		scanf("%d",&x);
		e[idx]=x;
		ne[idx]=head;
		head=idx;
		idx++;//记得增加idx的计数
	}
}

void showw()//输出 
{
	if(head==-1)
	{
		printf("Link list is empty\n");
		return ;
	}
	int i;
	for(i=head;i!=-1;i=ne[i])
	{
		printf("%d ",e[i]);
	}
	printf("\n");
}

void gett(int o)//获取 
{
	int i;
	int k;
	if(head==-1 || o>lenn() || o<1)
	{
		printf("get fail\n");
		return ;
	}
	for(i=head,k=1;i!=-1;i=ne[i],k++)
	{
		if(k==o)
		{
			printf("%d\n",e[i]);
			return ;
		}
	}
}

void insertt(int o,int x)//插入 
{
	int i;
	int k;
	if(o>lenn()+1 || o<1)
	{
		printf("insert fail\n");
		return ;
	}
	if(o==1)
	{
		e[idx]=x;
		ne[idx]=head;
		head=idx;
		idx++;
		printf("insert OK\n");
		return ;
	}
	for(i=head,k=1;i!=-1;i=ne[i],k++)
	{
		if(k==o-1)
		{
			e[idx]=x;
			ne[idx]=ne[i];
			ne[i]=idx;
			idx++;
			printf("insert OK\n");
			return ;
		}
	}
	
}

void dede(int o)
{
	int i;
	int k;
	if(o>lenn() || o<1 || head==-1)
	{
		printf("delete fail\n");
		return ;
	}
	if(o==1)
	{
		head=ne[head];
		printf("delete OK\n");
		return ;
	}
	for(i=head,k=1;i!=-1;i=ne[i],k++)
	{
		if(k==o-1)
		{
			ne[i]=ne[ne[i]];
			printf("delete OK\n");
			return ;
		}
	}
}



int main()
{
	int n,m;
	int o,x;
	char s[10];
	scanf("%d",&n);
	initial();//初始化 
	inn(n);//输入数据 
	scanf("%d",&m);
	while(m--)
	{
		scanf("%s",s);//这里建议不要用cin,输入的数据多,很容易超时 ,scanf真的很快
		if(strcmp(s,"show")==0)
		{
			showw();
		}
		else if(strcmp(s,"get")==0)
		{
			scanf("%d",&o);
			gett(o);
		}
		else if(strcmp(s,"insert")==0)
		{
			scanf("%d%d",&o,&x);
			insertt(o,x); 
		}
		else if(strcmp(s,"delete")==0)
		{
			scanf("%d",&o);
			dede(o);
		}
	}
}


点赞(0)
 

0.0分

1 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论