原题链接:数据结构-链表的基本操作
解题思路:
数组也可以模拟链表:用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分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复