• 【原创】浅谈指针(十)链表的写法


    前言

    最近我又来更新这个系列了,其实感觉指针对于我们还是非常重要的存在。指针之所以是初学者们的“噩梦”,它的难度源于它的灵活性。
    这篇文章,我想要来写一下指针的实际运用,如果指针只是一些考试的考题,那就没有意义了。最重要的,指针在C语言,乃至C++,都是不可或缺的一部分。

    链表的简单回顾

    链表是一种数据结构。

    对于一个链表来说,每个结点有两个域,即数据域和指针域,数据域是用来存放这个链表的数字,指针域用来存放下一个结点的地址。特别的,最后一个结点的指针域设为NULL。
    这样,就不需要让整个链表顺序存储了。

    对于数据的插入和删除操作,链表只需要新建结点即可:

    插入和删除的时间复杂度是O(1),不需要移动元素。而对于普通的线性表,需要移动数据,因此时间复杂度为O(n)。

    结构体声明

    对于链表的结构体,我们可以这样写:

    typedef struct List{
    	int data;
    	List *next;
    	List(int x){
    		this->data=x;
    		next=NULL;
    	}
    };
    List *lst;
    

    data是数据域,next是指针域。

    其中,List(x)是一个构造函数,这样在使用new进行结点分配的时候可以简便书写。分配的时候就需要这样写:

    l=new List(x);
    

    这个构造函数做了两件事:一个是把data进行赋值,一个是把next设为NULL。

    补充1:this指针
    其中,写this->data,this是指这个结构体本身,例如调用:

    l=new List(x);
    

    此时this就指向l。this是一个特殊的指针。有一种形象的比喻方式:

    当你进入一个房子后,你可以看见桌子、椅子、地板等,但是房子你是看不到全貌了。
    对于一个类的实例来说,你可以看到它的成员函数、成员变量,但是实例本身呢?
    this是一个指针,它时时刻刻指向你这个实例本身。

    当然,这里不写this也是可以的。这只是写法问题。

    补充2:->运算符
    这个运算符,我们一般称为“箭头运算符”。
    假设我们有现在下面的一个结构体:

    struct info{
      string name;
      int age;
    }
    

    如果现在有一个普通变量x,那么引用其中的age,写作:x.age
    如果现在有一个指针变量p,那么引用其中的age,要写作p->age
    也就是说,对于一个指针结构体,引用其中的成员需要使用->运算符。
    本质上,p->age等同于(*p).age,注意这里括号虽然麻烦但是不可省略。箭头运算符只是一种简便写法。

    在链表的最后添加元素

    我们知道,如果一个链表的当前结点为NULL,那么它必定是最后的结点。因此,我们可以采用递归的写法,如果链表当前节点不为NULL,那么就下一个结点。

    void add(List *&l,int x){
    	if(l==NULL){
    		l=new List(x);
    		return;
    	}
    	else add(l->next,x);
    }
    

    l=new List(x);,之前说过的构造函数写法。
    add(l->next,x)表示找下一个结点。

    补充3:*&是什么鬼!

    我们知道,&是引用传递参数。我之前的浅谈指针(三)写过,网页链接
    如果懒得在原文找的话,我这里直接把原文贴出来了:

    在这里,*表示指针,&表示引用传递,那么加在一起就是指针的引用传递,虽然声明看上去很烦,但是理解了也就是这么回事。

    输出链表的所有元素

    毫无难度的函数,我直接贴出来了,逻辑和add函数类似。

    void write(List *l){
    	if(l==NULL)return;
    	else{
    		printf("%d ",l->data);
    		write(l->next);
    	}
    }
    

    插入元素

    链表的灵活之处就是它的插入和删除函数。
    如下图所示,我们要在2之后插入一个10:

    首先,我们需要把10和3连接起来,否则一旦断掉2和3之间的连接,那么整个链表就直接分离了,无法再找到3的位置。

    下一步,就是把2和10连接起来,同时断开2和3的连接。

    这样就把插入的操作完成了,其实本质是很简单了。

    void insert(int pos,List *&l,int x){
    	if(pos==1){
    		List *p=new List(x);
    		p->next=l->next;
    		l->next=p;
    	}
    	else insert(pos-1,l->next,x);
    }
    

    为了找到待插入的位置pos,我们可以采用递归的方法,每往后一个结点pos-1,最终当pos=1时就到了想要的位置。

    删除元素

    同样的链表,假设删除其中的3:

    首先,先新建一个指针,指向3,否则后续操作过后就无法释放这块内存:

    第二步,把2连接到4上面去。

    最后,释放这个新建的指针,本质就是释放3。

    代码还是一样,注意最终到pos=2就要停止了,这个算法无法删除首个结点的位置。

    void remove(int pos,List *&l){
    	if(pos==2){
    		List *p=l->next;
    		l->next=l->next->next;
    		delete p;
    	}
    	else remove(pos-1,l->next);
    }
    

    完整思路

    一套完整的链表写下来也是有四五十行代码的,完整代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    typedef struct List{
    	int data;
    	List *next;
    	List(int x){
    		this->data=x;
    		next=NULL;
    	}
    };
    List *lst;
    void add(List *&l,int x){
    	if(l==NULL){
    		l=new List(x);
    		return;
    	}
    	else add(l->next,x);
    }
    void write(List *l){
    	if(l==NULL)return;
    	else{
    		printf("%d ",l->data);
    		write(l->next);
    	}
    }
    void insert(int pos,List *&l,int x){
    	if(pos==1){
    		List *p=new List(x);
    		p->next=l->next;
    		l->next=p;
    	}
    	else insert(pos-1,l->next,x);
    }
    void remove(int pos,List *&l){
    	if(pos==2){
    		List *p=l->next;
    		l->next=l->next->next;
    		delete p;
    	}
    	else remove(pos-1,l->next);
    }
    int main(){
    	int n,m;
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++){
    		int x;
    		scanf("%d",&x);
    		add(lst,x);
    	}
    	while(m--){
    		int k;
    		scanf("%d",&k);
    		if(k==1){//插入操作
    			int pos,val;
    			scanf("%d%d",&pos,&val);
    			insert(pos,lst,val);
    			write(lst);putchar('\n');
    		}
    		else if(k==2){//删除操作
    			int pos;
    			scanf("%d",&pos);
    			remove(pos,lst);
    			write(lst);putchar('\n');
    		}
    	}
    	return 0;
    }
    
  • 相关阅读:
    java使用jol打印对象信息
    TCP 面向字节流、延迟应答、异常情况
    C&C++结构实训(国防科大)
    RenderDoc图形调试器详细使用教程(基于DirectX11)
    Python爬虫实现(requests、BeautifulSoup和selenium)
    测绘项目数据在线管理浏览平台:四维轻云实现倾斜摄影模型轻量化处理
    CS231n-2022 Module1: 神经网络要点概述(2)
    零基础学习CANoe Panel(12)—— 进度条(Progress Bar)
    StrPool.C_COLON 和 StringPool.COLON 的拼接问题,踩坑了
    微信小程序- - - - - rich-text 富文本问题
  • 原文地址:https://www.cnblogs.com/jisuanjizhishizatan/p/15970571.html