要读懂程序,必选要先理解程序中的各个变量。
int a[] ; //存储单链表
int b[] ; //相当于动态操作的next指针,储存这个节点 的 下一个节点 的位置;
int idx ;//记录索引。
int head;//记录该链表的头节点的位置;
静态单链表的四个基本操作 。
1 : 初始化 。
void init()
{
head = -1 ;
idx = 0 ;
}
2 : 插入头节点。
void add_to_head( int x )
{
a[idx] = x ;
b[idx] = head ;
head = idx ;
idx ++ ;
}
3 : 在单链表的某一个位置插入值。
void add(int k , int x )
{
a[idx] = x ;
b[idx] = b[k] ;
b[k] = idx ;
idx ++ ;
}
4 : 删除单链表中的值 。
void remove(int k )
{
b[k] = b[b[k]] ;
}
AC代码 如下 :
#include<iostream>
using namespace std;
const int N = 1e5 + 99 ;
int a[N] , b[N] , idx , head ;
void init()
{
head = -1 ;
idx = 0 ;
}
void remove(int k )
{
b[k] = b[b[k]] ;
}
void add_to_head(int x)
{
a[idx] = x ;
b[idx] = head ;
head = idx ;
idx++;
}
void add( int k , int x )
{
a[idx] = x ;
b[idx] = b[k] ;
b[k] = idx ;
idx ++ ;
}
int main()
{
init() ; //一定要记得初始化。
int t ;
scanf("%d",&t) ;
while( t -- )
{
char m ;
getchar() ; //吸收缓冲区的空格
scanf("%c",&m) ;
getchar() ;
if( m == 'H')
{
int n ;
scanf("%d",&n);
add_to_head(n) ;
}
else if( m == 'D')
{
int n ;
scanf("%d",&n);
if( n == 0 )
head = b[head] ;
remove(n-1) ;
}
else if( m == 'I')
{
int n , l ;
scanf("%d%d",&n,&l) ;
add(n-1,l);
}
}
int i = head ;
while( i != -1 )
{
cout << a[i]<<" ";
i = b[i] ;
}
return 0;
}