输入第1行为1个正整数n,表示当前单链表长度;第2行为n个空格间隔的整数,为该链表n个元素的数据域值。第3行为1个正整数m,表示对该链表施加的操作数量;接下来m行,每行表示一个操作,为2个或3个整数,格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点,若k=0则表示表头插入。1 k表示删除链表中第k个结点,此时k不能为0。注:操作序列中若含有不合法的操作(如在长度为5的链表中删除第8个结点、删除第0个结点等),则忽略该操作。n和m不超过100000。
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode *List;
struct LNode
{
int data;
struct LNode *next;
};
List creat();
List insert(List L,int m,int n);
List Delete(List L,int m);
void print(List L);
int main()
{
List L;
int k,m,n,d;
L=creat();
scanf("%d",&d);
for(int i=0;i<d;i++)
{
scanf("%d",&k);
if(k==0)
{
scanf("%d %d",&m,&n);
L=insert(L,m,n);
}
if(k==1)
{
scanf("%d",&m);
L=Delete(L,m);
}
}
print(L);
return 0;
}
List creat()
{
int n;
List L;
List p1,p2;
L=(List)malloc(sizeof(List));
L->next=NULL;
p1=L;
scanf("%d",&n);
if(n<=0)
return NULL;
for(int i=0;i<n;i++)
{
if(i==0)
{
scanf("%d",&L->data);
continue;
}
p2=(List)malloc(sizeof(List));
scanf("%d",&p2->data);
p1->next=p2;
p1=p2;
}
p2->next=NULL;
return L;
}
List insert(List L,int m,int n)
{
int k=1;
List p=L;
List d;
d=(List)malloc(sizeof(List));
d->data=n;
d->next=NULL;
if(m<0)
return L;
if(m==0)
{
d->next=L;
return d;
}
else
{
while(k<m)
{
p=p->next;
k++;
if(p==NULL)
return L;
}
d->next=p->next;
p->next=d;
}
return L;
}
List Delete(List L,int m)
{
List p1,p2;
p1=p2=L;
if(m<0)
return L;
if(m==0)
return L;
if(m==1)
{
L=L->next;
return L;
}
for(int i=1;i<m;i++)
{
p1=p2;
p2=p2->next;
}
p1->next=p2->next;
return L;
}
void print(List L)
{
while(L)
{
printf("%d ",L->data);
L=L->next;
}
}
Delete没有判断输入的k大于链表长度的情况。