数组模拟链表

数组模拟链表

一.链表

链表的定义: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域
数组模拟链表
头指针总是指向链表的第一个结点,如果整个链表为空(即不包含任何结点),则将头指针置为NULL。为了操作方便,往往在首元结点前再增加一个结点,称之为头结点,头结点不存储元素。头指针指向头结点,头结点的指针域指向首元结点,我们称这种单链表为带头结点的单链表。链表为空时,头结点的指针域为空。

链表可分为单链表,双向链表,循环链表,二叉链表,十字链表,邻接表,邻接多重表等,其中单链表,双向链表和循环链表用于实现线性表的链式存储结构,其他形式多用于实现树和图等非线性结构。

二. 数组模拟单链表

// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void add_to_head(int x)
{
	e[idx]=x,ne[idx]=head,head=idx,idx++;
}
// 将头结点删除,需要保证头结点存在
void remove()
{
    head = ne[head];
}
//在节点K的右边插入一个数x
void  add(int k,int x)
{
	e[idx]=x,ne[idx]=ne[k],ne[k]=idx,idx++;
}
//删除节点K
void remove(int k)
{
	ne[k]=ne[ne[k]];
}

例题(单链表)

实现一个单链表,链表初始为空,支持三种操作:
向链表头插入一个数;
删除第 k 个插入的数后面的数;
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作,进行完所有操作后,从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。

输入格式
第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:

H x,表示向链表头插入一个数 x。
D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。
I k x,表示在第 k 个插入的数后面插入一个数 x(此操作中 k 均大于 0)。
输出格式
共一行,将整个链表从头到尾输出。

数据范围
1≤M≤100000
所有操作保证合法。

输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例:
6 4 6 5

代码

#include<iostream>
using namespace std;
const int N=100010;
int head,e[N],ne[N],idx;

void init()
{
	head=-1;
	idx=0;
}

void add_to_head(int x)
{
	e[idx]=x,ne[idx]=head,head=idx,idx++;
}

void  add(int k,int x)
{
	e[idx]=x,ne[idx]=ne[k],ne[k]=idx,idx++;
}

void remove(int k)
{
	ne[k]=ne[ne[k]];
}
int main()
{
	int m;
	cin>>m;
	
	init();
	
	while(m--)
	{
		int k,x;
		char op;
		cin>>op;
		if(op=='H')
		{
			cin>>x;
			add_to_head(x);
		 } 
	    
	    else if(op=='D')
	    {
	    	cin>>k;
	    	if(k==0) head=ne[head];
	    	remove(k-1);
		}
		
		else if(op=='I')
		{
			cin>>k>>x;
			add(k-1,x);

		}
    }
    for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
	cout<<endl; 
   
	return 0;
 } 

三.数组模拟双向链表

数组模拟链表
数组模拟链表

实现一个双链表,双链表初始为空,支持 5 种操作:

1.在最左侧插入一个数;
2.在最右侧插入一个数;
3.将第 k 个插入的数删除;
4.在第 k 个插入的数左侧插入一个数;
5.在第 k 个插入的数右侧插入一个数;
现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。

输入格式
第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:

L x,表示在链表的最左端插入数 x。
R x,表示在链表的最右端插入数 x。
D k,表示将第 k 个插入的数删除。
IL k x,表示在第 k 个插入的数左侧插入一个数。
IR k x,表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。

数据范围
1≤M≤100000
所有操作保证合法。

输入样例:
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例:
8 7 7 3 2 9
代码

#include<iostream>
#include<string>
using namespace std;
const int N=100010;

int e[N],r[N],l[N],idx=0;

//在节点k的左侧插入x
 void insertKL(int k,int x)
 {
 	l[idx]=l[k];
 	r[idx]=k;
 	r[l[k]]=idx;
 	l[k]=idx;
 	e[idx++]=x;
  } 
  //在最右端插入x
void insertR(int x)
{
   	r[idx]=1;
   	l[idx]=l[1];
   	r[l[idx]]=idx;
   	l[1]=idx;
   	e[idx++]=x;
}
//在下标为k的节点右侧插入x
void insertKR(int k,int x)
{
 l[idx]=k;
 r[idx]=r[k];
 l[r[k]]=idx;
 r[k]=idx;
 e[idx++]=x;
 } 
 //在节点k的左侧插入x
 void insertKL(int k,int x)
 {
 	l[idx]=l[k];
 	r[idx]=k;
 	r[l[k]]=idx;
 	l[k]=idx;
 	e[idx++]=x;
  } 
  //删除节点k;
void deleteK(int k)
{
  	r[l[k]]=r[k];
  	l[r[k]]=l[k];
}  
//初始化	
void init()
{
	//0为左端点,1为右端点;
	r[0]=1;
	l[1]=0;
	idx=2; 
}
int main()
{
	init();
	int m;
	cin>>m;
	string a;
	while(m--)
	{
	    int k,x;
		cin>>a;
		if(a=="R")  
		{
			cin>>x;
		    insertR(x);
		}
		else if(a=="L")
		{
			cin>>x;
			insertL(x);
		}
		else if(a=="D")
		{
			cin>>k;
			deleteK(k+1);//因为初始化加了两个节点,所以第k个数的下标为k+2-1
		}
		else if(a=="IL")
		{
			cin>>k>>x;
			insertKL(k+1,x);
		}
		else if(a=="IR")
		{
			cin>>k>>x;
			insertKR(k+1,x);
		}
	}
	for(int i=r[0];i!=1;i=r[i])  cout<<e[i]<<" ";
	cout<<endl;
	
	return 0;
 } 
上一篇:图的邻接表存储(链式前向星)


下一篇:单链表(数组实现)