精华内容
下载资源
问答
  • 数组模拟链表

    2021-04-02 15:16:30
    数组模拟链表一.链表二. 数组模拟单链表三.数组模拟双向链表 一.链表 链表的定义: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点...

    一.链表

    链表的定义: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域
    在这里插入图片描述
    头指针总是指向链表的第一个结点,如果整个链表为空(即不包含任何结点),则将头指针置为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;
     } 
    
    展开全文
  • 当然有:那就是:数组模拟链表顾名思义,通过一些特殊的方法,可以让数组具有链表的作用。我们先放代码,然后解释原理。int head[maxn],e=0;struct node{int next;int to;int w;}edge[maxn];void add(i...

    链表作为一种数据结构,对于空间的利用率非常之高。但是对于链表没有学好的同学来说,链表难上天了。有没有一种解决方案能实现链表却又不那么难呢?

    当然有:那就是:

    数组模拟链表

    顾名思义,通过一些特殊的方法,可以让数组具有链表的作用。

    我们先放代码,然后解释原理。

    int head[maxn],e=0;

    struct node{

    int next;

    int to;

    int w;

    }edge[maxn];

    void add(int u,int v,int d){

    edge[++e].next=head[u];

    edge[e].to=v;

    edge[e].w=d;

    head[u]=e;

    return ;

    }

    Node:

    其实我们一步步的看代码就能发现其中的端倪,究竟是怎么实现这么神奇的操作的。

    最基本的元素显然是node,具有三个属性next,to和w。

    为什么没有from?是因为链表都是单向的,没有回溯这一环。别和我说什么双向链表

    Add函数:

    add函数有三个参数:u,v,d。u、v代表两个点,d代表权值。

    函数的第一行涉及到了一个量:head[u]。于是我们寻找head[u]在哪里。

    我们在最后一行找到了,head[u]被上一个函数赋值为e。

    e是什么?

    大致看一眼就知道e代表边的总数,同时还是每条边的序号。

    因此head[u]代表上一个以u为起点的边的序号。

    在程序的一开始e便会++,所以e这个全局变量最终就是所有边的数量。

    再一次回到函数的开始, next属性赋值为head[u]。

    那个next就是指的上一个以u为起点的边的序号。

    到这里就看的很清楚了吧。我们也就知道届时该如何遍历这个链表。

    for(int i=head[p];i!=0;i=edge[i].next){

    /*...*/

    }

    这个循环的意义也就明白了,为什么是i!=0为判断条件,因为都是指向上一个以本节点为起点的边,那么第一条边之前没有边存在,那么就是0。

    就是这样,数组模拟链表的知识讲完了。

    c2843c055bf33d95270240d0d2fb02b3.png

    展开全文
  • 数组模拟链表

    2021-05-01 11:47:28
    为什么使用数组模拟链表 struct node { int val; node *next; }; 对于上面这种数据结构,也即动态分配链表地址空间的new node操作费时,而算法题的时间要求较高,因此采用耗时短的数组模拟链表(也即是静态链表)...

    为什么使用数组模拟链表

    struct node
    {
    	int val;
    	node *next;
    };
    

    对于上面这种数据结构,也即动态分配链表地址空间的new node操作费时,而算法题的时间要求较高,因此采用耗时短的数组模拟链表(也即是静态链表)的方式

    数组模拟的链表同时还可以模拟邻接表,邻接表的本质是n个由数组模拟的链表,可以用来存储树和图

    • e[i]:存储节点i的值
    • ne[i]:存储节点i的下一个节点
    • head表示头结点的下标
    • idx表示当前用到的点

    链表初始化

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

    在这里插入图片描述

    链表的插入操作(头插法)

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

    以插入11,21为例,先后执行insert(11),insert(21)

    • 执行insert(11)
      在这里插入图片描述
    • 执行insert(12)
      在这里插入图片描述
    #include <iostream>
    
    using namespace std;
    
    const int N=1e5+10;
    
    int e[N],ne[N],head,idx;
    
    void init()
    {
        head=-1;
        idx=0;
    }
    
    void add_to_head(int x)
    {
        e[idx]=x;
        ne[idx]=head;
        head=idx++;
    }
    
    void add(int k,int x)
    {
        e[idx]=x;
        ne[idx]=ne[k];
        ne[k]=idx++;
    }
    
    void remove(int k)
    {
        ne[k]=ne[ne[k]];
    }
    
    int main()
    {
        int m;cin>>m;
        init();
        int k,x;
        while(m--)
        {
            char op;
            cin>>op;
            if(op=='H')
            {
                cin>>x;
                add_to_head(x);
            }
            else if(op=='D')
            {
                cin>>k;
                if(!k) head=ne[head];
                else 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]<<' ';
    
        return 0;
    }
    
    展开全文
  • 数组模拟链表集合

    2020-05-04 07:58:37
    数组模拟链表 value[]数组存储数值 r[]数组存储链表数与数之间的位置关系 数组模拟链表初始化 #include<iostream> using namespace std; int value[101],r[101]; int main() { int n; cin>>n; for(int ...

    数组模拟链表 value[]数组存储数值 r[]数组存储链表数与数之间的位置关系

    数组模拟链表初始化

    #include<iostream>
    using namespace std;
    int value[101],r[101];
    int main()
    {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>value[i];
    for(int i=1;i<=n;i++)
    {
    if(i!=n) r[i]=i+1;
    else r[i]=0;
    }
    int t=1;
    for(int i=1;i<=n;i++)
    cout<<value[i]<< " ";
    cout<<endl;
    for(int i=1;i<=n;i++)
    cout<<r[i]<< " ";
    }
    

    输入
    6
    10 9 8 6 5 4 2
    输出
    10 9 8 6 5 4
    2 3 4 5 6 0 //0代表链表尾

    1.在末尾插入值
    2.在具体位置插入值
    3.在具体位置删除值
    4.在链表中插入任意值,链表的排序顺序不变
    5.输出链表

    此处下标以1开始的,可以具体问题具体对待

    #include<iostream>
    using namespace std;
    int value[101],nt[101],len,nxt; 
    //在链表末尾中插入一个值
    void init()
    {
    	 for(int i=1;i<=len;i++)
    	  cin>>value[i];
    	  for(int i=1;i<=len;i++)
    	  {
    	  	if(i!=len) nt[i]=i+1;
    	  	else nt[i]=0;	  
    	  }
    }
    void insertend(int x)
    {
    	len++;
    	value[len]=x;
    	nt[len-1]=len;
    	nt[len]=0;
     } 
    
     //在链表某个位置插入值具体问题具体分析 
     void insertmid(int x,int p)
     {
     	len++;
    	value[len]=x;
     	value[len] =x;
     	nt[len]=nt[p-1];
     	nt[p-1]=len;
     }
     //删除某个位置的值
     void del(int p)
     {
     	nt[p-1]=nt[p];
      } 
    //插入一个值,当前链表的排列顺序不变,比如当前从小到大
    void insertrule(int x)
    {
    	len++;
    	value[len]=x;
    	int t=1;
    	while(t)
    	{
    		if(value[t]>value[len])
    		{
    			nt[len]=nt[t-1];
    			nt[t-1]=len;
    			break;
    		}
    		t=nt[t];
    	}
     } 
     void print()
     {
        int t=1;
    	  while(t)
    	  {
    	  	cout<<value[t]<<" ";
    	  	t=nt[t];
    	  }	
    	  cout<<endl;
     }
    int main()
    {
    	cin>>len;
    	init();
    	print();
    	insertend(10);
    	print();
    	insertmid(19,3);
    	print();
    	del(3);
    	print();
    	insertrule(8);
    	print();
    	
    	  
     return 0;
    }
    

    输入
    9
    1 2 3 4 5 6 8 9 19

    输出

    1 2 3 4 5 6 8 9 19
    1 2 3 4 5 6 8 9 19 10
    1 2 19 3 4 5 6 8 9 19 10
    1 2 4 5 6 8 9 19 10
    1 2 4 5 6 8 8 9 19 10

    数组模拟双向链表

    双向链表

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,442
精华内容 976
关键字:

数组模拟链表